Abstrakt

V této práci se zabýváme problémy Ramseyovského typu, které byly motivovány otázkami z oblasti diskrétní geometrie. Soustředíme se na výsledky pro uspořádané struktury, jakými jsou uspořádané grafy a hypergrafy. Představíme uspořádaná Ramseyovská čísla, která jsou obdobou Ramseyovských čísel pro hypergrafy s lineárně uspořádanými množinami vrcholů. Studujeme rychlost růstu těchto čísel nad uspořádanými hypergrafy vzhledem k počtu jejich vrcholů. V práci dokážeme několik výsledků o uspořádaných Ramseyovských číslech, odvodíme některé aplikace v diskrétní geometrii a vyřešíme otevřené problémy několika autorů. Důkazy výsledků zmíněných v práci jsou založené na různých metodách, včetně důkazů provedených za asistence počítačem.

Nejdříve nalezneme uspořádaná párování, jejichž uspořádaná Ramseyovská čísla rostou superpolynomiálně, což je v silném kontrastu se situací nad neuspořádanými grafy omezených stupňů, o nichž je známo, že jejich Ramseyovská čísla rostou pouze lineárně. Poté ukážeme, že uspořádaná Ramseyovská čísla uspořádaných grafů s omezenou degenerovaností a omezeným intervalovým chromatickým číslem rostou pouze polynomiálně. Dokážeme, že uspořádaná Ramseyovská čísla jsou nanejvýš polynomiální pro grafy s omezenými délkami hran, čímž vyřešíme problém od autorů Conlon, Fox, Lee a Sudakov. Zodpovíme také další otázku od autorů Conlon, Fox, Lee a Sudakov nalezením 3-regulárních grafů, jejichž uspořádaná Ramseyovská čísla rostou superlineárně nad libovolným uspořádáním jejich vrcholů.

Odvodíme přesnou formuli pro uspořádaná Ramseyovská čísla monotónních cyklů a použijeme ji k nalezení přesné formule pro geometrická Ramseyovská čísla cyklů, čímž vylepšíme odhady od Károlyi et al. S použitím nejnovějších SAT solverů vyvrátíme domněnku autorů Peters a Szekeres z roku 2006 o zesílení slavné Erdősovy-Szekeresovy domněnky na uspořádané hypergrafy.

V poslední kapitole práce nalezneme přesnou formuli pro minimální počet křížení v x-monotónních nakresleních úplných grafů. Také představíme kombinatorickou charakterizaci těchto nakreslení pomocí obarvení uspořádaných 3-uniformních hypergrafů. Na závěr aplikujeme techniku simulovaného žíhání a získáme tak nejsilnější známý odhad na minimální počet křížení v pseudolineárních nakresleních úplných grafů.