Combinatorial Properties of Metrically Homogeneous Graphs

Abstract

Ramsey theory looks for regularities in large objects. Model theory studies algebraic structures as models of theories. The structural Ramsey theory combines 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 ingradient 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.

arXiv commentAn unofficial version of author's Bachelor thesis

References in corpus (6)

• All those Ramsey classes (Ramsey classes with closures and forbidden homomorphisms)
• On the isometry group of the Urysohn space
• The isometry group of the bounded Urysohn space is simple
• Ramsey expansions of metrically homogeneous graphs
• Completing graphs to metric spaces
• Simplicity of the automorphism groups of some binary homogeneous structures determined by triangle constraints

Cited by in corpus (5)

• Extending partial isometries of antipodal graphs
• Simplicity of the automorphism groups of generalised metric spaces
• Semigroup-valued metric spaces
• Forbidden cycles in metrically homogeneous graphs
• Structural Ramsey Theory and the Extension Property for Partial Automorphisms