Henson graph
{{Short description|Infinite graph without small cliques}}
{{unsolved|mathematics|Do the Henson graphs have the finite model property?}}
In graph theory, the Henson graph {{math|Gi}} is an undirected infinite graph, the unique countable homogeneous graph that does not contain an {{mvar|i}}-vertex clique but that does contain all {{mvar|Ki}}-free finite graphs as induced subgraphs. For instance, {{math|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 {{math|i ≥ 3}}) in 1971.{{citation
| last = Henson | first = C. Ward
| journal = Pacific Journal of Mathematics
| mr = 0304242
| pages = 69–83
| title = A family of countable homogeneous graphs
| volume = 38
| year = 1971
| doi=10.2140/pjm.1971.38.69| doi-access = free
}}. The first of these graphs, {{math|G3}}, 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 into a sequence with the property that, for every finite set {{mvar|S}} of vertices, there are infinitely many vertices having {{mvar|S}} as their set of earlier neighbors. (Only the Rado graph has such a sequence.) He then defines {{math|Gi}} to be the induced subgraph of the Rado graph formed by removing the final vertex (in the sequence ordering) of every {{mvar|i}}-clique of the Rado graph.
With this construction, each graph {{math|Gi}} is an induced subgraph of {{math|Gi + 1}}, and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph {{math|Gi}} omits at least one vertex from each {{mvar|i}}-clique of the Rado graph, there can be no {{mvar|i}}-clique in {{math|Gi}}.
Universality
Any finite or countable {{mvar|i}}-clique-free graph {{mvar|H}} can be found as an induced subgraph of {{math|Gi}} by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in {{math|Gi}} match the set of earlier neighbors of the corresponding vertex in {{mvar|H}}. That is, {{math|Gi}} is a universal graph for the family of {{mvar|i}}-clique-free graphs.
Because there exist {{mvar|i}}-clique-free graphs of arbitrarily large chromatic number, the Henson graphs have infinite chromatic number. More strongly, if a Henson graph {{math|Gi}} is partitioned into any finite number of induced subgraphs, then at least one of these subgraphs includes all {{mvar|i}}-clique-free finite graphs as induced subgraphs.
Symmetry
Like the Rado graph, {{math|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 {{math|Gi}} when {{math|i > 3}}: for these graphs, every automorphism of the graph has more than one orbit.