Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
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?)

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

PII: S 0002-9947(1980)0583847-2
Keywords: Homogeneous, ultrahomogeneous, undirected graph, elimination of quantifiers, amalgamation property, $ {\aleph _0}$-categorical
Article copyright: © Copyright 1980 American Mathematical Society