|
| |
|
| |
|
| |
|
| |
|
|
Freimanova věta v aditivní kombinatorice
Hančl, Jaroslav ; Nešetřil, Jaroslav (oponent) ; Klazar, Martin (vedoucí práce)
V předložené shrnující práci studujeme takzvaný inverzní problém aditivní teorie čísel. Snažíme se tedy charakterizovat množiny A přirozených čísel, víme-li nějaké informace o jejich násobcích 2A = A + A. Zpočátku se budeme věnovat konečným množinám s vlastností |2A| = 2|A| - 1, dále si ukážeme zobecnění pro takové abelovské grupy G, v nichž má každý prvek řad omezenýy konstantou r, a jejich podmnožiny A splňující |2A| - c|A|. Nakonec se dostaneme až k slavné Freimanově větě, která popisuje množiny přirozených čísel A, jež jsou malé ve smyslu |2A| - c|A|. Tuto větu dokážeme a uvedeme některé její důsledky a aplikace.
|
|
|
Ramseyova teorie a kombinatorické hry
Valla, Tomáš ; 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ámeli 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.
|
|
|
Combinatorial Properties of Finite Models
Hubička, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Pultr, Aleš (oponent) ; Cameron, P. (oponent)
V této práci se věnujeme univerzáním strukturám pro vnoření i homomorfismy a sjednocujeme výsledky týkající se obou těchto pojmů. Ukážeme, že mnohé z univerzálních a ultrahomogenních struktur jsou reprezentovatelné pomocí jednoduchých konečných technik. O takových strukturách říkáme, že mají konečnou prezentaci. Na základě klasické reprezentace náhodného grafu (R. Rado) hledáme konečné prezentace pro známé ultrahomogenní struktury. Podle klasifikačního programu najdeme prezentace všech ultrahomogenních neorientovaných grafů, turnajů a částečných uspořádání. Ukážeme také prezentaci racionálního Urysohnova prostoru a některých orientovaných grafů. Věnujeme se také známým strukturám, které lze považovat za konečné prezentace. Uvádíme přehled struktur, které popisují částečná uspořádání a u nichž můžeme dokázat jejich univerzalitu (například uspořádání množin slov, geometrických objektů, polynomů, či homomorfismové uspořádání struktur). Ukážeme nový kombinatorický důkaz existence univerzálních struktur pro třídy struktur definovaných pomocí zakázaných homomorfismů. Z tohoto důkazu plyne nová konstrukce homomorfismových dualit a souvislost s Urysohnovým prostorem.
|
|
| |
|
|
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.
|
host ::
RSS.