Intervalové pořadí - Interval order - Wikipedia


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á1, považováno za méně než jiné, Já2, pokud Já1 je úplně nalevo od Já2Více formálně, a poset je intervalové pořadí právě tehdy, když existuje a bijekce z do množiny skutečných intervalů, takže , tak, že pro všechny my máme v přesně kdy Takové posety mohou být ekvivalentně charakterizovány jako posety bez indukované podskupiny izomorfní do dvojice dvouprvků řetězy jinými slovy jako - 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 , je přesně to semiordery.
The doplněk z srovnávací graf intervalového pořadí (, ≤) je intervalový graf .
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 je nejmenší počet lineární objednávky jehož průsečík je . 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 je nejméně celé číslo pro které existují intervalové objednávky na s přesně kdy a . Dimenze intervalu objednávky nikdy není větší než její dimenze objednávky,[3].
Kombinatorika
Kromě toho, že je izomorfní s - zdarma posety, neoznačené intervalové objednávky jsou také v bijekci s podmnožinou bez pevného bodu involuce na objednané sady s mohutnost .[4] Jedná se o zapojení bez takzvaných hnízd levého nebo pravého souseda, kde pro jakoukoli involuci na , levý hnízdící isan takhle a pravé vnoření je takhle.
Takové involuce podle poloviční délky mají obyčejná generující funkce [5]
Koeficient v expanzi udává počet neoznačených intervalových objednávek velikosti . 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