Henson graph

In graph theory, the Henson graph $G i$ is an undirected infinite graph, the unique countable homogeneous graph that does not contain an $i$ -vertex clique but that does contain all $K i$ -free finite graphs as induced subgraphs. For instance, $G 3$ 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 \geq 3$ ) in 1971.[1] The first of these graphs, $G 3$ , 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 $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 $G i$ 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 $G i$ is an induced subgraph of $G i + 1$ , and the union of this chain of induced subgraphs is the Rado graph itself. Because each graph $G i$ omits at least one vertex from each $i$ -clique of the Rado graph, there can be no $i$ -clique in $G i$ .

Universality

Any finite or countable $i$ -clique-free graph $H$ can be found as an induced subgraph of $G i$ by building it one vertex at a time, at each step adding a vertex whose earlier neighbors in $G i$ match the set of earlier neighbors of the corresponding vertex in $H$ . That is, $G i$ 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 $G i$ 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

Like the Rado graph, $G 3$ 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 $G i$ when $i > 3$ : for these graphs, every automorphism of the graph has more than one orbit.[1]

gollark: Yes. This is possibly maybe insecure.

gollark: I probably need a better way to manage it than having people arbitrarily submit channel IDs.

gollark: I could add something which lets you connect to preapproved channels iff you are a server moderator and the channel is named "apionet" or something.

gollark: Currently yes.

gollark: It says `Jun 30 18:33:37 loki env[375]: WARNING 18:33:37 30/06/2021 Channel 828692487031750706 not found` a lot but nothing else.

References

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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[henson-1] 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.