СППМ/ЧУМ, 03 лекция (от 30 марта)

Материал из eSyr's wiki.

(Различия между версиями)
Перейти к: навигация, поиск

ESyr01 (Обсуждение | вклад)
(Новая: Линейный порядок. ... # e(P+Q) = c^n_{m+n} e(P) e(Q) # e('''2'''×'''n''') = 1/(n+1) C^n_{2n} — число Каталана # Для заборов: Σ_{n &g...)
К следующему изменению →

Версия 12:41, 30 марта 2009

Линейный порядок.

...

  1. e(P+Q) = c^n_{m+n} e(P) e(Q)
  2. e(2×n) = 1/(n+1) C^n_{2n} — число Каталана
  3. Для заборов: Σ_{n ≥ 0} e(Z_n)/n! x^n = tg x + sec x (т.к. tg имеет неч. разл., а секанс — нечётное, то чётные имеют назв. "числа секанса", а неч. — числа тангенса)
    Разложение тангенса: tg x = x + 1/3 x^3 + 2/15 x^5 + ... + 2^2n(2n - 1)/(2n)! B_n' x^{2n-1} + ...
    Разложение секанса: sec x = 1 + x^2/2 + 5/24 x^4 + ... + E_n' / (2n)! x^{2n}
    B, E — комбинаторные числа Бернулли и Эйлера. Однако в теор. иссл. понимаются не эти числа, поэтому штрихи. Под ними понимают вот что:
    • z/(e^z - 1) = Σ_{n≥0}B_n z^n/n!, B_n' = |B_{2n}|
    • (sin z + cos z) / (cos z - sin z) = Σ_{n≥0} T_n z^n/n!; E_n' = |E_{2n}| = T_{2n}/2^{2n}

В общем случае вычисл. лин. порядка — NP-полная задача.

Известно вот что: на множ. задано два порядка

= P_1, <P, ≤_2> = P_2, но один есть рподолдение другого (≤_1 ⊂ ≤_2). Тогда e(P_1) ≥ e(P_2) Рассм. грануированное множество: <граф> (l_1)!...(l_k)! ≤ e(P), равенство будет, когда квазицепь Для нас интересны следующие вещи: оказывается, иссл. нами число — одна из хар-к ЧУМ. Первая характеристика — число элементов. Но оно говорит не очень много. Число линеаризаций говорит больше:

  1. e(C) = 1
  2. e(n*1) = n!
Очевидно, что число факт. нах. между этими двумя числами. Как подсчитать эти числа? Известны 4 способа, лектор назовёт 2:
  1. построить решётку всех порядков (решётку порядковых идеалов), и посчитать число всех цепей. Решётка порядковых идеалов связано много с чем.
  2. оказывается, это число равно n!vol(P(P)), где vol — объём многогранника P(P), который строится следующим образом:
    Рассмотрим ЧУМ <P, ≤>, пусть оно имеет n элементов v_1...v_n. Рассмотрим n- мерное евкл. простарнство, координатами которого будут x_1...x_n. Рассмотрим единичный куб. СЕйчас мы строим P(P), он ограничен ебинич. кубом, понятно, что объём многогр. огр. 1. Строится он вот так: множество всех x_1...x_n ∈ R^n, и если v_i ∈ v_j ⇒ x_i ≤ x_j, то мы проводим такую гиперплоскость. Рассмотрим для
x_1 x_3 \ / x_2 Получим пирамиду, объём её 1/3, получим число линеар. 2, так и есть: x_3 x_1 | | x_1 x_3 | | x_2 x_2 Как простр. какую-нибудь линеаризацию: взять миним. эл-ты, цпорядочить их, убрать, посторить итерацию. Однако не любой порядок может быть так построен. Рассмотрим 1-й способ на Z_5: d e / \ / \ a b c В прошлый раз мы считали число ..., теперь мы считаем число восх. путей. Постр. булевую алг. из мин. эл-тов: <a,b,c> / | \ <a,b> <a,c> | X X | <a> <b> <c> \ | / ∅ Достр. d,e ... Через a,b,c прох. 3! путей, из a,b,c дву пути наверх — итого 6*2 = 12 путей. Через d два пути, через e 2 пути. 6*2+2+2 = 16 По теории получаем 2/15 * 5! = 16. Совпадают. Также удалось этим же методом посчитать для большой короны: e(S_n) = (n!)^2 n+1/n Как получена эта формула: прямым построением. А если для малой короны: Σ_{n≥0} e(s_n) / n! = x/cos^2 x Как доказывается: искл. добавленное ребро, потом добавим пути через новое ребро.
  • e(S_4) = 1088
  • e(Z_8) = 1385
e(P) = n! vol(P) — можно считать методом Монте-Карло (раскидать точку по единичному кубу, посчитать те, которые входят в многогранник). Проблема в том, что vol(P) — величина малая и требует большое количество попыток. <P, ≤> P(P) ≤ = ∩ ≤_1 ≤_i ∈ P(P) Задача: взять как можно меньше линеар. (k), чтобы получить исх. порядок. Число k наз. порядковой размерностью и будем обозн. так: dim(P) На прошлой лекции говорили, что лбюбой пор. может быть вложен в произв. цепей, и наз. его мультипликац. размерностью. Появл. две размерности. Теорема Оре. Мультиплик. и пор. размерности ЧУМ совпадают. Нас будет интерес. разм. как количество лин. порядков. Пример: b c d \|/ a Его можно разл. в произв. трёх порядков: A=[a,b,c,d], B=[a,d,b,c], C=[a,c,d,b]. Ясно, что граф есть A ∩ B ∩ C = A ∩ D, D = [a,d,c,b]. Значит., разм. этого множества равн. двум. Оказ., если число элементов 1,2,3,4,5, то разм. не превосходит 2. Для 6 элементов — все имеют 2, кроме трёх искл.: S_3 (3), шеврон и двоёст. к нему x x |\ /| x x x \ / x (шеврон) Задача: с1 с2 | | b1Xb2 | | a1 a2 Если больше 6 элементов: лектор указ. те ЧУМ, у которых разм. 3. Вообще говоря, их довольно много. ЧУМ высоной разм. построить сложно, однако сущ. стандартный пример: если взять большую корону, то размерность её n: dim(S_n) = n Можно рассм. как упорядоч. по вкл. 1-элем. и n-1 элем. dim(B^n) = n. У неё можно выкинуть всё, кроме 1 и предпосл. слоёв, и разм. останется. Монотонность по мощности: ... Малая корона: dim(s_n) = 2 При удалении одного элемента ЧУМ его разм. понижается не более, чем на единицу: dim(X-x)≤dim(X)≤dim(X-x)+1 Через неск. лет тот же Хирогучи(?) уст. другой факт: если мн. имеет более 4 эл-тов, то его разм. не превосх. n/2. Третье. Размерность ЧУМ не превосх. его ширины: dim(X) ≤ w(X) dim(X) ≤ w(X-π(X))+1, где π(X) — множество Паретте (множ. макс. элементов), множество Зачем это надо: число мин. альт. в задаче многокрит. выбора. Размерность S_n^k: dim(S_n^k) = [2(n+k)/(k+2)] (округл. вверх) S_n — единст. 2n-элементное множество разм. n. Критические точки Пусть имеется ЧУМ, и есть точки x и y. Пускай x≤y. Это озн., что ∀ u u≤x: u≤y. И наоборот: ∀ v y≤v: x≤v. Множ. несравнимых пар P обозн. incomp(P). Теперь пусть x,y ∈ incomp(P), а свойство осталось. Такие пары наз. критическими. Множество: crit(P) dim(P) ≤ |crit(P)| Для каждой крит. пары необх. своя линеар. Переходим к самому вкусному. Размерность ЧУМ. Мы знаем, по т. Хирогучи, что удал. одного элемента уменьш. разм. не более, ем на единиц. Теперь предст. множ., искл. любого уменьш. разм. dim(P)=d. Такое ЧУМ наз. d-неприводимым. Что известно по ним: S_n — n-несводимое множество. S-3, Sh (шеврон) — 3-несводимые. Оказывается, что если разм. d, то выкидывание может привести к d-несводимому. На сегодняшний день все 3-несводимые ЧУМ известны и описаны. Их 19 различных типов. Насчёт 4-несв. и дальше неизвестно. Но преобл. мнение, что если для 3-несв. ясно и регулярно, то выше они ведут крайне нерег. и разумному описанию не поддаются. Например: когда общая корона несводима? Несводима о.к. в след. случаях:
  1. n+k = q(k+2)+1 (2q+1)-несводимое
  2. n+k = q(k+2) + [1/2 (k + 2)](вниз) + 1, k=0, k-неч. (2q+1)-несводимое
  3. Обобщ. корона несводима только в этих случаях
Пусть ЧУМ из n (n≥4) элементов d-несводимо. Какое макс. знач. может принимать множество Паретте? μ(n,d)=? Проблема пост. в 90-х годах. Почти 20 лет висит задача, ничего. μ(n,d)≤n-d Зачёт. Ближе к зачётной неделе. После 9 мая. Как будет проходить зачёт: лектор таки что-то спросит. Тот, кто хочет, чтобы его спрашивали как можно меньше, пусть напишет небольшой рефератик, страниц на 5, где будут записаны осн. вещи, что вы поняли. Литература: литературы нет. Из того, что есть:
  1. Р. Стенли. "Перичислительная комбинаторика", т. 1
  2. Биркгоф, Барти "Современная прикладная алгебра"
  3. "Теория решёток", "Общая еория решёток"
  4. Троттер. "Теория размерности ЧУМ"
squr@cs.msu.su


Эта статья является конспектом лекции.

Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.

Личные инструменты
Разделы