The Classification of Homogeneous Simple 3-graphs

Abstract

We classify the ultrahomogeneous complete 3-edge-coloured graphs (3-graphs) with simple theory. This extends Lachlan's result (a corollary of the Effective Classification Theorem for stable structures) classifying the stable homogeneous 3-graphs. The unstable structures in this class are: + Primitive structures: The random 3-graph ${\Gamma }^{i,j,k}$ + Imprimitive structures with infinite classes: * $K_m^i[{\Gamma }^{j,k}]$, $m\in \omega +1$ * ${\Gamma }^{i,j}[K_{\omega }^k]$ * ${\mathcal{B}}_n^{i,j}$, $n\in \omega$, $n\ge 2$ * ${\mathcal{B}}^i$ + Imprimitive structures with finite classes: * $C^i({\Gamma }^{j,k})$ * ${\Gamma }^{i,j}[K_n^k]$, $n\in \omega$ Where $\{i,j,k\}=\{R,S,T\}$, ${\mathcal{B}}_n^{i,j}$ is the random $n$-partite graph, and $\mathcal{B}$ is the Fraïssé limit of the class of all finite 3-graphs in which the predicate $i$ is an equivalence relation (i.e., the triangles $iij$ and $iik$ are forbidden). Finally, $C^i({\Gamma }^{j,k})$ is the 3-graph obtained from the following construction: enumerate the Random Graph in predicates $j,k$ as $\{v_n:n\in \omega \}$. For each vertex $v_n$, there are two vertices, $a_n$ and $b_n$ in $C^i({\Gamma }^{j,k})$ which are $i$-related. There are no more $i$-edges, and if $j(v_n,v_m)$ holds, declare $j(a_n,a_m)\wedge j(b_n,b_m)$. All other edges are of type $k$.

97 pages, 26 figures

References in corpus (1)

• On Weak Elimination of Hyperimaginaries and its Consequences