В.П. Воронин - Дополнительные главы дискретной математики (1127085), страница 13
Текст из файла (страница 13)
Суммой (объединением) частичных порядков P и Q называется частично упорядоченноемножество P ∪ Q, 6 такое, что1. a, b ∈ P =⇒ a 6 b ⇔ a 6P b;2. a, b ∈ Q =⇒ a 6 b ⇔ a 6Q b;3. a ∈ P, b ∈ Q =⇒ a ⊃⊂ b.Определение 1.4.9. Декартовым произведением частичных порядков P и Q называется частично упорядоченноемножество (P × Q, 6) такое, чтоa1 , a2 ∈ P, b1 , b2 ∈ Q =⇒ (a1 , a2 ) 6 (b1 , b2 ) ⇔ a1 6P a2 , b1 6Q b2 .Примером декартова произведения может случить произведение цепей C2 и C3 .` (2, 3)`C3 3C2 ×C3@` (2, 2) @` (1, 3)C2@@2`2`` (2, 1) @` (1, 2) @` (0, 3)@@` (2, 0) @` (1, 1) @` (0, 2)1`1`@@@` (1, 0) @` (0, 1)@0`@` (0, 0)0`В частном случае C1 = B, а Bn — n-мерный булев куб — можно трактовать как частично упорядоченное множествоn-ой декартовой степени цепи C1 .e 6 βe и расРассмотрим n-мерныйединичный куб Bn , назадан описанный выше частичный порядок.
Если αh которомie , βe = k, то интервал αe , βe является гранью этого куба размерности k. Ее можно обозначатьстояние Хэмминга ρ αe и βe совпадают hсохраним,следующим образом: те n − k разрядов, в которых наборы αа оставшиеся — те, в которыхieee , β = (α1 , . . . , −, . . . ), при этом перваяe стоят нули, а в наборе β стоят единицы, заменим прочерками: αв наборе αкомпонента с прочерком называется направлением грани. В качестве еще одного примера рассмотрим частично упорядоченное множество Γ, состоящее из трех элементов.Γ`0−`@@`1;`0(−, −)`−`!2(−, 0) `(−, 1) `(0,` −) (1,` −)@=HH HH@`H H1`(0, 1)` HH` HH`(0, 0)(1, 0)(1, 1)Таким образом, легко видеть, что Γ2 представляет собой частично упорядоченное множество граней двумерного куба повключению.
По аналогии можно заявить, что Γn является частичным порядком также по включению граней n-мерногоединичного куба.Определение 1.4.10. Отображение ϕ : P → Q называется монотонным (изотонным), если∀ a, b ∈ P : a 6P b =⇒ ϕ (a) 6Q ϕ (b) .Примерами монотонных отображения являются монотонные функции алгебры логики.Определение 1.4.11.
Пусть S — множество всех монотонных отображений P → Q (иногда пишут S = QP ). Тогда кардинальной степенью частично упорядоченных множеств P и Q называется частично упорядоченное множество(S, 6) такое, что∀ϕ1 , ϕ2 ∈ S =⇒ ϕ1 6 ϕ2 ⇔ ∀ a ∈ P : ϕ1 (a) 6Q ϕ2 (a) .451.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАВ качестве примера построим кардинальную степень двух цепей: C2C2 . Чтобы представить все монотонные функции,отображающие C2 в C2 , перейдем к их представлению векторами длины 3: (a, b, c) : a 6 b 6 c, a, b, c ∈ {0, 1, 2}. Частичныйпорядок этих векторов представлен на диаграмме Хассе:`(2, 2, 2)(1, 1, 2)(1, 1, 1)(0, 1, 1)` (1, 2, 2)@`@`(0, 2, 2)HHH`H`(0, 1, 2)``(0, 0, 2)@@` (0, 0, 1)`(0, 0, 0)Этот частичный порядок изоморфен множеству векторов из нулей и единиц длины 5, упорядоченных по перестановкеединиц справа налево.
В дальнейшем при изучении решеток станет ясен комбинаторный смысл этой аналогии.Определение 1.4.12. Пусть C1 , . . . ,Cn суть цепи частично упорядоченного множества (P, 6). Будем говорить, что ониобразуют покрытиеэтого частично упорядоченного множества, если Ci 6= ∅, i = 1, n, для любых 1 6 i < j 6 n ⇒SnCi ∩C j = ∅,C= P.ii=1Очевидно, что для любого частичного порядка всегда существует покрытие: достаточно рассмотреть тривиальное— каждый элемент объявить цепью. Справедливо утверждение о том, что число цепей в покрытии не может быть меньше ширины множества. Действительно, ширина множества равна наибольшей длине антицепи, но все элементы в нейнесравнимы, следовательно, никакие два не могут находится в одной цепи покрытия.
Таким образом, каждый элементнаибольшей антицепи должен содержаться в своей отдельной цепи покрытия. Справедливо и обратное неравенство.Теорема 1.10 (Дилуорс). Пусть (P, 6) — конечное частично упорядоченное множество. Тогда его ширинаравна минимальному числу цепей, его покрывающих. Док-во. Проведем индукцию по числу элементов в P. Базис индукции (случай |P| = 1) очевиден.
Пусть теоремасправедлива при |P| 6 k, то есть частично упорядоченное множество, содержащее не более k элементов можно покрыть цепями, число которых равно ширине P. Докажем случай |P| = k + 1. Возьмем произвольный элемент a ∈ P ирассмотрим другой носитель P∗ = P \ {a}. Возможно два случая:1. Ширина частично упорядоченного множества (P∗ , 6) меньше ширины исходного множества, то есть не превосходит k. Тогда по индуктивному предположению существует покрытие (P∗ , 6) не более, чем k цепями, добавив ккоторым цепь, состоящую из единственного элемента a, получим покрытие (P, 6) не более, чем k + 1 цепями, чтои требовалось доказать.2.
Ширина частично упорядоченного множества (P∗ , 6) равна ширине (P, 6). В этом случае разобьем P∗ относительно a на три части:U = {b ∈ P | a < b} ,L = {b ∈ P | b < a} ,C1 C2 C3CiUUiP∗ NNiLLiN = {b ∈ P | a ⊃⊂ b} .Cn−1 CnaПо транзитивности каждый элемент из L предшествует любому элементу из U. В дальнейшем n — ширина частично упорядоченного множества P∗ . По индуктивному предположению существуют n цепей C1 , .
. . ,Cn , покрывающихP∗ . Разобьем каждую цепь также на три части: Ci = Ui ∪ Ni ∪ Li , где Ui = U ∩Ci , Ni = N ∩Ci , Li = L ∩Ci , ∀ i = 1, n.Возможно два подслучая:(a) ∃ i ∈ [1, n] ∩ N : Ni = ∅. В этом случае уплотним цепь Ci элементом a, при этом получим покрытие n цепямимножества (P, 6). Таким образом, построено покрытие цепями, число которых равно ширине множества, чтои утверждалось в теореме.46ГЛАВА 1. КОМБИНАТОРИКА(b) ∀ i = 1, n Ni 6= ∅. Прежде чем перейти к рассмотрению следующих двух подслучаев заметим, что любая цепьпокрытия целиком лежит либо в U ∪ N, либо в L ∪ N (докажите).i.
Если найдется номер j такой, что частично упорядоченное множество (P∗ \U j , 6) имеет ширину, меньшую n, то искомым покрытием является покрытие (P∗ \U j , 6), объединенное с цепью U j ∪ {a}. Аналогичен случай, когда найдется номер ` такой, что частично упорядоченное множество (P∗ \ L` , 6) имеетширину, меньшую n. Таким образом, и в этом случае искомое покрытие существует.ii. Не ограничивая общности рассуждений, будем считать, что все цепи лежат в U ∩ N.
Предположим,при удалении любого Ui , i = 1, n ширина множества сохраняется. В это случае для любого i множество (U ∪ N) \ Ui имеет ширину n, а его максимальной антицепью является цепь Ai длины n, причем накаждой из цепей C j присутствует один элемент каждой антицепи Ai , ∀ i = 1, n. Важно, что один из элементов каждойSантицепи находится на Ni : Ai ∩ Ni 6= ∅, ∀ i = 1, n. Рассмотрим объединение всех такихантицепей A = ni=1 Ai .
В цепях Ui ∪ Ni выбираем наименьший элемент из A ∩ (Ui ∪ Ni ) — ai ∈ Ni . Утверждается, что A∗ = {a1 , . . . , an } — антицепь. Доказательство от противного: пусть ∃ b, c ∈ A∗ , b < c. Еслиb ∈ As , то возьмем d ∈ As — элемент, лежащий на той же цепи, что и c но выше (так как c наименьшийиз элементов As , лежащих на той же цепи). Тогда по транзитивности c < d ⇒ b < d, что противоречиттому, что As антицепь.
Таким образом, в P∗ антицепью является A∗ , а в P — A∗ ∪ {a}, что противоречитпредположению о том, что ширина P равна ширине P∗ и равна n.Теорема доказана.nЦепи Анселя. Рассмотрим единичный n-мерный куб Bn с традиционным частичным порядком. Обозначим Bk =e ∈ Bn : kαe k = k} — k-ый слой для k = 0, n. Очевидно, для любого k слой Bnk является антицепью длины Bnk = nk .{α nПокажем, что последовательность Bnk = ak k=0 монотонно убывает.
Действительно,n ak+1n−kk+1= n =akk+1kмонотонно убывает. Покажем, что в случае четного n последовательность {ak }nk=0 является унимодальной, а в случаенечетного — два серединных элемента последовательности являются максимальными. Действительно, если n = 2m, тоn−kn−k> 1, k > m ⇒<1k<m⇒k+1k+1 nnnnn<< ··· <>> ··· >.01mm+1nЕсли же n = 2m + 1, тоn−kn−kn−kk<m⇒> 1, k = m ⇒= 1, k > m ⇒<1k+1k+1k+1 nnnnnnn<< ··· <<=>> ··· >.01m−1mm+1m+2nВ любом случае можно утверждать, что ширина Bn не меньше, чем b nn c .
Покажем, что в действительности справед2ливо равенство: ширина Bn в точности равна b nn c . Для этого проведем следующую цепочку рассуждений: в n-мерном2единичном кубе существует ровно n! максимальных цепей из e0вe1. Это вытекает из того, что число путей из нуля вединицу равно числу способов упорядоченной расстановки n единиц по n позициям (замена каждого нуля единицейдобавляет ребро к уже существующей цепи, а всего ребер — n).
Аналогично, число максимальных цепей из e0вe1,e : kαe k = k равно k! (n − k)!. Используя эти факты, рассмотрим произвольнуюпроходящих через заданную вершину αe1 , . . . , αes }, причем kαei k = ki , i = 1, s. Всего различных цепей, проходящих через Aантицепь A = {αk1 ! (n − k1 )! + k2 ! (n − k2 )! + · · · + ks ! (n − ks )! 6 n!Отсюда имеемs∑1n 6 1, в то же времяi=1 kis∑1n >i=1 kin=⇒s6,nn2b n2 cse` не лежит в среднем (в случае четного n) или в двух средних (в случае нечетного n) слоях,причем, если хотя бы одно αто неравенство будет строгим. Таким образом, помимо того, что показано равенство ширины n-мерного куба b nn c ,2еще и указан общий вид максимальных антицепей. В случае четного n максимальная антицепь всего одна — n2 -ыйслой.
Случай нечетного n = 2m + 1 требует особого рассмотрения. Очевидно, что если хотя бы один элемент антицепилежит вне двух средних слоев, то данная антицепь не будет максимальной. Предположим, что максимальная антицепь471.4. ЧАСТИЧНО УПОРЯДОЧЕННЫЕ МНОЖЕСТВАn принадлежит одновременно обоим средним слоям: A = X ∪Y, X ⊂ Bnm+1 , Y ⊂ Bnm , причем X,Y 6= ∅. Так как mn = m+1,двудольный граф, долями которого являются Bnm+1 и Bnm , а ребрами — все ребра, соединяющие эти же слои в Bn , будетоднородным (каждой вершине инцидентно одинаковое число ребер).
Для множества X рассмотрим его тень:noe ∈ Bnm ∃ βe ∈ X : αe < βe .P (X) = αОчевидно, что число ребер, соединяющих множество X со своей тенью не превосходит числа ребер, соединяющих P (X)с верхней долей:|X| · (m + 1) 6 |P (X)| · (m + 1) =⇒ |X| 6 |P (X)| ,nпричем равенство достигается только в том случае, когда X совпадает n со всем слоем, иными словами, в случае X Bm+1nверно строгое неравенство |X| < |P (X)|. Но Y = Bm \ P (X) и |Y | < Bm+1 \ X , следовательно, A не является максимальной антицепью, так как |A| < |Bnm |. Таким образом,по доказанномув случае нечетного n единичный куб Bn содержитnnвсего две максимальные антицепи: соответственно 2 -ый и 2 -ый слои.Единичный n-мерный куб является ранжированным частично упорядоченным множеством.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
