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 be an undirected graph. The complementary graph is where iff and . Let be the complete undirected graph on *n* vertices and let *E* be the graph [ill] i.e. . *G* is ultrahomogeneous just in case every isomorphism of subgraph of smaller cardinality can be lifted to an automorphism of *G*. Let . Theorem: Let , *be two countable (infinite) ultrahomogeneous graphs such that for each* *can be embedded in* , *just in case it can be embedded in* . *Then* . Corollary: *There are a countable number of countable ultrahomogeneous (undirected) graphs*.

**[F]**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****[G]**A. Gardiner,*Homogeneous graphs*, J. Combinatorial Theory Ser. B**20**(1976), no. 1, 94–102. MR**0419293****[H1]**C. Ward Henson,*A family of countable homogeneous graphs*, Pacific J. Math.**38**(1971), 69–83. MR**0304242****[H2]**C. Ward Henson,*Countable homogeneous relational structures and ℵ₀-categorical theories*, J. Symbolic Logic**37**(1972), 494–500. MR**0321727****[P]**M. G. Peretjat′kin,*Complete theories with a finite number of countable models*, Algebra i Logika**12**(1973), 550–576, 618 (Russian). MR**0354347****[S]**James H. Schmerl,*Countable homogeneous partially ordered sets*, Algebra Universalis**9**(1979), no. 3, 317–321. MR**544855**, 10.1007/BF02488043**[Wl]**Robert E. Woodrow,*There are four countable ultrahomogeneous graphs without triangles*, J. Combin. Theory Ser. B**27**(1979), no. 2, 168–179. MR**546859**, 10.1016/0095-8956(79)90078-9**[W2]**-,*Theories with a finite number of countable models and a small language*, Ph.D. Dissertation, Simon Fraser University, 1976.

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

DOI:
https://doi.org/10.1090/S0002-9947-1980-0583847-2

Keywords:
Homogeneous,
ultrahomogeneous,
undirected graph,
elimination of quantifiers,
amalgamation property,
-categorical

Article copyright:
© Copyright 1980
American Mathematical Society