В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 14
Текст из файла (страница 14)
Как оказалось, ширинаBn совпадает с мощностью наибольшего слоя. Такие ранжированные частично упорядоченные множества называютсяшпернеровыми. Рассмотрим еще один пример шпернерова множества.Ранее было обозначено через Γn частично упорядоченное по включению множество граней n-мерного единичногокуба. Также было показано, что всего граней 3n . Проведем ту же цепочку рассуждений, что и в случае Bn . Единицей вэтом частичном порядке является тривиальная грань Bn , а вот нуля здесь нет: минимальными являются 2n элементов,являющихся также тривиальными гранями, состоящими из одной вершины каждая. Всего в Γn существует 2n n! максимальных антицепей (спускаясь по частичному порядку, на k-ом шаге выбираем одну из (n − k + 1) ранее невыбранныхкоординат и одним из двух способов заменяем ее либо на 0, либо на 1).
Всегоk-мерных граней nk 2n−k , так как их числоnравно количеству способов выбора k степеней свободы из n возможных ( k способов), в каждом из которых возможнывсе допустимые значения фиксированных n − k координат (2n−k вариантов). Всего цепей, проходящих через выбраннуюгрань размерности k равно 2k k! (n − k)!, так как их количество равно числу способов упорядоченного открывания n − kфиксированных координат ((n − k)! способов), после каждого из которых возможны все 2k k! цепей до минимальныхэлементов.Покажем унимодальность последовательности чисел {bk }nk=0 k-мерных граней: bk = nk 2n−k . Действительно,n n−k−1k+1 2n n−kk 2bk+1=bk=1 n−k·2 k+1монотонно убывает. Пусть n > 3.
Тогдаn−1bk+1⇒< 1.3bknnОтсюда три случая: если n ≡ 2 (mod 3), то наибольший n слоев два: слой 3 -мерных и 3 -мерных граней; если жеn 6≡ 2 (mod 3), то наибольший слой один: множество 3 -мерный граней. В дальнейшем нам понадобится лишь тотфакт, что в любом случае 3n -ый слой является максимальным.nНайдем ширину множества Γn . Очевидно, она не меньше, чем ширина наибольшего слоя, то есть b nn c · 2n−b 3 c .3e1 , . . . , αes }, причем размерность граниПокажем точное равенство. Для этого рассмотрим произвольную антицепь A = {αei равна ki для i = 1, s. Количество максимальных цепей, проходящих через элементы A, не превосходит общего числаαмаксимальных цепей в Γn :k<n−1bk+1⇒> 1,3bkk=n−1bk+1⇒= 1,3bkk>2k1 k1 ! (n − k1 )! + 2k2 k2 ! (n − k2 )! + · · · + 2ks ks ! (n − ks )! 6 n!2n .Отсюда имеемs∑1n n−ki 6 1, в то же времяki 2s∑1n n−ki >ki 2snn2n−b 3 c .=⇒ s 6nn n−b 3n c3b n3 c 2 Отсюдавидно, что если хотя бы один элемент антицепи лежит вне 3n -ого слоя в случае n 6≡ 2 (mod 3) (вне n3 -ого иn3 -ого слоев в случае n ≡ 2 (mod 3)), то антицепь не будет максимальной, так как будет выполняться соответствую 2nщее строгое неравенство.
Итак, Γn является также шпернеровым множеством и его ширина равна b nn c 2d 3 e .3Рассмотрим частично упорядоченное множество Bn . Булевой функцией, заданной на нем называется любое отображение Bn → B1 . Монотонной булевой функцией, заданной на Bn называется любая булева функция f , удовлетворяющаяимпликации e 6 βe =⇒ f (αe ) 6 f βe .αi=1i=148ГЛАВА 1. КОМБИНАТОРИКАНас будет интересовать вопрос о числе таких отображений как о функции, зависящей от n. В дальнейшем условимсяобозначать ее через ψ (n).
В случае n = 0 все функции монотонны (так как они суть константы 0 и 1): ψ (0) = 2. Приn = 1 немонотонной является лишь отрицание, так что ψ (n) = 3. В дальнейшем n > 2. Для начал получимтривиальнуюnнижнюю оценку на число монотонных функций для n > 2. Для этого рассмотрим в Bn два слоя: n2 -ыйи n 2 + 1 -ый.Определим семейство монотонных функций Φ = Φ1 ∪ Φ2 следующимобразом: на всех слоях выше 2 + 1 -го опреnделим все функцииравнымиединице,анавсехслояхниже-гоопределим2 их равными нулю. Все функции из Φ1равны нулю на n2 -ом слое и определены произвольным образом на n2 + 1 -ом — всего таких столько же, сколько( nn )существует способов определить функцию на b n cn +1 наборах, то есть 2 b 2 c+1 . Все функции из Φ1 наоборот: равны2 единице на n2 + 1 -ом слое и определены произвольным образом на 2n -ом — всего таких столько же, сколько су( nn )ществует способов определить функцию на b nn c наборах, то есть 2 b 2 c .
Очевидно, что пересечение Φ1 ∩ Φ2 содержит2 лишь одну функцию: равную нулю вплоть до 2n -го слоя, и равную единице, начиная с n2 + 1 -ого слоя. Учитываято, что все остальные функции в Φ1 и Φ2 различны, получена нижняя оценка на число булевых монотонных функций:( nn )( nn )ψ (n) > 2 b 2 c + 2 b 2 c+1 − 1.Следующая, интересующая нас задача — это расшифровка монотонной булевой функции. Известно, что некотораяфункция f : Bn → B является монотонной.
Требуется ее расшифровать, то есть определить ее значения на всех вершинах Bn . При этом разрешается задавать вопросы вида: чему равна функция на данном наборе. Нас будет интересоватьнаименьшее число вопросов как функция от n. Договоримся в дальнейшем обозначать ее ϕ (n). Для получения нижнейоценки на эту функцию воспользуемся семейством функций Φ, построеннымприполучении нижней оценки на числомонотонных булевых функций: если задано вопросов меньше, чем b nn c + b n cn +1 , то заведомо найдется вершина на22одном из выделенных средних слоев, на котором значение функции не спрашивалось. В этом случае двумя монотонными функциями, неразличимыми таким тестом будут функции из Φ, различные лишь на вершине, на которой значение неспрашивалось.
Таким образом, nn.ϕ (n) > n + n 22 +1Теорема 1.11 (Ансель). Bn может быть покрыт b nn c максимальными цепями со следующими свойствами:2nn 1. число цепей длины n − 2p + 1 для p = 0, 2 равно np − p−1,2. в наименьшей вершине цепи длины n − 2p + 1 как в наборе из нулей единиц содержится в точности pединиц и n − p нулей, а в наибольшей — n − p единиц и p нулей,3. для любых наборов α1 l α2 l α3 на цепи длины n − 2p + 1α1 = ( . . . 0 .
. . 0 . . . )α2 = ( . . . 0 . . . 1 . . . )α3 = ( . . . 1 . . . 1 . . . )их относительное дополнение до квадрата α:α = ( ... 1 ... 0 ... )лежит на цепи длины n − 2p − 1.Замечание. Из пункта 1 видно, что все цепи имеют длину одной и той же четности, причем в случае нечетного n всецепи имеют четную длину, а в случае четного n — нечетную. Док-во.
Проведем индукцию по n. Для n = 0 теорема, очевидно верна.àПокрытие состоит всего из одной цепи, для которой пункты 1, 2 и 3 тривиальны. Для n = 1 утверждения также выполняются:a` 1a` 0491.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАПокрытие содержит единственную цепь, для которой проверка условий 1, 2, 3 также не вызывает затруднений. Такиетривиальные цепи, образующие покрытия B0 и B1 называются цепями Анселя. Более интересны случаи n = 2 и n = 3,на которых можно наглядно продемонстрировать индуктивный переход.Пусть n = 2. Куб B2 получается соединением всех вершин одномерного куба B110 с одноименными вершинами одномерного куба B211 , при этом все вершины B210 получают метки, начинающиеся нулем, а все вершины, принадлежавшиеB211 получают метки, начинающиеся единицей.
Рассмотрим в B210 и в B211 уже построенные на предыдущем шаге ихпокрытия цепями Анселя.B2B211B2B211à 10à 10@@@@à 01@à 01@11 à11 à@@@@@@00 à00 àB210B210Разрываем цепь в B211 и соединяем ее бывший максимальный элемент с максимальным элементом цепи покрытия B210 .В случае n = 3 алгоритм действий аналогичный. Куб B3 получается соединением всех вершин двумерного куба B210с одноименными вершинами одномерного куба B311 , при этом все вершины B310 получают метки, начинающиеся нулем,а все вершины, принадлежавшие B311 получают метки, начинающиеся единицей. Рассмотрим в B310 и в B311 уже построенные на предыдущем шаге их покрытия цепями Анселя.B3B3311Bà 111@@a` 101 110@a``a 011@@a` 001 010@a`a`B311à 111@@a` 101 110@a`a` 011@@a` 001 010@a`-100a`100àà000000B310B310Снова отрываем от каждой цепи в B311 максимальный элемент и делаем его максимальным соответствующей цепи B310 .Теперь мы можем формализовать индуктивный переход.
Пусть существует способ покрывать Bn цепями Анселя,при котором выполняются условия 1, 2 и 3. Тогда искомое покрытие для Bn+1 строится следующим образом: от каждойцепи в Bn+111 отрывается максимальный элемент и присоединяется к соответствующей цепи в Bn+110 . При этом длинывсех цепей в Bn+111 увеличиваются на единицу, а длины всех цепей в Bn+110 уменьшаются на единицу (цепи длины 1 вBn+110 исчезают).Bn+1`aBn10a`a``aa``aa`a`Bn+111a`a`a`a`a`a`Проверим, удовлетворяет ли такое покрытие условиям теоремы:n 1. Цепи длины (n + 1) − 2p + 1 получаются из цепей длины n − 2p + 1, лежащих в грани Bn10 (всего их np − p−1)nnудлинением на единицу и из цепей длины n − 2 (p − 1) + 1, лежащих в грани Bn11 (всего их p−1− p−2) укорочеn n+1 нием на единицу.
Итого, цепей такой длины ровно np − p−2= n+1p − p−1 .2. Возможны два тривиальных подслучая:(a) цепь получена удлинением соответствующей из Bn10 . Тогда число нулей в наименьшей вершине увеличилосьна единицу (из-за появившегося первого разряда), число единиц в ней сохранилось, а число единиц в наибольшей вершине увеличилось на единицу (тоже из-за первого разряда), в то время как число нулей в нейсохранилось. Таким образом, условие выполняется.50ГЛАВА 1. КОМБИНАТОРИКА(b) Цепь получена укорочением соответствующей из Bn11 . Тогда число нулей в минимальной вершине цепи сохранилось, число единиц в ней же увеличилось из-за появившегося первого разряда, а число единиц в максимальной вершине осталось прежним (так как одна единица добавилась первым разрядом, но бывшаямаксимальная вершина удалена, поэтому новая лежит уровнем ниже, следовательно, в младших разрядахсодержит на одну единицу меньше), в то время как число нулей в максимальной вершине увеличилось наединицу (из-за спуска ее на один уровень вниз).
Таким образом, и в этом случае условие сохраняется.3. Берем три вершины с одной цепи, идущие подряд. Возможны два случая.(a) Они взяты с укороченной цепи. Тогда, поскольку при индуктивном построении они были взяты с цепи Bn11длины на единицу больше, их дополнение до квадрата лежит (по индуктивному предположению) также в Bn11на цепи длины на 2 меньше (по индуктивному предположению соответствующая цепь, содержавшая нужноедополнение до квадрата, имела длину на 2 больше до отщепления максимальных элементов с каждой цепи,но после отщепления, как легко видеть, баланс длин сохранился).(b) Они взяты с удлиненной цепи. Возможны два подслучая.i. Все три вершины лежат в Bn10 . В этом случае по индуктивному предположению их дополнение до квадрата также находится в Bn10 , причем оно лежит на цепи длины на 2 меньше (по индуктивному предположению соответствующая цепь, содержавшая нужное дополнение до квадрата, имела длину на 2 меньшедо добавления максимальных элементов к каждой цепи из Bn11 , но после их добавления, как легко видеть, баланс длин сохранился).ii.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
