|
|
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...
|
|
|
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...
|
|
|
Erdos-Szekeres type theorems
Eliáš, Marek ; Matoušek, Jiří (vedoucí práce) ; Cibulka, Josef (oponent)
Nech P = (p1, p2, . . . , pN ) je postupnosť bodov v rovine, kde pi = (xi, yi) a x1 < x2 < · · · < xN . Slávna Erdős-Szekeresova veta z roku 1935 hovorí, že každá taká postupnosť P obsahuje monotónnu podpostupnosť S dĺžky√ N . Iná, podobne slávna veta z toho istého článku hovorí, že každá taká po- stupnosť P obsahuje konvexnú alebo konkávnu podpostupnosť dĺžky Ω(log N). Najprv definujeme (k + 1)-ticu K ⊆ P ako pozitívnu, keď leží na grafe funkcie s nezápornou k-tou deriváciou a podobne tiež negatívnu (k + 1)-ticu. Ďalej hovoríme, že S ⊆ P je monotónna k-teho rádu, keď jej (k + 1)-tice sú buďto všetky pozitívne alebo všetky negatívne. V tejto práci skúmame kvantitatívne odhady pre zodpovedajúce Ramseyovské funkcie. Dostávame Ω(log(k−1) N) ako dolný odhad. Taktiež uvádzame vylepšené odhady pre súvisiace problémy ako Order types a One-sided sets of hyperplanes. 1
|
|
|
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...
|
host ::
RSS.