Rozměr objednávky - Order dimension

Částečné pořadí dimenze 4 (zobrazené jako Hasseův diagram ) a čtyři celková uspořádání, která tvoří realizátor tohoto částečného pořadí.

V matematice je rozměr z uspořádaná množina (uspořádané množiny) je nejmenší počet celkových zakázek průnik z nich vede k částečnému pořadí. Tento koncept se také někdy nazývá dimenze objednávky nebo dimenze Dushnik-Miller částečné objednávky. Dushnik & Miller (1941) nejprve studoval dimenzi řádu; pro podrobnější léčbu tohoto subjektu, než je zde uvedeno, viz Trotter (1992) .

Formální definice

Rozměr posety P je nejmenší celé číslo t, pro které existuje rodina

${\ displaystyle {\ mathcal {R}} = (<_ {1}, \ tečky, <_ {t})}$

z lineárních rozšíření o P tak, že na každé x a y v P , x předchází y v P , když a jen tehdy, pokud předchází y ve všech lineárních rozšíření. To znamená,

${\ displaystyle P = \ bigcap {\ mathcal {R}} = \ bigcap _ {i = 1} ^ {t} <_ {i}.}$

Alternativní definicí dimenze objednávky je minimální počet celkových objednávek , takže P vloží do svého produktu s komponentním objednáváním, tj. Právě tehdy, když pro všechna i ( Hiraguti 1955 , Milner & Pouzet 1990 ). ${\ displaystyle x \ leq y}$${\ displaystyle x_ {i} \ leq y_ {i}}$

Realizátoři

Rodina lineárních objednávek na X se nazývá realizátor poset P = ( X , < _P ), pokud ${\ displaystyle {\ mathcal {R}} = (<_ {1}, \ tečky, <_ {t})}$

${\ displaystyle <_ {P} = \ bigcap {\ mathcal {R}}}$,

což znamená, že pro libovolná x a y v X , x < _P y přesně, když x < ₁ y , x < ₂ y , ..., a x < _t y . Ekvivalentní definice dimenze posety P je tedy „nejmenší mohutností realizátora P “.

Je možné ukázat, že jakákoli neprázdná rodina R lineárních rozšíření je realizátorem konečné částečně uspořádané množiny P právě tehdy, když pro každou kritickou dvojici ( x , y ) P , y < _i x pro nějaký řád < _i v R .

Příklad

Nechť n je kladné celé číslo a nechť P je částečné pořadí na prvcích a _i a b _i (pro 1 ≤ i ≤ n ), ve kterém a _i ≤ b _j kdykoli i ≠ j , ale žádné další páry nejsou srovnatelné. Zejména, je _i a b _i jsou nesrovnatelné v P ; Na P lze nahlížet jako na orientovanou formu korunového grafu . Obrázek ukazuje uspořádání tohoto typu pro n = 4.

Pak se pro každou i jakékoliv Realizer musí obsahovat lineární pořadí, které začíná se všemi z _j kromě _i (v některých pořadí), pak zahrnuje b _i , pak se _i a končí všechny zbývající b _j . Je tomu tak proto, že pokud by existoval Realizer která nezahrnovala takový příkaz, pak křižovatka objednávek, které Realizer by musel si _i předcházející b _i , což by bylo v rozporu s nesrovnatelnost s _i a b _i v P . A naopak, každá rodina lineárních řádů, která obsahuje jeden řád tohoto typu pro každé i, má P jako svůj průsečík. Tak, P má rozměr přesně n . Ve skutečnosti je P známé jako standardní příklad posetu dimenze n a je obvykle označováno S _n .

Objednávka dimenze dva

Dílčí objednávky s dimenzí objednávky dva lze charakterizovat jako dílčí objednávky, jejichž graf srovnatelnosti je doplňkem grafu srovnatelnosti jiného dílčího řádu ( Baker, Fishburn & Roberts 1971 ). To znamená, že P je částečný řád s dimenzí řádu dva právě tehdy, pokud existuje částečný řád Q na stejné sadě prvků, takže každá dvojice x , y odlišných prvků je srovnatelná přesně v jednom z těchto dvou dílčích řádů. Pokud je P realizováno dvěma lineárními rozšířeními, pak může být částečný řád Q komplementární s P realizován obrácením jednoho ze dvou lineárních rozšíření. Proto jsou srovnatelné grafy dílčích řádů dimenze dvě přesně permutačními grafy , grafy, které jsou samy o sobě grafy srovnatelnosti a doplňují grafy srovnatelnosti.

Dílčí objednávky dimenze objednávky dva zahrnují sériově paralelní dílčí objednávky ( Valdes, Tarjan & Lawler 1982 ). Jsou to přesně dílčí řády, jejichž Hasseovy diagramy mají dominantní kresby , které lze získat použitím pozic ve dvou permutacích realizátoru jako kartézských souřadnic.

Výpočetní složitost

V polynomiálním čase je možné určit, zda daná konečná částečně uspořádaná množina má dimenzi řádu nejvýše dvě, například testováním, zda je graf srovnatelnosti částečného řádu permutační graf. U libovolného k  ≥ 3 je však NP-úplné otestovat, zda je rozměr řádu nejvýše k ( Yannakakis 1982 ).

Posety výskytu grafů

Výskyt poset každé neřízené grafu G má vrcholy a hrany G jako jeho prvky; v tomto posetu, x ≤ y, jestliže buď x = y nebo x je vrchol, y je hrana a x je koncový bod y . Některé druhy grafů mohou být charakterizovány rozměry pořadí jejich výskytu Posets: graf je cesta graf právě tehdy, když rozměr pořadí svého výskytu uspořádané množiny je nejvýše dva, a v souladu s Schnyder teorému je rovinný graf , zda a pouze pokud je řádová dimenze jejího výskytu výskyt maximálně tři ( Schnyder 1989 ).

Pro kompletní graf na n vrcholech je řádová dimenze výskytu incidence ( Hoşten & Morris 1999 ). Z toho vyplývá, že všechny jednoduché n -vertexové grafy mají dopadové posety s dimenzí řádu . ${\ displaystyle \ Theta (\ log \ log n)}$${\ displaystyle O (\ log \ log n)}$

k -rozměr a 2-rozměr

Zevšeobecněním dimenze je pojem k -dimension (písemný ), což je minimální počet řetězců délky nanejvýš k, do jejichž produktu lze vložit částečné pořadí. Zejména na 2-dimenzi objednávky lze pohlížet jako na velikost nejmenší sady, takže se objednávka vloží do pořadí zahrnutí na této sadě. ${\ displaystyle {\ textrm {dim}} _ {k}}$

Viz také

• Intervalová dimenze

Reference

• Baker, KA; Fishburn, P .; Roberts, FS (1971), „Částečné objednávky dimenze 2“, Networks , 2 (1): 11–28, doi : 10,1002 / net.3230020103.
• Dushnik, Ben; Miller, EW (1941), "Částečně uspořádané množiny", American Journal of Mathematics , 63 (3): 600–610, doi : 10,2307 / 2371374 , hdl : 10338.dmlcz / 100377 , JSTOR  2371374.
• Hiraguti, Tosio (1955), „O dimenzi objednávek“ (PDF) , The Science Reports of the Kanazawa University , 4 (1): 1–20, MR  0077500.
• Hosten, Serkan; Morris, Walter D., Jr. (1999), „ Řádová dimenze celého grafu“, Diskrétní matematika , 201 (1–3): 133–139, doi : 10,1016 / S0012-365X (98) 00315-X , MR  1687882.
• Milner, EC; Pouzet, M. (1990), „Note on the dimension of a poset“, Order , 7 (1): 101–102, doi : 10.1007 / BF00383178 , MR  1086132 , S2CID  123485792.
• Schnyder, W. (1989), "Planární grafy a posetová dimenze", Řád , 5 (4): 323–343, doi : 10,1007 / BF00353652 , S2CID  122785359.
• Trotter, William T. (1992), Kombinatorika a částečně uspořádané množiny: Dimension theory , Johns Hopkins Series in the Mathematical Sciences, The Johns Hopkins University Press, ISBN 978-0-8018-4425-6.
• Valdes, Jacobo; Tarjan, Robert E .; Lawler, Eugene L. (1982), „Uznání sériových paralelních digrafů“, SIAM Journal on Computing , 11 (2): 298–313, doi : 10,1137 / 0211023.
• Yannakakis, Mihalis (1982), „Složitost problému dimenze částečného řádu“, SIAM Journal on Algebraic and Discrete Methods , 3 (3): 351–358, doi : 10.1137 / 0603036.