Из Википедии, бесплатной энциклопедии
  (Перенаправлен из Zigzag poset )
Перейти к навигации Перейти к поиску
Схема Хассе шестиэлементного забора.

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

a < b > c < d > e < f > h < я ...

или же

a > b < c > d < e > f < h > i ...

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

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

1, 1, 2, 4, 10, 32, 122, 544, 2770, 15872, 101042 (последовательность A001250 в OEIS ).

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

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

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

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

a > b > c < d > e > f < g > h > i .

В этих обозначениях забор - это частично упорядоченный набор формы Q (1, n ).

Эквивалентные условия [ править ]

Следующие условия эквивалентны для чугуна P : [ ссылка ]

  1. P - непересекающееся объединение зигзагообразных множеств.
  2. Если a ≤ b ≤ c в P , либо a = b, либо b = c .
  3. << = , т.е. никогда не бывает, чтобы a < b и b < c , так что <является вакуумно транзитивным.
  4. Р имеет размерность не более одного (определяется аналогично размерности Крулля о наличии коммутативного кольца ).
  5. Каждый элемент P либо максимален, либо минимален .
  6. Категория среза Pos / P является декартово замкнутой . [6]

В простые идеалы коммутативного кольца R , упорядоченных по включению, удовлетворяют эквивалентные условия выше , если и только если R имеет размерность Крулля не более одного. [ необходима цитата ]

Заметки [ править ]

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

Ссылки [ править ]

  • Андре, Дезире (1881), "Sur les permutations alternées", J. Math. Pures Appl. , (Сер. 3), 7 : 167–184..
  • Бек, Иштван (1990), «Частичные порядки и числа Фибоначчи», Fibonacci Quarterly , 28 (2): 172–174, MR  1051291.
  • Карри, JD; Visentin, Т. (1991), "Число порядка , сохраняющая карту заборов и коронок", орден , 8 (2): 133-142, DOI : 10.1007 / BF00383399 , ЛВП : 10680/1724 , МР  1137906 , S2CID  122356472.
  • Даффус, Дуайт ; Рёдль, Войтех; Сэндс, Билл; Вудро, Роберт (1992), "Перечень сохраняющих карт порядка", Order , 9 (1): 15-29, DOI : 10.1007 / BF00419036 , MR  1194849 , S2CID  84180809.
  • Фарли, Джонатан Дэвид (1995), "Число заказов сохраняющих карт между заборами и коронок", орден , 12 (1): 5-44, DOI : 10.1007 / BF01108588 , MR  1336535 , S2CID  120372679.
  • Gansner, Эмден R. (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), "Корона, заборы и решетка dismantlable", Canadian Journal математики , 26 (5): 1257-1271, DOI : 10,4153 / CJM-1974-120-2 , MR  0417003.
  • Рутковский, Александр (1992a), "Число строго возрастает отображения заборов", заказ , 9 (1): 31-42, DOI : 10.1007 / BF00419037 , МР  1194850 , S2CID  120965362.
  • Рутковский, Александр (1992b), "Формула для числа сохраняющего порядка самих-отображений забора", заказ , 9 (2): 127-137, DOI : 10.1007 / BF00814405 , МР  1199291 , S2CID  121879635.
  • Сальви, Родольфо; Салви, Норма Загалья (2008), «Чередующиеся унимодальные последовательности чисел Уитни», Ars Combinatoria , 87 : 105–117, MR  2414008.
  • Стэнли, Ричард П. (1986), Enumerative Combinatorics , Wadsworth, Inc. CS1 maint: discouraged parameter (link) Упражнение 3.23а, стр. 157.
  • Вальдес, Якобо; Тарджан, Роберт Э .; Лоулер, Евгений Л. (1982), "Признание серии параллельных орграфах", SIAM журнал по вычислениям , 11 (2): 298-313, DOI : 10,1137 / 0211023.

Внешние ссылки [ править ]

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