text size

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.
Title:
Ramsey-type results for ordered hypergraphs
Title (in czech):
Ramseyovské výsledky pro uspořádané hypergrafy
Type:
Dissertation
Author:
Mgr. Martin Balko
Supervisor:
doc. RNDr. Pavel Valtr, Dr.
Opponents:
Dr. David Conlon
prof. RNDr. Jaroslav Nešetřil, DrSc.
Thesis Id:
122288
Faculty:
Faculty of Mathematics and Physics (MFF)
Department:
Department of Applied Mathematics (32-KAM)
Study programm:
Informatics (P1801)
Study branch:
Discrete Models and Algorithms (4I4)
Degree granted:
Ph.D.
Defence date:
27/09/2016
Defence result:
Pass
Language:
English
Keywords (in czech):
uspořádaný graf, uspořádané Ramseyovo číslo, Erdősova–Szekeresova věta, průsečíkové číslo, monotónní nakreslení
Keywords:
ordered graph, ordered Ramsey number, Erdős–Szekeres theorem, crossing number, monotone drawing
Abstract (in czech):
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:
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
Documents
Download Document Author Type File size
Download Text of the thesis Mgr. Martin Balko 1.27 MB
Download Attachment to the thesis Mgr. Martin Balko 814 kB
Download Abstract in czech Mgr. Martin Balko 72 kB
Download Abstract in english Mgr. Martin Balko 70 kB
Download Supervisor's review doc. RNDr. Pavel Valtr, Dr. 41 kB
Download Opponent's review Dr. David Conlon 147 kB
Download Opponent's review prof. RNDr. Jaroslav Nešetřil, DrSc. 743 kB
Download Defence's report doc. RNDr. Jiří Fiala, Ph.D. 153 kB