# Strengthening Rödl’s theorem

Maria Chudnovsky
Princeton University, Princeton, NJ 08544

Alex Scott
Mathematical Institute, University of Oxford, Oxford OX2 6GG, UK

Paul Seymour
Princeton University, Princeton, NJ 08544

Sophie Spirkl
University of Waterloo, Waterloo, Ontario N2L3G1, Canada This material is
based upon work supported in part by the U. S. Army Research Office under
grant number W911NF-16-1-0404, and supported by NSF grant DMS 1763817.Research
supported by EPSRC grant EP/V007327/1.Supported by AFOSR grant
A9550-19-1-0187, and by NSF grant DMS-1800053.We acknowledge the support of
the Natural Sciences and Engineering Research Council of Canada (NSERC),
[funding reference number RGPIN-2020-03912]. Cette recherche a été financée
par le Conseil de recherches en sciences naturelles et en génie du Canada
(CRSNG), [numéro de référence RGPIN-2020-03912].

###### Abstract

What can be said about the structure of graphs that do not contain an induced
copy of some graph $H$? Rödl showed in the 1980s that every $H$-free graph has
large parts that are very dense or very sparse. More precisely, let us say
that a graph $F$ on $n$ vertices is $\varepsilon$-restricted if either $F$ or
its complement has maximum degree at most $\varepsilon n$. Rödl proved that
for every graph $H$, and every $\varepsilon>0$, every $H$-free graph $G$ has a
linear-sized set of vertices inducing an $\varepsilon$-restricted graph. We
strengthen Rödl’s result as follows: for every graph $H$, and all
$\varepsilon>0$, every $H$-free graph can be partitioned into a bounded number
of subsets inducing $\varepsilon$-restricted graphs.

##  1 Introduction

What can be said about the structure of graphs that do not contain an induced
copy of some graph $H$? In the 1980s, Rödl [5] showed that every $H$-free
graph has large parts that are very dense or very sparse. More precisely: for
a graph $G$, let us say $X\subseteq V(G)$ is weakly $\varepsilon$-restricted
if one of $G[X],\overline{G}[X]$ has at most $\varepsilon|X|^{2}$ edges; and
that $X$ is $\varepsilon$-restricted if one of the graphs $G[X]$,
$\overline{G}[X]$ has maximum degree at most $\varepsilon|X|$. Rödl [5] proved
the following:

###### 1.1

For every graph $H$, and all $\varepsilon>0$, there exists $\delta>0$ such
that for every $H$-free graph $G$, there is a weakly $\varepsilon$-restricted
set $X\subseteq V(G)$ with $|X|\geq\delta|G|$.

Every $\varepsilon$-restricted graph is weakly $\varepsilon$-restricted, and
every weakly $\epsilon$-restricted graph has an induced subgraph of linear
size that is $2\varepsilon$-restricted. Thus an equivalent version of Rödl’s
theorem is the following:

###### 1.2

For every graph $H$, and all $\varepsilon>0$, there exists $\delta>0$ such
that for every $H$-free graph $G$, there is an $\varepsilon$-restricted set
$X\subseteq V(G)$ with $|X|\geq\delta|G|$.

Rödl’s theorem is an easy consequence of Szemerédi’s regularity lemma, and has
proved extremely useful. For example, it is now a standard tool in approaching
the Erdős-Hajnal conjecture (see for instance the breakthrough paper [1],
where it was crucial, and much subsequent work). A proof of 1.2 not using the
regularity lemma (and consequently with much better constants) was given by
Fox and Sudakov [2].

In this paper, we are concerned with partitions of $H$-free graphs such that
every vertex class is either sparse or dense. It is easy to prove that
$H$-free graphs can be partitioned into a bounded number of weakly
$\varepsilon$-restricted subsets:

###### 1.3

For every graph $H$, and all $\varepsilon>0$, there is an integer $N$ such
that for every $H$-free graph $G$, there is a partition of $V(G)$ into at most
$N$ weakly $\varepsilon$-restricted subsets.

Indeed, it is enough to apply 1.3 repeatedly to partition most of the vertices
into weakly $\varepsilon/2$-restricted subsets, and then add the remaining
vertices into the largest set. (See Nikiforov [3] for a strengthening of 1.3.)

But what about partitions into sets that satisfy the stronger property of
being $\varepsilon$-restricted? This is much harder, and the main result of
this paper is the following:

###### 1.4

For every graph $H$, and all $\varepsilon>0$, there is an integer $N$ such
that for every $H$-free graph $G$, there is a partition of $V(G)$ into at most
$N$ $\varepsilon$-restricted subsets.

This is significantly stronger than 1.3.

Some remarks: first, it is sometimes necessary to use some
$\varepsilon$-restricted subsets of cardinality at most two, even in graphs
$G$ with $|G|$ large. For example, let $G$ be a star $K_{1,n}$ with $n$ large,
and let $\varepsilon<1/2$: then every $\varepsilon$-restricted subset
containing the centre of the star has cardinality at most two. (Note that this
is not the case for 1.3; for example, a large star is already weakly
$\epsilon$-restricted.)

Second, as far as we know, 1.4 does not follow from 1.3. There is a different
weakening of 1.4: under the same hypotheses, $V(G)$ is the union of at most
$N$ $\varepsilon$-restricted subsets (not necessarily pairwise disjoint).
Again, this does not imply 1.4 as far as we know, but in this case we do not
know an easy proof for it.

Third, our proof of 1.4 (and the proof in [4] of 2.2, which we will need to
apply) does not use the regularity lemma. Thus we anticipate that the number
$N$ in 1.4 is significantly smaller (as a function of $1/\varepsilon$) than
numbers that are produced via the regularity lemma, but we have not made an
estimate for it.

If $A,B\subseteq V(G)$ are disjoint, we say that $B$ is $\varepsilon$-sparse
to $A$ (in $G$) if every vertex in $B$ has at most $\varepsilon|A|$ neighbours
in $A$; and $B$ is $\varepsilon$-dense to $A$ if $B$ is $\varepsilon$-sparse
to $A$ in $\overline{G}$. The method of proof of 1.4 is via the following
statement:

###### 1.5

For every graph $H$, and all $\varepsilon,\eta,\theta>0$, there exists an
integer $N$ such that, for every $H$-free graph $G$, there is a partition of
$V(G)$ into nonempty sets
$A_{1},\ldots,A_{k},B_{1},\ldots,B_{k},C_{1},\ldots,C_{n}$, where
$k\leq|H|^{2}$ and $n\leq N$, such that:

  * •

$A_{1},\ldots,A_{k}$ and $C_{1},\ldots,C_{n}$ are $\varepsilon$-restricted
sets;

  * •

for $1\leq i\leq k$, $|B_{i}|\leq\eta|A_{i}|$;

  * •

for $1\leq i\leq k$, $B_{i}$ is either $\theta$-sparse or $\theta$-dense to
$A_{i}$.

We will prove this in section 2, and apply it to deduce 1.4 in section 3.

Graphs in this paper are finite and without loops or parallel edges. If $G$ is
a graph and $X\subseteq V(G)$, we denote the subgraph of $G$ induced on $X$ by
$G[X]$, and $\overline{G}$ denotes the complement graph of $G$. If $G,H$ are
graphs, we say that $G$ is $H$-free if no induced subgraph of $G$ is
isomorphic to $H$.

##  2 Proving the main lemma

In this section we prove 1.5. Let $A,B\subseteq V(G)$ be disjoint, and let
$c,\varepsilon>0$. We say that $(A,B)$ is $(c,\varepsilon)$-full if for all
$A^{\prime}\subseteq A$ with $|A^{\prime}|\geq c|A|$ and $B^{\prime}\subseteq
B$ with $|B^{\prime}|\geq c|B|$, the number of edges between
$A^{\prime},B^{\prime}$ is at least
$\varepsilon|A^{\prime}|\cdot|B^{\prime}|$. Similarly, $(A,B)$ is
$(c,\varepsilon)$-empty if it is $(c,\varepsilon)$-full in the complement
graph. Thus if $(A,B)$ is $(c,\varepsilon)$-full, and $A^{\prime}\subseteq A$
and $B^{\prime}\subseteq B$ with $|A^{\prime}|/|A|,|B^{\prime}|/|B|\geq
c^{\prime}>c$ then $(A^{\prime},B^{\prime})$ is
$(c/c^{\prime},\varepsilon)$-full.

We need a version of a standard result called the “embedding lemma”:

###### 2.1

Let $G,H$ be graphs, let $0<\varepsilon\leq 1/2$, and let $A_{v}\;(v\in V(H))$
be pairwise disjoint nonempty subsets of $V(G)$, such that for all distinct
$u,v\in V(H)$, if $u,v$ are adjacent in $H$ then $(A_{u},A_{v})$ is
$(\varepsilon^{|H|},\varepsilon)$-full, and if $u,v$ are nonadjacent then
$(A_{u},A_{v})$ is $(\varepsilon^{|H|},\varepsilon)$-empty. Then for each
$v\in V(H)$ there exists $a_{v}\in A_{v}$ such that the map sending $v$ to
$a_{v}$ for each $v\in V(H)$ is an isomorphism from $H$ to an induced subgraph
of $G$.

Proof. We proceed by induction on $|H|$. If $|H|\leq 1$ the result is true, so
we assume $|H|>1$. Let $v\in V(H)$, and let $N,M$ be the sets of neighbours of
$v$ in $H$ and in $\overline{H}$ respectively. Let $c=\varepsilon^{|H|}$. For
each $u\in N$ there are fewer than $c|A_{v}|$ vertices in $A_{v}$ with fewer
than $\varepsilon|A_{u}|$ neighbours in $A_{u}$, since $(A_{v},A_{u})$ is
$(c,\varepsilon)$-full; and similarly for each $u\in M$ there are fewer than
$c|A_{v}|$ vertices in $A_{v}$ with fewer than $\varepsilon|A_{u}|$ non-
neighbours in $A_{u}$. Since $(|H|-1)c<1$ (because $\varepsilon\leq 1/2$),
there exists $a_{v}\in A_{v}$ with at least $\varepsilon|A_{u}|$ neighbours in
$A_{u}$ for each $u\in N$, and at least $\varepsilon|A_{u}|$ non-neighbours in
$A_{u}$ for each $u\in M$. For each $u\in N$ let $B_{u}$ be the set of
neighbours of $v\in A_{u}$, and for each $u\in M$ let $B_{u}$ be the set of
non-neighbours of $v$ in $A_{u}$. Thus each $B_{u}\neq\emptyset$, since
$|B_{u}|\geq\varepsilon|A_{u}|$. Let $H^{\prime}$ be obtained from $H$ by
deleting $v$.

Thus for all distinct $u,w\in V(H^{\prime})$, if $u,w$ are adjacent then
$(B_{u},B_{w})$ is $(c\varepsilon^{-1},\varepsilon)$-full, and if $u,w$ are
nonadjacent then $(B_{u},B_{w})$ is $(c\varepsilon^{-1},\varepsilon)$-empty.
From the inductive hypothesis, for each $u\in V(H^{\prime})$ there exists
$a_{u}\in A_{u}$ such that the map sending $u$ to $a_{u}$ for each $u\in
V(H^{\prime})$ is an isomorphism from $H^{\prime}$ to an induced subgraph of
$G$. But then the theorem holds. This proves 2.1.

The following is proved in [4]:

###### 2.2

For all $c,\varepsilon,\tau>0$ with $\varepsilon<\tau\leq 8/9$, there exists
$\gamma>0$ with the following property. Let $G$ be a bipartite graph with a
bipartition $(A,B)$, with at least $\tau|A|\cdot|B|$ edges and with
$A,B\neq\emptyset$. Then there exist $A^{\prime}\subseteq A$ and
$B^{\prime}\subseteq B$ with $|A^{\prime}|/|A|,|B^{\prime}|/|B|\geq\gamma$,
such that $(A^{\prime},B^{\prime})$ is $(c,\varepsilon)$-full.

Now we can prove 1.5, which we restate:

###### 2.3

For every graph $H$, and all $0<\varepsilon,\eta,\theta<1$, there exists an
integer $N$ such that, for every $H$-free graph $G$, there is a partition of
$V(G)$ into nonempty sets
$A_{1},\ldots,A_{k},B_{1},\ldots,B_{k},C_{1},\ldots,C_{n}$, where
$k\leq|H|^{2}$ and $n\leq N$, such that:

  * •

$A_{1},\ldots,A_{k}$ and $C_{1},\ldots,C_{n}$ are $\varepsilon$-restricted
sets;

  * •

for $1\leq i\leq k$, $|B_{i}|\leq\eta|A_{i}|$;

  * •

for $1\leq i\leq k$, $B_{i}$ is either $\theta$-dense or $\theta$-sparse to
$A_{i}$.

Proof. We may assume that $\varepsilon,\eta,\theta<1/3$, by reducing them if
necessary. For each $\varepsilon^{\prime}>0$, let
$\delta_{\varepsilon^{\prime}}$ satisfy 1.2 with $\varepsilon,\delta$ replaced
by $\varepsilon^{\prime},\delta_{\varepsilon^{\prime}}$.

Let $c_{|H|}=(\theta/4)^{|H|}$. For $m=|H|-1,|H|-2,\ldots,0$ in turn:

  * •

for $i=m,m-1,\ldots,1$ in turn, let
$\Gamma{(m,i)}=\gamma_{m,i+1}\Gamma{(m,i+1)}$ (or $1$ if $i=m$); and choose
$\gamma_{m,i}$ such that 2.2 holds, with $c,\varepsilon,\tau,\gamma>0$
replaced by $\Gamma{(m,i)}c_{m+1}/3,\theta/4,\theta/2,\gamma_{m,i}$
respectively (by decreasing $\gamma_{m,i}$ if necessary we may assume that
$\gamma_{m,i}\leq 1/3$ and $\gamma_{m,i}\leq\gamma_{m,i+1}$);

  * •

let $c_{m}=\gamma_{m,0}c_{m+1}$;

  * •

let $\varepsilon_{m}=3^{|H|-m}\varepsilon$.

For each $\gamma>0$, let $n_{\gamma}$ be the smallest nonnegative integer that
satisfies $(1-\delta_{\varepsilon})^{n_{\gamma}}\leq\gamma$. For $1\leq
m\leq|H|$, define $k_{m}=m(m-1)/2$ and

$\ell_{m}=\sum_{1\leq i\leq m}n_{q_{i}},$

where $p_{i}=\varepsilon_{i+1}\Gamma{(i,0)}$ and
$q_{i}=\eta\delta_{p_{i}}\Gamma{(i,0)}/2$. Let $N=\ell_{|H|}+k_{|H|}+|H|$; we
claim that $N$ satisfies the theorem.

Let $G$ be $H$-free.

(1) For all $\gamma$ with $0<\gamma<1$, and for every $X\subseteq V(G)$, there
is a partition of $X$ into at most $n_{\gamma}+1$ sets, so that one of them
has cardinality at most $\gamma|X|$ and the others are all
$\varepsilon$-restricted.

Let $X\subseteq V(G)$. Choose an $\varepsilon$-restricted set $A_{1}\subseteq
X$ with $|A_{1}|\geq\delta_{\varepsilon}|X|$; and inductively for each $i>1$,
choose an $\varepsilon$-restricted set $A_{i}\subseteq
X\setminus(A_{1}\cup\cdots\cup A_{i-1})$ with
$|A_{i}|\geq\delta_{\varepsilon}|X\setminus(A_{1}\cup\cdots\cup A_{i-1})|$. It
follows that $|X\setminus(A_{1}\cup\cdots\cup
A_{i-1})|\leq(1-\delta_{\varepsilon})^{i}|X|$ for each $i\geq 0$, and in
particular when $i=n_{\gamma}$. This proves (1).

Let $V(H)$ have vertices $v_{1},\ldots,v_{|H|}$. For $0\leq m\leq|H|$, we are
interested in partitions of $V(G)$ into sets
$A_{1},\ldots,A_{k},B_{1},\ldots,B_{k},C_{1},\ldots,C_{\ell}$,
$D_{1},\ldots,D_{m}$, and $E$, with the following properties:

  * •

$k\leq k_{m}$ and $\ell\leq\ell_{m}$;

  * •

$A_{1},\ldots,A_{k},C_{1},\ldots,C_{\ell}$ and $D_{1},\ldots,D_{m}$ are all
nonempty;

  * •

$A_{1},\ldots,A_{k},C_{1},\ldots,C_{\ell}$ are $\varepsilon$-restricted;

  * •

for $1\leq i\leq k$, $|B_{i}|\leq\eta|A_{i}|$, and $B_{i}$ is either
$(1-\theta)$-dense or $(1-\theta)$-sparse to $A_{i}$;

  * •

$D_{1},\ldots,D_{m}$ are $\varepsilon_{m}$-restricted;

  * •

for $1\leq i<j\leq m$, if $v_{i},v_{j}$ are adjacent in $H$ then
$(D_{i},D_{j})$ is $(c_{m},\theta/4)$-full, and if $v_{i},v_{j}$ are
nonadjacent then $(D_{i},D_{j})$ is $(c_{m},\theta/4)$-empty;

  * •

$|E|\leq(\eta/2)\min(|D_{1}|,\ldots,|D_{m}|)$ if $m>0$.

Let us call such a thing a partition of type $(k,\ell,m)$. To make clear which
set plays which role in the partition, we will write them as:

$(A_{1},B_{1}),\ldots,(A_{k},B_{k})$ $C_{1},\ldots,C_{\ell}$
$D_{1},\ldots,D_{m}$ $E.$

Choose such a partition, of type $(k,\ell,m)$ say, with $m\leq|H|$ maximum.
(This is possible, since $G$ admits a partition of type $(0,0,0)$, setting
$E=V(G)$.) Suppose that $E\neq\emptyset$.

Since $c_{|H|}=(\theta/4)^{|H|}$, and $D_{1},\ldots,D_{m}$ are nonempty, it
follows from 2.1 that $m\leq|H|-1$. For $1\leq i\leq m$, choose
$E_{i}\subseteq E$ such that $E_{i}$ is $\theta/2$-sparse to $D_{i}$ if
$v_{m+1},v_{i}$ are adjacent in $H$, and $E_{i}$ is $\theta/2$-dense to
$D_{i}$ if $v_{m+1}$ are nonadjacent, with $E_{1}\cup\cdots\cup E_{m}$
maximal. Let $E_{0}=E\setminus(E_{1}\cup\cdots\cup E_{m})$. Thus for $1\leq
i\leq m$, $E_{0}$ is $(1-\theta/2)$-dense to $D_{i}$ if $v_{m+1},v_{i}$ are
adjacent in $H$, and $E_{i}$ is $(1-\theta/2)$-sparse to $D_{i}$ if
$v_{m+1},v_{i}$ are nonadjacent.

We recall that $|E|\leq\eta\min(|D_{1}|,\ldots,|D_{m})$, and since
$E\neq\emptyset$, it follows that $|D_{i}|\geq\eta^{-1}>1$ for $1\leq i\leq
m$. Thus $\lfloor|D_{i}|/2\rfloor\geq|D_{i}|/3$, for $1\leq i\leq m$.

Let $\varepsilon^{\prime}=\varepsilon_{m+1}\Gamma{(m,0)}$, and let
$\delta^{\prime}=\delta_{\varepsilon^{\prime}}$. From 1.2 there exists
$F\subseteq E_{0}$ with $|F|\geq\delta^{\prime}|E|$ such that $F$ is
$\varepsilon^{\prime}$-restricted. Let $F_{0}=F$, and for $1\leq i\leq m$
define $F_{i}\subseteq F_{i-1}$ with $|F_{i}|\geq\gamma_{m,i}|F_{i-1}|$, and
$H_{i}\subseteq E_{i}$ with $|D_{i}|/2\geq|H_{i}|\geq\gamma_{m,i}|D_{i}|$, as
follows. Let us assume that $v_{m+1},v_{i}$ are adjacent (if they are non-
adjacent, the construction is the same in the complement). Thus $F_{i-1}$ is
$(1-\theta/2)$-dense to $D_{i}$. (We remark that this is a weak assertion: it
means that each vertex in $F_{i-1}$ has at most $(1-\theta/2)|D_{i}|$ non-
neighbours in $D_{i}$.) From the definition of $\gamma_{m,i}$, there exist
$F_{i}\subseteq F_{i-1}$ and $H_{i}^{\prime}\subseteq D_{i}$, with
$|F_{i}|\geq\gamma_{m,i}|F_{i-1}|$ and
$|H_{i}^{\prime}|\geq\gamma_{m,i}|D_{i}|$, such that $(F_{i},H_{i}^{\prime})$
is $(\Gamma{(m,i)}c_{m+1}/3,\theta/4)$-full. Let $H_{i}\subseteq
H_{i}^{\prime}$ of cardinality
$\min(|H_{i}^{\prime}|,\lfloor|D_{i}|/2\rfloor)$. In particular,
$|H_{i}|\geq\gamma_{m,i}|F_{i-1}|$, since $\gamma_{m,i}\leq 1/3$. Also,
$|H_{i}|\geq|H_{i}^{\prime}|/3$, and so $(F_{i},H_{i})$ is
$(\Gamma{(m,i)}c_{m+1},\theta/4)$-full. Thus for $1\leq i\leq m$,
$(F_{i},H_{i})$ is $(\Gamma{(m,i)}c_{m+1},\theta/4)$-full if $v_{i},v_{m+1}$
are adjacent, and $(\Gamma{(m,i+1)}c_{m+1},\theta/4)$-empty if $v_{i},v_{m+1}$
are non-adjacent. Also

$|F_{m}|\geq\Gamma{(m,m-1)}|F_{m-1}|\geq\cdots\geq\Gamma{(m,i)}|F_{i}|.$

Consequently $(F_{m},H_{i})$ is $(c_{m+1},\theta/4)$-full if $v_{i},v_{m+1}$
are adjacent, and $(c_{m+1},\theta/4)$-empty if $v_{i},v_{m+1}$ are non-
adjacent.

Now $|E|\leq\eta\min(|D_{1}|,\ldots,|D_{m}|)$. Let
$\eta^{\prime}=\eta\delta^{\prime}\Gamma{(m,0)}/2$. By (1) there exist at most
$n_{\eta^{\prime}}$ pairwise disjoint nonempty $\varepsilon$-restricted
subsets of $E_{0}\setminus F_{m}$ such that their union ($J$ say) satisfies
$|E_{0}\setminus(F_{m}\cup J)|\leq\eta^{\prime}|E_{0}\setminus F_{m}|$. Let
these sets be $J_{1},\ldots,J_{n}$ say. Let $H_{m+1}=F_{m}$. We claim that the
sets

$(A_{1},B_{1}),\ldots,(A_{k},B_{k}),(D_{1}\setminus
H_{1},E_{1}),\ldots,(D_{m}\setminus H_{m},E_{m})$
$C_{1},\ldots,C_{\ell},J_{1},\ldots,J_{n}$ $H_{1},\ldots,H_{m},H_{m+1}$
$E_{0}\setminus(F_{m}\cup J)$

form a partition of $V(G)$ of type $(k+m,\ell+n,m+1)$. To show this, we must
check the following conditions:

  * •

Is it true that $k+m\leq k_{m+1}$ and $\ell+n\leq\ell_{m+1}$? The first holds
since $k\leq k_{m}$ and $k_{m+1}=k_{m}+m$; and the second holds since
$\ell+n\leq\ell_{m}+n_{\eta^{\prime}}=\ell_{m+1}$.

  * •

Is it true that $A_{1},\ldots,A_{k},D_{1}\setminus H_{1},\ldots,D_{m}\setminus
H_{m},C_{1},\ldots,C_{\ell},J_{1},\ldots,J_{n},H_{1},\ldots,H_{m}$ and $F_{m}$
are all nonempty? Certainly $A_{1},\ldots,A_{k},C_{1},\ldots,C_{\ell}$ are
nonempty from their definition, and so are $J_{1},\ldots,J_{n}$. For $1\leq
i\leq m$, since $|E|\leq\eta|D_{i}|$ and $E\neq\emptyset$, it follows that
$|D_{i}|\geq 2$; and so $D_{i}\setminus H_{i}\neq\emptyset$, since
$|H_{i}|\leq|D_{i}|/2$. Also
$|H_{i}|=\min(|H_{i}^{\prime}|,\lfloor|D_{i}|/2\rfloor)$, and
$|H_{i}^{\prime}|\geq\gamma_{m,i}|D_{i}|>0$, and $\lfloor|D_{i}|/2\rfloor>0$,
so $H_{i}$ is nonempty. Finally, $|F_{m}|\geq\Gamma{(m,0)}|F_{0}|$, and
$|F_{0}|\geq\delta^{\prime}|E|>0$; so $F_{m}\neq\emptyset$.

  * •

Is it true that $A_{1},\ldots,A_{k},D_{1}\setminus H_{1},\ldots,D_{m}\setminus
H_{m},C_{1},\ldots,C_{\ell},J_{1},\ldots,J_{n}$ are $\varepsilon$-restricted?
$A_{1},\ldots,A_{k}$, $C_{1},\ldots,C_{\ell}$ and $J_{1},\ldots,J_{n}$ are
$\varepsilon$-restricted from their definition. For $1\leq i\leq m$, $D_{i}$
is $\varepsilon_{m}$-restricted, and since $|H_{i}|\leq|D_{i}|/2$, it follows
that $D_{i}\setminus H_{i}$ is $2\varepsilon_{m}$-restricted and hence
$\varepsilon$-restricted.

  * •

Is it true that for $1\leq i\leq k$, $|B_{i}|\leq\eta|A_{i}|$, and $B_{i}$ is
either $(1-\theta)$-dense or $(1-\theta)$-sparse to $A_{i}$; and for $1\leq
i\leq m$, $|E_{i}|\leq\eta|D_{i}\setminus H_{i}|$, and $E_{i}$ is either
$(1-\theta)$-dense or $(1-\theta)$-sparse to $D_{i}\setminus H_{i}$? The first
is true from their definition. For the second, let $1\leq i\leq m$. Then
$|E_{i}|\leq|E|\leq\eta|D_{i}|$. Assume that $v_{i},v_{m+1}$ are adjacent (the
other case is similar). Then $E_{i}$ is $\theta/2$-sparse to $D_{i}$, and
since $|H_{i}|\leq|D_{i}|/2$, it follows that $E_{i}$ is is $\theta$-sparse to
$D_{i}\setminus H_{i}$.

  * •

Is it true that $H_{1},\ldots,H_{m},H_{m+1}$ are
$\varepsilon_{m+1}$-restricted? For $1\leq i\leq m$, $D_{i}$ is
$\varepsilon_{m}$-restricted, and since $|H_{i}|\geq|D_{i}|/3$, $H_{i}$ is
$3\varepsilon_{m}$-restricted and hence $\varepsilon_{m+1}$-restricted. Also
$F$ is $\varepsilon^{\prime}$-restricted, and $|F_{m}|\geq\Gamma{(m,0)}|F|$;
and so $F_{m}$ is $\varepsilon^{\prime}/\Gamma{(m,0)}$-restricted and hence
$\varepsilon_{m+1}$-restricted.

  * •

Is it true that for $1\leq i<j\leq m+1$, if $v_{i},v_{j}$ are adjacent in $H$
then $(H_{i},H_{j})$ is $(c_{m+1},\theta/4)$-full, and if $v_{i},v_{j}$ are
nonadjacent then $(H_{i},H_{j})$ is $(c_{m+1},\theta/4)$-empty? If $j=m+1$, we
already saw that $(F_{m},H_{i})$ is $(c_{m+1},\theta/4)$-full if
$v_{i},v_{m+1}$ are adjacent, and $(c_{m+1},\theta/4)$-empty if
$v_{i},v_{m+1}$ are non-adjacent. So we may assume that $j\leq m$. Assume that
$v_{i},v_{j}$ are adjacent (the other case is similar). Then $(D_{i},D_{j})$
is $(c_{m},\theta/4)$-full, and since $|H_{i}|\geq\gamma_{m,i}|F_{i-1}|$ and
$|H_{j}|\geq\gamma_{m,j}|F_{j-1}|$, and
$\gamma_{m,i},\gamma_{m,j}\geq\gamma_{m,0}$, and $c_{m}=\gamma_{m,0}c_{m+1}$,
it follows that $(H_{i},H_{j})$ is $(c_{m+1},\theta/4)$-full.

  * •

Is it true that $|E_{0}\setminus(F_{m}\cup
J)|\leq(\eta/2)\min(|H_{1}|,\ldots,|H_{m}|,|H_{m+1}|)$? From the choice of
$J$, $|J|\geq(1-\eta)|E_{0}\setminus F_{m}|$, and so

$|E_{0}\setminus(F_{m}\cup J)|\leq\eta^{\prime}|E_{0}\setminus
F_{m}|\leq|E_{0}|/3.$

But $|E_{0}|\leq|E|\leq(\eta/2)|D_{i}|\leq(3\eta/2)|H_{i}|$, and so
$|E_{0}\setminus(F_{m}\cup J)|\leq(\eta/2)|H_{i}|$, for $1\leq i\leq m$.
Finally, to show that $|E_{0}\setminus(F_{m}\cup J)|\leq(\eta/2)|H_{m+1}|$,
observe that

$|E_{0}\setminus(F_{m}\cup
J)|\leq\eta^{\prime}|E_{0}|\leq\eta^{\prime}|E|\leq\eta^{\prime}|F|/\delta^{\prime}=(\eta/2)\Gamma{(m,0)}|F|\leq(\eta/2)|F_{m}|.$

This proves that $G$ admits a partition of type $(k+m,\ell+n,m+1)$, contrary
to the choice of $m$. Hence $E=\emptyset$. So $V(G)$ can be partitioned into
the pairs $A_{i}\cup B_{i}$ with $B_{i}\neq\emptyset$, and the
$\varepsilon$-restricted sets $C_{1},\ldots,C_{\ell},D_{1},\ldots,D_{m}$, and
the $\varepsilon$-restricted sets $A_{i}$ with $1\leq i\leq k$ for which
$B_{i}=\emptyset$. This proves 1.5.

##  3 Deducing the theorem

We need the following lemma (logarithms in this paper are to base $e$):

###### 3.1

Let $\varepsilon>0$ with $\varepsilon\leq 1/16$. Let $G$ be a graph, and let
$A,B$ be nonempty disjoint subsets of $V(G)$, such that $B$ is
$\varepsilon$-sparse to $A$. Let $p$ be an integer with
$\log(2|B|)/\varepsilon\leq p\leq|A|/12$. Then there exists $P\subseteq A$
with $|P|=p$, such that $P$ is $2\varepsilon$-sparse to $B$, and $B$ is
$12\varepsilon$-sparse to $P$.

Proof. We may assume that some vertex in $B$ has a neighbour in $A$, because
otherwise the result holds, and since $\varepsilon\leq 1/16$ it follows that
$|A|\geq 16$. Let $Q$ be the set of vertices in $A$ with fewer than
$2\varepsilon|B|$ neighbours in $B$, and let $q=|Q|$. There are at least
$(|A|-q)(2\varepsilon|B|)$ and at most $\varepsilon|A|\cdot|B|$ edges between
$A$ and $B$, and so $q\geq|A|/2\geq 8$. Let $k=\lceil 12\varepsilon p\rceil$.

Let $u_{1},\ldots,u_{2p}\in Q$, not necessarily all distinct. Let $y$ be the
number of subsets of $Q$ of cardinality $p$ that contain all of
$u_{1},\ldots,u_{2p}$ (note that $p\leq|A|/12\leq q$); and for each $v\in B$,
let $z(v)$ be the number of subsets $I\subseteq\\{1,\ldots,2p\\}$ of
cardinality $k$ such that $u_{i}$ is adjacent to $v$ for all $i\in I$ (note
that $k=\lceil 12\varepsilon p\rceil\leq\lceil 2p\rceil=2p$).

(1) There is a choice of $u_{1},\ldots,u_{2p}$ with $y=0$ and $z(v)=0$ for all
$v\in B$.

Choose $u_{1},\ldots,u_{2p}\in Q$ uniformly and independently at random. Let
$\overline{y}$ be the expectation of $y$, and $\overline{z}(v)$ the
expectation of each $z(v)$. We will show that $\overline{y}<1/2$, and
$\overline{z}(v)\leq 1/(2|B|)$ for each $v\in B$, from which the claim
follows. First,

$\overline{y}=\binom{q}{p}\left(\frac{p}{q}\right)^{2p}\leq\frac{q^{p}}{p!}\left(\frac{p}{q}\right)^{2p},$

and by Stirling’s approximation, $p!\geq(p/e)^{p}$; so

$\overline{y}\leq\left(\frac{eq}{p}\right)^{p}\left(\frac{p}{q}\right)^{2p}=\left(\frac{ep}{q}\right)^{p}.$

Since $p\leq|A|/12$ and $q\geq|A|/2$, it follows that $ep/q<1/2$, and so
$\overline{y}<1/2$.

For $v\in B$, since $v$ has at most $\varepsilon|A|\leq 2\varepsilon|Q|$
neighbours in $Q$, it follows that

$\overline{z}(v)\leq\binom{2p}{k}(2\varepsilon)^{k}\leq\frac{(2p)^{k}}{k!}(2\varepsilon)^{k}.$

Since $k!\geq(k/e)^{k}$, we deduce that

$\overline{z}(v)\leq\left(\frac{2ep}{k}\right)^{k}(2\varepsilon)^{k}=\left(\frac{4e\varepsilon
p}{k}\right)^{k}\leq\left(\frac{e}{3}\right)^{k}\leq\left(\frac{e}{3}\right)^{12\varepsilon
p}$

since $k\geq 12\varepsilon p$ and $e<3$. From the hypothesis,
$\log(2|B|)\leq\varepsilon p\leq 12\varepsilon p\log(3/e)$, and so
$\left(e/3\right)^{12\varepsilon p}\leq 1/(2|B|)$.

Hence $\overline{z}(v)\leq 1/(2|B|)$, and so the sum of $\overline{y}$ and all
the $\overline{z}(v)\;(v\in B)$ is less than one. This proves (1).

Choose $u_{1},\ldots,u_{2p}$ as in (1). Since $y=0$ it follows that
$|\\{u_{1},\ldots,u_{2p}\\}|\geq p$; choose
$P\subseteq\\{u_{1},\ldots,u_{2p}\\}$ with $|P|=p$. Each vertex in $P$ has at
most $2\varepsilon|B|$ neighbours in $B$, since $P\subseteq Q$; and each $v\in
B$ has at most $12\varepsilon p$ neighbours in $P$, since $z(v)=0$. This
proves 3.1.

Let $G$ be a graph, let $k\geq 1$ be an integer, and let $\varepsilon>0$. A
$(k,\varepsilon)$-path-partition of $G$ is a sequence
$(W_{0},W_{1},\ldots,W_{k})$ of subsets of $V(G)$, pairwise disjoint and with
union $V(G)$, such that for $0\leq i\leq k-1$:

  * •

$W_{i}$ is $\varepsilon$-restricted;

  * •

$|W_{i+1}\cup\cdots\cup W_{k}|\leq|W_{i}|/12$;

  * •

$W_{i+1}\cup\cdots\cup W_{k}$ is either $\varepsilon/12$-sparse or
$\varepsilon/12$-dense to $W_{i}$.

If we are trying to partition $V(G)$ into $\varepsilon$-restricted sets, and
$G$ admits a $(k,\varepsilon)$-path-partition, then all but one of its sets
are $\varepsilon$-restricted; the difficulty lies in handling the final set
$W_{k}$.

###### 3.2

Let $0<\varepsilon\leq 1/3$, and let $G$ be a graph admitting a
$(k,\varepsilon/2)$-path-partition $(W_{0},\ldots,W_{k})$, where $k=\lceil
2/\varepsilon\rceil$. Then $V(G)$ can be partitioned into at most
$9217\varepsilon^{-2}$ $\varepsilon$-restricted subsets.

Proof. Let $p=|W_{k}|$, and $\varepsilon^{\prime}=\varepsilon/24$.

(1) We may assume that $\log(2kp)\leq\varepsilon^{\prime}p$.

Suppose not; then $\log(2kp)>\varepsilon p/24$, and since $k\leq
4/\varepsilon$, it follows that

$8p/\varepsilon\geq 2kp>e^{\varepsilon p/24}\geq(\varepsilon p/24)^{3}/6,$

(because $e^{x}\geq x^{3}/3!$ for all $x>0$). We deduce that $p^{2}\leq
48(24^{3}/\varepsilon^{4})$, and so $p<815/\varepsilon^{2}$. Since
$\varepsilon\leq 1/3$ and therefore $k\leq 2/\varepsilon+1\leq
1/\varepsilon^{2}$, the theorem holds, because $V(G)$ is the union of
$W_{0},\ldots,W_{k-1}$ and the $p$ singletons $\\{v\\}\;(v\in W_{k})$. This
proves (1).

(2) For $0\leq i\leq k$, there exists $C_{i}\subseteq W_{i}$ with $|W_{i}|=p$,
such that for $0\leq i\leq k-1$, either

  * •

$C_{i}$ is $2\varepsilon^{\prime}$-sparse to $C_{i+1}\cup\cdots\cup C_{k}$,
and $C_{i+1}\cup\cdots\cup C_{k}$ is $12\varepsilon^{\prime}$-sparse to
$C_{i}$, or

  * •

$C_{i}$ is $2\varepsilon^{\prime}$-dense to $C_{i+1}\cup\cdots\cup C_{k}$, and
$C_{i+1}\cup\cdots\cup C_{k}$ is $12\varepsilon^{\prime}$-dense to $C_{i}$.

The choice of $C_{i}$ is inductive, as follows: let $C_{k}=W_{k}$, and now
suppose that $0\leq i\leq k-1$, and $C_{i+1},\ldots,C_{k}$ are defined. Let
$B=C_{i+1}\cup\cdots\cup C_{k}$. Thus $|B|=(k-i)p$ and $B$ is either
$\varepsilon^{\prime}$-sparse or $\varepsilon^{\prime}$-dense to $W_{i}$
(because $(W_{0},\ldots,W_{k})$ is a $(k,12\varepsilon^{\prime})$-path-
partition). Moreover,

$p\leq|\bigcup_{i<j\leq k}W_{j}|\leq|W_{i}|/12.$

Suppose first that $B$ is $\varepsilon^{\prime}$-sparse to $W_{i}$. By (1),
$\log(2kp)\leq\varepsilon^{\prime}p$. By 3.1, taking $A=W_{i}$, and replacing
$\varepsilon$ by $\varepsilon^{\prime}$, we deduce that there exists
$C_{i}\subseteq W_{i}$ with $|C_{i}|=p$, such that $C_{i}$ is
$2\varepsilon^{\prime}$-sparse to $B$, and $B$ is
$12\varepsilon^{\prime}$-sparse to $C_{i}$. Similarly, if $B$ is
$\varepsilon^{\prime}$-dense to $W_{i}$, then 3.1 applied in $\overline{G}$
implies that there exists $C_{i}\subseteq W_{i}$ with $|C_{i}|=p$, such that
$C_{i}$ is $2\varepsilon^{\prime}$-dense to $B$, and $B$ is
$12\varepsilon^{\prime}$-dense to $C_{i}$. In either case, this completes the
inductive definition of $C_{0},\ldots,C_{k}$, and so proves (2).

Now for $0\leq i\leq k-1$, either $C_{i}$ is $2\varepsilon^{\prime}$-sparse to
$C_{i+1}\cup\cdots\cup C_{k}$, or $2\varepsilon^{\prime}$-dense to
$C_{i+1}\cup\cdots\cup C_{k}$; choose $I\subseteq\\{0,\ldots,k-1\\}$ with
$|I|\geq k/2$ such that either $C_{i}$ is $2\varepsilon^{\prime}$-sparse to
$C_{i+1}\cup\cdots\cup C_{k}$ for all $i\in I$, or $C_{i}$ is
$2\varepsilon^{\prime}$-dense to $C_{i+1}\cup\cdots\cup C_{k}$ for all $i\in
I$. Let $C=\bigcup_{i\in I\cup\\{k\\}}C_{i}$.

(3) $C$ is $\varepsilon$-restricted.

To see this, suppose first that $C_{i}$ is $2\varepsilon^{\prime}$-sparse to
$C_{i+1}\cup\cdots\cup C_{k}$ for all $i\in I$. Let $v\in C_{j}$ where $j\in
I\cup\\{k\\}$, and let $I_{1}=\\{i\in I:i<j\\}$, and $I_{2}=\\{i\in
I\cup\\{k\\}:i>j\\}$. Since $C_{j}$ is $2\varepsilon^{\prime}$-sparse to
$C_{j+1}\cup\cdots\cup C_{k}$, it follows that $v$ has at most
$2\varepsilon^{\prime}p(k-j)\leq\varepsilon p(k-j)/2$ neighbours in
$C_{j+1}\cup\cdots\cup C_{k}$ (and hence at most the same number in
$\bigcup_{i\in I_{2}}C_{i}$). Since $C_{i+1}\cup\cdots\cup C_{k}$ (and hence
$C_{j}$) is $12\varepsilon^{\prime}$-sparse to $C_{i}$, it follows that $v$
has at most $12\varepsilon^{\prime}p=\varepsilon p/2$ neighbours in $C_{i}$,
for each $i<j$; and therefore $v$ has at most $\varepsilon pj/2$ neighbours in
$\bigcup_{i\in I_{1}}C_{i}$. Since $v$ has at most $p-1$ neighbours in
$C_{j}$, and $\varepsilon\leq 1$, it follows that $v$ has at most

$\varepsilon p(k-j)/2+\varepsilon pj/2+p-1\leq\varepsilon
pk/2+p\leq\varepsilon p(k+1)=\varepsilon|C|$

neighbours in $C$, and so $C$ is $\varepsilon$-restricted. If $C_{i}$ is
$2\varepsilon^{\prime}$-dense to $C_{i+1}\cup\cdots\cup C_{k}$ for all $i\in
I$, we use the same argument in the complement. This proves (3).

For each $i\in I$, since $|C_{i}|=|W_{k}|\leq|W_{i}|/2$ and $W_{i}$ is
$\varepsilon/2$-restricted, it follows that $W_{i}\setminus C_{i}$ is
$\varepsilon$-restricted. But then $V(G)$ admits a partition into the sets
$W_{i}\;(i\in\\{1,\ldots,k-1\\}\setminus I)$, the sets $W_{i}\setminus
C_{i}\;(i\in I)$, and $C$, and these sets are all $\varepsilon$-restricted.
This proves 3.2.

A rooted tree is a tree $T$ with a designated vertex $r$ called the root. If
$s,t\in V(T)$ we say $s$ is a descendant of $t$ if $t$ belongs to the path of
$T$ between $r$ and $s$. For $t\in V(T)$, let $d(t)$ be the length of the path
of $T$ between $r,t$. For $t\in V(T)$, let $T(t)$ be the set of all
descendants of $t$ different from $t$,

Now let $G$ be a graph, let $h,\ell\geq 1$ be integers, and let
$\varepsilon,\eta>0$. An $(h,\ell,\varepsilon,\eta)$-tree-partition of $G$ is
a pair $(T,(W_{t}:t\in V(T)))$ such that $T$ is a rooted tree (let its root be
$r$) and $W_{t}\subseteq V(G)$ for each $t\in V(T)$, with the following
properties:

  * •

every vertex $t$ of $T$ satisfies $d(t)\leq\ell$ and is adjacent to at most
$h$ of its descendants; and if $d(t)=\ell-1$ then $t$ is adjacent to at most
one of its descendants;

  * •

the sets $W_{t}\;(t\in V(T))$ are nonempty and pairwise disjoint, and have
union $V(G)$;

  * •

for each $t\in V(T)$, if $d(t)<\ell$ then $W_{t}$ is $\varepsilon$-restricted;

  * •

for each $t\in V(T)$, $|\bigcup_{s\in T(t)}W_{s}|\leq\eta|W_{t}|$;

  * •

for each $t\in V(T)$, $\bigcup_{s\in T(t)}W_{s}$ is either
$\varepsilon/12$-sparse or $\varepsilon/12$-dense to $W_{t}$.

An $(h,\ell,\varepsilon,\eta)$-tree-partition is tight if every maximal path
of $T$ with one end $r$ has length $\ell$. We need:

###### 3.3

Let $h>0$ be an integer, let $0<\varepsilon\leq 1$, let $K=\lceil
2/\varepsilon\rceil$, and let $0<\eta\leq 1/(24h^{K})$. Let $G$ be a graph
admitting a tight $(h,K,\varepsilon/(4h^{K}),\eta)$-tree-partition
$(T,(W_{t}:t\in V(T)))$, where $K=\lceil 2/\varepsilon\rceil$. Then $V(G)$ can
be partitioned into at most $9217h^{K}\varepsilon^{-2}$
$\varepsilon$-restricted subsets.

Proof. For each $t\in V(T)$, let $S(t)$ be the set of all descendants $s$ of
$t$ such that $d(t)=K$. (Thus $S(t)\neq\emptyset$, since the tree-partition is
tight.) Let $t\in V(T)$ with $d(t)=i$. Since there exists $s\in S(t)$, and

$|W_{t}|\geq\eta^{i-K}|W_{s}|\geq\eta^{i-K}\geq h^{K-i},$

it follows that $|W_{t}|h^{i-K}\geq 1$, and so
$\lfloor|W_{t}|h^{i-K}\rfloor\geq|W_{t}|h^{i-K}/2$. Consequently, and since
$|S(t)|\leq h^{K-i}$, for each $s\in S(t)$ we may choose $A^{s}_{t}\subseteq
W_{t}$, with $|A^{s}_{t}|\geq|W_{t}|h^{i-K}/2$, such that the sets
$A^{s}_{t}\;(s\in S(t))$ are pairwise disjoint and have union $W_{t}$. (In
particular, $A^{s}_{s}=W_{s}$.)

Let $s\in S(r)$, and let $t_{0},\ldots,t_{K}$ be the vertices in order of the
path of $T$ between $r,s$, where $t_{0}=r$ and $t_{K}=s$. We claim that
$(A^{s}_{t_{0}},A^{s}_{t_{1}},\ldots,A^{s}_{t_{K}})$ is a
$(K,\varepsilon/2)$-path-partition of $G[A^{s}]$, where
$A^{s}=A^{s}_{t_{0}}\cup A^{s}_{t_{1}}\cup\cdots\cup A^{s}_{t_{K}}$. To see
this, we must show that for $0\leq i\leq K-1$:

  * •

$A^{s}_{t_{i}}$ is $\varepsilon/2$-restricted;

  * •

$|\bigcup_{i<j\leq K}A^{s}_{t_{j}}|\leq|A^{s}_{t_{i}}|/12$;

  * •

$\bigcup_{i<j\leq K}A^{s}_{t_{j}}$ is either $\varepsilon/24$-sparse or
$\varepsilon/24$-dense to $A^{s}_{t_{i}}$.

Let $0\leq i\leq K-1$. Since $d(t_{i})=i<K$, it follows that $W_{t_{i}}$ is
$\varepsilon/(4h^{K})$-restricted, and since
$|A^{s}_{t_{i}}|\geq|W_{t_{i}}|h^{i-K}/2\geq|W_{t_{i}}|/(2h^{K})$, we deduce
that $A^{s}_{t_{i}}$ is $(\varepsilon/2)$-restricted.

To show that $|\bigcup_{i<j\leq K}A^{s}_{t_{j}}|\leq|A^{s}_{t_{i}}|/12$,
observe that

$|\bigcup_{i<j\leq K}A^{s}_{t_{j}}|\leq|\bigcup_{i<j\leq K}W_{t_{j}}|\leq\eta
W_{t_{i}}\leq|A^{s}_{t_{i}}|(2\eta h^{K-i})\leq|A^{s}_{t_{i}}|/12.$

Finally, to show that $\bigcup_{i<j\leq K}A^{s}_{t_{j}}$ is either
$\varepsilon/24$-sparse or $\varepsilon/24$-dense to $A^{s}_{t_{i}}$, observe
that, since $(T,(W_{t}:t\in V(T)))$ is an
$(h,K,\varepsilon/(4h^{K}),\eta)$-tree-partition, it follows that
$\bigcup_{i<j\leq K}W_{t_{j}}$ is either $\varepsilon/(48h^{K})$-sparse or
$\varepsilon/(48h^{K})$-dense to $W_{t_{i}}$, and hence so is
$\bigcup_{i<j\leq K}A^{s}_{t_{j}}$; and therefore $\bigcup_{i<j\leq
K}A^{s}_{t_{j}}$ is either $\varepsilon/24$-sparse or $\varepsilon/24$-dense
to $A^{s}_{t_{i}}$, since $A^{s}_{t_{i}}|\geq|W_{t_{i}}|/(2h^{K})$.

This proves that $(A^{s}_{t_{0}},A^{s}_{t_{1}},\ldots,A^{2}_{t_{K}})$ is a
$(K,\varepsilon/2)$-path-partition of $G[A^{s}]$. By 3.2, $A^{s}$ is the
disjoint union of at most $9217\varepsilon^{-2}$ $\varepsilon$-restricted
subsets. But the sets $A^{s}\;(s\in S(r))$ form a partition of $V(G)$, and
since $|S(r)|\leq h^{K}$, it follows that $V(G)$ is the disjoint union of at
most $9217h^{K}\varepsilon^{-2}$ $\varepsilon$-restricted subsets. This proves
3.3.

Next we eliminate the “tight” hypothesis:

###### 3.4

Let $h>0$ be an integer, let $0<\varepsilon\leq 1$, let $K=\lceil
2/\varepsilon\rceil$, and let $0<\eta\leq 1/(24h^{K})$. Let $G$ be a graph
admitting an $(h,K,\varepsilon/(4h^{K}),\eta)$-tree-partition $(T,(W_{t}:t\in
V(T)))$, Then $V(G)$ can be partitioned into at most
$9218h^{K}\varepsilon^{-2}$ $\varepsilon$-restricted subsets.

Proof. As before, for each $t\in V(T)$, let $S(t)$ be the set of all
descendants $s$ of $t$ such that $d(s)=K$. If $t\in V(T)$ and
$S(t)=\emptyset$, then $W_{t}$ is $\varepsilon$-restricted; so if
$S(t)=\emptyset$ for all $t\in V(T)$ then $V(G)$ can be partitioned into
$|V(T)|$ $\varepsilon$-restricted sets, and the theorem is true. So we may
assume that $S(t)\neq\emptyset$ for some $t$. Let $T^{\prime}$ be the subtree
of $T$ induced on the set of all vertices $t\in V(T)$ with
$S(t)\neq\emptyset$. Let $X$ be the union of the sets $W_{t}\;(t\in
V(T^{\prime}))$; then $(T^{\prime},(W_{t}:t\in V(T)))$ is a tight
$(h,K,\varepsilon/(4h^{K}),\eta)$-tree-partition of $G[X]$. Moreover,
$V(G)\setminus X$ can be partitioned into at most $|V(T)\setminus X|$
$\varepsilon$-restricted sets, and by 3.3, $X$ can be partitioned into at most
$9217h^{K}\varepsilon^{-2}$ $\varepsilon$-restricted sets; and since
$|V(T)|\leq h^{K}$, this proves 3.4.

We deduce:

###### 3.5

Let $H$ be a graph, and let $h=|H|^{2}$. Let $\varepsilon>0$, let $K=\lceil
2/\varepsilon\rceil$, and let $\eta=1/(24h^{K})$. Let $N$ be as in 1.5, with
$(\varepsilon,\eta,\theta)$ replaced by
$\left(\varepsilon/(4h^{K}),\eta,\varepsilon/(48h^{K})\right)$. Let $G$ be an
$H$-free graph admitting an $(h,k,\varepsilon/(4h^{K}),\eta)$-tree-partition
$(T,(W_{t}:t\in V(T)))$, where $k\leq K$. Then $V(G)$ can be partitioned into
at most $(K-k)h^{K}N+9218h^{K}\varepsilon^{-2}$ $\varepsilon$-restricted
subsets.

Proof. We proceed by induction on $K-k$. If $K-k=0$ then the result follows
from 3.4, so we assume that $k<K$, and the result holds for $k+1$. Let
$(T,(W_{t}:t\in V(T)))$ be an $(h,k,\varepsilon/(4h^{K}),\eta)$-tree-partition
of $G$, and let $r$ be the root of $T$, and $S(r)$ the set of all $s\in V(T)$
with $d(s)=k$, where $d(s)$ denotes the distance in $T$ between $r,s$.

Let $s\in S(r)$. By 1.5, there is a partition of $W_{s}$ into nonempty sets

$A^{s}_{1},\ldots,A^{s}_{m_{s}},B^{s}_{1},\ldots,B^{s}_{m_{s}},C^{s}_{1},\ldots,C^{s}_{n_{s}},$

where $m_{s}\leq h$ and $n_{s}\leq N$, such that:

  * •

$A^{s}_{1},\ldots,A^{s}_{m_{s}}$ and $C^{s}_{1},\ldots,C^{s}_{n_{s}}$ are
$\varepsilon/(4h^{K})$-restricted sets;

  * •

for $1\leq i\leq m_{s}$, $|B^{s}_{i}|\leq\eta|A^{s}_{i}|$;

  * •

for $1\leq i\leq m_{s}$, $B^{s}_{i}$ is either $\varepsilon/(48h^{K})$-sparse
or $\varepsilon/(48h^{K})$-dense to $A^{s}_{i}$.

Let $X$ be the union, over all $s\in S(r)$, of all the sets
$C^{s}_{1},\ldots,C^{s}_{n_{s}}$. Since each of these sets is
$\varepsilon/(4h^{K})$-restricted and hence $\varepsilon$-restricted, it
follows that $X$ can be partitioned into at most $h^{k}N$
$\varepsilon$-restricted sets. For each $s\in S(r)$, let us delete $s$ from
$T$ and add $2m_{s}$ new vertices
$t_{1}^{s},\ldots,t_{m_{s}}^{s},u^{s}_{1},\ldots,u^{s}_{m_{s}}$ to $T$, where
$t_{1}^{s},\ldots,t_{m_{s}}^{s}$ are adjacent to the neighbour of $s$ in $T$,
and $u^{s}_{j}$ is adjacent to $t^{s}_{j}$ for $1\leq j\leq m_{s}$. (Note that
if $t$ is the neighbour of $s$ in $T$, then $s$ is the only descendant of
$t$.) Let $T^{\prime}$ be the tree formed by adding these new vertices (for
all $s\in S(r)$). Define $W_{t_{j}^{s}}=A^{s}_{j}$ and
$W_{u^{s}_{j}}=B^{s}_{j}$ for $1\leq j\leq m_{s}$ and each $s\in S(r)$; then
$(T^{\prime},(W_{t}:t\in V(T^{\prime})))$ is a
$(h,k+1,\varepsilon/(4h^{K}),\eta)$-tree-partition of the subgraph
$G[V(G)\setminus X]$. From the inductive hypothesis, $V(G)\setminus X$ can be
partitioned into at most $(K-k-1)h^{k}N+9218h^{K}\varepsilon^{-2}$
$\varepsilon$-restricted sets; but $X$ can be partitioned into at most
$h^{k}N$ $\varepsilon$-restricted sets, and so $V(G)$ can be partitioned into
at most $(K-k)h^{k}N+9218h^{K}\varepsilon^{-2}$ $\varepsilon$-restricted sets.
This proves 3.5.

Now we can deduce 1.4, which we restate:

###### 3.6

For every graph $H$, and all $\varepsilon>0$, there is an integer $M$ such
that for every $H$-free graph $G$, there is a partition of $V(G)$ into at most
$M$ $\varepsilon$-restricted subsets.

Proof. Let $K=\lceil 2/\varepsilon\rceil$, let $h=|H|^{2}$, let
$\eta=1/(24h^{K})$, and let $N$ be as in 1.5, with $(\varepsilon,\eta,\theta)$
replaced by

$\left(\varepsilon/(4h^{K}),\eta,\varepsilon/(48h^{K})\right).$

Let $M=h^{K+1}((K-1)N+9218\varepsilon^{-2})+N$. We claim that $M$ satisfies
the theorem.

Let $G$ be $H$-free. By 1.5, $V(G)$ can be partitioned into nonempty sets

$A_{1},\ldots,A_{k},B_{1},\ldots,B_{k},C_{1},\ldots,C_{n},$

where $k\leq h$ and $n\leq N$, such that:

  * •

$A_{1},\ldots,A_{k}$ and $C_{1},\ldots,C_{n}$ are
$\varepsilon/(4h^{K})$-restricted sets;

  * •

for $1\leq i\leq k$, $|B_{i}|\leq\eta|A_{i}|$;

  * •

for $1\leq i\leq k$, $B_{i}$ is either $(\varepsilon/(48h^{K}))$-sparse or
$(\varepsilon/(48h^{K}))$-dense to $A_{i}$.

Thus for $1\leq i\leq k$, $G[A_{i}\cup B_{i}]$ admits a
$(1,1,\varepsilon/(4h^{K}),\eta)$-tree-partition, and so, by 3.5, $A_{i}\cup
B_{i}$ admits a partition into at most $(K-1)h^{K}N+9218h^{K}\varepsilon^{-2}$
$\varepsilon$-restricted sets. Since the sets $C_{1},\ldots,C_{n}$ are all
$\varepsilon$-restricted, it follows that $V(G)$ admits a partition into at
most

$h((K-1)h^{K}N+9218h^{K}\varepsilon^{-2})+N$

$\varepsilon$-restricted sets. This proves 3.6.

## References

  * [1] N. Bousquet, A. Lagoutte and S. Thomassé, “The Erdős-Hajnal conjecture for paths and antipaths”, J. Combinatorial Theory, Ser. B 113 (2015), 261–264.
  * [2] J. Fox and B. Sudakov, “Induced Ramsey-type theorems”, Advances in Math. 219 (2008), 1771–1800.
  * [3] V. Nikiforov, “Edge distribution of graphs with few copies of a given graph”, Combin. Probab. Comput. 15 (2006), 895–902.
  * [4] A. Scott, P. Seymour and S. Spirkl, “Pure pairs. IV. Trees in bipartite graphs”, submitted for publication, arXiv:2009.09426.
  * [5] V. Rödl, “On universality of graphs with uniformly distributed edges”, Discrete Math. 59 (1986), 125–134.