Забор (математика)

Частично упорядоченное множество с попеременно связанными элементами

Диаграмма Хассе шестиэлементного забора.

В математике забор , также называемый зигзагообразным посетом , представляет собой частично упорядоченное множество ( посет ), в котором отношения порядка образуют путь с чередующимися ориентациями:

${\displaystyle a<b>c<d>e<f>h<i\cdots }$

или

${\displaystyle a>b<c>d<e>f<h>i\cdots }$

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

Линейное расширение забора называется чередующейся перестановкой ; задача Андре о подсчете числа различных линейных расширений изучается с 19 века. ^[1] Решения этой задачи подсчета, так называемые зигзагообразные числа Эйлера или числа вверх/вниз, таковы:

${\displaystyle 1,1,2,4,10,32,122,544,2770,15872,101042.}$

(последовательность A001250 в OEIS ).

Число антицепей в заборе равно числу Фибоначчи ; распределительная решетка с таким количеством элементов, полученная из забора с помощью теоремы Биркгофа о представлении , имеет своим графом куб Фибоначчи . ^[2]

Частично упорядоченный набор является последовательно-параллельным тогда и только тогда, когда он не содержит четырех элементов, образующих забор. ^[3]

Несколько авторов также исследовали количество карт, сохраняющих порядок, от заборов к самим себе или к заборам других размеров. ^[4]

Вверх-вниз частично упорядоченный набор Q ( a , b ) является обобщением зигзагообразного частично упорядоченного набора, в котором для каждого восходящего набора существует a нисходящих ориентаций и b общих элементов. ^[5] Например, Q (2,9) имеет элементы и отношения

${\displaystyle a>b>c<d>e>f<g>h>i.}$

В этой нотации забор — это частично упорядоченное множество вида Q (1, n ) .

Ссылки

1. Андре (1881).
2. Ганснер (1982) называет тот факт, что эта решетка имеет число Фибоначчи элементов, «хорошо известным фактом», в то время как Стэнли (1986) просит описать его в упражнении. См. также Höft & Höft (1985), Beck (1990) и Salvi & Salvi (2008).
3. Вальдес, Тарьян и Лоулер (1982).
4. Карри и Висентин (1991); Даффус и др. (1992); Рутковский (1992а); Рутковский (1992b); Фарли (1995).
5. Ганснер (1982).

• Андре, Дезире (1881), «Сюр-ль-альтернативные перестановки», J. Math. Приложение Pures. , (Сер. 3), 7 : 167–184..
• Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Fibonacci Quarterly , 28 (2): 172–174, MR  1051291.
• Currie, JD; Visentin, TI (1991), «Число карт ограждений и корон, сохраняющих порядок», Order , 8 (2): 133–142, doi : 10.1007/BF00383399, hdl : 10680/1724 , MR  1137906, S2CID  122356472.
• Даффус, Дуайт ; Рёдль, Войтех; Сэндс, Билл; Вудроу, Роберт (1992), «Перечисление карт, сохраняющих порядок», Order , 9 (1): 15–29, doi :10.1007/BF00419036, MR  1194849, S2CID  84180809.
• Фарли, Джонатан Дэвид (1995), «Число карт, сохраняющих порядок между заборами и коронами», Order , 12 (1): 5–44, doi :10.1007/BF01108588, MR  1336535, S2CID  120372679.
• Ганснер, Эмден Р. (1982), «О решетке идеалов порядка частично упорядоченного множества вверх-вниз», Дискретная математика , 39 (2): 113–122, doi : 10.1016/0012-365X(82)90134-0 , MR  0675856.
• Хёфт, Хартмут; Хёфт, Маргрет (1985), «Последовательность Фибоначчи распределительных решеток», Fibonacci Quarterly , 23 (3): 232–237, MR  0806293.
• Келли, Дэвид; Ривал, Иван (1974), «Короны, заборы и разборные решетки», Канадский журнал математики , 26 (5): 1257–1271, doi : 10.4153/cjm-1974-120-2 , MR  0417003.
• Рутковский, Александр (1992a), «Число строго возрастающих отображений заборов», Order , 9 (1): 31–42, doi :10.1007/BF00419037, MR  1194850, S2CID  120965362.
• Рутковский, Александр (1992b), «Формула для числа сохраняющих порядок самоотображений забора», Order , 9 (2): 127–137, doi :10.1007/BF00814405, MR  1199291, S2CID  121879635.
• Сальви, Родольфо; Сальви, Норма Загалья (2008), «Чередующие унимодальные последовательности чисел Уитни», Ars Combinatoria , 87 : 105–117, MR  2414008.
• Стэнли, Ричард П. (1986), Перечислительная комбинаторика , Wadsworth, Inc.Упражнение 3.23а, стр. 157.
• Вальдес, Якобо; Тарьян, Роберт Э.; Лоулер , Юджин Л. (1982), «Распознавание серий параллельных орграфов», SIAM Journal on Computing , 11 (2): 298–313, doi :10.1137/0211023.

Внешние ссылки

• Вайсштейн, Эрик В. "Посет с забором". MathWorld .