# A note on the indivisibility of the Henson graphs

Kenneth Gill<EMAIL_ADDRESS>
(Date: October 30, 2023)

###### Abstract.

We show that in contrast to the Rado graph, the Henson graphs are not
computably indivisible.

††footnotetext: This work is part of the author’s Ph.D. dissertation at Penn
State University [Gil23].

##  1\. Introduction

The Rado graph is, up to graph isomorphism, the unique countable undirected
graph that satisfies the following property: if $A$ and $B$ are any finite
disjoint sets of vertices, there is a vertex not in $A$ or $B$ which is
connected to every member of $A$ and to no member of $B$. It is homogeneous
and universal for the class of finite graphs.

Our interest here lies with the closely related family of _Henson graphs_ ,
introduced by C. Ward Henson in 1971 [Hen71]. For each $n\geq 3$, the Henson
graph $H_{n}$ is up to isomorphism the unique countable graph which satisfies
the following property analogous to that characterizing the Rado graph: for
any finite disjoint sets of vertices $A$ and $B$, if $A$ does not contain a
copy of $K_{n-1}$, then there is a vertex $x\notin A\cup B$ connected to every
member of $A$ and to no member of $B$. (Here we write $K_{m}$ for the complete
graph on $m$ vertices.) The graph $H_{n}$ is homogeneous and universal for the
class of $K_{n}$-free finite graphs.

We presume familiarity with the basic terminology of computable structure
theory, as for example in the first chapter of [Mon21]. A structure
$\mathcal{S}$ is said to be _indivisible_ if for any presentation
$\mathcal{A}$ of $\mathcal{S}$ and any coloring $c$ of
$\operatorname{\mathrm{dom}}\mathcal{A}$ with finite range, there is a
monochromatic subset of $\operatorname{\mathrm{dom}}\mathcal{A}$ which induces
a substructure isomorphic to $\mathcal{S}$. We call the monochromatic subset
in question a _homogeneous set_ for $c$. $\mathcal{S}$ is _computably
indivisible_ if there is a homogeneous set computable from $\mathcal{A}$ and
$c$, for any presentation $\mathcal{A}$ and coloring $c$ of
$\operatorname{\mathrm{dom}}\mathcal{A}$.

For the rest of the paper, we fix a computable presentation of $H_{n}$ with
domain $\mathbb{N}$ and thus focus only on the coloring. Viewed as a structure
in the language of a single binary relation, the Rado graph is known to be
indivisible, and computably so (folklore). Each of the Henson graphs is also
indivisible. Henson himself proved that a weak form of indivisibility holds
for each $H_{n}$. Full indivisibility was first shown for $n=3$ by Komjáth and
Rödl [KR86], and then for all $n$ by El-Zahar and Sauer [ES89]. (A clarified
and corrected version of the proof of Komjáth and Rödl can be found in
[Gil23].) Work on the Ramsey theory of the Henson graphs has progressed beyond
vertex colorings; recently, Natasha Dobrinen has undertaken a deep study of
the structure of $H_{n}$ and shown that for each $n$, $H_{n}$ has finite big
Ramsey degrees, developing many novel techniques in the process [Dob20,
Dob22].

Our far more modest result concerns only vertex colorings and states that
unlike the Rado graph, none of the Henson graphs is computably indivisible:

######  Theorem 1.

Hn-noce For every $n\geq 3$, there is a computable 2-coloring of $H_{n}$ with
no c.e. homogeneous set.

This theorem naturally raises the question of how complicated a homogeneous
set for a coloring of $H_{n}$ can or must be. An analysis of the proof of the
indivisibility of $H_{3}$ by Komjáth and Rödl in [KR86] demonstrates that a
homogeneous set can always be computed in the first jump of the coloring. For
$H_{n}$ in general, the proof of El-Zahar and Sauer in [ES89] shows that the
$(2n-3)$rd jump of a coloring suffices to compute a homogeneous set. The
latter is a strictly worse upper bound for $n=3$, and it is currently unknown
whether a similar discrepancy exists for any $n\geq 4$. Where vertex colorings
of $H_{n}$ fall on the spectrum of coding vs. cone avoidance is another
intriguing question.

##  2\. Proof of the theorem

Write $x\in G$, for a graph $G$, to mean $x$ is a vertex of $G$. By abuse of
notation, if $V\subset G$ is any set of vertices, we will identify $V$ with
the induced subgraph of $G$ on $V$. Furthermore, we always identify natural
numbers with the elements of $H_{n}$ they encode via our fixed computable
presentation of $H_{n}$, and sets of naturals with the corresponding induced
subgraphs of $H_{n}$. If $A=\\{a_{1}<\cdots<a_{n}\\}$ and
$B=\\{b_{1}<\cdots<b_{n}\\}$ are two sets of vertices in a graph $G$, write
$A\simeq^{\ast}B$ if the map $a_{i}\mapsto b_{i}$ is an isomorphism of induced
subgraphs. If the vertices of $G$ are given some linear ordering, denote by
$G\\!\upharpoonright\\!m$ the induced subgraph of $G$ on its first $m$
vertices. If $x\in G$, let $G(x)$ denote the induced subgraph of $G$
consisting of the neighbors of $x$. A set of the form $G(x)$ is referred to as
a “neighbor set”. Let $\mathscr{T}_{n}$ be the set of finite $K_{n}$-free
simple connected graphs.

We will need two lemmas. The first is a consequence of the following theorem
of Jon Folkman, which appears as Theorem 2 in [Fol70]. For a graph $G$, let
$\delta(G)$ be the largest $n$ such that $G$ contains a subgraph isomorphic to
$K_{n}$.

######  Theorem 2 (Folkman).

Folkman For each $k>0$ and finite graph $F$, there is a finite graph $G$ such
that

  1. (a)

$\delta(G)=\delta(F)$, and

  2. (b)

for any partition of the vertices of $G$ as $G_{1}\sqcup\cdots\sqcup G_{k}$,
there is an $i$ such that $G_{i}$ contains a subgraph isomorphic to $F$.

Part (a) implies that $G$ is $K_{n}$-free if $F$ is.

######  Lemma 3.

fact1 For each $n$ and $k$, there is a $G\in\mathscr{T}_{n}$ which is not an
induced subgraph of $\bigcup_{i=1}^{k}H_{n}(x_{i})$ for any vertices
$x_{1},\dotsc,x_{k}\in H_{n}$. In particular, no finite union of neighbor sets
in $H_{n}$ can contain an isomorphic copy of $H_{n}$.

###### Proof.

By applying Folkman with $F=K_{n-1}$, there is a $K_{n}$-free $G$ such that
for every partition of $G$ into $k$ sets, at least one set contains a
$K_{n-1}$. Since a neighbor set in $H_{n}$ cannot contain a $K_{n-1}$, this
means that $G$ is not contained in any union of $k$ neighbor sets. ∎

Note that the graph $G$ can be found computably from $n$ and $k$ by a brute-
force search. The next fact is a restatement of Lemma 1 of [ES89]:

######  Lemma 4 (El-Zahar & Sauer).

fact2 Let $\Delta$ be a finite induced subgraph of $H_{n}$ with $d$ vertices.
Let $\Gamma$ be any member of $\mathscr{T}_{n}$ with $d+1$ vertices put in
increasing order such that $\Delta\simeq^{\ast}\Gamma\\!\upharpoonright\\!d$.
Then there are infinitely many choices of $x\in H_{n}$ such that
$\Delta\cup\\{x\\}\simeq^{\ast}\Gamma$.

###### Proof of Hn-noce.

The proof is by a finite injury priority argument. We build a computable
$c\colon H_{n}\to 2$, viewing $2$ as the set $\\{R,B\\}$ (red and blue), to
meet requirements

$\displaystyle
R_{e}\colon\left({\left\lvert{W_{e}}\right\rvert=\infty\land\left\lvert{c(W_{e})}\right\rvert=1}\right)\implies\text{\thref{fact2}
fails if $H_{n}$ is replaced with $W_{e}\subset H_{n}$}.$

These are given the priority order $R_{0}>R_{1}>R_{2}>\cdots$. We also define
a computable function $p$ in stages, where $p(x,s)$ is the planned color of
vertex $x$ at stage $s$, beginning with $p(x,0)=R$ (red) for all $x$. This
function will be used to keep track of vertices which requirements “reserve”
to be a certain color. Only one vertex will actually be colored at each stage,
starting with $c(0)=R$.

A requirement $R_{e}$ is said to be active at stage $s$ if $e\leq s$ and
$W_{e,s}$ contains at least one element that was enumerated after the most
recent stage in which $R_{e}$ was injured (to be explained below). If $R_{e}$
was never injured, we say it is active simply if $W_{e,s}\neq\emptyset$. Each
requirement $R_{e}$ will amass a finite list of vertices
$\\{x_{e}^{1},x_{e}^{2},\dotsc,x_{e}^{\ell}\\}$ in $W_{e}$ as its followers,
together with a target graph $\Gamma_{e}$ (also explained below). When a
follower $x_{e}^{m}$ is added, $R_{e}$ will set the function $p(x,s)$ for some
vertices $x\in H_{n}(x_{e}^{m})$; we say $R_{e}$ _reserves_ $x$ when it sets
$p(x,s)$. Weaker requirements cannot reserve vertices which are currently
reserved by stronger requirements. The followers, target graph, and
reservations of $R_{e}$ are canceled when $R_{e}$ is injured by a stronger
requirement. (Canceling a reserved vertex just means the vertex is no longer
considered to be reserved by $R_{e}$, and does not change the values of $p$ or
$c$.) We may as well assume each $W_{e}$ is monochromatic, and will refer to
$R_{e}$ as either a red or blue requirement accordingly.

We now detail the construction, and afterwards show that all requirements are
injured at most finitely often and are met. First, if no $R_{e}$ is active at
stage $s+1$ for $e\leq s$, set $p(x,s+1)=p(x,s)$ for all $x$, set
$c(s+1)=p(s+1,s+1)$, and end the stage. If a requirement $R_{e}$ is already
active at stage $s+1$ and has no follower, give it a follower $x_{e}^{1}$
which is any element of $W_{e,s}$ that was enumerated after the stage in which
$R_{e}$ was last injured, or otherwise any element of $W_{e,s}$ if $R_{e}$ was
never injured. Then for every $y\in H_{n}(x_{e}^{1})$ which is not currently
reserved by a stronger requirement and has not yet been colored, reserve $y$
by setting $p(y,s+1)$ to be the opposite color as $c(x_{e}^{1})$.

If $R_{e}$ is active and has a follower at stage $s+1$ but no target graph,
let its target graph be some $\Gamma_{e}\in\mathscr{T}_{n}$ which cannot be
contained in $k+1$ neighbor sets, where $k$ is the total number of all
followers of stronger currently active requirements. Such a $\Gamma_{e}$ may
be furnished by fact1. Order $\Gamma_{e}$ in such a way that each vertex
(except the first) is connected to at least one previous vertex.

Next, suppose that at least one requirement is active and has a follower and
target graph at stage $s+1$. Go through the following procedure for each such
$R_{e}$ in order from strongest to weakest. Let $m$ be the number of followers
of $R_{e}$ at stage $s$; we will at this point have
$\\{x_{e}^{1},\dotsc,x_{e}^{m}\\}\simeq^{\ast}\Gamma_{e}\\!\upharpoonright\\!m$.
Suppose there is some $x\in W_{e,s+1}$ with $x$ greater than the stage at
which $x_{e}^{m}$ was enumerated into $W_{e}$, and such that
$\\{x_{e}^{1},\dotsc,x_{e}^{m},x\\}\simeq^{\ast}\Gamma_{e}\\!\upharpoonright\\!(m+1)$.
If so, then give $R_{e}$ the new follower $x_{e}^{m+1}=x$, and for all $y\in
H_{n}(x_{e}^{m+1})$ with $y>s+1$ such that $y$ is not currently reserved by
any stronger requirement, have $R_{e}$ reserve $p(y,s+1)=R$ if $R_{e}$ is
blue, or $p(y,s+1)=B$ if $R_{e}$ is red. Injure all weaker requirements by
canceling their followers, target graphs, and reservations. After this is done
for all active $R_{e}$, end the stage by making $p(z,s+1)=p(z,s)$ for any $z$
for which $p(z,\cdot)$ was not modified earlier in the stage, and then letting
$c(s+1)=p(s+1,s+1)$. If instead no $x$ as above was found for any active
$R_{e}$, then set $p(x,s+1)=p(x,s)$ for all $x$, set $c(s+1)=p(s+1,s+1)$, and
end the stage. This completes the construction.

Each requirement only need accumulate a finite list of followers, so in
particular $R_{0}$ will only injure other requirements finitely many times.
After the last time a requirement is injured, it only injures weaker
requirements finitely often, so inductively we have that every requirement is
only injured finitely many times before acquiring its final list of followers
and target graph. And each requirement is satisfied: suppose (without loss of
generality) $R_{e}$ is blue. For each $i\geq 2$, the vertex $x_{e}^{i}$ is an
element of $H_{n}(x_{e}^{j})$ for some $j<i$, by assumption on how we have
ordered $\Gamma_{e}$. If $x_{e}^{j}$ was enumerated into $W_{e}$ at stage $s$,
then when this $x_{e}^{j}$ was chosen as a follower, $R_{e}$ reserved every
element of $H_{n}(x_{e}^{j})$ greater than $s$ by making its planned color
red—except for those vertices which were already reserved (to be blue) by
stronger (red) requirements. Therefore, if $x_{e}^{i}$ is blue, then since in
particular the construction requires $x_{e}^{i}>s$, we must have $x_{e}^{i}$ a
neighbor of some follower of a stronger (red) requirement. (We asked for
$x_{e}^{i}$ to be greater than the stage $t$ at which $x_{e}^{i-1}$ was
enumerated. Such an $x_{e}^{i}$ can be found for any $t$ by fact2.) So this
copy we are building of $\Gamma_{e}$ inside $W_{e}$ is contained entirely in a
union of neighbor sets of followers of stronger active requirements, except
possibly for $x_{e}^{1}$ which may lie outside of any such neighbor set. If
$R_{e}$ is never injured again, then the number $k$ of such followers never
changes again; it is the same as it was when the target graph $\Gamma_{e}$ was
chosen not to fit inside $k+1$ neighbor sets. The latter number is large
enough to also cover $x_{e}^{1}$, so that this copy of $\Gamma_{e}$ can never
be completed inside $W_{e}$, implying fact2 fails in $W_{e}$. ∎

Acknowledgements: This research was supported in part by NSF grant
DMS-1854107. I am extremely grateful to my thesis advisors Linda Brown
Westrick and Jan Reimann for their invaluable help, and also to Peter Cholak
for his comments on an earlier version of the proof of Hn-noce.

## References

  * [Dob20] Natasha Dobrinen  “The Ramsey theory of the universal homogeneous triangle-free graph” paper 2050012  In _J. Math. Logic_ 20.2, 2020  DOI: 10.1142/S0219061320500129
  * [Dob22] Natasha Dobrinen  “The Ramsey theory of Henson graphs”, 2022  arXiv:1901.06660
  * [ES89] Mohamed El-Zahar and Norbert Sauer  “The indivisibility of the homogeneous $K_{n}$-free graphs”  In _J. Comb. Theory_ 47, B, 1989, pp. 162–170
  * [Fol70] Jon Folkman  “Graphs with monochromatic complete subgraphs in every edge coloring”  In _SIAM J. Appl. Math._ 18.1, 1970, pp. 19–24
  * [Gil23] Kenneth Gill  “Two studies in complexity”, 2023
  * [Hen71] C. Henson  “A family of countable homogeneous graphs”  In _Pacific J. Math._ 38.1, 1971, pp. 69–83
  * [KR86] Peter Komjáth and Vojtèch Rödl  “Coloring of universal graphs”  In _Graphs and Combinatorics_ 2, 1986, pp. 55–60
  * [Mon21] Antonio Montalbán  “Computable structure theory: Within the arithmetic”, Perspectives in Logic  Cambridge University Press, 2021  DOI: 10.1017/9781108525749