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

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

Версия 12:42, 30 марта 2009 (править) ESyr01 (Обсуждение | вклад) ← К предыдущему изменению		Текущая версия (12:43, 30 марта 2009) (править) (отменить) ESyr01 (Обсуждение | вклад)
Строка 197:		Строка 197:
	squr@cs.msu.su		squr@cs.msu.su
		+
		+	{{СППМ}}
		+	{{Lection-stub}}

---

Текущая версия

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

...

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_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> <b,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