Stupňovaný poset

Graded poset ( POS ) je poset P vybavený funkcí pořadí ρ od P do N , která splňuje následující dvě vlastnosti:

Funkce pořadí je kompatibilní s uspořádáním v tom smyslu, že pro libovolné x a y s řádem x < y , ρ( x ) < ρ( y )
Funkce pořadí je kompatibilní s relací podřízenosti uspořádání v tom smyslu, že pro jakékoli x podřízené y musí platit ρ( y ) = ρ( x ) + 1.

Hodnota funkce hodnosti prvku PLAT se nazývá hodnost prvku. Někdy se klasifikovaná PLAT nazývá ranged , ale definice ranged může mít trochu jiný význam, viz článek " Ranked poset ". Úroveň hodnosti odstupňované částečně uspořádané sady je podmnožinou všech prvků POTS, která má danou hodnotu hodnosti [1] [2] .

Stupňované posety hrají důležitou roli v kombinatorice a mohou být reprezentovány jako Hasseův diagram .

Příklady

Několik příkladů klasifikovaných PLAT (s funkcemi hodnocení):

přirozená čísla N s jejich přirozeným pořadím (hodnost je samotné číslo) nebo nějaký interval [0, N ] této PLAT,
N n s řádem přímé redukce nebo podmnožinou této množiny, která je součinem intervalů,
kladná čísla uspořádaná podle počtu prvočíselných dělitelů, přičemž se bere v úvahu násobnost, nebo podmnožina tohoto posetu tvořená děliteli pevného čísla N ,
Booleovská mřížka konečných podmnožin množiny (rank je počet prvků v podmnožině),
mřížka dělení množiny na konečný počet částí, uspořádaná nepřímo podle stupně dělení (funkce pořadí je počet částí),
mřížka oddílů konečné množiny X , uspořádaná podle stupně rozdělení (funkce pořadí je počet prvků X mínus počet částí oddílu),
skupina a generující množina , nebo ekvivalentně její Cayleyův graf , řád - slabé nebo silné Bruchatovo pořadí , funkce pořadí - délka slova (délka nejkratšího redukovaného slova).
- konkrétně pro Coxeterovy skupiny , například permutace dobře uspořádané množiny n - prvků, se slabým nebo silným Bruchatovým řádem (funkce pořadí je počet sousedních inverzí),
geometrické svazy , jako je mřížka podprostorů vektorového prostoru (funkce pořadí je dimenze podprostoru),
distributivní mřížka konečné nižší množiny jiného posetu (funkce pořadí je počet prvků),
Youngova mřížka , speciální případ předchozího příkladu (funkce pořadí je počet buněk v Youngově diagramu),
lícové mřížky vícerozměrných konvexních mnohostěnů (funkce pořadí - rozměr plochy + 1),
abstraktní mnohostěny (funkce pořadí - "vzdálenost" od nejmenší plochy - 1),
abstraktní simpliciální komplexy (funkce pořadí je počet prvků simplexu).

Alternativní popisy

Ohraničený poset [3] umožňuje gradování tehdy a jen tehdy, když všechny maximální řetězce v P mají stejnou délku [4] — pokud nastavíte rank nejmenšího prvku na 0, pak je rank zcela určen. To pokrývá mnoho koncových případů. Viz obrázek pro příklad, který neumožňuje promoci. Neomezené PLAT však mohou být podstatně obtížnější.

Funkce kandidáta na pořadí kompatibilní s řazením dělá POTS odstupňovaný právě tehdy, když pro x < z , kde z má pořadí n + 1, musí platit x ≤ y < z pro všechny prvky y stupně n . Tato podmínka je dostatečná, protože v případě, kdy je x podřízeno z , jedinou možností je y = x , a podmínka je nutná, protože v odstupňovaném PLZ lze za y vzít jakýkoli prvek maximálního pořadí s x ≤ y < z , které vždy existuje a je podřízené z .

Často získáme PLZ s přirozeným kandidátem na funkci hodnosti. Pokud jsou například její prvky podmnožinami nějaké základní množiny B , lze vzít počet prvků těchto podmnožin. Pak může být výše uvedené kritérium praktičtější než definice, protože nezmiňuje podřízenost. Pokud je například B samo o sobě množinou a P sestává z konečných nižších množin (podmnožin, pro které pro jakýkoli prvek podmnožiny všechny menší prvky patří do stejné množiny), pak je tato podmínka automaticky splněna, protože pro nižší množiny x ⊂ z vždy existuje maximum prvku z , který není v x a lze jej odstranit z z a získat y .

V některých obecných PLZ, jako jsou čelní mřížky mnohostěnů , existuje přirozené třídění ( rozměr ), které při použití jako funkce pořadí poskytuje minimální prvek, prázdnou plochu, s úrovní -1. V takových případech je vhodné výše uvedenou definici „opravit“ přidáním hodnoty -1 k množině platných hodnot funkce pořadí. Pokud dovolíme funkci rank nabývat libovolné celočíselné hodnoty, dostaneme úplně jiný koncept. V tomto případě se například nedá mluvit o existenci minimálního prvku.

Stupňovaný PLZ (s kladnými hodnotami funkce pořadí) nemůže mít žádný prvek x , do kterého jsou řetězce libovolné délky s maximálním prvkem x , jinak by měl prvky libovolně malého (včetně záporného) pořadí. Například množinu celých čísel (s přirozeným pořadím) nelze ohodnotit PLAT. Žádný interval (s více než jedním prvkem), racionální nebo reálná čísla nelze stupňovat . (Zejména klasifikované posety jsou dobře podložené , což znamená, že splňují podmínku sestupného řetězce - neobsahují žádný nekonečný sestupný řetězec [5] ). Od nynějška považujeme mory, ve kterých žádné takové řetězce nejsou. Z toho vyplývá, že pro x < y můžeme získat y z x v konečném počtu kroků postupným výběrem prvku, kterému je předchozí prvek podřízen. To také znamená, že (pro hodnostní funkce nabývající kladných celočíselných hodnot) kompatibilita ρ s pořadím vyplývá z požadavku podřazenosti. Jako varianta definice odstupňovaného PLB Birkhoff [6] umožňuje, aby funkce pořadí měla libovolné (nejen nezáporné) celočíselné hodnoty. V této variantě lze třídit celá čísla (pomocí funkce identity) a kompatibilita funkce pořadí s pořadím není nadbytečným požadavkem.

Všimněte si, že klasifikovaný PLZ nemusí splňovat podmínku vzestupného řetězce . Například přirozená čísla obsahují nekonečný vzestupný řetězec . $0<1<2<\cdots$

PLB je klasifikováno tehdy a pouze tehdy, když je klasifikována jakákoli připojená součást jeho grafu srovnatelnosti , takže následující popis předpokládá, že tento graf srovnatelnosti je propojený. Na každé připojené komponentě je funkce pořadí jedinečná až do rovnoměrného posunu (takže funkci pořadí lze vždy zvolit tak, aby minimální úroveň připojeného prvku měla úroveň 0).

Má -li P nejmenší prvek Ô, je to ve třídění ekvivalentní podmínce, že pro libovolný prvek x mají všechny maximální řetězce v intervalu [Ô, x ] stejnou délku. Tato podmínka je nezbytná, protože jakýkoli krok v maximálním řetězci je podřízenost, která mění pořadí o 1. Podmínka je dostatečná i proto, že pokud je splněna, lze z uvedené délky určit pořadí x (délka konečné řetězec se rovná počtu "kroků", takže pořadí je o jeden menší než počet prvků řetězce), a když je y podřízené x , přidání x k maximálnímu řetězci [p, y ] dává maximální řetězec v [p , x ].

Pokud má P také největší prvek V (tedy jde o ohraničené PLB ), pak lze předchozí podmínku zjednodušit na požadavek, aby všechny maximální řetězce v P měly stejnou (konečnou) délku. Tato podmínka je dostačující, protože libovolný pár maximálních řetězců v [Ô, x ] může být rozšířen o maximální řetězec v [ x , V], což dává pár maximálních řetězců v P .

Poznámka Richard Stanley definuje PLAT jako odstupňovanou délkou n , pokud její maximální řetězce mají délku n [7] . Tato definice je uvedena v kontextu, kde se zaměřuje především na konečné PSM, a zatímco slova „délka n “ jsou v knize často vynechána, pro obecné PSM se tato definice nezdá být vhodná, protože (1) neříká nic o tom, že PSM mají nekonečné maximální řetězce a (2) vylučuje důležité PLAT, jako jsou Youngovy mřížky . Není také jasné, proč v odstupňovaném PLN musí mít všechny minimální prvky, stejně jako všechny maximální prvky, stejnou délku, ačkoli Stanley uvádí příklady, ze kterých je zřejmé, že to nevyžaduje (tamtéž, s. 216 a 219).

Běžný případ

Mnoho autorů v oblasti kombinatoriky definuje odstupňované PLZ tak, že všechny minimální prvky P musí mít hodnost 0 a navíc, že existuje maximální hodnost r , která je hodností jakéhokoli maximálního prvku. V tomto případě klasifikace znamená, že všechny maximální řetězce mají délku r , jak je uvedeno výše. V tomto případě se říká, že P má hodnost r .

Dále jsou v tomto případě čísla hodnosti nebo Whitneyova čísla spojena s úrovní hodnosti . Tato čísla jsou definována jako = počet prvků množiny P , které mají hodnost i . $W_{0},W_{1},W_{2},...$ $W_i$

Whitneyova čísla jsou příbuzná mnoha důležitým kombinatorickým teorémům . Klasickým příkladem je Spernerova věta , kterou lze vyjádřit následujícím způsobem:

Pro stupeň jakékoli konečné množiny je maximální mohutnost Spernerovy rodiny rovna maximálnímu Whitneyovu číslu .

{\mathcal {P}}(S)

S

Znamená to, že

Jakýkoli konečný stupeň množiny má vlastnost Sperner

Viz také

Předobjednávka - předobjednávka s normou je obdobou odstupňovaného PLZ, kde je mapování na celá čísla nahrazeno pořadovými čísly
Hvězdný produkt , metoda pro spojení dvou odstupňovaných platitudů

Poznámky

↑ Stanley, 1984 , str. 29–34.
↑ Butler, 1994 , str. 151.
↑ Což znamená, že sada má minimální a maximální prvek
↑ tj. neexistuje situace, kdy neexistuje situace, kdy jsou oba řetězce a maximální. $x<z_{1}<y$ $x<w_{1}<w_{2}<y$
↑ Absence libovolně dlouhého sestupného řetězce vycházejícího z daného prvku samozřejmě vylučuje existenci nekonečného sestupného řetězce. I když, absence řetězce libovolné délky je přísnější - sada má nekonečně dlouhé sestupné řetězce začínající na , ale neobsahuje žádný nekonečný sestupný řetězec. ${\displaystyle \mathbb {N} \cup \{\infty \))$ $\infty$
↑ Birkhoff, 1967 , s. 5.
↑ Stanley, 1997 , str. 99.

Literatura

Garrett Birkhoff. Teorie mřížky. — Am. Matematika. Soc.. - Colloquium Publications, 1967. - V. 25.
Richard Stanley. Podíl pozic Peck // Objednávka . - 1984. - T. 1 , vydání. 1 . — S. 29–34 . - doi : 10.1007/BF00396271 .
Lynne M. Butlerová. Podskupina Svazy a symetrické funkce . - American Mathematical Society, 1994. - V. 539. - S. 151. - (Memoirs of the American Mathematical Society). — ISBN 9780821826003 .
Richard Stanley. Enumerativní kombinatorika, v.1. - Cambridge University Press , 1997. - V. 49. - (Cambridge Studies in Advanced Mathematics). - ISBN 0-521-66351-2 .
Ian Anderson. Kombinatorika konečných množin . - Oxford, UK: Clarendon Press , 1987. - ISBN 0-19-853367-5 .
Konrád Engel. Spernerova teorie. - Cambridge, UK (et al.): Cambridge University Press, 1997. - ISBN 0-521-45206-6 .
Joseph PS Kung, Gian-Carlo Rota, Catherine H. Yan. Kombinatorika: Cesta Rota. - Cambridge, UK (et al.): Cambridge University Press, 2009. - ISBN 978-0-521-73794-4 .