Материал из eSyr's wiki.
Линейный порядок.
...
- e(P+Q) = c^n_{m+n} e(P) e(Q)
- e(2×n) = 1/(n+1) C^n_{2n} — число Каталана
- Для заборов: Σ_{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), равенство будет, когда квазицепь
Для нас интересны следующие вещи: оказывается, иссл. нами число — одна из хар-к ЧУМ.
Первая характеристика — число элементов. Но оно говорит не очень много. Число линеаризаций говорит больше:
- e(C) = 1
- e(n*1) = n!
Очевидно, что число факт. нах. между этими двумя числами.
Как подсчитать эти числа? Известны 4 способа, лектор назовёт 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-несв. ясно и регулярно, то выше они ведут крайне нерег. и разумному описанию не поддаются.
Например: когда общая корона несводима? Несводима о.к. в след. случаях:
- n+k = q(k+2)+1 (2q+1)-несводимое
- n+k = q(k+2) + [1/2 (k + 2)](вниз) + 1, k=0, k-неч. (2q+1)-несводимое
- Обобщ. корона несводима только в этих случаях
Пусть ЧУМ из n (n≥4) элементов d-несводимо. Какое макс. знач. может принимать множество Паретте? μ(n,d)=?
Проблема пост. в 90-х годах. Почти 20 лет висит задача, ничего.
μ(n,d)≤n-d
Зачёт. Ближе к зачётной неделе. После 9 мая.
Как будет проходить зачёт: лектор таки что-то спросит. Тот, кто хочет, чтобы его спрашивали как можно меньше, пусть напишет небольшой рефератик, страниц на 5, где будут записаны осн. вещи, что вы поняли.
Литература: литературы нет.
Из того, что есть:
- Р. Стенли. "Перичислительная комбинаторика", т. 1
- Биркгоф, Барти "Современная прикладная алгебра"
- "Теория решёток", "Общая еория решёток"
- Троттер. "Теория размерности ЧУМ"
squr@cs.msu.su
Эта статья является конспектом лекции.
Эта статья ещё не вычитана. Пожалуйста, вычитайте её и исправьте ошибки, если они есть.
