Русская Википедия:Градуированное частично упорядоченное множество
Градуированное частично упорядоченное множество — частично упорядоченное множество P, снабжённое функцией ранга ρ из P в N, удовлетворяющей следующим двум свойствам:
- функция ранга совместима с упорядочиванием, в смысле, что для любых x и y с порядком x < y должно выполняться ρ(x) < ρ(y);
- функция ранга совместима с Шаблон:Не переведено 5 упорядочения, в смысле, что для любого x подчинённого y должно выполняться ρ(y) = ρ(x) + 1.
Значение функции ранга элемента частично упорядоченного множества называется рангом элемента.
Иногда градуированное частично упорядоченное множество называется ранжированным, но определение ранжированное может иметь несколько другое значение (Шаблон:Не переведено 5). Уровнем ранга градуированного частично упорядоченного множества называется подмножество всех элементов частично упорядоченного множества, имеющим заданное значение рангаШаблон:SfnШаблон:Sfn.
Градуированные частично упорядоченные множества играют важную роль в комбинаторике и могут быть представлены в виде диаграммы Хассе.
Примеры
Несколько примеров градуированных частично упорядоченных множеств (с функциями ранга):
- натуральные числа N с их естественным порядком (ранг — само число) или некоторый интервал [0,N] этого частично упорядоченного множества,
- Nn с Шаблон:Не переведено 5 или подмножество этого частично упорядоченного множества, являющееся произведением интервалов,
- положительные числа, упорядоченные по числу простых делителей с учётом кратности или подмножество этого частично упорядоченного множества, образованное делителями фиксированного числа N,
- булева решётка конечных подмножеств множества (ранг — число элементов в подмножестве),
- решётка разбиений множества на конечное число частей, упорядоченная обратно степени разбиения (ранговая функция — число частей),
- решётка разбиений конечного множества X, упорядоченная по степени разбиения (ранговая функция — число элементов X минус число частей разбиения),
- группа и порождающее множество, или, эквивалентно, её граф Кэли, порядок — слабый или сильный порядок Брюа, ранговая функция — длина слова (длина самого короткого приведённого слова).
- в частности, для групп Коксетера, например, перестановок вполне упорядоченного множества из n-элементов, со слабым или сильным порядком Брюа (ранговая функция — число смежных инверсий),
- Шаблон:Не переведено 5, такие как решётка подпространств векторного пространства (ранговая функция — размерность подпространства),
- дистрибутивная решётка конечного нижнего множества другого частично упорядоченного множества (ранговая функция — число элементов),
- Шаблон:Не переведено 5, частный случай предыдущего примера (ранговая функция — число ячеек в диаграмме Юнга),
- Шаблон:Не переведено 5 многомерных выпуклых многогранников (ранговая функция — размерность грани + 1),
- абстрактные многогранники (ранговая функция — «расстояние» от наименьшей грани — 1),
- Шаблон:Не переведено 5 (ранговая функция — число элементов симплекса).
Альтернативные описания
Ограниченное частично упорядоченное множество[1] допускает градуирование тогда и только тогда, когда все максимальные цепочки в P имеют одну длину[2] — если установить ранг наименьшего элемента равным 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.
В некоторых общих частично упорядоченных множествах, таких как Шаблон:Не переведено 5 выпуклых многограников, существует естественное градуирование (размерность), которое, будучи использованным в качестве функции ранга, даёт минимальный элемент, пустую грань с рангом −1. В таких случаях удобно «подправить» определение выше путём добавления значения −1 к множеству допустимых значений функции ранга. Если же позволить функции ранга принимать произвольные целые значения, получим совсем другое понятие. В этом случае, например, нельзя говорить о существовании минимального элемента.
Градуированное частично упорядоченное множество (с положительными значениями функции ранга) не может имеет какого-либо элемента x, до которого существуют цепочки произвольной длины с максимальным элементом x, в противном случае оно имело бы элементы произвольно малого (в том числе и отрицательного) ранга. Например, множество целых чисел (с естественным порядком) не может быть градуированным частично упорядоченным множеством. Не может быть градуированным частично упорядоченным множеством любой интервал (более чем с одним элементом), рациональных или вещественных чисел. (В частности, градуированные частично упорядоченные множества являются вполне фундированными, что означает, что они удовлетворяют Шаблон:Не переведено 5 — они не содержат какой-либо Шаблон:Не переведено 5[3]). С этого момента мы рассматриваем частично упорядоченные множества, в которых таких цепочек нет. Отсюда следует, что при x < y мы можем получить y из x за конечное число шагов, последовательно выбирая элемент, которому предыдущий элемент подчинён. Это также означает, что (для функций ранга, принимающих положительные целые значения) совместимость ρ с порядком следует из требования подчинённости. В качестве варианта определения градуированного частично упорядоченного множества БиркгофШаблон:Sfn позволяет функции ранга иметь произвольные (а не только неотрицательные) целые значения. В этом варианте целые числа могут быть градуированы (с помощью тождественной функции) и совместимость функции ранга с порядком не является избыточным требованием.
Градуированное частично упорядоченное множество не обязано удовлетворять условию Шаблон:Не переведено 5. Например, натуральные числа содержат бесконечную возрастающую цепочку <math>0 < 1 < 2 < \cdots</math>.
Частично упорядоченное множество является градуированным тогда и только тогда, когда любая связная компонента его графа сравнимости является градуированной, так что дальнейшее описание предполагает, что этот граф сравнимости связен. На каждой связной компоненте функция ранга единственна с точностью до однородного сдвига (так что функцию ранга можно всегда выбрать так, что минимальный ранг связной компоненты имеет ранг 0).
Если P имеет наименьший элемент Ô, при градуировании это эквивалентно условию, что для любого элемента x все максимальные цепи в интервале [Ô,x] имеют одну и ту же длину. Это условие необходимо, поскольку любой шаг в максимальной цепи является отношением подчинения, которое изменяет ранг на 1. Условие является также достаточным, поскольку в случае его выполнения можно использовать упомянутую длину для определения ранга x (длина конечной цепи равно числу «шагов», так что ранг на единицу меньше числа элементов цепи), и когда y подчинён x, добавление x к максимальной цепи [Ô,y] даёт максимальную цепь в [Ô,x].
Если P имеет также наибольший элемент Î (так что это ограниченное частично упорядоченное множество), тогда предыдущее условие может быть упрощено до требования, что все максимальные цепи в P имеют одну и ту же (конечную) длину. Это условие достаточно, поскольку любая пара максимальных цепей в [Ô,x] могут быть расширены максимальной цепью в [x,Î], что даёт пару максимальных цепей в P.
Шаблон:Не переведено 5 определяет частично упорядоченное множество градуированным с длиной n, если его максимальные цепи имеют длину nШаблон:Sfn. Это определение даётся в контексте, где, в основном, рассматриваются конечные частично упорядоченные множества, и, хотя в книге часто слова «длины n» опущены, для частично упорядоченного множества общего вида это определение не выглядит приемлемым, поскольку (1) оно ничего не говорит о частично упорядоченных множествах, имеющих бесконечные максимальные цепи, и (2) оно исключает такие важные частично упорядоченные множества, как Шаблон:Не переведено 5. Также неясно, почему в градуированном частично упорядоченном множестве все минимальные элементы, как и все максимальные элементы, должны иметь одну и ту же длину, хотя Стэнли даёт примеры, по которым ясно, что он не требует этого (там же, стр.216 и 219).
Обычный случай
Многие авторы в области комбинаторики определяют градуированное частично упорядоченное множество таким образом, что все минимальные элементы P должны иметь ранг 0, и более того, что существует максимальный ранг r, являющийся рангом любого максимального элемента. В этом случае градуирование означает, что все максимальные цепи имеют длину r, как сказано выше. В этом случае говорят, что P имеет ранг r.
Далее, в этом случае с уровнем ранга связываются ранговые числа, или числа Уитни <math>W_0,W_1,W_2,... </math>. Эти числа определяются как <math>W_i</math> = число элементов множества P, имеющих ранг i .
Числа Уитни связаны со множеством важных комбинаторных теорем. Классический пример — Шаблон:Не переведено 5, которую можно сформулировать следующим способом: для степени <math> \mathcal P(S) </math> любого конечного множества <math>S</math> максимальная мощность Шаблон:Не переведено 5 равна максимальному числу Уитни. Это означает, что любая конечная степень множества имеет Шаблон:Не переведено 5.
См. также
- Шаблон:Не переведено 5 — предупорядочение с нормой является аналогом градуированного частично упорядоченного множества, где отображение в целые числа заменяется на порядковые числа
- Шаблон:Не переведено 5 — метод комбинирования двух градуированных частично упорядоченных множеств
Примечания
Литература
- ↑ Что означает, что в множестве есть минимальный и максимальный элементы
- ↑ То есть нет ситуации, когда не возникает ситуации, когда обе цепочки <math>x < z_1 < y</math> и <math>x < w_1 < w_2 < y</math> являются максимальными.
- ↑ Отсутствие произвольно длинной убывающей цепи, начинающейся с данного элемента, конечно, исключает существование бесконечной убывающей цепи. Хотя, отсутствие цепи произвольной длины строже — множество <math>\N\cup\{\infty\}</math> имеет бесконечно длинные убывающие цепочки, начинающиеся в <math>\infty</math>, но не содержит какой-либо бесконечной убывающей цепи.
