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

Градуированное частично упорядоченное множество (ЧУМ) — это частично упорядоченное множество 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] позволяет функции ранга иметь произвольные (а не только неотрицательные) целые значения. В этом варианте целые числа могут быть градуированы (с помощью тождественной функции) и совместимость функции ранга с порядком не является избыточным требованием.

Заметим, что градуированное ЧУМ не обязано удовлетворять условию возрастающей цепочки^[англ.]. Например, натуральные числа содержат бесконечную возрастающую цепочку [math]\displaystyle{ 0 \lt 1 \lt 2 \lt \cdots }[/math].

ЧУМ является градуированным тогда и только тогда, когда любая связная компонента его графа сравнимости является градуированной, так что дальнейшее описание предполагает, что этот граф сравнимости связен. На каждой связной компоненте функция ранга единственна с точностью до однородного сдвига (так что функцию ранга можно всегда выбрать так, что минимальный ранг связной компоненты имеет ранг 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.

Далее, в этом случае с уровнем ранга связываются ранговые числа, или числа Уитни [math]\displaystyle{ W_0,W_1,W_2,... }[/math]. Эти числа определяются как [math]\displaystyle{ W_i }[/math] = число элементов множества P, имеющих ранг i .

Числа Уитни связаны со множеством важных комбинаторных теорем. Классический пример — теорема Спернера^[англ.], которую можно сформулировать следующим способом:

Для степени [math]\displaystyle{ \mathcal P(S) }[/math] любого конечного множества [math]\displaystyle{ S }[/math] максимальная мощность семейства Спернера^[англ.] равна максимальному числу Уитни.

Это означает, что

Любая конечная степень множества имеет свойство Спернера^[англ.]

См. также

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

Примечания

↑ Stanley, 1984, с. 29–34.
↑ Butler, 1994, с. 151.
↑ Что означает, что в множестве есть минимальный и максимальный элементы
↑ Т.е. нет ситуации, когда не возникает ситуации, когда обе цепочки [math]\displaystyle{ x \lt z_1 \lt y }[/math] и [math]\displaystyle{ x \lt w_1 \lt w_2 \lt y }[/math] являются максимальными.
↑ Отсутствие произвольно длинной убывающей цепи, начинающейся с данного элемента, конечно, исключает существование бесконечной убывающей цепи. Хотя, отсутствие цепи произвольной длины строже — множество [math]\displaystyle{ \N\cup\{\infty\} }[/math] имеет бесконечно длинные убывающие цепочки, начинающиеся в [math]\displaystyle{ \infty }[/math], но не содержит какой-либо бесконечной убывающей цепи.
↑ 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] Т.е. нет ситуации, когда не возникает ситуации, когда обе цепочки [math]\displaystyle{ x \lt z_1 \lt y }[/math] и [math]\displaystyle{ x \lt w_1 \lt w_2 \lt y }[/math] являются максимальными.

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

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

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

[1]

[2]

[3]

[4]

[5]

[6]

[7]