Forbidden cycles in metrically homogeneous graphs

08/15/2018
by   Jan Hubička, et al.
0

Aranda, Bradley-Williams, Hubička, Karamanlis, Kompatscher, Konečný and Pawliuk recently proved that for every primitive 3-constrained space Γ of finite diameter δ from Cherlin's catalogue of metrically homogeneous graphs there is a finite family F of {1,2,..., δ}-edge-labelled cycles such that each {1,2,..., δ}-edge-labelled graph is a (not necessarily induced) subgraph of Γ if and only if it contains no homomorphic images of cycles from 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 F. This has further applications, for example, interpreting the graphs as semigroup-valued metric spaces or homogenizations of ω-categorical {1,δ}-edge-labelled graphs.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset