graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, the Henson graph is an undirected infinite graph, the unique countable homogeneous graph that does not contain an -vertex clique but that does contain all -free finite graphs as induced subgraphs. For instance, 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 ) in 1971.. The first of these graphs, , is also called the homogeneous triangle-free graph or the universal triangle-free graph.

Construction

To construct these graphs, Henson orders the vertices of the

Rado graph In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...

into a sequence with the property that, for every finite set of vertices, there are infinitely many vertices having as their set of earlier neighbors. (The existence of such a sequence uniquely defines the Rado graph.) He then defines to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every -clique of the Rado graph. With this construction, each graph is an induced subgraph of , and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph omits at least one vertex from each -clique of the Rado graph, there can be no -clique in .

Universality

Any finite or countable -clique-free graph can be found as an induced subgraph of by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in match the set of earlier neighbors of the corresponding vertex in . That is, is a

universal graph In mathematics, a universal graph is an infinite graph that contains ''every'' finite (or at-most-countable) graph as an induced subgraph. A universal graph of this type was first constructed by Richard Rado and is now called the Rado graph or ...

for the family of -clique-free graphs. Because there exist -clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all -clique-free finite graphs as induced subgraphs.

Symmetry

Like the Rado graph, 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 when : for these graphs, every automorphism of the graph has more than one orbit.

References

{{reflist Parametric families of graphs Infinite graphs