Intervalové pořadí - Interval order - Wikipedia

Částečná objednávka na setu {A, b, C, d, E, F} ilustrovaný jeho Hasseův diagram (vlevo) a kolekce intervalů, které jej představují (vpravo).

The ${ displaystyle (2 + 2)}$ poset (černý Hasseův diagram) nemůže být součástí intervalového pořadí: pokud A má úplnou pravdu b, a d překrývá s oběma A a b, a C má úplnou pravdu d, pak C musí mít úplnou pravdu b (světle šedý okraj).

v matematika, zvláště teorie objednávek, intervalové pořadí pro kolekci intervalů na skutečné linii je částečná objednávka odpovídající jejich prioritnímu vztahu zleva doprava - jeden interval, Já₁, považováno za méně než jiné, Já₂, pokud Já₁ je úplně nalevo od Já₂Více formálně, a poset ${ displaystyle P = (X, leq)}$ je intervalové pořadí právě tehdy, když existuje a bijekce z ${ displaystyle X}$ do množiny skutečných intervalů, takže ${ displaystyle x_ {i} mapsto ( ell _ {i}, r_ {i})}$, tak, že pro všechny ${ displaystyle x_ {i}, x_ {j} v X}$ my máme${ displaystyle x_ {i}$ v ${ displaystyle P}$ přesně kdy ${ displaystyle r_ {i} < ell _ {j}}$Takové posety mohou být ekvivalentně charakterizovány jako posety bez indukované podskupiny izomorfní do dvojice dvouprvků řetězy jinými slovy jako ${ displaystyle (2 + 2)}$- zdarma posety.^[1]

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

The doplněk z srovnávací graf intervalového pořadí (${ displaystyle X}$, ≤) je intervalový graf ${ displaystyle (X, cap)}$.

Intervalové objednávky by neměly být zaměňovány s objednávkami obsahujícími interval, které jsou objednávky na zařazení v intervalech na reálné linii (ekvivalentně, objednávky dimenze ≤ 2).

Intervalové objednávky a dimenze

Nevyřešený problém v matematice: Jaká je složitost určení dimenze objednávky intervalového pořadí? (více nevyřešených úloh z matematiky)

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

Související parametr je dimenze intervalu, který je definován analogicky, ale pokud jde o intervalové objednávky místo lineárních objednávek. Tedy intervalová dimenze částečně uspořádané množiny ${ displaystyle P = (X, leq)}$ je nejméně celé číslo ${ displaystyle k}$ pro které existují intervalové objednávky ${ displaystyle preceq _ {1}, ldots, preceq _ {k}}$ na ${ displaystyle X}$ s ${ displaystyle x leq y}$ přesně kdy ${ displaystyle x preceq _ {1} y, ldots,}$ a ${ displaystyle x preceq _ {k} y}$. Dimenze intervalu objednávky nikdy není větší než její dimenze objednávky,^[3].

Kombinatorika

Kromě toho, že je izomorfní s ${ displaystyle (2 + 2)}$- zdarma posety, neoznačené intervalové objednávky ${ displaystyle [n]}$ jsou také v bijekci s podmnožinou bez pevného bodu involuce na objednané sady s mohutnost ${ displaystyle 2n}$.^[4] Jedná se o zapojení bez takzvaných hnízd levého nebo pravého souseda, kde pro jakoukoli involuci${ displaystyle f}$ na ${ displaystyle [2n]}$, levý hnízdící isan ${ displaystyle i in [2n]}$ takhle ${ Displaystyle i$ a pravé vnoření je ${ displaystyle i in [2n]}$ takhle${ Displaystyle f (i)$.

Takové involuce podle poloviční délky mají obyčejná generující funkce ^[5]

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

Koeficient ${ displaystyle t ^ {n}}$ v expanzi ${ displaystyle F (t)}$ udává počet neoznačených intervalových objednávek velikosti ${ displaystyle n}$. Pořadí těchto čísel (sekvence A022493 v OEIS ) začí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, Řada A, 117 (7): 884–909, arXiv:0806.0666, doi:10.1016 / j.jcta.2009.12.007, PAN  2652101.
• 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, R. H. (1994), „Na souhru mezi dimenzí intervalu a dimenzí“ (PDF), SIAM Journal on Discrete Mathematics, 7 (1): 32–40, doi:10.1137 / S089548019121885X, PAN  1259007.
• Fishburn, Peter C. (1970), „Nepřenosná lhostejnost s nestejnými intervaly lhostejnosti“, Journal of Mathematical Psychology, 7 (1): 144–149, doi:10.1016/0022-2496(70)90062-3, PAN  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, PAN  1860536.

Další čtení

• Fishburn, Peter (1985), Intervalové objednávky a intervalové grafy: Studie částečně seřazených sad, John Wiley