velikost textu

Ramsey-type results for ordered hypergraphs

Upozornění: Informace získané z popisných dat či souborů uložených v Repozitáři závěrečných prací nemohou být použity k výdělečným účelům nebo vydávány za studijní, vědeckou nebo jinou tvůrčí činnost jiné osoby než autora.
Název:
Ramsey-type results for ordered hypergraphs
Název v češtině:
Ramseyovské výsledky pro uspořádané hypergrafy
Typ:
Disertační práce
Autor:
Mgr. Martin Balko
Školitel:
doc. RNDr. Pavel Valtr, Dr.
Oponenti:
Dr. David Conlon
prof. RNDr. Jaroslav Nešetřil, DrSc.
Id práce:
122288
Fakulta:
Matematicko-fyzikální fakulta (MFF)
Pracoviště:
Katedra aplikované matematiky (32-KAM)
Program studia:
Informatika (P1801)
Obor studia:
Diskrétní modely a algoritmy (4I4)
Přidělovaný titul:
Ph.D.
Datum obhajoby:
27. 9. 2016
Výsledek obhajoby:
Prospěl/a
Jazyk práce:
Angličtina
Klíčová slova:
uspořádaný graf, uspořádané Ramseyovo číslo, Erdősova–Szekeresova věta, průsečíkové číslo, monotónní nakreslení
Klíčová slova v angličtině:
ordered graph, ordered Ramsey number, Erdős–Szekeres theorem, crossing number, monotone drawing
Abstrakt:
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˝sovy– o Szekeresovy domněnky nad uspořádanými hypergrafy. Dokážeme přesnou formuli pro minimální počet průsečíků v jednoduchých x- monotónních nakresleních úplných grafů a ukážeme kombinatorickou charakterizaci těchto nakreslení pomocí obarvení uspořádaných úplných 3-uniformních hypergrafů. 1
Abstract v angličtině:
Ramsey-type results for ordered hypergraphs Martin Balko Abstract We introduce ordered Ramsey numbers, which are an analogue of Ramsey numbers for graphs with a linear ordering on their vertices. We study the growth rate of ordered Ramsey numbers of ordered graphs with respect to the number of vertices. We find ordered match- ings whose ordered Ramsey numbers grow superpolynomially. We show that ordered Ramsey numbers of ordered graphs with bounded degeneracy and interval chromatic number are at most polynomial. We prove that ordered Ramsey numbers are at most polynomial for ordered graphs with bounded bandwidth. We find 3-regular graphs that have superlinear ordered Ramsey numbers, regardless of the ordering. The last two results solve problems of Conlon, Fox, Lee, and Sudakov. We derive the exact formula for ordered Ramsey numbers of mono- tone cycles and use it to obtain the exact formula for geometric Ramsey numbers of cycles that were introduced by Károlyi et al. We refute a conjecture of Peters and Szekeres about a strengthening of the fa- mous Erd˝s–Szekeres conjecture to ordered hypergraphs. We obtain o the exact formula for the minimum number of crossings in simple x-monotone drawings of complete graphs and provide a combinatorial characterization of these drawings in terms of colorings of ordered complete 3-uniform hypergraphs. 1
Dokumenty
Stáhnout Dokument Autor Typ Velikost
Stáhnout Text práce Mgr. Martin Balko 1.27 MB
Stáhnout Příloha k práci Mgr. Martin Balko 814 kB
Stáhnout Abstrakt v českém jazyce Mgr. Martin Balko 72 kB
Stáhnout Abstrakt anglicky Mgr. Martin Balko 70 kB
Stáhnout Posudek vedoucího doc. RNDr. Pavel Valtr, Dr. 41 kB
Stáhnout Posudek oponenta Dr. David Conlon 147 kB
Stáhnout Posudek oponenta prof. RNDr. Jaroslav Nešetřil, DrSc. 743 kB
Stáhnout Záznam o průběhu obhajoby doc. RNDr. Jiří Fiala, Ph.D. 153 kB