Original title: Kombinatorické vlastnosti metricky homogenních grafů
Translated title: Combinatorial Properties of Metrically Homogeneous Graphs
Authors: Konečný, Matěj ; Hubička, Jan (advisor) ; Nešetřil, Jaroslav (referee)
Document type: Bachelor's theses
Year: 2018
Language: eng
Abstract: [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. 1 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
Keywords: homogeneous structure; metric space; Ramsey expansion; Ramsey theory; homogenní struktura; metrický prostor; Ramseyova teorie; ramseyovská expanze

Institution: Charles University Faculties (theses) (web)
Document availability information: Available in the Charles University Digital Repository.
Original record: http://hdl.handle.net/20.500.11956/100925

Permalink: http://www.nusl.cz/ntk/nusl-386845


The record appears in these collections:
Universities and colleges > Public universities > Charles University > Charles University Faculties (theses)
Academic theses (ETDs) > Bachelor's theses