AA3-4(Posets) (1127142), страница 2
Текст из файла (страница 2)
Часть IV: Частично упорядоченные множестваОперации над ч.у. множествами20 / 76Прямое произведение: пример 1[[[(c, 1)cba×10=(b, 1)[[[[[[(a, 1)(a, 0)Прямое произведение цепей 3 и 2(b, 0)(c, 0)ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у. множествамиПрямое произведение: пример 2[[◦◦◦◦[[◦◦◦Зигзаги (или заборы) Z3 и Z4◦ [AA ◦ AAA AAA [[ AAAA ◦ AA ◦ ◦ ◦ ◦◦ [[[AAAA AAAA [[[ AA AAAA◦◦◦◦Прямое произведение Z3 × Z421 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваОперации над ч.у.
множествамиТеорема ОреТеоремаКаждый частичный порядок изоморфен некоторомуподмножеству декартова произведения цепей.ОпределениеМультипликативной размерностью ч.у. множества Pназывается наименьшее число k линейных порядков Li таких,существует вложение P ,→ L1 × . . .
× Lk .22 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияРазделы1Основные понятия теории ч.у. множеств2Операции над ч.у. множествами3Линеаризация4Задачи c решениями5Модели Крипке6Что надо знать23 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияПредставление P = h P, 6 i в виде пересечения цепейТеорема (Шпильрайна, принцип продолжения порядка)12Любой частичный порядок 6 может быть продолжен долинейного на том же множестве.Каждый порядок есть пересечение всех своих линейныхпродолжений (линеаризаций).P → L,P = L1 ∩ .
. . ∩ Le(P) ,где e(P) — множество всех линеаризаций ч.у. множества P.Доказательство (для конечного случая, |P | = n)1Если P — не цепь, то в P найдутся несравнимые элементы;произвольно определим порядок на них и продолжим его потранзитивности. Если получившиеся ч.у. множество ещё нецепь, то выберем новую пару несравнимых элементов ипоступаем, как указано выше.Через конечное число шагов получаем линейный порядок.24 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваЛинеаризацияТопологическая сортировка12(продолжение). Т.к. возможен различный выбор парнесравнимых элементов и при каждом выборе можнополагать любой их порядок, то можно получить всевозможные линейные продолжения исходного частичногопорядка.Пересечение всех таких цепей даст исходное ч.у. множество:если x 6 y, то аналогичное следование будет и во всехполученных линейных порядках, а при x y всегда найдётсяпара цепей с противоположным их следованием, что впересечении цепей и даст несравнимость этих элементов.Для конечных ч.у.
множеств заданных парами вида a l b, поисктакого линейного продолжения в теоретическомпрограммировании называют топологической сортировкой.Задача решается за линейное время.25 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация26 / 76Представление ч.у. множества пересечением цепейcd[[[ ba=dccdba∩baПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация27 / 76Некоторые ч.у. множества◦◦...◦hhhh◦hhhh . . .hhh◦◦Малая корона sn['['hb 4[4'['hb 4[4 [[hb 4A4 [Ahb'4h'['[A4 Ah [A[4 h4 h ['hh44 [[[h'hA4[4'A'[A[[h'h4[4''[hh44h[A[A[4AhA[[[[[4 h'['[4h'['[4aaaaab144123452345Корона S5ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваЛинеаризация«e(P)= ?» — NP-полная задача, но:n+me(P + Q) =e(P)e(Q), n = |P|, m = |Q|;n 12ne(2 × n) =— числа Каталана;n+1 nX e(Zn ) xnn>0n!= tg x + sec x ,значения Zn при чётных n — числа секанса, а при нечётных —числа тангенса;e(Sn ) = (n + 1)!(n − 1)! ;X e(sn )xxn =;n!cos2 xn>1log(e(B n ))n3= log− log e + o(1) .n2bn/2c228 / 76ПРИКЛАДНАЯ АЛГЕБРА.
Часть IV: Частично упорядоченные множестваЛинеаризацияВероятностное пространство на линеарезацияхПри дискретных задач часто рассматривают связанное с ч.у.множеством P вероятностное пространство на множестве всехe(P ) его линеаризаций, в котором каждая линеаризацияравновероятна.В этом пространстве для элементов x, y, z, . . . ч.у. множестваP рассматривают события E вида x 6 y, (x 6 y) N (x 6 z) ит.д.Вероятность Pr [E] такого события:Pr [E] =число линеаризаций, в которых имеет место E.e(P)Теорема (XYZ-теорема)Пусть h P, 6 i — ч.у. множество и x, y, z ∈ P .
ТогдаPr [ x 6 y ] · Pr [ x 6 z ] 6 Pr [ (x 6 y) N (x 6 z) ] .29 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияПроблема сортировки и «1/3 – 2/3 предположение»— определить линейный порядк L с помощью минимальногоколичества вопросов «верно ли, что x < y в L?».Обобщение: L — зафиксированная, но неизвестнаялинеаризация ч.у. множества P.Оптимальная процедура поиска L включает в себя нахождениеэлементов x и y, для которых Pr [ x < y ] ≈ 12 .С.С.
Кислицын (1968) высказал «1/3 – 2/3 предположение»:“любое не являющееся цепью ч.у. множество содержит парунесравнимых элементов x и y, для которых126 Pr [ x 6 y ] 6”.33Позднее это утверждение независимо выдвинули американскиеисследователи М. Фредман и Н. Линал.30 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация1/3 – 2/3 предположениеПример 2 + 1 показывает,что указанные границынесужаемы (имеется и примердесятиэлементного ч.у. множествасо связанной диаграммой Хассе).Данное предположение до сих пор успешно противостоит всемпопыткам его доказать и представляет собой одну из наиболееинтригующих проблем комбинаторной теории ч.у.
множеств(С. Фелснер и У.Т. Троттер).На сегодняшний день наиболее сильный результат:√√5+ 55− 56 Pr[x 6 y] 6≈ 0, 7236 .0, 2764 ≈101031 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация32 / 76Ч.у. множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b ∈ P, a 6= bЯсно, чтопоскольку Pr [ a 6 b ] = 1 − Pr [ b 6 a ], спектрсимметричен относительно 12 ;для всех неодноэлементныхтривиально упорядоченных множеств Spec = 21 ; 1 0, 2 , 1 — единственный трёхэлементный спектр;все четырёхэлементные спектры должны иметь вид{ 0, α, 1 − α, 1 }, где 0 < α < 21 ;Гипотеза (2002): α = 13 .ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияЧ.у.
множества: размерностьПо теореме Шпильрайна ч.у. множество P совпадает спересечением всех e(P) своих линеаризаций, но тот жерезультат можно получить, взяв значительно меньшее числолинейных продолжений.Например, ч.у. множество Pbd[[ c[ aимеет 6 линеаризаций, но P = [ a, b, c, d ] ∩ [ a, d, c, b ].Пусть P — ч.у. множество и R = { L1 , . . . , Lk } —совокупность цепей такая, что P = L1 ∩ . . . ∩ Lk , то говорят,что R реализует P.33 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация34 / 76Ч.у.
множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).Теорема (Оре)Порядковая и мультипликативная размерности ч.у. множествасовпадают.[ 1, 2, 3, 4, 5 ] ∩ [ 2, 4, 1, 3, 5 ]:— [ a, b, c ] × [ d, e ]ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияdim(P) — более тонкая оценка ч.у. множества, чем e(P)Размерность ... имеют:1 — только цепи;2 — тривиально упорядоченные множества(т.е. размерность не может интерпретироваться как мераотличия данного ч.у. множества от линейного);— Zn ;— все отличные от цепей ч.у.
множеств, при |P | 6 6, кроме3 — s3 , sh и shd (см. диаграммы) :n — Sn .35 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияО размерности ч.у. множества P = h P, 6 i∅ 6= Q ⊆ P ⇒ dim(Q) 6 dim(P), при удалении 1-гоэлемента его размерность уменьшается не более, чем на 1;dim(P + Q) = max dim(P), dim(Q) , если хотя быодно из множеств не является цепью и dim(P + Q) = 2;dim(P × Q) 6 dim(P) + dim(Q);dim(P) 6 |P|/2 при |P| > 4 (теорема Хирагучи).Теорема («компактности»)Пусть P — такое ч.у.
множество, что любое его конечное ч.у.подмножество имеет размерность, не превосходящую d.Тогда dim(P) 6 d.wp1 :n4c1nc21−6 dim(P) 61−, n = |P|.log n4log n36 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияd-несводимые ч.у. множестваОпределениеЧ.у. множество P называется d-несводимым для некоторогоd > 2, если dim(P) = d и dim(P 0 ) < d для любогособственного ч.у. подмножества P 0 ⊂ P .... несводимые множества:2 — двухэлементная антицепь (единственное);3 — s3 , sh, shd + ... — описаны, регулярны и хорошо изучены;4 — достаточно часто встречаются и весьма причудливы;t — St (единственное 2t-элементное) + ...;каждое t-несводимое ч.у.
множество являетсяч.у. подмножеством некоторого (t + 1)-несводимого.37 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризация4-несводимое ч.у. множество[[[◦◦' '◦ ''A'A ◦A''A'A''' '''AAA AA'A'' '''' AA A'◦◦◦ [◦ [[◦◦◦38 / 76ПРИКЛАДНАЯ АЛГЕБРА. Часть IV: Частично упорядоченные множестваЛинеаризацияПроблема НогинаКаково наибольшее значение π(d, n) мощности множествамаксимальных элементов d-несводимого n-элементного ч.у.множества при d > 4?Данная проблема до сих пор остаётся открытой.Утверждениеπ(d, n) 6 n − d .39 / 76ПРИКЛАДНАЯ АЛГЕБРА.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
