Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Countable ultrahomogeneous undirected graphs

Authors: A. H. Lachlan and Robert E. Woodrow
Journal: Trans. Amer. Math. Soc. 262 (1980), 51-94
MSC: Primary 05C99; Secondary 03C10, 03C65
MathSciNet review: 583847
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [F] R. Fraissé, Sur l'extension aux relations de quelques propriétés des ordres, Ann. Sci. École Norm. Sup. 71 (1954), 361-388. MR 0069239 (16:1006b)
  • [G] A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976), 94-102. MR 0419293 (54:7316)
  • [H1] C. Ward Henson, A family of countable homogeneous graphs, Pacific J. Math. 38 (1971), 69-83. MR 0304242 (46:3377)
  • [H2] -, Countable homogeneous relational structures and $ {\aleph _0}$-categorical theories, J. Symbolic Logic 37 (1972), 494-500. MR 0321727 (48:94)
  • [P] M. G. Peretyiatkin, On complete theories with a finite number of denumerable models, Algebra i Logika 12 (1973), 550-576. MR 0354347 (50:6827)
  • [S] J. Schmerl, Countable homogeneous partial ordered sets, Algebra Universalis 9 (1979), 317-321. MR 544855 (81g:06001)
  • [Wl] Robert E. Woodrow, There are four countable ultrahomogeneous graphs without triangles, J. Combinatorial Theory Ser. B 27 (1979), 168-179. MR 546859 (81f:05141)
  • [W2] -, Theories with a finite number of countable models and a small language, Ph.D. Dissertation, Simon Fraser University, 1976.

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C99, 03C10, 03C65

Retrieve articles in all journals with MSC: 05C99, 03C10, 03C65

Additional Information

Keywords: Homogeneous, ultrahomogeneous, undirected graph, elimination of quantifiers, amalgamation property, $ {\aleph _0}$-categorical
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society