|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (vedoucí práce)
Strukturální Ramseyova teorie je obor na rozmezí kombinatoriky a teorie modelů s hlubokými souvislostmi s dynamickými systémy. Ramseyovskost většiny známých ramseyovských tříd v konečném binárním symetrickém relačním jazyce se dá dokázat s využitím nějaké varianty tzv. shortest path completion (například Sauerovy S-metrické prostory, Conantovy zobecněné metrické prostory, Braunfel- dovy Λ-ultrametrické prostory či Cherlinovy metricky homogenní grafy). V této práci zkoumáme limity shortest path completion. Nabízíme abstrakci - met- rické prostory se vzdálenostmi z pologrupy - pro všechny zmíněné ramseyovské třídy a studujeme ramseyovské expanze a EPPA (extension property for partial automorphisms) této abstrakce. Na tyto výsledky lze také nahlížet jako na důkaz toho, že samotná otázka, které neúplné struktury mají zúplnění v nějaké amal- gamační třídě, je zajímavá a důležitá. Naše výsledky mají i další aplikace (jako například stationary independence relations). Jako důsledek našich obecných vět znovu dokážeme výsledky Hubičky a Nešetřila o Sauerových S-metrických prostorech, výsledky Hubičky, Nešetřila a autora o Conantových generlizovaných metrických prostorech, Braunfeldovy výsledky o Λ-...
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (vedoucí práce)
Strukturální Ramseyova teorie je obor na rozmezí kombinatoriky a teorie modelů s hlubokými souvislostmi s dynamickými systémy. Ramseyovskost většiny známých ramseyovských tříd v konečném binárním symetrickém relačním jazyce se dá dokázat s využitím nějaké varianty tzv. shortest path completion (například Sauerovy S-metrické prostory, Conantovy zobecněné metrické prostory, Braunfel- dovy Λ-ultrametrické prostory či Cherlinovy metricky homogenní grafy). V této práci zkoumáme limity shortest path completion. Nabízíme abstrakci - met- rické prostory se vzdálenostmi z pologrupy - pro všechny zmíněné ramseyovské třídy a studujeme ramseyovské expanze a EPPA (extension property for partial automorphisms) této abstrakce. Na tyto výsledky lze také nahlížet jako na důkaz toho, že samotná otázka, které neúplné struktury mají zúplnění v nějaké amal- gamační třídě, je zajímavá a důležitá. Naše výsledky mají i další aplikace (jako například stationary independence relations). Jako důsledek našich obecných vět znovu dokážeme výsledky Hubičky a Nešetřila o Sauerových S-metrických prostorech, výsledky Hubičky, Nešetřila a autora o Conantových generlizovaných metrických prostorech, Braunfeldovy výsledky o Λ-...
|
|
|
Computing and estimating ordered Ramsey numbers
Poljak, Marian ; Balko, Martin (vedoucí práce) ; Hubička, Jan (oponent)
Zabýváme se uspořádanými Ramseyovými čísly, která představují analogii klasick- ých Ramseyových čísel pro uspořádané grafy. Zlepšíme některé již dosažené výsledky pro speciální třídu uspořádaných párování a vyvrátíme platnost Rohatgiho domněnky. Rozšíříme klasický pojem Ramsey dobrosti pro uspořádaný případ a pokusíme se charak- terizovat všechny Ramsey dobré souvislé uspořádané grafy. Nastíníme, jak lze Ramseyova čísla odhadnout výpočetně a popíšeme naši utilitu založenou na SAT řešičích, která byla pro tento účel vyvinuta a kterou mohou využít další výzkumníci zabývající se tímto té- matem. 1
|
|
|
Semigroup-valued metric spaces
Konečný, Matěj ; Hubička, Jan (vedoucí práce) ; Pultr, Aleš (oponent)
Strukturální Ramseyova teorie je obor na rozmezí kombinatoriky a teorie modelů s hlubokými souvislostmi s dynamickými systémy. Ramseyovskost většiny známých ramseyovských tříd v konečném binárním symetrickém relačním jazyce se dá dokázat s využitím nějaké varianty tzv. shortest path completion (například Sauerovy S-metrické prostory, Conantovy zobecněné metrické prostory, Braunfel- dovy Λ-ultrametrické prostory či Cherlinovy metricky homogenní grafy). V této práci zkoumáme limity shortest path completion. Nabízíme abstrakci - met- rické prostory se vzdálenostmi z pologrupy - pro všechny zmíněné ramseyovské třídy a studujeme ramseyovské expanze a EPPA (extension property for partial automorphisms) této abstrakce. Na tyto výsledky lze také nahlížet jako na důkaz toho, že samotná otázka, které neúplné struktury mají zúplnění v nějaké amal- gamační třídě, je zajímavá a důležitá. Naše výsledky mají i další aplikace (jako například stationary independence relations). Jako důsledek našich obecných vět znovu dokážeme výsledky Hubičky a Nešetřila o Sauerových S-metrických prostorech, výsledky Hubičky, Nešetřila a autora o Conantových generlizovaných metrických prostorech, Braunfeldovy výsledky o Λ-...
|
|
|
Combinatorial Properties of Metrically Homogeneous Graphs
Konečný, Matěj ; Hubička, Jan (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Ramseyova teorie hledá " pořádek v dostatečně velkém nepořádku". Teorie modelů studuje algebraické struktury jako modely teorií. Strukturální Ramseyova teorie tyto dva obory kombinuje a zabývá se ramseyovskými otázkami o určitých modelově-teoretických strukturách. V roce 2005 Nešetřil zahájil systematickou studii takzvaných Ramseyových tříd konečných struktur. Tato práce je příspěvkem do Nešetřilova programu: Studujeme zde ramseyovské expanze primitivních 3- constrained tříd z Cherlinova katalogu metricky homogenních grafů. Klíčovou ingrediencí je kombinatorický algoritmus, který doplní chybějící vzdálenosti v gra- fech s váženými hranami tak, aby dostal struktury z Cherlinova katalogu. Dalším důsledkem tohoto algoritmu je také EPPA, což je jiná kombinatorická vlastnost tříd konečných struktur. 1
|
|
|
Combinatorial Games Theory
Valla, Tomáš ; Nešetřil, Jaroslav (vedoucí práce) ; Sgall, Jiří (oponent) ; Spirakis, Paul (oponent)
Název práce: Kombinatorická teorie her Autor: Tomáš Valla Katedra / Ústav: IUUK MFF UK Vedoucí doktorské práce: Prof. RNDr. Jaroslav Nešetřil, DrSc., IUUK MFF UK Abstrakt: Tématem dizertační práce je studium složitosti, která vzniká, pokud k urči- tému prostředí či procesu uvážíme jeho kompetitivní variantu, a to především pomocí metod algoritmické teorie her, teorie složitosti, a dalších nástrojů. Například v prostředí Internetu je vyloučeno aplikovat na graf propojených počítačů libovolný klasický gra- fový algoritmus, protože ten zpravidla vyžaduje existenci centrální autority, která s grafem manipuluje. V této práci popisujeme distribuovanou a lokálně definovanou hru, která v kompetitivním prostředí bez centrální autority simuluje výpočet váženého vr- cholového pokrytí grafu, včetně zobecnění na tzv. hitting set a submodulární váhovací funkci. Dokážeme, že tato hra má vždy Nashovo ekvilibrium a každé toto ekvilibrium dá stejně dobrou aproximaci optimálního pokrytí, jakou lze dosáhnout nejlepšími zná- mými aproximačními algoritmy. Přesněji, tzv. cena anarchie naší hry je stejná jako faktor u nejlepšího známého aproximačního algoritmu. Dosavadní výsledky v této ob- lasti neměly cenu anarchie omezenu ani konstantou. Kromě toho v práci předkládáme i výsledky z oblasti her tzv. grafových prohledávacích her a...
|
|
|
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
|
host ::
RSS.