|
| |
|
|
Částečné k-stromy na plochách
Vaner, Michal ; Valtr, Pavel (oponent) ; Kratochvíl, Jan (vedoucí práce)
V této práci je řešen následující problém: Je dán graf G neúplný k-strom vnořitelný do některé plochy. Je možné jej doplnit tak, aby vznikl úplný k-strom, který je do dané plochy stále vnořitelný? Jak je ukázáno, pro malá k (· 2) to jde na libovolné ploše. Naopak, pro k ¸ 4 lze na každé ploše najít graf, který doplnit nelze a pro dostatečně velké k již nelze doplnit žádný. Případ, kdy k = 3, je hraniční, nebot' existuje nekonečně mnoho vnořitelných úplných 3-stromů, ale nejsou vnořitelné všechny. Ví se, že takto rozšiřovat lze 3-stromy v rovině, zde je pro úplnost uveden prozatím nepublikovaný důkaz prof. Kratochvíla a prof. Thomase. V této práci je důkaz rozšířen na projektivní rovinu. Další plochy zatím prozkoumané nejsou.
|
|
|
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.
|
|
|
Representations and Visualization of Graphs
Štola, Jan ; Kratochvíl, Jan (vedoucí práce) ; Valtr, Pavel (oponent) ; Wood, David (oponent)
The 3D visibility (graph) drawing is a graph drawing in IR3 where vertices are represented by 2D sets placed into planes parallel to xy-plane and the edges correspond to z-parallel visibility among these sets. We continue the study of 3D visibility drawing of complete graphs by rectangles and regular polygons. We show that the maximum size of a complete graph with a 3D visibility drawing by regular n-gons is O(n4). This polynomial bound improves signifficantly the previous best known (exponential) bound 6n3 3n1 3 26n.We also provide several lower bounds. We show that the complete graph K2k+3 (resp. K4k+6) has a 3D visibility drawing by regular 2k-gons (resp.(2k + 1)-gons). We improve the best known upper bound on the size of a complete graph with a 3D visibility drawing by rectangles from 55 to 50. This result is based on the exploration of unimodal sequences of k-tuples of numbers. A sequence of numbers is unimodal if it rst increases and then decreases. A sequence of k-tuples of numbers is unimodal if it is unimodal in each component. We derive tight bounds on the maximum length of a sequence of k-tuples without a unimodal subsequence of length n. We show a connection between these results and Dedekind numbers, i.e., the numbers of antichains of a power set P(1; : : : ; k) ordered by inclusion.
|
|
| |
|
| |
|
|
Ramseyovské věty v geometrii
Stolař, Rudolf ; Kratochvíl, Jan (oponent) ; Valtr, Pavel (vedoucí práce)
Euklidovská Ramseyho teorie se zabývá zkoumáním konfigurací bodů, pro které lze při každém obarvení n-dimenzionálního euklidovského prostoru najít v některé z barev jejich posunutou a otočenou kopii. Její asymetrická část potom verzemi tvrzení, v nichž pro každou barvu hledáme jinou konfiguraci bodů. V této práci se zabýváme především asymetrickými ramseyovskými větami a vlastnostmi n-dimenzionálních hyperkrychlí, pro které dokážeme několik nových odhadů. Velká část práce je věnována barvení více barvami a dosažené výsledky úzce souvisejí se známým problémem chromatického čísla euklidovského prostoru. Zmíníme se také o možnosti zobecnění pojmu chromatického čísla a o některých aspektech takového zobecnění. Pozornost obrátíme i k problémům spojeným s hledáním vícebarevných konfigurací a ukážeme horní odhad pro speciální případ dvoubarevných čtverců.
|
|
|
Ramsey-type results for ordered hypergraphs
Balko, Martin ; Valtr, Pavel (vedoucí práce) ; Conlon, David (oponent) ; Nešetřil, Jaroslav (oponent)
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...
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; Valtr, Pavel (oponent) ; Nešetřil, Jaroslav (vedoucí práce)
Ramseyova teorie studuje vnitřní homogenitu matematických struktur (grafů, číselných oborů), jejichž části (podgrafy, podmnožiny) jsou libovolně obarveny. Často platí, že je-li studovaný objekt dostatečně velký, lze v něm najít určitý jednobarevný podobjekt. Kombinatorické hry jsou hry dvou hráčů s plnou informací, kde záleží pouze na jejich inteligenci. Teorie kombinatorických her studuje především otázky existence vyhrávajících či neprohrávajících strategií. Vezmeme-li ramseyovskou větu a necháme-li objekt, který tato věta studuje, střídavě barvit dvěma hráči, jejichž cílem je vytvořit určitý monochromatický podobjekt, dostaneme kombinatorickou hru. Předmětem našeho zájmu je jednak nejmenší velikost objektu, při které platí ramseyovská věta, tzv. ramseyovské číslo, a jednak nejmeněí velikost téhož objektu, při které má první hráč vyhrávající strategii v příslušné kombinatorické hře, tzv. herní číslo. V této práci popisujeme takové ramseyovské věty, u nichž je ramseyovské číslo podstatně větší než číslo herní. To znamená, že podáváme důkazy existence vyhrávajících strategií prvního hráče spolu s horními odhady na ramseyovská a herní čísla a obě čísla porovnáváme.
|
|
|
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)
|
host ::
RSS.