Abstract:
The well-known Rado graph R is universal in the set of all countable
graphs I, since every countable graph is an induced subgraph of R. We
study universality in I and, using R, show the existence of 20 pairwise
non-isomorphic graphs which are universal in I and denumerably many
other universal graphs in I with prescribed attributes. Then we contrast
universality for and universality in induced-hereditary properties of graphs
and show that the overwhelming majority of induced-hereditary properties
contain no universal graphs. This is made precise by showing that there are
2(20 ) properties in the lattice K< of induced-hereditary properties of which
only at most 20 contain universal graphs.
In a final section we discuss the outlook on future work; in particular
the question of characterizing those induced-hereditary properties for which
there is a universal graph in the property.
