PA_full (1127144), страница 25
Текст из файла (страница 25)
множества: спектрОпределение:Spec (P) =Pr [ a 6 b ] | a, b 2 P, a 6= bЯсно, чтопоскольку Pr [ a 6 b ] = 1 Pr [ b 6 a ], спектрсимметричен относительно 12 ;для всех неодноэлементных тривиально упорядоченныхмножеств Spec = 12 ;0, 12 , 1� единственный трёхэлементный спектр;все четырёхэлементные спектры должны иметь вид{ 0, ↵, 1 ↵, 1 }, где 0 < ↵ < 12 ;Гипотеза (2002): ↵ = 13 .351 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерностьПо теореме Шпильрайна ч.у.
множество P совпадает спересечением всех e(P) своих линеаризаций.Однако тот же результат можно получить, взяв значительноменьшее число линейных продолжений. Например, ч.у.множество Pcbdaимеет 6 линеаризаций, но P = [ a, b, c, d ] \ [ a, d, c, b ].352 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерностьПо теореме Шпильрайна ч.у. множество P совпадает спересечением всех e(P) своих линеаризаций.Однако тот же результат можно получить, взяв значительноменьшее число линейных продолжений. Например, ч.у.множество Pcbdaимеет 6 линеаризаций, но P = [ a, b, c, d ] \ [ a, d, c, b ].Пусть P � ч.у.
множество и R = { L1 , . . . , Lk } �совокупность цепей такая, что P = L1 \ . . . \ Lk , то говорят,что R реализует P.352 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).353 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияЧ.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).Теорема (Оре)Порядковая и мультипликативная размерности ч.у.
множествасовпадают.353 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация353 / 432Ч.у. множества: размерность...ОпределениеНаименьшее число линейных порядков, дающих в пересечении данноеч.у. множество P называется его (порядковой) размерностью(символически dim(P )).Теорема (Оре)Порядковая и мультипликативная размерности ч.у. множествасовпадают.[ 1, 2, 3, 4, 5 ] \ [ 2, 4, 1, 3, 5 ]:� [ a, b, c ] ⇥ [ d, e ]Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияdim(P) � более тонкая оценка ч.у.
множества, чем e(P)Размерность ... имеют:1 � только цепи;2 � тривиально упорядоченные множества(т.е. размерность не может интерпретироваться как мераотличия данного ч.у. множества от линейного);� Zn ;� все отличные от цепей ч.у. множеств, при |P | 6 6, кроме3 � s3 , sh и shd (см. диаграммы) :n � Sn .354 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияО размерности ч.у. множества 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 (теорема Хирагучи).355 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияО размерности ч.у.
множества 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.355 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация355 / 432О размерности ч.у.
множества 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 :n4✓1c1log n◆n6 dim(P) 64✓1c2log n◆, n = |P|.Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация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)-несводимого.356 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризация4-несводимое ч.у. множество357 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема НогинаКаково наибольшее значение ⇡(d, n) мощности множествамаксимальных элементов d-несводимого n-элементного ч.у.множества при d > 4?Данная проблема до сих пор остаётся открытой.358 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЛинеаризацияПроблема НогинаКаково наибольшее значение ⇡(d, n) мощности множествамаксимальных элементов d-несводимого n-элементного ч.у.множества при d > 4?Данная проблема до сих пор остаётся открытой.Утверждение⇡(d, n) 6 nd.358 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды359 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств360 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьРаздел IIIОсновные понятия теории ч.у.
множествОперации над ч.у. множествамиЛинеаризацияЧто надо знать5Алгебраические решёткиРешётки: определение, основные свойстваМодулярные и дистрибутивные решёткиПрименение теории решёток к задаче классификацииЧто надо знать361 / 432Прикладная алгебраНекоторые вопросы теории частично упорядоченных множествЧто надо знатьЧастично упорядоченные (ч.у.) множества: определение,примеры, основные понятия. Диаграммы Хассе и особыеэлементы ч.у.
множеств.Ранжированные ч.у. множества. Цепное условиеЖордана-Дедекинда. Порядковые гомоморфизмыИдеалы и фильтры ч.у. множеств. Конусы. Точные грани.Операции над ч.у. множествами.Теорема Шпильрайна. Линейное продолжение ч.у.множества и топологическая сортировка.Линеаризации и вероятностное пространство над ними.XYZ-теорема. Проблема сортировки и �1/3 – 2/3предположение�.Спектр и размерность ч.у. множеств. Свойстваразмерности, d-несводимые множества и проблема Ногина.362 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел I1Конечные поля или поля ГалуаПоля вычетов по модулю простого числаВычисление элементов в конечных поляхЛинейная алгебра над конечным полемКорни многочленов над конечным полемСуществование и единственность поля Галуа из pnэлементовЦиклические подпространстваЗадачиЧто надо знать2Коды, исправляющие ошибкиПонятие помехоустойчивого кодирования.
Коды ХэммингаГрупповые (линейные) коды363 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел IIЦиклические кодыКоды БЧХЗадачиЧто надо знать3Теория перечисления ПойаДействие группы на множествеПрименение леммы Бёрнсайда для решениякомбинаторных задачПрименение теоремы Пойа для решения комбинаторныхзадачЗадачиЧто надо знать4Некоторые вопросы теории частично упорядоченныхмножеств364 / 432Прикладная алгебраАлгебраические решёткиРешётки: определение, основные свойстваРаздел IIIОсновные понятия теории ч.у. множествОперации над ч.у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
