Реттік жиынтар: Комбинаторикадағы реттелген жиындар

Кіріспе

Математикада, комбинаторика саласында, бағаланған ішінара реттелген жиынтық (посеттік) P – барлық натурал сандар жиынына ρ реңк функциясымен жабдықталған. ρ функциясы келесі екі қасиетті қанағаттандыруы керек:

Реңк функциясы реттелумен үйлесімді, яғни реттелген жиынтықтағы барлық x және y үшін, егер x < y болса, онда ρ(x) < ρ(y);
Реңк реттелудің жабу қатынасына сәйкес келеді, яғни барлық x және y үшін, егер y, x-ті жабатын болса, онда ρ(y) = ρ(x) + 1. Посеттің элементінің реңк функциясының мәні оның реңкі деп аталады. Кейде бағаланған посеттік реңктік посеттік деп те аталады, бірақ бұл сөздің басқа да мағыналары бар; қараңыз Реңктік посеттік. Бағаланған посеттің реңкі немесе реңк деңгейі – белгілі бір реңк мәніне ие посеттің барлық элементтерінің ішкі жиыны. Бағаланған посеттіктер комбинаторикада маңызды рөл атқарады және оларды Хассе диаграммасы арқылы бейнелеуге болады.

Басқа сипаттамалар

Шектелген позит егер және тек P-дегі барлық максималды тізбектердің ұзындығы бірдей болса, жіктелуге мүмкіндік береді: ең кіші элементтің рангін 0-ге теңеу, содан кейін ранг функциясын толық анықтайды. Бұл көптеген шекті жағдайларды қамтиды; теріс мысал үшін суретті қараңыз. Дегенмен, шексіз позиттер күрделірек болуы мүмкін. Ранг функциясының үміткері, ретке сәйкес келіп, егер және тек егер x < z болса, z-дің рангі n + 1 болса, x ≤ y < z рангі n болатын элемент y табылатын болса, позитті жіктелген позитке айналдырады. Бұл шарт жеткілікті, себебі егер z, x-тің жабуы болса, онда y = x деген жалғыз мүмкін таңдау болады, бұл x және z-дің рангілері 1-ге өзгеше екенін көрсетеді, ал ол қажет, себебі жіктелген позитте y үшін x ≤ y < z кез келген ең жоғары рангі элементті алуға болады, ол әрқашан бар және z-мен жабылады. Көбінесе позитке ранг функциясы үшін табиғи үміткер келеді; мысалы, егер оның элементтері қандай да бір негізгі жиынның шекті ішкі жиындары болса, онда сол ішкі жиынның элементтерінің санын алуға болады. Онда жоғарыда келтірілген критерий анықтамадан гөрі практикалық болуы мүмкін, себебі ол жабулар туралы айтуды болдырмайды. Мысалы, егер B өзі позит болса, ал P оның шекті төменгі жиынтықтарынан (оның элементтерінің әрқайсысымен бірге барлық кіші элементтер де ішкі жиынға кіреді) құралса, онда критерий автоматты түрде орындалады, себебі төменгі жиынтықтар үшін x ⊆ z әрқашан x-тен жоқ z-дің ең үлкен элементі болады, және оны z-ден алып тастап, y-ді жасауға болады. Кейбір жалпы позиттерде, мысалы, дөңес политоптың беттік торында өлшем бойынша табиғи жіктелу бар, егер оны ранг функциясы ретінде қолданса, ең кіші элемент, бос бет, -1 рангін береді. Мұндай жағдайларда жоғарыда көрсетілген анықтаманы -1 мәнін ранг функциясы үшін рұқсат етілген мәндер жиынтығына қосу арқылы өзгерту ыңғайлы болуы мүмкін. Дегенмен, кездейсоқ бүтін сандарға ранг ретінде рұқсат беру түбегейлі басқа ұғымды береді; мысалы, ең кіші элементтің болуы енді кепілдендірілмейді. Жіктелген позит (оң бүтін сан рангімен) кез келген элемент x үшін, олар үшін кез келген ұзындықтағы тізбектер болуы мүмкін емес, әйтпесе ол кез келген кішкентай (және ақырында теріс) рангі элементтерге ие болуы керек. Мысалы, бүтін сандар (әдеттегі ретпен) жіктелген позит бола алмайды, сондай-ақ кез келген интервал (бір элементтен көп) рационалды немесе нақты сандар бола алмайды. (Атап айтқанда, жіктелген позиттер жақсы негізделген, яғни олар төмендеу тізбегі шартын (DCC) қанағаттандырады: олар шексіз төмендеу тізбектерін қамтымайды.) Сондықтан, бұдан былай біз тек осылай болмаған позиттерді ғана қарастырамыз. Бұл дегеніміз, x < y кез келген кезде біз x-тен y-ге бірнеше рет жабуды таңдап, шекті санда жете аламыз. Бұл сонымен қатар (оң бүтін сан ранг функциялары үшін) ρ-нің ретке сәйкестігі жабулар туралы талаптан туындайды дегенді білдіреді. Жіктелген позиттің анықтамасының нұсқасы ретінде Бирхофф ранг функцияларының кездейсоқ (тек теріс емес) бүтін сандық мәндеріне ие болуына мүмкіндік береді. Бұл нұсқада бүтін сандар оның орнына (бірлік функциясы бойынша) жіктелуі мүмкін, ал рангтардың ретке келтірумен үйлесімділігі артық емес. Үшінші нұсқа ретінде Брайтуэлл мен Уэст ранг функциясын бүтін санға бағалайтын етіп анықтайды, бірақ оның ретке келтірумен үйлесімділігін талап етпейді; сондықтан бұл нұсқа кез келген функция бойынша, мысалы, нақты сандарды да бағалай алады, өйткені жабулар туралы талап бұл мысал үшін бос. Жіктелген позиттердің жоғарылайтын тізбек шартын (ACC) қанағаттандыруы міндетті емес екенін ескеріңіз: мысалы, табиғи сандар шексіз жоғарылайтын тізбекті қамтиды. Позиттің салыстырмалылық графигінің әрбір байланысқан компоненті жіктелген болса және тек қана болса, онда позит жіктеледі, сондықтан одан әрі сипаттаулар осы салыстырмалылық графигінің байланысқа ие екенін болжайды. Әр байланысқан компоненттегі ранг функциясы біркелкі ауысуға дейін ғана бірегей болады (осылайша ранг функциясын әрқашан таңдауға болады, сондықтан олардың байланысқан компонентіндегі ең төменгі рангі элементтері 0-ге ие болады). Егер P-де ең кіші элемент Ô болса, онда жіктелу кез келген элемент x үшін интервалдағы барлық максималды тізбектердің ұзындығы бірдей [Ô, x] деген шартқа тең. Бұл шарт қажет, себебі ең үлкен тізбектегі әрбір қадам - бұл жабу қатынасы, ...

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.

Note Stanley defines a poset to be graded of length n if all its maximal chains have length n (Stanley 1997, p.99). This definition is given in a context where interest is mostly in finite posets, and although the book subsequently often drops the part "of length n", it does not seem appropriate to use this as definition of "graded" for general posets, because (1) it says nothing about posets whose maximal chains are infinite, in particular (2) it excludes important posets like Young's lattice. Also it is not clear why in a graded poset all minimal elements, as well as all maximal elements, should be required to have the same length, even if Stanley gives examples making clear that he does mean to require that (ibid, pp.216 and 219).