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

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

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

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

...

# e(P+Q) = c^n_{m+n} e(P) e(Q)
# e('''2'''&times;'''n''') = 1/(n+1) C^n_{2n} — число Каталана
# Для заборов: &Sigma;_{n &ge; 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) = &Sigma;_{n&ge;0}B_n z^n/n!, B_n' = |B_{2n}|
#:* (sin z + cos z) / (cos z - sin z) = &Sigma;_{n&ge;0} T_n z^n/n!; E_n' = |E_{2n}| = T_{2n}/2^{2n}

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

Известно вот что: на множ. задано два порядка <P, &le;_1> = P_1, <P, &le;_2> = P_2, но один есть рподолдение другого (&le;_1 &sub; &le;_2). Тогда e(P_1) &ge; e(P_2)

Рассм. грануированное множество: <граф>
(l_1)!...(l_k)! &le; e(P), равенство будет, когда квазицепь

Для нас интересны следующие вещи: оказывается, иссл. нами число — одна из хар-к ЧУМ.

Первая характеристика — число элементов. Но оно говорит не очень много. Число линеаризаций говорит больше:
# e(C) = 1
# e(n*'''1''') = n!
Очевидно, что число факт. нах. между этими двумя числами.

Как подсчитать эти числа? Известны 4 способа, лектор назовёт 2:
# построить решётку всех порядков (решётку порядковых идеалов), и посчитать число всех цепей. Решётка порядковых идеалов связано много с чем.
# оказывается, это число равно n!vol('''P'''(P)), где vol — объём многогранника '''P'''(P), который строится следующим образом: 
#: Рассмотрим  ЧУМ <P, &le;>, пусть оно имеет n элементов v_1...v_n. Рассмотрим n- мерное евкл. простарнство, координатами которого будут x_1...x_n. Рассмотрим единичный куб. СЕйчас мы строим '''P'''(P), он ограничен ебинич. кубом, понятно, что объём многогр. огр. 1. Строится он вот так: множество всех x_1...x_n &isin; R^n, и если v_i &isin; v_j &rArr; x_i &le; 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>  
  \  |  /
    &empty;
Достр. 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

Как получена эта формула: прямым построением.

А если для малой короны: 
 &Sigma;_{n&ge;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, &le;>

'''P'''(P)

&le; = &cap; &le;_1

&le;_i &isin; '''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 &cap; B &cap; C = A &cap; 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)&le;dim(X)&le;dim(X-x)+1
Через неск. лет тот же Хирогучи(?) уст. другой факт: если мн. имеет более 4 эл-тов, то его разм. не превосх. n/2.

Третье. Размерность ЧУМ не превосх. его ширины: dim(X) &le; w(X)

dim(X) &le; w(X-&pi;(X))+1, где &pi;(X) — множество Паретте (множ. макс. элементов), множество

Зачем это надо: число мин. альт. в задаче многокрит. выбора.

Размерность S_n^k:
 dim(S_n^k) = [2(n+k)/(k+2)] (округл. вверх)

S_n — единст. 2n-элементное множество разм. n.

Критические точки

Пусть имеется ЧУМ, и есть точки x и y. Пускай x&le;y. Это озн., что &forall; u u&le;x: u&le;y. И наоборот: &forall; v y&le;v: x&le;v.

Множ. несравнимых пар P обозн. incomp(P).

Теперь пусть x,y &isin; incomp(P), а свойство осталось. Такие пары наз. критическими. Множество: crit(P)

dim(P) &le; |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&ge;4) элементов d-несводимо. Какое макс. знач. может принимать множество Паретте? &mu;(n,d)=?

Проблема пост. в 90-х годах. Почти 20 лет висит задача, ничего.

&mu;(n,d)&le;n-d

Зачёт. Ближе к зачётной неделе. После 9 мая.

Как будет проходить зачёт: лектор таки что-то спросит. Тот, кто хочет, чтобы его спрашивали как можно меньше, пусть напишет небольшой рефератик, страниц на 5, где будут записаны осн. вещи, что вы поняли.

Литература: литературы нет.

Из того, что есть:
# Р. Стенли. "Перичислительная комбинаторика", т. 1
# Биркгоф, Барти "Современная прикладная алгебра"
# "Теория решёток", "Общая еория решёток"
# Троттер. "Теория размерности ЧУМ"

squr@cs.msu.su

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.name/wiki/%D0%A1%D0%9F%D0%9F%D0%9C/%D0%A7%D0%A3%D0%9C%2C_03_%D0%BB%D0%B5%D0%BA%D1%86%D0%B8%D1%8F_%28%D0%BE%D1%82_30_%D0%BC%D0%B0%D1%80%D1%82%D0%B0%29

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

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

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 14: / Строка 14: @@
 В общем случае вычисл. лин. порядка — NP-полная задача.
-Известно вот что: на множ. задано два порядка &lt;P, &le;_1&gt; = P_1, &lt;P, &le;_2&gt; = P_2, но один есть рподолдение другого (&le;_1 &sub; &le;_2). Тогда e(P_1) &ge; e(P_2)
+Известно вот что: на множ. задано два порядка <P, &le;_1> = P_1, <P, &le;_2> = P_2, но один есть рподолдение другого (&le;_1 &sub; &le;_2). Тогда e(P_1) &ge; e(P_2)
-Рассм. грануированное множество: &lt;граф&gt;
+Рассм. грануированное множество: <граф>
 (l_1)!...(l_k)! &le; e(P), равенство будет, когда квазицепь
@@ Строка 29: / Строка 29: @@
 # построить решётку всех порядков (решётку порядковых идеалов), и посчитать число всех цепей. Решётка порядковых идеалов связано много с чем.
 # оказывается, это число равно n!vol('''P'''(P)), где vol — объём многогранника '''P'''(P), который строится следующим образом:
-#: Рассмотрим  ЧУМ &lt;P, &le;&gt;, пусть оно имеет n элементов v_1...v_n. Рассмотрим n- мерное евкл. простарнство, координатами которого будут x_1...x_n. Рассмотрим единичный куб. СЕйчас мы строим '''P'''(P), он ограничен ебинич. кубом, понятно, что объём многогр. огр. 1. Строится он вот так: множество всех x_1...x_n &isin; R^n, и если v_i &isin; v_j &rArr; x_i &le; x_j, то мы проводим такую гиперплоскость. Рассмотрим для
+#: Рассмотрим  ЧУМ <P, &le;>, пусть оно имеет n элементов v_1...v_n. Рассмотрим n- мерное евкл. простарнство, координатами которого будут x_1...x_n. Рассмотрим единичный куб. СЕйчас мы строим '''P'''(P), он ограничен ебинич. кубом, понятно, что объём многогр. огр. 1. Строится он вот так: множество всех x_1...x_n &isin; R^n, и если v_i &isin; v_j &rArr; x_i &le; x_j, то мы проводим такую гиперплоскость. Рассмотрим для
  x_1  x_3
   \   /
@@ Строка 50: / Строка 50: @@
 Постр. булевую алг. из мин. эл-тов:
-   &lt;a,b,c&gt;
+   <a,b,c>
   /  |  \
-&lt;a,b&gt; &lt;a,c&gt; &lt;b,c&gt;
+<a,b> <a,c> <b,c>
  | X   X |
- &lt;a&gt; &lt;b&gt; &lt;c&gt;
+ <a> <b> <c>
   \  |  /
     &empty;
@@ Строка 81: / Строка 81: @@
 e(P) = n! vol('''P''') — можно считать методом Монте-Карло (раскидать точку по единичному кубу, посчитать те, которые входят в многогранник). Проблема в том, что vol('''P''') — величина малая и требует большое количество попыток.
-&lt;P, &le;&gt;
+<P, &le;>
 '''P'''(P)