Intervalové pořadí - Interval order

Částečné pořadí na množině { a , b , c , d , e , f } ilustrované jeho Hasseovým diagramem (vlevo) a kolekcí intervalů, které jej představují (vpravo).

Poset (černá Hasse diagram) nemůže být součástí intervalu pořadí: v případě, je zcela vpravo b , a d překrytí jak s A a B , a C je zcela vpravo d , pak c musí být zcela vpravo B (světle šedý okraj).${\ displaystyle (2 + 2)}$

V matematice , zejména v teorii řádů , je intervalové pořadí pro kolekci intervalů na reálné linii částečné pořadí odpovídající jejich prioritnímu vztahu zleva doprava - jeden interval, I ₁ , je považován za méně než jiný, I ₂ , pokud I ₁ je zcela nalevo od I ₂ . Více formálně, je počitatelné poset je interval objednávky tehdy a jen tehdy, pokud existuje bijekce z k množině reálných časových intervalech, takže tak, že pro všechny máme v přesně kdy . Taková posety mohou být ekvivalentně charakterizována jako posety, které nemají indukovanou podmnožinu izomorfní s dvojicí řetězců dvou prvků , jinými slovy jako posety bez. ${\ displaystyle P = (X, \ leq)}$${\ displaystyle X}$${\ displaystyle x_ {i} \ mapsto (\ ell _ {i}, r_ {i})}$${\ displaystyle x_ {i}, x_ {j} \ v X}$${\ displaystyle x_ {i} <x_ {j}}$${\ displaystyle P}$${\ displaystyle r_ {i} <\ ell _ {j}}$${\ displaystyle (2 + 2)}$

Podtřídou intervalových objednávek získaných omezením intervalů na jednotkové délky, takže všechny mají formu , jsou přesně semiordery . ${\ displaystyle (\ ell _ {i}, \ ell _ {i} +1)}$

Doplněk na srovnávací graf intervalu, aby ( , ≤) je interval graf . ${\ displaystyle X}$ ${\ displaystyle (X, \ cap)}$

Intervalové příkazy by neměly být zaměňovány s příkazy k zadržení intervalu, což jsou příkazy k zahrnutí v intervalech na skutečné řádce (ekvivalentně, příkazy dimenze ≤ 2).

Intervalové objednávky a dimenze

Důležitým parametrem dílčích objednávek je dimenze objednávky : dimenze částečné objednávky je nejmenší počet lineárních objednávek, jejichž průsečík je . U intervalových objednávek může být dimenze libovolně velká. A zatímco je známo, že problém stanovení dimenze obecných parciálních řádů je NP-tvrdý , určení dimenze intervalového řádu zůstává problémem neznámé výpočetní složitosti . ${\ displaystyle P}$${\ displaystyle P}$

Příbuzným parametrem je intervalová dimenze , která je definována analogicky, ale ve smyslu intervalových objednávek místo lineárních objednávek. Tak interval rozměr uspořádaná množina je nejméně celé číslo , pro které existuje interval objednávky na s přesně kdy a . Dimenze intervalu objednávky nikdy není větší než její dimenze objednávky. ${\ displaystyle P = (X, \ leq)}$ ${\ displaystyle k}$${\ displaystyle \ preceq _ {1}, \ ldots, \ preceq _ {k}}$${\ displaystyle X}$${\ displaystyle x \ leq y}$${\ displaystyle x \ preceq _ {1} y, \ ldots,}$${\ displaystyle x \ preceq _ {k} y}$

Kombinatorika

Kromě toho, že jsou izomorfní až volná posety, jsou neznačené intervalové objednávky také v bijekci s podmnožinou involucí bez pevného bodu na objednaných množinách s mohutností . Jsou to involucema s žádnými takzvanými vlevo nebo vpravo sousedních nestings když z nějakých umocňování na , levou hnízdění je taková, že i právo hnízdění je taková, že . ${\ displaystyle (2 + 2)}$${\ displaystyle [n]}$ ${\ displaystyle 2n}$${\ displaystyle f}$${\ displaystyle [2n]}$${\ displaystyle i \ in [2n]}$${\ Displaystyle i <i + 1 <f (i + 1) <f (i)}$${\ displaystyle i \ in [2n]}$${\ Displaystyle f (i) <f (i + 1) <i <i + 1}$

Takové involuce mají podle poloviční délky běžnou generační funkci

${\ displaystyle F (t) = \ součet _ {n \ geq 0} \ prod _ {i = 1} ^ {n} (1- (1-t) ^ {i}).}$

Koeficient v expanzi udává počet neznačených intervalových řádů velikosti . Pořadí těchto čísel (sekvence A022493 v OEIS ) začíná ${\ displaystyle t ^ {n}}$${\ displaystyle F (t)}$${\ displaystyle n}$

1, 2, 5, 15, 53, 217, 1014, 5335, 31240, 201608, 1422074, 10886503, 89903100, 796713190, 7541889195, 75955177642,…

Poznámky

Reference

• Bousquet-Mélou, Mireille ; Claesson, Anders; Dukes, Mark; Kitaev, Sergey (2010), „(2 + 2) volná posety, sekvence výstupu a vzor vyhýbající se permutacím“, Journal of Combinatorial Theory , Series A, 117 (7): 884–909, arXiv : 0806.0666 , doi : 10,1016 / j .jcta.2009.12.007 , MR  2652101 , S2CID  8677150.
• Felsner, S. (1992), Interval Orders: Combinatorial Structure and Algorithms (PDF) , Ph.D. disertační práce, Technická univerzita v Berlíně.
• Felsner, S .; Habib, M .; Möhring, RH (1994), „On the interplay between interval dimension and dimension“ (PDF) , SIAM Journal on Discrete Mathematics , 7 (1): 32–40, doi : 10,1137 / S089548019121885X , MR  1259007.
• Fishburn, Peter C. (1970), „Přechodná lhostejnost s nestejnými intervaly lhostejnosti“, Journal of Mathematical Psychology , 7 (1): 144–149, doi : 10,1016 / 0022-2496 (70) 90062-3 , MR  0253942.
• Zagier, Don (2001), „Vassilievovy invarianty a podivná identita související s funkcí Dedekind eta“, Topologie , 40 (5): 945–960, doi : 10,1016 / s0040-9383 (00) 00005-7 , MR  1860536.

Další čtení

• Fishburn, Peter (1985), Interval Orders and Interval Graphs: A Study of Partually Ordered Sets , John Wiley