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

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

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]**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*-*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.

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