|
|
Chromatic invariants in graph drawing
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme vlivem barevnosti grafu na existenci různých druhů ortogonálních nakreslení tohoto grafu. Studujeme otázku, jak velké můžeme volit kb,n tak, aby každý graf barevnosti nejvýše kb,n měl n-rozměrné ortogonální nakreslení s hranami s nejvýše b ohyby. kb,n nazývá1ne multipartitním číslem reprezentace/ nakreslení. Pro ortogonální nakreslení, v nichž jsou vrcholy reprezentovány úsečkami v IRn, je v práci multipartitní číslo odvozeno přesně pro všechna n. Přesná hodnota je určena taktéž pro viditelnostní reprezentace pomocí obdélníků a čtverců. Navíc jsou vylepšeny nejlepší známé horní a dolní odhady pro trojrozměrné ortogonální nakreslení pomocí obdélníků a hranolů. Dolní odhad je zvýšen ze 3 na 22 a horní snížen ze 183 na 42. Powered by TCPDF (www.tcpdf.org)
|
|
| |
|
| |
|
|
Ramseyovské otázky v euklidovském prostoru
Cibulka, Josef ; Valtr, Pavel (vedoucí práce) ; Černý, Jakub (oponent)
Jedním ze základních problémů euklidovské Ramseyovy teorie je určení barevnosti euklidovského prostoru. Barevnost prostoru je nejmenší počet barev, se kterými lze celý prostor obarvit tak, aby žádné dva stejnobarevné body nebyly v jednotkové vzdálenosti. V práci je ukízáno, že barevnost šestirozměrného reálného prostoru je alespoň 11 a že barevnost sedmirozměrného racionálního prostoru je alespoň 15. Dále je předveden nový důkaz dolního odhadu devět pro barevnost pětirozměrného reálného prostoru a zjednodušen důkaz dolního odhadu sedm pro čtyřrozměrný reálný prostor. Je známo, že barevnost n-rozměrného reálného prostoru roste exponenciálně v n. Ukážeme některé podprostory reálného prostoru, pro které barevnost roste pomaleji než exponenciálně. Dále shrneme předchozí výsledky pro obecné normované prostory a nškteré konkrétní neeuklidovské prostory.
|
|
|
Generating simple drawings of graphs
Čermák, Filip ; Balko, Martin (vedoucí práce) ; Valtr, Pavel (oponent)
V této práci se zabýváme průsečíkovými čísly úplných grafů. Nejprve uvedeme dlouhou historii velmi starého problému týkajícího se určení průsečíkového čísla Kn a poté ukážeme současný pokrok v Hararyho-Hillově domněnce postupným procházením jejích důkazů pro speciální třídy nakreslení Kn. Vytvoříme program pro generování databáze všech jednoduchých nakreslení Kn, kde n ≤ 8. Rovněž implementujeme program vizualizující tato nakreslení a umožňující uživateli vytvořit vlastní jednoduchá nakreslení obecných grafů. Vizualizér navíc zachycuje strukturu průsečíků zobrazených nakreslení. Naše pro- gramy využijeme k ověření domněnky Balka, Fulka a Kynčla pro malé případy a odhalíme chybu v článku autorů Mutzela a Oettershagena. 1
|
|
|
Pokrývání sečen konvexní oblasti
Sterzik, Marek ; Valtr, Pavel (vedoucí práce)
Pro danou konvexní oblast v rovině se snažíme nalézt co možná nejkratší množinu (navíc volitelné splňující předepsané vlastnosti), která protíná všechny přímky, které protínají danou oblast. Velikost pokrívajích množin měříme Hausdorffovou 1-dimenzionální mírou 1. V první kapitole je podán úvod do problému. Druhá kapitola se zabývá problémem horního odhadu velikosti minimimální pokrývající množiny. Třetí kapitola se zabývá existencí a vlastnostmi nejmensího pokrytí. Ve čtvrté kapitole je rozebírán problém dolního odhadu pro velikost pokrytí. V páté kapitole jsou studovány další souvislosti a zobecnění problému.
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (vedoucí práce)
Ramseyovské výsledky pro uspořádané hypergrafy Martin Balko Abstract Představíme uspořádaná Ramseyova čísla, která jsou obdobou Ramseyových čísel pro grafy s lineárně uspořádanými vrcholy. Studujeme růst uspořádaných Ramseyových čísel uspořádaných grafů vzhledem k počtu vrcholů. Nalezneme uspořádaná párování se superpolynomiálními uspořádanými Ramseyovými čísly. Ukážeme, že uspořádaná Ramseyova čísla uspořádaných grafů s omezenou dege- nerovaností a intervalovým chromatickým číslem jsou nanejvýš poly- nomiální. Dokážeme, že uspořádaná Ramseyova čísla jsou nanejvýš polynomiální pro uspořádané grafy s omezenými délkami hran. Nalezne- me 3-regulární grafy se superlineárními uspořádanými Ramseyovými čísly nad všemi uspořádáními. Poslední dva výsledky řeší problémy od autorů Conlon, Fox, Lee a Sudakov. Odvodíme přesnou formuli pro uspořádaná Ramseyova čísla mono- tónních cyklů a použijeme ji k získání přesné formule pro geomet- rická Ramseyova čísla cyklů, která byla představena Károlyim a spol. Vyvrátíme domněnku Peterse a Szekerese o zesílení slavné Erd˝osovy- Szekeresovy domněnky nad uspořádanými hypergrafy. Dokážeme přesnou formuli pro minimální počet...
|
|
|
Odhady počtu prázdných čtyřstěnů a ostatních simplexů
Reichel, Tomáš ; Valtr, Pavel (vedoucí práce) ; Balko, Martin (oponent)
Mějme v jednotkové krychli konečnou množinu M uniformně náhodně zvolených bodů. Každá čtveřice bodů z M má jakožto čtyřstěn buď uvnitř nějaký bod z množiny M, nebo je prázdná. V této práci předvedeme horní odhad střední hodnoty počtu těchto prázdných čtyřstěnů vzhledem k velikosti množiny M a ukážeme, jak je odhad nejspíše vzdálen od aproximace střední hodnoty, kterou necháme přímočarým algoritmem spočí- tat počítač. Nakonec pak opustíme trojrozměrný případ a budeme se věnovat obecnější úloze v libovolné dimenzi d, kde namísto prázdných čtyřstěnů v krychli budou figurovat prázdné d-simplexy v d-dimenzionální krychli. Horní odhad pro d-dimenzionální případ pak porovnáme s výsledky z jiného článku o stejném tématu. 1
|
|
|
Structural properties of hereditary permutation classes
Opler, Michal ; Jelínek, Vít (vedoucí práce) ; Valtr, Pavel (oponent)
Permutační třída C je splittovatelná pokud je obsažena v mergi svých dvou vlastních podtříd, a je 1-amalgamovatelná pokud pro libovolné permutace σ, τ ∈ C, každá s jedním vyznačeným prvkem, dokážeme najít permutaci π ∈ C, která obsahuje σ i τ tak že jejich vyznačené prvky splývají. V této práci zkoumáme 1-amalgamovatelnost a splittovatelnost permutačních tříd. Již dříve bylo dokázáno, že nesplittovatelnost implikuje 1-amalgamovatelnost. My ukážeme, že tyto dvě vlastnosti permutačních tříd nejsou ekvivalentní nalezením permutační třídy, která je splittovatelná a zároveň 1-amalgamovatelná. Navíc ukážeme, že existuje nekonečně mnoho takových permutačních tříd. Naše konstrukce je založená na konceptu LR-nafouknutí nebo více obecně na dědičných 2-obarvení, které v této práci také zavedeme a které by mohly být zajímavé i mimo naše použití. 1
|
|
|
O vnitřku minimálního konvexního mnohoúhelníku
Šplíchal, Ondřej ; Valtr, Pavel (vedoucí práce) ; Rataj, Jan (oponent)
Zvolme konečnou množinu bod· P v rovině v obecné poloze, tj. žádné 3 body neleží na přímce. Konvexní n-úhelník je minimální, pokud v jeho konvexním obalu neleží jiný konvexní n-úhelník s vrcholy v P. Erd®s a Szekeres (1935) ukázali, že pro každé n ≥ 3 existuje minimální číslo ES(n) takové, že mezi libovolnými ES(n) body v rovině v obecné poloze lze vybrat n bod·, které tvoří vrcholy konvexního n-úhelníku. Z jejich tvrzení vyplývá, že v topologic- kém vnitřku minimálního konvexního n-úhelníku m·že ležet jen omezený po- čet bod· P pro libovolnou volbu P. Označíme maximální takový počet jako mci(n). V práci ukážeme horní odhad mci(n) ≤ ES(n) − n a spodní odhad 2n−3 − n + 2 ≤ mci(n) pro n ≥ 3.
|
host ::
RSS.