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, Ph.D. Dissertation, Simon Fraser University, 1976.
Additional Information
- © Copyright 1980 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 262 (1980), 51-94
- MSC: Primary 05C99; Secondary 03C10, 03C65
- DOI: https://doi.org/10.1090/S0002-9947-1980-0583847-2
- MathSciNet review: 583847