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

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

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

а < б > c < d > е < ж > час < я ...

или

а > б < c > d < е > ж < час > я ...

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

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

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

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

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

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

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

а > б > c < d > е > ж < грамм > час > я.

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

Эквивалентные условия

Следующие условия эквивалентны для ч.у. п:[нужна цитата ]

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

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

Примечания

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

Рекомендации

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

внешняя ссылка