Countable ultrahomogeneous undirected graphs

Lachlan, A. H.; Woodrow, Robert E.

doi:10.1090/S0002-9947-1980-0583847-2

Countable ultrahomogeneous undirected graphs
HTML articles powered by AMS MathViewer

by A. H. Lachlan and Robert E. Woodrow PDF

Trans. Amer. Math. Soc. 262 (1980), 51-94 Request permission

Abstract:

Let $G = \left \langle {{V_G}, {E_G}} \right \rangle$ be an undirected graph. The complementary graph $\tilde G$ is $\left \langle {{V_G}, {E_{\tilde G}}} \right \rangle$ where $({V_1}, {V_2}) \in {E_{\tilde G}}$ iff ${V_1} \ne {V_2}$ and $({V_1}, {V_2}) \notin {E_G}$. Let $K(n)$ be the complete undirected graph on n vertices and let E be the graph [ill] i.e. $\left \langle {\{ a, b, c\} , \{ (b, c), (c, b)\} } \right \rangle$. G is ultrahomogeneous just in case every isomorphism of subgraph of smaller cardinality can be lifted to an automorphism of G. Let $\mathcal {D} = \{ K(n): n \in \omega \} \cup \{ E, \tilde E\} \cup \{ \tilde K(n): n \in \omega \}$. Theorem: Let ${G_1}$, ${G_2}$ be two countable (infinite) ultrahomogeneous graphs such that for each $H \in \mathcal {D} H$ can be embedded in ${G_1}$, just in case it can be embedded in ${G_2}$. Then ${G_1} \cong {G_2}$. Corollary: There are a countable number of countable ultrahomogeneous (undirected) graphs.

References

Roland Fraïssé, Sur l’extension aux relations de quelques propriétés des ordres, Ann. Sci. Ecole Norm. Sup. (3) 71 (1954), 363–388 (French). MR 0069239
A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 94–102. MR 419293, DOI 10.1016/0095-8956(76)90072-1
C. Ward Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69–83. MR 304242
C. Ward Henson, Countable homogeneous relational structures and $\aleph _{0}$-categorical theories, J. Symbolic Logic 37 (1972), 494–500. MR 321727, DOI 10.2307/2272734
M. G. Peretjat′kin, Complete theories with a finite number of countable models, Algebra i Logika 12 (1973), 550–576, 618 (Russian). MR 0354347
James H. Schmerl, Countable homogeneous partially ordered sets, Algebra Universalis 9 (1979), no. 3, 317–321. MR 544855, DOI 10.1007/BF02488043
Robert E. Woodrow, There are four countable ultrahomogeneous graphs without triangles, J. Combin. Theory Ser. B 27 (1979), no. 2, 168–179. MR 546859, DOI 10.1016/0095-8956(79)90078-9

Theories with a finite number of countable models and a small language