Název:
Kombinatorické vlastnosti metricky homogenních grafů
Překlad názvu:
Combinatorial Properties of Metrically Homogeneous Graphs
Autoři:
Konečný, Matěj ; Hubička, Jan (vedoucí práce) ; Nešetřil, Jaroslav (oponent) Typ dokumentu: Bakalářské práce
Rok:
2018
Jazyk:
eng
Abstrakt: [eng][cze] Ramsey theory looks for regularities in large objects. Model theory studies algebraic structures as models of theories. The structural Ramsey theory com- bines these two fields and is concerned with Ramsey-type questions about certain model-theoretic structures. In 2005, Nešetřil initiated a systematic study of the so-called Ramsey classes of finite structures. This thesis is a contribution to the programme; we find Ramsey expansions of the primitive 3-constrained classes from Cherlin's catalogue of metrically homogeneous graphs. A key ingredient is an explicit combinatorial algorithm to fill-in the missing distances in edge-labelled graphs to obtain structures from Cherlin's classes. This algorithm also implies the extension property for partial automorphisms (EPPA), another combinatorial property of classes of finite structures. 1Ramseyova 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
Klíčová slova:
homogenní struktura; metrický prostor; Ramseyova teorie; ramseyovská expanze; homogeneous structure; metric space; Ramsey expansion; Ramsey theory