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

Введение

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

Функция ранга совместима с упорядочением, то есть для любых x и y из P, если x < y, то ρ(x) < ρ(y), и
Ранг согласуется с отношением покрытия в упорядочении, то есть для любых x и y, если y покрывает x, то ρ(y) = ρ(x) + 1. Значение функции ранга для элемента посе́та называется его рангом. Иногда градуированное посе́т называют ранжированным посе́том, но эта фраза имеет и другие значения; см. Ранжированное посе́т. Ранг или ранговый уровень градуированного посе́та — это подмножество всех элементов посе́та, имеющих заданное значение ранга. Градуированные посе́ты играют важную роль в комбинаторике и могут быть визуализированы с помощью диаграммы Хассе.

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

Ограниченный частично упорядоченный набор (посет) допускает градуировку, если и только если все максимальные цепи в P имеют одинаковую длину: установление ранга наименьшего элемента равным 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): они не содержат бесконечных убывающих цепей.) В дальнейшем мы будем рассматривать только посеты, в которых этого не происходит. Это подразумевает, что для любых x < y можно перейти от x к y, последовательно выбирая покрытие, конечное число раз. Это также означает, что (для ранговых функций, принимающих положительные целые значения) совместимость ρ с порядком следует из требования относительно покрытий. В качестве варианта определения градуированного посета, Биркофф допускает, чтобы ранговые функции принимали произвольные (а не только неотрицательные) целые значения. В этом варианте целые числа могут быть градуированы (тождественной функцией) в его рамках, и совместимость рангов с порядком не является избыточной. В качестве третьего варианта, Брайтвелл и Уэст определяют ранговую функцию как принимающую целые значения, но не требуют ее совместимости с порядком; следовательно, этот вариант может градуировать даже, например, вещественные числа любой функцией, поскольку требование относительно покрытий становится несущественным для этого примера. Следует отметить, что градуированные посеты не обязаны удовлетворять условию восходящей цепи (ACC): например, натуральные числа содержат бесконечную восходящую цепь. Посет градуирован, если и только если каждая связная компонента его графа сопоставимости градуирована, поэтому дальнейшие характеризации будут предполагать, что этот граф сопоставимости связен. На каждой связной компоненте ранговая функция уникальна только с точностью до равномерного сдвига (так что ранговую функцию всегда можно выбрать так, чтобы элементы минимального ранга в их связной компоненте имели ранг 0). Если P имеет наименьший элемент Ô, то градуированность эквивалентна условию, что для любого элемента x все максимальные цепи в интервале [Ô, x] имеют одинаковую длину. Это условие необходимо, поскольку каждый шаг в максимальной цепи является отношением покрытия, которое должно изменять ранг на 1. Оно также достаточно, поскольку при его выполнении можно использовать указанную длину для определения ранга x (длина конечной цепи – это ее число "шагов", то есть на единицу меньше числа ее элементов), и всякий раз, когда x покрывает y, добавление x к максимальной цепи в [Ô, y] дает максимальную цепь в [Ô, x]. Если P также имеет наибольший элемент Î (так что это ограниченный посет), то предыдущее условие можно упростить до требования, что все максимальные цепи в P имеют одинаковую (конечную) длину. Этого достаточно, поскольку любую пару максимальных цепей в [Ô, x] можно расширить максимальной цепью в [x, Î], чтобы получить пару максимальных цепей в P.

A bounded poset admits a grading if and only if all maximal chains in P have the same length: setting the rank of the least element to 0 then determines the rank function completely. This covers many finite cases of interest; see picture for a negative example. However, unbounded posets can be more complicated. A candidate rank function, compatible with the ordering, makes a poset into graded poset if and only if, whenever one has x < z with z of rank n + 1, an element y of rank n can be found with x ≤ y < z. This condition is sufficient because if z is taken to be a cover of x, the only possible choice is y = x showing that the ranks of x and z differ by 1, and it is necessary because in a graded poset one can take for y any element of maximal rank with x ≤ y < z, which always exists and is covered by z. Often a poset comes with a natural candidate for a rank function; for instance if its elements are finite subsets of some base set B, one can take the number of elements of those subsets. Then the criterion just given can be more practical than the definition because it avoids mention of covers. For instance if B is itself a poset, and P consists of its finite lower sets (subsets for which with every one of its elements, all smaller elements are also in the subset), then the criterion is automatically satisfied, since for lower sets x ⊆ z there is always a maximal element of z that is absent from x, and it can be removed from z to form y. In some common posets such as the face lattice of a convex polytope there is a natural grading by dimension, which if used as rank function would give the minimal element, the empty face, rank −1. In such cases it might be convenient to bend the definition stated above by adjoining the value −1 to the set of values allowed for the rank function. Allowing arbitrary integers as rank would however give a fundamentally different notion; for instance the existence of a minimal element would no longer be assured. A graded poset (with positive integer ranks) cannot have any elements x for which arbitrarily long chains with greatest element x exist, as otherwise it would have to have elements of arbitrarily small (and eventually negative) rank. For instance, the integers (with the usual order) cannot be a graded poset, nor can any interval (with more than one element) of rational or real numbers. (In particular, graded posets are well founded, meaning that they satisfy the descending chain condition (DCC): they do not contain any infinite descending chains.) Henceforth we shall therefore only consider posets in which this does not happen. This implies that whenever x < y we can get from x to y by repeatedly choosing a cover, finitely many times. It also means that (for positive integer rank functions) compatibility of ρ with the ordering follows from the requirement about covers. As a variant of the definition of a graded poset, Birkhoff allows rank functions to have arbitrary (rather than only nonnegative) integer values. In this variant, the integers can be graded (by the identity function) in his setting, and the compatibility of ranks with the ordering is not redundant. As a third variant, Brightwell and West define a rank function to be integer valued, but don't require its compatibility with the ordering; hence this variant can grade even e. g. the real numbers by any function, as the requirement about covers is vacuous for this example. Note that graded posets need not satisfy the ascending chain condition (ACC): for instance, the natural numbers contain the infinite ascending chain
A poset is graded if and only if every connected component of its comparability graph is graded, so further characterizations will suppose this comparability graph to be connected. On each connected component the rank function is only unique up to a uniform shift (so the rank function can always be chosen so that the elements of minimal rank in their connected component have rank 0). If P has a least element Ô then being graded is equivalent to the condition that for any element x all maximal chains in the interval [Ô, x] have the same length. This condition is necessary since every step in a maximal chain is a covering relation, which should change the rank by 1. The condition is also sufficient, since when it holds, one can use the mentioned length to define the rank of x (the length of a finite chain is its number of "steps", so one less than its number of elements), and whenever x covers y, adjoining x to a maximal chain in [Ô, y] gives a maximal chain in [Ô, x]. If P also has a greatest element Î (so that it is a bounded poset), then the previous condition can be simplified to the requirement that all maximal chains in P have the same (finite) length. This suffices, since any pair of maximal chains in [Ô, x] can be extended by a maximal chain in [x, Î] to give a pair of maximal chains in P.

Следует отметить, что Стенли определяет посет как градуированный длины n, если все его максимальные цепи имеют длину n (Stanley 1997, p.99). Это определение дано в контексте, где интерес в основном сосредоточен на конечных посетах, и хотя книга впоследствии часто опускает часть "длины n", не представляется уместным использовать это в качестве определения "градуированного" для общих посетов, поскольку (1) это ничего не говорит о посетах, максимальные цепи которых бесконечны, в частности (2) исключает важные посеты, такие как решетка Янга. Также неясно, почему в градуированном посете требуется, чтобы все минимальные элементы, а также все максимальные элементы имели одинаковую длину, даже если Стенли приводит примеры, показывающие, что он действительно имеет это в виду (ibid, pp.216 и 219).