Градуированное частично упорядоченное множество

Градуированное частично упорядоченное множество — частично упорядоченное множество P, снабжённое функцией ранга ρ из P в N, удовлетворяющей следующим двум свойствам:

функция ранга совместима с упорядочиванием, в смысле, что для любых x и y с порядком x < y должно выполняться ρ(x) < ρ(y);
функция ранга совместима с отношением подчинения^[англ.] упорядочения, в смысле, что для любого x подчинённого y должно выполняться ρ(y) = ρ(x) + 1.

Значение функции ранга элемента частично упорядоченного множества называется рангом элемента.

Иногда градуированное частично упорядоченное множество называется ранжированным, но определение ранжированное может иметь несколько другое значение (Ранжированное частично упорядоченное множество^[англ.]). Уровнем ранга градуированного частично упорядоченного множества называется подмножество всех элементов частично упорядоченного множества, имеющим заданное значение ранга^[1]^[2].

Градуированные частично упорядоченные множества играют важную роль в комбинаторике и могут быть представлены в виде диаграммы Хассе.

Примеры

Несколько примеров градуированных частично упорядоченных множеств (с функциями ранга):

натуральные числа N с их естественным порядком (ранг — само число) или некоторый интервал [0,N] этого частично упорядоченного множества,
Nⁿ с порядком прямого приведения^[англ.] или подмножество этого частично упорядоченного множества, являющееся произведением интервалов,
положительные числа, упорядоченные по числу простых делителей с учётом кратности или подмножество этого частично упорядоченного множества, образованное делителями фиксированного числа N,
булева решётка конечных подмножеств множества (ранг — число элементов в подмножестве),
решётка разбиений множества на конечное число частей, упорядоченная обратно степени разбиения (ранговая функция — число частей),
решётка разбиений конечного множества X, упорядоченная по степени разбиения (ранговая функция — число элементов X минус число частей разбиения),
группа и порождающее множество, или, эквивалентно, её граф Кэли, порядок — слабый или сильный порядок Брюа, ранговая функция — длина слова (длина самого короткого приведённого слова).
- в частности, для групп Коксетера, например, перестановок вполне упорядоченного множества из n-элементов, со слабым или сильным порядком Брюа (ранговая функция — число смежных инверсий),
геометрические решётки^[англ.], такие как решётка подпространств векторного пространства (ранговая функция — размерность подпространства),
дистрибутивная решётка конечного нижнего множества другого частично упорядоченного множества (ранговая функция — число элементов),
решётка Юнга^[англ.], частный случай предыдущего примера (ранговая функция — число ячеек в диаграмме Юнга),
решётки граней^[англ.] многомерных выпуклых многогранников (ранговая функция — размерность грани + 1),
абстрактные многогранники (ранговая функция — «расстояние» от наименьшей грани — 1),
абстрактные симплициальные комплексы^[англ.] (ранговая функция — число элементов симплекса).

Альтернативные описания

Ограниченное частично упорядоченное множество^[3] допускает градуирование тогда и только тогда, когда все максимальные цепочки в P имеют одну длину^[4] — если установить ранг наименьшего элемента равным 0, то ранг определяется полностью. Это перекрывает много конечных случаев. См. рисунок примера, не допускающего градуирования. Неограниченные частично упорядоченные множества, однако, могут быть существенно сложнее.

Функция-кандидат ранга, совместимая с упорядочением, делает частично упорядоченное множество градуированным тогда и только тогда, когда для x < z, где z имеет ранг n+1, для всех элементов y ранга n должно выполняться x ≤ y < z. Это условие является достаточным, поскольку в случае, когда x подчинён z, единственная возможность — y = x, и условие является необходимым, поскольку в градуированном частично упорядоченное множество можно в качестве y взять любой элемент максимального ранга с x ≤ y < z, который всегда существует и подчинён z.

Часто получаем частично упорядоченное множество с естественным кандидатом для ранговой функции. Например, если его элементы являются подмножествами некоторого базового множества B, можно взять число элементов этих подмножеств. Тогда выше указанный критерий может оказаться более практичным, чем определение, поскольку в нём не упоминается подчинение. Например, если B само по себе является частично упорядоченным множеством и P состоит из конечных нижних множеств (подмножества, для которых для любого элемента подмножества все меньшие элементы принадлежат тому же множеству), тогда это условие автоматически удовлетворяется, поскольку для нижних множеств x ⊂ z всегда существует максимальный элемент множества z, который отсутствует в x и может быть удалён из z для получения y.

В некоторых общих частично упорядоченных множествах, таких как решётки граней^[англ.] выпуклых многограников, существует естественное градуирование (размерность), которое, будучи использованным в качестве функции ранга, даёт минимальный элемент, пустую грань с рангом −1. В таких случаях удобно «подправить» определение выше путём добавления значения −1 к множеству допустимых значений функции ранга. Если же позволить функции ранга принимать произвольные целые значения, получим совсем другое понятие. В этом случае, например, нельзя говорить о существовании минимального элемента.

Градуированное частично упорядоченное множество (с положительными значениями функции ранга) не может имеет какого-либо элемента x, до которого существуют цепочки произвольной длины с максимальным элементом x, в противном случае оно имело бы элементы произвольно малого (в том числе и отрицательного) ранга. Например, множество целых чисел (с естественным порядком) не может быть градуированным частично упорядоченным множеством. Не может быть градуированным частично упорядоченным множеством любой интервал (более чем с одним элементом), рациональных или вещественных чисел. (В частности, градуированные частично упорядоченные множества являются вполне фундированными, что означает, что они удовлетворяют условию убывающей цепочки^[англ.] — они не содержат какой-либо бесконечной убывающей цепи^[англ.]^[5]). С этого момента мы рассматриваем частично упорядоченные множества, в которых таких цепочек нет. Отсюда следует, что при x < y мы можем получить y из x за конечное число шагов, последовательно выбирая элемент, которому предыдущий элемент подчинён. Это также означает, что (для функций ранга, принимающих положительные целые значения) совместимость ρ с порядком следует из требования подчинённости. В качестве варианта определения градуированного частично упорядоченного множества Биркгоф^[6] позволяет функции ранга иметь произвольные (а не только неотрицательные) целые значения. В этом варианте целые числа могут быть градуированы (с помощью тождественной функции) и совместимость функции ранга с порядком не является избыточным требованием.

Градуированное частично упорядоченное множество не обязано удовлетворять условию возрастающей цепочки^[англ.]. Например, натуральные числа содержат бесконечную возрастающую цепочку $0<1<2<\cdots$ .

Частично упорядоченное множество является градуированным тогда и только тогда, когда любая связная компонента его графа сравнимости является градуированной, так что дальнейшее описание предполагает, что этот граф сравнимости связен. На каждой связной компоненте функция ранга единственна с точностью до однородного сдвига (так что функцию ранга можно всегда выбрать так, что минимальный ранг связной компоненты имеет ранг 0).

Если P имеет наименьший элемент Ô, при градуировании это эквивалентно условию, что для любого элемента x все максимальные цепи в интервале [Ô,x] имеют одну и ту же длину. Это условие необходимо, поскольку любой шаг в максимальной цепи является отношением подчинения, которое изменяет ранг на 1. Условие является также достаточным, поскольку в случае его выполнения можно использовать упомянутую длину для определения ранга x (длина конечной цепи равно числу «шагов», так что ранг на единицу меньше числа элементов цепи), и когда y подчинён x, добавление x к максимальной цепи [Ô,y] даёт максимальную цепь в [Ô,x].

Если P имеет также наибольший элемент Î (так что это ограниченное частично упорядоченное множество), тогда предыдущее условие может быть упрощено до требования, что все максимальные цепи в P имеют одну и ту же (конечную) длину. Это условие достаточно, поскольку любая пара максимальных цепей в [Ô,x] могут быть расширены максимальной цепью в [x,Î], что даёт пару максимальных цепей в P.

Ричард Стэнли^[англ.] определяет частично упорядоченное множество градуированным с длиной n, если его максимальные цепи имеют длину n^[7]. Это определение даётся в контексте, где, в основном, рассматриваются конечные частично упорядоченные множества, и, хотя в книге часто слова «длины n» опущены, для частично упорядоченного множества общего вида это определение не выглядит приемлемым, поскольку (1) оно ничего не говорит о частично упорядоченных множествах, имеющих бесконечные максимальные цепи, и (2) оно исключает такие важные частично упорядоченные множества, как решётки Юнга^[англ.]. Также неясно, почему в градуированном частично упорядоченном множестве все минимальные элементы, как и все максимальные элементы, должны иметь одну и ту же длину, хотя Стэнли даёт примеры, по которым ясно, что он не требует этого (там же, стр.216 и 219).

Обычный случай

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

Далее, в этом случае с уровнем ранга связываются ранговые числа, или числа Уитни $W_{0},W_{1},W_{2},...$ . Эти числа определяются как $W_{i}$ = число элементов множества P, имеющих ранг i .

Числа Уитни связаны со множеством важных комбинаторных теорем. Классический пример — теорема Спернера^[англ.], которую можно сформулировать следующим способом: для степени ${\mathcal {P}}(S)$ любого конечного множества $S$ максимальная мощность семейства Спернера^[англ.] равна максимальному числу Уитни. Это означает, что любая конечная степень множества имеет свойство Спернера^[англ.].

См. также

Предупорядочение^[англ.] — предупорядочение с нормой является аналогом градуированного частично упорядоченного множества, где отображение в целые числа заменяется на порядковые числа
Звёздное произведение^[англ.] — метод комбинирования двух градуированных частично упорядоченных множеств

Примечания

↑ Stanley, 1984, с. 29–34.
↑ Butler, 1994, с. 151.
↑ Что означает, что в множестве есть минимальный и максимальный элементы
↑ То есть нет ситуации, когда не возникает ситуации, когда обе цепочки $x<z_{1}<y$ и $x<w_{1}<w_{2}<y$ являются максимальными.
↑ Отсутствие произвольно длинной убывающей цепи, начинающейся с данного элемента, конечно, исключает существование бесконечной убывающей цепи. Хотя, отсутствие цепи произвольной длины строже — множество $\mathbb {N} \cup \{\infty \}$ имеет бесконечно длинные убывающие цепочки, начинающиеся в $\infty$ , но не содержит какой-либо бесконечной убывающей цепи.
↑ Birkhoff, 1967, с. 5.
↑ Stanley, 1997, с. 99.

Литература

Garrett Birkhoff. Lattice Theory. — Am. Math. Soc.. — Colloquium Publications, 1967. — Т. 25.
Richard Stanley. Quotients of Peck posets // Order. — 1984. — Т. 1, вып. 1. — С. 29–34. — doi:10.1007/BF00396271.
Lynne M. Butler. Subgroup Lattices and Symmetric Functions. — American Mathematical Society, 1994. — Т. 539. — С. 151. — (Memoirs of the American Mathematical Society). — ISBN 9780821826003.
Richard Stanley. Enumerative Combinatorics, т.1. — Cambridge University Press, 1997. — Т. 49. — (Cambridge Studies in Advanced Mathematics). — ISBN 0-521-66351-2.
Ian Anderson. Combinatorics of Finite Sets. — Oxford, UK: Clarendon Press, 1987. — ISBN 0-19-853367-5.
Konrad Engel. Sperner Theory. — Cambridge, UK (et al.): Cambridge University Press, 1997. — ISBN 0-521-45206-6.
Joseph P. S. Kung, Gian-Carlo Rota, Catherine H. Yan. Combinatorics: The Rota Way. — Cambridge, UK (et al.): Cambridge University Press, 2009. — ISBN 978-0-521-73794-4.

[_57371779e764bf0c-1] Stanley, 1984, с. 29–34.

[_67e657d52d1a82d9-2] Butler, 1994, с. 151.

[3] Что означает, что в множестве есть минимальный и максимальный элементы

[4] То есть нет ситуации, когда не возникает ситуации, когда обе цепочки $x<z_{1}<y$ и $x<w_{1}<w_{2}<y$ являются максимальными.

[5] Отсутствие произвольно длинной убывающей цепи, начинающейся с данного элемента, конечно, исключает существование бесконечной убывающей цепи. Хотя, отсутствие цепи произвольной длины строже — множество $\mathbb {N} \cup \{\infty \}$ имеет бесконечно длинные убывающие цепочки, начинающиеся в $\infty$ , но не содержит какой-либо бесконечной убывающей цепи.

[_a3ca1ca9538285a2-6] Birkhoff, 1967, с. 5.

[_5145ccec7ba45149-7] Stanley, 1997, с. 99.

[1]

[2]

[3]

[4]

[5]

[6]

[7]