Градуированный посет

В математике , в разделе комбинаторики , градуированное ЧУ-множество — это частично упорядоченное множество (ЧУ-множество) P, снабженное ранговой функцией ρ от P до множества N всех натуральных чисел . ρ должен удовлетворять следующим двум свойствам:

Функция ранга совместима с упорядочиванием, что означает, что для всех x и y в порядке, если x < y , то ρ ( x ) < ρ ( y ), и
Ранг соответствует соотношению покрытия порядка, что означает, что для всех x и y , если y покрывает x , то ρ ( y ) = ρ ( x ) + 1.

Значение функции ранга для элемента ЧУУ называется его рангом . Иногда градуированный частично упорядоченный набор называют ранжированным частично упорядоченным набором, но эта фраза имеет и другие значения; см . Ранговый посет . Ранг или . уровень ранга градуированного ЧУУ — это подмножество всех элементов ЧУУ, имеющих заданное значение ранга ^[1]^[2]

Градуированные ЧУМы играют важную роль в комбинаторике и могут быть визуализированы с помощью диаграммы Хассе .

Примеры [ править ]

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

Натуральные числа N их обычного порядка (ранг: само число) или некоторого интервала [0, N ] этого частично упорядоченного множества.
Н ^н с порядком продукта (суммой компонентов) или его подмножеством, которое является произведением интервалов
Положительные целые числа, упорядоченные по делимости (количество простых множителей, учитываемых с кратностью) или их подмножество, образованное делителями фиксированного N.
Булева решетка конечных подмножеств множества, упорядоченного по включению (количество элементов подмножества)
Любая дистрибутивная решетка конечных нижних множеств другого частичного множества (количества элементов)
- В частности, любая конечная дистрибутивная решетка
Посет всех немаркированных посетов на $\{1,...,n\}$ (количество элементов) ^[3]
Решетка Юнга (количество ячеек на диаграмме Юнга)
Любая геометрическая решетка , например решетка подпространств векторного пространства ( размерность подпространства)
Решетка разбиений множества на конечное число частей, упорядоченная обратным уточнением (количество частей)
Решетка разбиений конечного множества X , упорядоченная путем уточнения (количество элементов X минус количество частей)
Решетка граней ( выпуклых многогранников размерность грани плюс один)
Абстрактный многогранник («расстояние» от наименьшей грани минус один)
Абстрактный симплициальный комплекс (количество элементов симплекса)
Группа . с порождающим набором или, что эквивалентно, ее графом Кэли , упорядоченным по слабому или сильному порядку Брюа и ранжированным по длине слова (длине кратчайшего сокращенного слова)
- В частности , группа Кокстера , например, перестановки полностью упорядоченного набора из n элементов со слабым или сильным порядком Брюа (количество соседних инверсий).

Альтернативные характеристики [ править ]

Ограниченное частичное множество ^[4] допускает градуировку тогда и только тогда, когда все максимальные цепи в P имеют одинаковую длину: ^[5] установка ранга наименьшего элемента равным 0 полностью определяет функцию ранга. Это охватывает множество конечных случаев, представляющих интерес; см. рисунок для отрицательного примера. Однако неограниченные ЧУУ могут быть более сложными.

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

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

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

Градуированное ЧУМ (с целочисленными положительными рангами) не может иметь элементов x, для которых существуют сколь угодно длинные цепочки с наибольшим элементом x , поскольку в противном случае оно должно было бы иметь элементы сколь угодно малого (и, в конечном итоге, отрицательного) ранга. Например, целые числа (обычного порядка) не могут быть градуированным ЧУМ, равно как и любой интервал (с более чем одним элементом) рациональных или действительных чисел . (В частности, градуированные ЧУМ являются хорошо обоснованными , что означает, что они удовлетворяют условию нисходящей цепи (DCC): они не содержат никаких бесконечных нисходящих цепей . ^[6]) Поэтому в дальнейшем мы будем рассматривать только ч.у.у., в которых этого не происходит. Это означает, что всякий раз, когда x < y, мы можем перейти от x к y, многократно выбирая покрытие конечное число раз. Это также означает, что (для функций положительного целого ранга) совместимость ρ с порядком следует из требования о покрытиях. Как вариант определения градуированного ЧУМ, Биркгоф ^[7] позволяет функциям ранга иметь произвольные (а не только неотрицательные) целочисленные значения. В этом варианте целые числа можно градуировать (по функции тождественности) в его настройке, и совместимость рангов с порядком не является лишней. В качестве третьего варианта Брайтвелл и Уэст ^[8] определить функцию ранга как целочисленную, но не требовать ее совместимости с упорядочиванием; следовательно, этот вариант может классифицировать даже, например, действительные числа по любой функции, поскольку требование о покрытиях бессмысленно для этого примера .

Обратите внимание, что градуированные ЧУУ не обязательно должны удовлетворять условию возрастающей цепочки (ACC): например, натуральные числа содержат бесконечную возрастающую цепочку. $0<1<2<\dots$ .

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

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

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

Примечание. Стэнли определяет ЧУМ как градуированное длиной n, если все его максимальные цепи имеют длину n (Stanley 1997, стр. 99). Это определение дано в контексте, где интерес в основном вызывают конечные ЧУ, и хотя в книге впоследствии часто опускается часть «длины 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$ максимальная мощность семейства Спернера равна максимальному числу Уитни .

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

Каждое конечное степенное множество обладает свойством Спернера.

См. также [ править ]

Оценка (математика)
Предварительное упорядочение - предварительное упорядочение с нормой аналогично градуированному частичному набору, заменяющему карту целых чисел на карту порядковых чисел.
Звездное произведение — метод объединения двух градуированных частично упорядоченных множеств.

Примечания [ править ]

^ Стэнли, Ричард (1984), «Частные множества Пека», Порядок , 1 (1): 29–34, doi : 10.1007/BF00396271 , MR 0745587 , S2CID 14857863 .
^ Батлер, Линн М. (1994), Решетки подгрупп и симметричные функции , Мемуары Американского математического общества, том. 539, Американское математическое общество, с. 151, ISBN 9780821826003 .
^ Калберсон, Джозеф К.; Роулинз, Грегори Дж. Э. (1990), «Новые результаты алгоритма подсчета частично упорядоченных наборов» , Order , 7 (4): 361–374, doi : 10.1007/BF00383201 , S2CID 120473635
^ Это означает, что у него есть наименьший и наибольший элемент .
^ Т.е. не бывает такой ситуации, как $x<z_{1}<y$ и $x<w_{1}<w_{2}<y$ обе являются максимальными цепями.
^ Отсутствие нисходящих цепочек произвольной длины, начинающихся с фиксированного элемента, конечно, исключает любые бесконечные нисходящие цепочки. Однако первое условие строго сильнее; набор $\mathbb {N} \cup \{\infty \}$ имеет сколь угодно длинные цепи, спускающиеся от $\infty$ , но не имеет бесконечных нисходящих цепей.
^ «Теория решетки», Am. Математика. Soc., Публикации коллоквиума, том 25, 1967, стр.5.
^ См. ссылку [2], стр.722.

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

Стэнли, Ричард (1997). Перечислительная комбинаторика (том 1, Кембриджские исследования по высшей математике 49) . Издательство Кембриджского университета . ISBN 0-521-66351-2 .
Андерсон, Ян (1987). Комбинаторика конечных множеств . Оксфорд, Великобритания: Clarendon Press . ISBN 0-19-853367-5 .
Энгель, Конрад (1997). Теория Шпернера . Кембридж, Великобритания (и др.): Издательство Кембриджского университета. ISBN 0-521-45206-6 .
Кунг, Джозеф PS; Рота, Джан-Карло ; Ян, Кэтрин Х. (2009). Комбинаторика: Путь Роты . Кембридж, Великобритания (и др.): Издательство Кембриджского университета. ISBN 978-0-521-73794-4 .

[stanley-1] Стэнли, Ричард (1984), «Частные множества Пека», Порядок , 1 (1): 29–34, doi : 10.1007/BF00396271 , MR 0745587 , S2CID 14857863 .

[2] Батлер, Линн М. (1994), Решетки подгрупп и симметричные функции , Мемуары Американского математического общества, том. 539, Американское математическое общество, с. 151, ISBN 9780821826003 .

[culberson-3] Калберсон, Джозеф К.; Роулинз, Грегори Дж. Э. (1990), «Новые результаты алгоритма подсчета частично упорядоченных наборов» , Order , 7 (4): 361–374, doi : 10.1007/BF00383201 , S2CID 120473635

[4] Это означает, что у него есть наименьший и наибольший элемент .

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

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

[7] «Теория решетки», Am. Математика. Soc., Публикации коллоквиума, том 25, 1967, стр.5.

[8] См. ссылку [2], стр.722.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice