Forbidden cycles in metrically homogeneous graphs

Jan Hubička, Michael Kompatscher, Matěj Konečný

Published 2018-08-15Version 1

Aranda, Bradley-Williams, Hubi\v{c}ka, Karamanlis, Kompatscher, Kone\v{c}n\'y and Pawliuk recently proved that for every primitive 3-constrained space $\Gamma$ of finite diameter $\delta$ from Cherlin's catalogue of metrically homogeneous graphs there is a finite family $\mathcal F$ of $\{1,2,\ldots, \delta\}$-edge-labelled cycles such that each $\{1,2,\ldots, \delta\}$-edge-labelled graph is a (not necessarily induced) subgraph of $\Gamma$ if and only if it contains no homomorphic images of cycles from $\mathcal F$. This analysis is a key to showing that the ages of metrically homogeneous graphs have Ramsey expansions and the extension property for partial automorphisms. In this paper we give an explicit description of the cycles in families $\mathcal F$. This has further applications, for example, interpreting the graphs as semigroup-valued metric spaces or homogenizations of $\omega$-categorical $\{1,\delta\}$-edge-labelled graphs.