|
|
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.
|
|
|
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 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
|
|
|
Extension Properties of Graphs and Structures
Klavík, Pavel ; Nešetřil, Jaroslav (vedoucí práce) ; Širáň, Jozef (oponent) ; Hell, Pavol (oponent)
Rozšiřovací vlastnosti grafů a struktur Pavel Klavík Hlavní motivace pro studium kreslení grafů a geometrických reprezentací je najít způ- soby, jak vizualizovat grafy efektivně, aby jejich struktura byla tak srozumitelná, jak je to jenom možné. V této práci se zaměřujeme na strukturální vlastnosti, které vyplývají z toho, že grafy mají určitý druh geometrických reprezentací. Studujeme dva druhy geo- metrických reprezentací: Průnikové reprezentace, ve kterých jsou vrcholy reprezentovány geometrickými množinami, zatímco hrany jsou kódovány jejich průniky, a rovinná vnoření rovinných grafů, což jsou kreslení grafů do roviny bez křížení hran. Z existence geomet- rické reprezentace lze vyvodit dodatečné informace o grafu. Hlavní myšlenka této práce je se ptát, jaká další informace se dá vyvodit ze struktury všech možných geometrických reprezentací. V části I studujeme problém rozšiřování částečných reprezentací pro průnikové reprezen- tace. Vedle grafu obsahuje vstup také částečnou reprezentaci, která předepisuje reprezentaci indukovaného podgrafu. Ptáme se, zdali je možné tuto částečnou reprezentaci rozšířit na plnou reprezentaci vstupního grafu, aniž bychom pozměnili předepsané množiny. Tento pro- blém jsem uvedl v roce 2010 ve své bakalářské práci. Popisujeme přehled známých výsledků pro řadu grafových tříd....
|
|
|
Stuctural Aspects of Graph Homomorphisms
Bok, Jan ; Nešetřil, Jaroslav (vedoucí práce) ; Hubička, Jan (oponent)
Tato diplomová práce se zabývá náhodnými procházkami, Lipschitzovskými zobrazeními a grafovými homomorfismy. Diskutujeme propojení těchto pojmů, dáváme přehled dosavadních výsledků a ukazujeme nové výsledky. Grafový homomorfismus je zobrazení mezi dvěma grafy zachovávající sousednost. Hlavním předmětem zkoumání jsou pro nás homomorfismy grafů do nekonečných cest. Konkrétně nás zajímají dva parametry: maximální rozsah a průměrný rozsah. Průměrný rozsah grafu je očekávaná velikost obrazu uniformně a náhodně zvoleného homomorfismu do nekonečné cesty. Ukazujeme, jak odvodit vztahy pro výpočet průměrného rozsahu na různých třídách grafů a zabýváme se hlavními hypotézami, které se týkají tohoto parametru. Pro maximální rozsah ukazujeme přesný vztah a způsob výpočtu na obecném grafu. Kromě toho studujeme problém rozšiřování částečného homomorfismu, kde ukážeme jeho polynomialitu pro některé případy. 1
|
|
|
Algebraic, Structural, and Complexity Aspects of Geometric Representations of Graphs
Zeman, Peter ; Klavík, Pavel (vedoucí práce) ; Nešetřil, Jaroslav (oponent)
Title: Algebraic, Structural and Complexity Aspects of Geometric Representations of Graphs Author: Peter Zeman Department: Computer Science Institute Supervisor: RNDr. Pavel Klavík Supervisor's e-mail: klavik@iuuk.mff.cuni.cz Keywords: automorphism groups, interval graphs, circle graphs, comparability graphs, H-graphs, recognition, dominating set, graph isomorphism, maximum clique, coloring Abstract: We study symmetries of geometrically represented graphs. We describe a tech- nique to determine the automorphism group of a geometrically represented graph, by understanding the structure of the induced action on all geometric representations. We prove that interval graphs have the same automorphism groups as trees, and for a given interval graph, we construct a tree with the same automorphism group which answers a question of Hanlon [Trans. Amer. Math. Soc 272(2), 1982]. For permutation and circle graphs, we give an inductive characterization by semidirect and wreath prod- ucts. We also prove that every abstract group can be realized by the automorphism group of a comparability graph/poset of the dimension at most four. We also study H-graphs, introduced by Biró, Hujter, and Tuza in 1992. Those are intersection graphs of connected subgraphs of a subdivision of a graph H. This thesis is the first comprehensive...
|
|
|
Extension property of structures
Hartman, David ; Nešetřil, Jaroslav (vedoucí práce) ; Pultr, Aleš (oponent) ; Woodrow, Robert (oponent)
Tato práce rozebírá vlastnost relačních struktur, která implikuje jejich vysokou symetričnost. Strukturu nazveme homogenní pokud lze libovolné lokální zobrazení rozšířit na zobrazení nad celou strukturou a to pro li- bovolnou volbu konečné vzorové množiny. Typ lokálního a globálního zo- brazení potom určuje různé typy homogenity. Prominentní místo má ul- trahomogenita, která označuje strukturu, pro kterou libovolný lokální iso- morfismus nad konečnými podstrukturami je rozšiřitelný na automorfismus. Na rozdíl od grafů je klasifikace ultrahomogenních relačních struktur stále otevřeným problémem. Cílem práce je charakterizovat "vzdálenost" od ho- mogenity a to dvěma způsoby. Nejprve zvyšuje "složitost struktury" přidáváním relací a sleduje změny klasifikace homogenních struktur. To vede k několika klasifikacím homomorfně-homogenních L-obarvitelných grafů pro různé L, kde L-obarvitelný graf je graf, kde vrcholy a hrany dostávají množiny barev z částečně uspořádané množiny L. Na to navazují výsledky a diskuze nad hier- archií tříd definovanou skrze různé typy homogenity s ohledem na koincidenci jednotlivých tříd. Druhý pohled zkoumá pro dané struktury jak minimálně rozšířit jejich jazyk, abychom dosáhli homogenity....
|
|
|
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...
|
|
|
Representation of special classes of combinatorial objects
Scholleová, Barbora ; Nešetřil, Jaroslav (vedoucí práce) ; Loebl, Martin (oponent)
V této práci se pokoušíme propojit poznatky ze dvou oblastí teorie grafů. Nejprve uvádíme základní pojmy týkající se homomorfismů grafů. Text směřuje k defi- nici nahrazovací operace užitím vhodného nahrazovacího grafu. Dále popisujeme vlastnosti stromové hloubky, jedné z význačných charakteristik každého grafu. Posléze se zabýváme reprezentacemi kategorií v kategorii Graph všech konečných grafů a Graphk všech konečných grafů se stromovou hloubkou nejvýše k.
|
|
| |
host ::
RSS.