In graph theory, the Henson graph Gi is an undirected infinite graph, the unique countable homogeneous graph that does not contain an i-vertex clique but that does contain all Ki-free finite graphs as induced subgraphs. For instance, G3 is a triangle-free graph that contains all finite triangle-free graphs.
These graphs are named after C. Ward Henson, who published a construction for them (for all i ≥ 3) in 1971.[1] The first of these graphs, G3, is also called the homogeneous triangle-free graph or the universal triangle-free graph.
Construction edit
To construct these graphs, Henson orders the vertices of the Rado graph into a sequence with the property that, for every finite set S of vertices, there are infinitely many vertices having S as their set of earlier neighbors. (The existence of such a sequence uniquely defines the Rado graph.) He then defines Gi to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every i-clique of the Rado graph.[1]
With this construction, each graph Gi is an induced subgraph of Gi + 1, and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph Gi omits at least one vertex from each i-clique of the Rado graph, there can be no i-clique in Gi.
Universality edit
Any finite or countable i-clique-free graph H can be found as an induced subgraph of Gi by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in Gi match the set of earlier neighbors of the corresponding vertex in H. That is, Gi is a universal graph for the family of i-clique-free graphs.
Because there exist i-clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph Gi is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all i-clique-free finite graphs as induced subgraphs.[1]
Symmetry edit
Like the Rado graph, G3 contains a bidirectional Hamiltonian path such that any symmetry of the path is a symmetry of the whole graph. However, this is not true for Gi when i > 3: for these graphs, every automorphism of the graph has more than one orbit.[1]
References edit
- ^ a b c d Henson, C. Ward (1971), "A family of countable homogeneous graphs", Pacific Journal of Mathematics, 38: 69–83, doi:10.2140/pjm.1971.38.69, MR 0304242.