Problems in Ramsey Theory, Probabilistic
Combinatorics and Extremal Graph Theory
Bhargav Peruvemba Narayanan
Trinity College
and
Department of Pure Mathematics and Mathematical Statistics
University of Cambridge
This dissertation is submitted for the degree of
Doctor of Philosophy
October 29, 2015
Declaration
This document is the result of my own work and includes nothing which is the
outcome of work done in collaboration, except where specifically indicated in the
text. The results in Chapters 2 and 4 were obtained in collaboration with T. Kit-
tipassorn and my contribution was about 50%. Chapter 5 is based on joint work
with B. Bolloba´s and A. Raigorodskii and in this case, I did the majority of the
work. Chapter 6 is based on joint work with J. Balogh and B. Bolloba´s and my
contribution was about 60%. The results in Chapter 7 were obtained in collaboration
with with P. Balister, B. Bolloba´s and J. Lee and my contribution was about 50%.
Chapter 8 is based on joint work with B. Bolloba´s, T. Kittipassorn and A. Scott and
my contribution was about 40%. Finally, Chapter 9 is based on joint work with P.
Balister, S. Binski and B. Bolloba´s and my contribution was about 50%. No part of
this dissertation has been submitted for any other qualification.
Bhargav Peruvemba Narayanan
Abstract
In this dissertation, we treat several problems in Ramsey theory, probabilistic
combinatorics and extremal graph theory.
We begin with the Ramsey theoretic problem of finding exactly m-coloured
graphs. For which natural numbers m ∈ N are we guaranteed to find an m-coloured
complete subgraph in any edge colouring of the complete graph on N? We resolve
this question completely and prove, answering a question of Stacey and Weidl [104],
that whenever we colour N(2) with infinitely many colours, we are guaranteed to find
an
(
n
2
)
-coloured complete subgraph for each n ∈ N. In addition, we also demonstrate
that given a colouring of N(2) with k colours, there are at least
√
2k distinct values
m ∈ [k] for which an infinite m-coloured complete subgraph exists. Finally, we also
prove that given a colouring of N(2) with k colours and m ∈ [k], we can always find an
infinite mˆ-coloured complete subgraph for some mˆ ∈ [k] such that |m− mˆ| ≤√m/2.
Next, we give some results in probabilistic combinatorics. First, we investigate
the stability of the Erdo˝s–Ko–Rado Theorem. For natural numbers n, r ∈ N with
n ≥ r, the Kneser graph K(n, r) is the graph on the family of r-element subsets
of {1, . . . , n} in which two sets are adjacent if and only if they are disjoint. Delete
the edges of K(n, r) with some probability, independently of each other: is the
independence number of this random graph equal to the independence number of
the Kneser graph itself? We shall answer this question affirmatively as long as r/n is
bounded away from 1/2, even when the probability of retaining an edge of the Kneser
graph is quite small; we also prove a much more precise result when r = o(n1/3). We
then study a geometric bootstrap percolation model on the three dimensional grid
[n]3 called line percolation. In line percolation with infection parameter r, infection
spreads from a subset A ⊂ [n]3 of initially infected lattice points as follows: if there is
an axis parallel line L with r or more infected lattice points on it, then every lattice
point of [n]3 on L gets infected and we repeat this until the infection can no longer
spread. Our main result is the determination the critical density of initially infected
points at which percolation (infection of the entire grid) becomes likely.
Finally, we present two results in extremal graph theory. First, we consider a
graph partitioning problem. For a graph G, let f(G) be the largest integer k such
that there are two vertex-disjoint subgraphs of G, each on k vertices, inducing the
same number of edges. We prove that f(G) ≥ n/2 − o(n) for every graph G on n
vertices, settling a conjecture of Caro and Yuster [36]. Finally, we study the problem
of cops and robbers on the grid where the robber is allowed to move faster than the
cops. We prove that when the speed of the robber is a sufficiently large constant, the
number of cops needed to catch the robber on an n×n grid is exp(Ω(log n/ log log n)).
Acknowledgements
I am very grateful to my supervisor, Be´la Bolloba´s, for all that he has done
for me over the last three years. I cannot thank him enough for his guidance and
generosity, all the beautiful mathematics he has introduced me to, and the many
fantastic research visits he has organised. I would also like to thank Be´la and his
wonderful wife Gabi for all their support in general, and the many enjoyable evenings
full of American football in particular.
I am grateful to Ramarathnam ‘Venkie’ Venkatesan for introducing me to the
world of mathematical research and for always believing in me; he has been a source
of great support and excellent advice, mathematical and otherwise.
I would like to thank all my collaborators: Paul Balister, Jo´zsef Balogh, Scott
Binski, Victor Falgas-Ravry, Teeradej Kittipassorn, Da´niel Kora´ndi, Jonathan Lee,
Shoham Letzter, Andrei Raigorodskii, Julian Sahasrabudhe, Alex Scott and Istva´n
Tomon. I would also like to thank Sean Eberhard, Josh Erde, Imre Leader and Mark
Walters for many interesting discussions.
My thanks to Richard Johnson, Tomas Jusˇkevicˇius, Sebastian Koch, Micha l
Przykucki, Stephen Smith and all the other members of Team Bolloba´s for the
mini-seminars, the coffee time problem sessions and all the other fun things we have
done together.
I am grateful to Trinity College for providing me with the financial support
for my work. I should also like to thank the University of Memphis, the Alfre´d
Re´nyi Institute of Mathematics, Budapest, the Theory Group at Microsoft Research,
Redmond, and the IMT Institute for Advanced Studies, Lucca for their hospitality.
I would like to thank Juhan Aru, Tom Gillespie, Vytautas Gruslys, Are`s Me´roueh,
Gunnar Peng, Paul Smith, Moses Tanenbaum, Noam Zamir and my other friends in
Cambridge for making my time here so memorable. My thanks also to Adhiraj Alai,
Advait Alai, Neal Bushaw, Audrius Feigelovicius, Rajkishan Gunasekaran, Immanuel
Thomas and all my other friends in far off places for their support.
Finally, I would like to thank my parents, Sarala and Raju, for everything.
Without their love and encouragement, none of this would have been possible.
Contents
Chapter 1. Introduction 1
1. Ramsey theory 1
2. Probabilistic combinatorics 2
3. Extremal graph theory 4
Part 1. Ramsey theory 7
Chapter 2. A canonical Ramsey theorem for exactly m-coloured graphs 9
1. Introduction 9
2. Our results 9
3. Proof of the main theorem 13
4. Extensions and applications 20
5. Concluding remarks 24
Chapter 3. Infinite exactly m-coloured complete graphs 27
1. Introduction 27
2. Lower bounds 30
3. Upper bounds 35
4. Concluding remarks 36
Chapter 4. Approximations to infinite m-coloured complete hypergraphs 39
1. Introduction 39
2. Proofs of the main results 42
3. Concluding remarks 50
Part 2. Probabilistic combinatorics 51
Chapter 5. Transference for the Erdo˝s–Ko–Rado theorem, I 53
1. Introduction 53
2. Preliminaries 57
3. Upper bound for the critical threshold 59
4. Lower bound for the critical threshold 67
5. Concluding remarks 68
Chapter 6. Transference for the Erdo˝s–Ko–Rado theorem, II 71
1. Introduction 71
2. Preliminaries 72
3. The number of disjoint pairs 74
4. Proof of the main result 78
5. Avenues for improvement 81
6. Concluding remarks 87
Chapter 7. Line percolation 89
1. Introduction 89
2. Our results 91
3. Probabilistic preliminaries 95
4. Line percolation in two dimensions 96
5. The critical probability in three dimensions 104
6. Minimal percolating sets 113
7. Concluding remarks 114
Part 3. Extremal graph theory 115
Chapter 8. Disjoint induced subgraphs of the same order and size 117
1. Introduction 117
2. Preliminaries 119
3. Overview of our strategy 124
4. Proof of the main result 126
5. Concluding remarks 145
Chapter 9. Catching a fast robber on the grid 147
1. Introduction 147
2. Proof of the main result 149
3. Concluding remarks 158
Bibliography 159
CHAPTER 1
Introduction
This dissertation is divided into three parts. The first part covers some
Ramsey theory, the second is devoted to questions from probabilistic combina-
torics and the third part deals with some problems in extremal graph theory.
In what follows, we briefly discuss the problems and the results presented in
the subsequent chapters.
1. Ramsey theory
Ramsey theory is concerned with questions about whether one can always
find homogeneous substructures in large discrete structures. These questions
are typically phrased in terms of colourings; a homogeneous substructure in
this case is usually a substructure on which the colouring is particularly simple
to describe. The first part of the dissertation consists of three chapters which
are concerned with the following question: given a large coloured structure and
a natural number m ∈ N, can one always find a substructure that is coloured
with exactly m distinct colours?
Given an edge-coloured graph, call a subgraph m-coloured if the colouring
attains exactly m different values in the subgraph. For a natural number
m > 1, it is natural to ask if one is guaranteed to find an exactly m-coloured
complete subgraph in every edge-colouring of the complete graph on N with
sufficiently many colours. It is not clear that there are any natural numbers
with this property; the injective colouring shows, for example, that there is no
such guarantee unless m =
(
n
2
)
for some n ∈ N. In Chapter 2, which is joint
work with T. Kittipassorn [76], we answer a question of Stacey and Weidl [104]
and prove that whenever we colour N(2) with infinitely many colours, we are
1
guaranteed to find an
(
n
2
)
-coloured complete subgraph for each n ∈ N. We
need two key ideas to prove this theorem. The first is to ask a more general
question, the answer to which is a canonical Ramsey theorem for m-coloured
complete subgraphs that implies the result we would like to prove. The second
is that to prove this canonical Ramsey theorem (which is about edge-coloured
complete graphs), somewhat strangely, we need to suitably generalise the result
to general edge-coloured graphs (as opposed to complete graphs).
In Chapter 3, we investigate the following question: given a colouring of
N(2) with k colours, for how many distinct values m ∈ [k] are we guaranteed to
find an infinite m-coloured complete subgraph? We show in [91] that we are
guaranteed at least
√
2k distinct values and that this bound is tight infinitely
often. We prove this result by proving a more intricate (and stronger) structural
result by induction.
In Chapter 4, which is joint work with T. Kittipassorn [75], we study the
following related problem: given a colouring of N(2) with k colours and m ∈ [k],
how close can we get to finding an infinite m-coloured complete subgraph?
Our main result is that we can always find an infinite mˆ-coloured complete
subgraph for some mˆ ∈ [k] such that |m− mˆ| ≤√m/2, and that this is best
possible. In the process, we also resolve a conjecture of mine from [91]. We
also study how one might generalise this result to uniform hypergraphs; we
consider two natural variants one of which we prove to be true while showing
the other to be false.
2. Probabilistic combinatorics
The first two chapters of the second part of this dissertation are concerned
with a ‘sparse-random’ analogue of the Erdo˝s–Ko–Rado theorem. The Erdo˝s–
Ko–Rado Theorem is a central (and very simple) result in extremal set theory
which tells us how large uniform intersecting families can be. One possible
formulation of the Erdo˝s–Ko–Rado theorem is the following: if n ≥ 2r, then the
size of the largest independent set of the graph K(n, r) is
(
n−1
r−1
)
, where K(n, r)
2
is the Kneser graph with parameters n, r ∈ N; the vertex set of this graph is
the family of r-element subsets of {1, . . . , n}, and two r-sets are adjacent in
K(n, r) if and only if they are disjoint.
Let us delete the edges of the Kneser graph with some probability, indepen-
dently of each other; is the independence number of this random graph equal
to the independence number of the Kneser graph itself? Chapters 5 and 6 are
both concerned with this question.
In Chapter 5, which is based on joint work with B. Bolloba´s and A. Raig-
orodskii [30], we answer the question affirmatively when r = o(n1/3) and also
determine the precise critical threshold at which the answer becomes negative;
it turns out that a random analogue of the Erdo˝s–Ko–Rado theorem continues
to hold even after we have deleted practically all the edges of the Kneser graph.
Chapter 6, which is based on joint work with J. Balogh and B. Bolloba´s [17],
contains a more substantial result: we show the answer to be in the affirmative
as long as r/n is bounded away from 1/2. To prove this result, we make use of
a variety of tools. For example, we give some new estimates for the number of
disjoint pairs in a family in terms of its distance from an intersecting family.
We also briefly describe how ideas from the theory of graph containers can help
sharpen these results.
In the third chapter of this part, we study a geometric bootstrap percolation
model on the d-dimensional grid [n]d. In this model, line percolation, with
infection parameter r, infection spreads from a subset A ⊂ [n]d of initially
infected lattice points as follows: if there is an axis parallel line L with r or more
infected lattice points on it, then every lattice point of [n]d on L gets infected
and we repeat this until the infection can no longer spread. The elements of
the set A are usually chosen independently, with some density p, and the main
question is to determine pc(n, r, d), the density at which percolation (infection of
the entire grid) becomes likely. As is often the case with bootstrap percolation
models, analysing the process in three dimensions turns out be significantly
more challenging than the corresponding problem in two dimensions. Our
3
main result in Chapter 7, which is based on joint work with P. Balister, B.
Bolloba´s and J. Lee [11], is the determination of the critical probability in
three dimensions up to multiplicative constants. The crux of the proof is in
showing that long-range interactions are not very helpful in spreading the
infection. This is done with a coupling argument where we run the process
and wait for certain ‘bad’ events to occur; we then restart the process with the
‘badness’ built in from the start, but also impose additional constraints on how
the infection might spread which makes this modified process easier to follow.
We also determine the size of minimal percolating sets using the polynomial
method.
3. Extremal graph theory
The first of the two chapters of this part, Chapter 8, is based on joint
work with B. Bolloba´s, T. Kittipassorn and A. Scott [28], and is concerned
with a graph partitioning problem. We would like to find two vertex-disjoint
induced subgraphs of a given graph of the same order and size; how large can
we guarantee these subgraphs to be? We answer this question and settle a
conjecture of Caro and Yuster by showing that any n-vertex graph contains
two very large, indeed of order n/2− o(n), disjoint induced subgraphs of the
same order and size. The main idea is that for each graph, there is a (small)
probability such that if we delete vertices from the graph independently with
this probability, the resulting graph has many useful ‘gadgets’ (pairs of vertices
that have suitable degree differences which we can use to find a suitable partition
of this graph). However, since the argument has to cover all graphs, there is
no simple description of this probability and we need to distinguish a few cases
and tailor the argument suitably to fit each case.
The second chapter of this part, Chapter 9, is concerned with the game of
cops and robbers. It is well known that in the traditional variant of the game
of cops and robbers on an n× n grid, two cops are necessary and sufficient to
catch the robber. In Chapter 9, which is based on joint work with P. Balister,
4
S. Binski and B. Bolloba´s [10], we ask how many cops are needed to catch the
robber if the robber is allowed to move faster than the cops. We show that if
the robber’s speed is greater than some large constant, then at least n1/ log logn
cops are needed to catch the robber on an n × n grid. While this seems to
be very far from the truth (indeed, we think the number of cops needed to
catch a fast robber should be almost, if not actually, linear in n), the proof
strategy might be of independent interest: we use a dynamic variant of the
density-based strategy used by Bolloba´s and Leader to resolve Conway’s Angel
and Devil problem in three dimensions.
5
Part 1
Ramsey theory
CHAPTER 2
A canonical Ramsey theorem for exactly m-coloured
graphs
Joint work with Teeradej Kittipassorn.
1. Introduction
A classical result of Ramsey [96] says that when the edges of a complete
graph on a countably infinite vertex set are finitely coloured, one can always
find a complete infinite subgraph all of whose edges have the same colour.
Ramsey’s theorem has since been generalised in many ways; most of these
generalisations are concerned with finding other monochromatic structures. For
a survey of many of these generalisations, see the book of Graham, Rothschild
and Spencer [63]. Ramsey theory has witnessed many developments over the
last fifty years and continues to be an area of active research today; see, for
instance, [106, 39, 69, 82, 22].
Alternatively, anti-Ramsey theory, which originates in a paper of Erdo˝s,
Simonovits and So´s [51], is concerned with finding large ‘rainbow coloured’ or
‘totally multicoloured’ structures. Between these two ends of the spectrum,
one could consider the question of finding structures which are coloured with
exactly m different colours as was first done by Erickson [52]; it is this line of
enquiry that we pursue here.
2. Our results
Our notation is standard. We write [n] for {1, ..., n}, the set of the first n
natural numbers. For a set X, we write X(2) for the family of all two element
9
subsets of X; equivalently, X(2) is the complete graph on the vertex set X. We
denote a surjective map f from a set X to another set Y by f : X Y . By a
colouring of a graph, we mean a colouring of the edges of the graph.
Let ∆ : N(2) C be a surjective colouring of the edges of the complete
graph on N with an arbitrary set of colours C. If the set of colours C is infinite,
we say that ∆ is an infinite-colouring and if C is finite, we say that ∆ is a
k-colouring if |C| = k. We say that a subset X of N is (exactly) m-coloured if
∆(X(2)), the set of values attained by ∆ on the edges with both endpoints in
X, has size exactly m. We write γ∆(X), or γ(X) in short, for the size of the
set ∆(X(2)); in other words, every set X is γ(X)-coloured.
This chapter is concerned with canonical Ramsey theory, a subject which
originates in a classical paper of Erdo˝s and Rado [47]. To give readers unfamiliar
with this subject a flavour of the results in this area, we recall a basic canonical
Ramsey theorem proved by Erdo˝s and Rado. To state this result, it will be
convenient to introduce some notation. We say that X ⊂ N is rainbow coloured
if no two edges with both endpoints in X receive the same colour. Also, we
say that X ⊂ N is left coloured if for i, j, k, l ∈ X with i < j and k < l,
∆(ij) = ∆(kl) if and only if i = k, and the definition of right coloured is
analogous; if X is left or right coloured, we say, in short, that X is lexically
coloured. With these definitions in place, we can now state the canonical
Ramsey theorem of Erdo˝s and Rado [47].
Theorem 2.1. For any colouring ∆ : N(2) C, there exists an infinite
subset X of N such that either
(1) X is 1-coloured, or
(2) X is rainbow coloured, or
(3) X is lexically coloured.
Returning to the question at hand, our main aim in this chapter is to prove
a canonical Ramsey theory for m-coloured graphs. For a colouring ∆ : N(2) C
10
of the complete graph on N with an arbitrary set of colours, we define the set
G∆ = {γ∆(X) : X ⊂ N}.
Stacey and Weidl [104] considered the following question: are there natural
numbers m ∈ N that are guaranteed to be elements of G∆ for every infinite-
colouring ∆? It is clear that the natural number 1 trivially has this property
since an edge is a 1-coloured complete graph; however, it is not at all clear why
any natural number m > 1 should have this property. By considering a rainbow
colouring of N, we see that m ∈ N cannot have this property unless m = (n
2
)
for some n ≥ 2. On the other hand, Stacey and Weidl were able to show that(
3
2
)
is always an element of G∆ for every infinite-colouring ∆. But for n ≥ 4,
they were unable to decide whether or not there exists an infinite-colouring
∆ such that
(
n
2
)
/∈ G∆. In particular, they asked if all natural numbers of the
form
(
n
2
)
must be contained in G∆ for every infinite-colouring ∆.
Here, we shall consider a more general question: when is G∆ 6= N? As
remarked above, for an injective colouring ∆, G∆ = {
(
n
2
)
: n ≥ 2} 6= N. There
is another infinite-colouring ∆ for which G∆ 6= N which is slightly less obvious.
Given X ⊂ N, if there is a vertex v ∈ X such that X \ {v} is 1-coloured and
all the edges between v and X \ {v} have distinct colours (which are also all
different from the colour appearing in X \ {v}), then we say that X is star
coloured (with centre v). It is easy to check (see Figure 1) that if N is star
coloured by ∆, then G∆ = N \ {2}.
Our main result, stated below, is that the two colourings described above
are, in a sense, the ‘canonical’ colourings for which G∆ 6= N.
Theorem 2.2. For every infinite-colouring ∆ : N(2) N, either
(1) G∆ = N, or
(2) there exists an infinite rainbow coloured subset of N, or
(3) there exists an infinite star coloured subset of N.
11
12
3
4
5 6
2 3
v
4 5
1
1
1
1
1
1
Figure 1. A rainbow colouring and a star colouring with centre v.
An immediate consequence of Theorem 2.2 is that the answer to the question
posed by Stacey and Weidl is in the affirmative.
Corollary 2.3. For every infinite-colouring ∆ : N(2) N, and for every
natural number n ≥ 2, (n
2
) ∈ G∆.
We do not prove Theorem 2.2 as stated. Instead, it will be more convenient
to prove a stronger result which we shall state (and prove) in Section 3.
Stacey and Weidl [104] also asked what happens in the context of colourings
using finitely many colours. More precisely, they raised the following question:
do there exist natural numbers m ∈ N with the property that for all sufficiently
large k ∈ N, m ∈ G∆ for every k-colouring ∆ : N(2) [k]? Observe that
any such natural number m, assuming one exists, must be of the form
(
n
2
)
or(
n
2
)
+ 1 for some natural number n ≥ 2. One can see this by considering the
family of ‘small-rainbow colourings’ of the complete graph on N which colour
all the edges of some finite complete subgraph with distinct colours and all the
remaining edges with a single colour not used in the finite (rainbow coloured)
complete subgraph. On the other hand, when m is of the form
(
n
2
)
or
(
n
2
)
+ 1
for some natural number n ≥ 2, we have the following positive result.
Theorem 2.4. For all n ∈ N, there exists a natural number C = C(n) such
that for any k-colouring ∆ : N(2) [k] with k ≥ C, both (n
2
)
,
(
n
2
)
+ 1 ∈ G∆.
12
It turns out that the techniques used to prove Theorem 2.2 also allow us
to prove a finitary version of the same theorem. In Section 4, we present this
finitary result and use it prove Theorem 2.4 in a slightly stronger form. We
conclude with some discussion in Section 5.
3. Proof of the main theorem
To prove Theorem 2.2, it will be more convenient to work with general
infinite graphs. By an infinite graph, we mean a graph whose vertex set is N
which has infinitely many edges.
It will be helpful to establish a few notational conveniences. Given an
infinite graph G and an infinite-colouring ∆ : G N of the edges of G, for a
subset X of N, we shall write γG(X), or just γ(X) when both the colouring
and the graph in question are clear from the context, for the number of distinct
colours attained by ∆ on G[X], the subgraph of G induced by X; if H is a
subgraph of G, we write γH(X) for the the number of distinct colours attained
by ∆ on H[X]. For disjoint subsets X and Y , write γ(X, Y ) for the number
of distinct colours in the induced bipartite subgraph between X and Y in G.
Also, for a vertex v ∈ N, we shall write γ(v) for γ({v},N \ {v}), the number of
distinct colours of the edges incident to v in G.
We define the set G∆ for an infinite-colouring ∆ : G N of an infinite
graph G in the obvious way by setting
G∆ = {γG(X) : X ⊂ N}.
In a general graph G, we say that X is rainbow coloured in G if G[X] is
a complete subgraph of G which is rainbow coloured. We say that X is star
coloured (with centre v) in G if there is a vertex v ∈ X such that G[X \ {v}] is
either an independent set or a 1-coloured complete graph, and all the edges
between v and X \ {v} are present and have distinct colours, which are also
all different from the colour of G[X \ {v}] in the case where X \ {v} does not
induce an independent set. The following result easily implies Theorem 2.2.
13
Theorem 3.1. For every infinite-colouring ∆ : G N of an infinite graph
G, either
(1) G∆ = N, or
(2) there exists an infinite rainbow coloured subset of N; or
(3) there exists an infinite star coloured subset of N.
For any finite set of colours S, note that if we delete all the edges of an
infinite graph G which are coloured with a colour from S by an infinite-colouring
∆ of the edges of G, the resulting graph H is infinite and the restriction of ∆
to H is an infinite-colouring. This makes the statement of Theorem 3.1 more
amenable to induction than that of Theorem 2.2 and motivates the stronger
statement of Theorem 3.1.
Fix an infinite-colouring ∆ : G N of an infinite graph G and note that if
we have a partition X = X1 ∪X2 ∪ . . . Xn of a subset X of N, then∑
1≤i≤n
γ(Xi) +
∑
1≤i ks, we can
find vertices x, y ∈ V \ S such that
(∆(xu1),∆(xu2), . . . ,∆(xus)) = (∆(yu1),∆(yu2), . . . ,∆(yus)).
We claim that there is a subset T ⊂ S of size t = n2 such that for all u ∈ T ,
∆(xu) 6∈ ∆(T (2)). Consider the set
A = {(u, T ) : u ∈ T ⊂ S, |T | = t, ∆(xu) ∈ ∆(T (2))}.
As S is rainbow coloured, there is at most one edge ab in S(2) of colour ∆(xu)
for each u ∈ S. If (u, T ) is in A, then we must have a, b ∈ T . So for each
u ∈ S, there are at most (s−2
t−2
)
sets T such that (u, T ) ∈ A. Therefore,
|A| ≤ s(s−2
t−2
)
<
(
s
t
)
since s = t2. Hence there exists a T which does not appear
in A and the claim follows.
Hence, there is indeed a subset T of S of size t = n2 such that ∆(xu) 6∈
∆(T (2)) for all u ∈ T . Let Q = {∆(xu) : u ∈ T}. If |Q| < n, then as |T | = n2,
there are vertices v1, v2, . . . , vn in T such that
∆(xv1) = ∆(xv2) = · · · = ∆(xvn).
Since this colour ∆(xv1) is not an element of ∆(T
(2)), we conclude that the set
{x, v1, v2, . . . , vn} is (
(
n
2
)
+ 1)-coloured.
So we may assume that |Q| ≥ n. Then there is a subset U ⊂ T of size n
such that the colours ∆(xu) are distinct for all u ∈ U . Since U ⊂ T , the colour
23
∆(xu) is not an element of ∆(U (2)) for each u ∈ U . We hence conclude that
U ∪ {x} is rainbow coloured.
Recall that there is a vertex y 6= x in V \ S such that ∆(xu) = ∆(yu)
for all u ∈ S. Since at most one edge e in (U ∪ {x})(2) is coloured with the
same colour as the edge xy, by removing the endpoint of e which lies in U if
necessary, we can find a subset U ′ of U of size n − 1 such that ∆(xy) is not
an element of ∆((U ′ ∪ {x})(2)). Then U ′ ∪ {x, y} is ((n
2
)
+ 1)-coloured since
U ′ ∪ {x} and U ′ ∪ {y} are rainbow coloured sets of size n using the same set of
colours.
It is easy to see that, taken together, Corollary 4.4 and Theorem 4.5 imply
Theorem 2.4.
The following corollary of Lemma 4.3 about finding m-coloured complete
bipartite subgraphs might be of independent interest.
Corollary 4.6. For all m ∈ N, there exists a natural number B = B(m)
such that if ∆ : U × V [k] is a k-colouring of the complete bipartite graph
between two countable sets U and V with k ≥ B colours, then there exist X ⊂ U
and Y ⊂ V such that the complete bipartite subgraph between by X and Y is
m-coloured.
Proof. It is easy to check that it suffices to take B(m) = L(m,m), where
L is the constant guaranteed by Lemma 4.3.
5. Concluding remarks
We conclude by mentioning two questions that would merit further study.
First, the problem of determining for each k ∈ N, which natural numbers
m ∈ N are guaranteed to belong to G∆ for every k-colouring ∆ : N(2) [k] is
quite interesting; while we have taken a few steps towards this in this chapter,
the full question is still far from being resolved. Second, it would be reasonable
to ask the questions considered here for uniform hypergraphs. However, even in
the case of N(3), it is not immediately clear to us what the canonical structures
24
analogous to the rainbow coloured and star coloured complete graphs should
be.
25
CHAPTER 3
Infinite exactly m-coloured complete graphs
1. Introduction
In the last chapter, we investigated, for a given colouring of the complete
graph on the natural numbers, the properties of the set of those natural numbers
m for which there exists an m-coloured complete subgraph. In this chapter, we
shall study how the situation changes when one is interested in finding a ‘large’
m-coloured complete subgraph.
We begin by briefly recalling some of the definitions from the previous
chapter. Let ∆ : N(2) C be a surjective colouring of the edges of the complete
graph on N with an arbitrary set of colours C. If the set of colours C is infinite,
we say that ∆ is an infinite-colouring and if C is finite, we say that ∆ is a
k-colouring if |C| = k. Given a colouring ∆ : N(2) C of the complete graph
on N, we say that a subset X of N is (exactly) m-coloured if ∆(X(2)), the set of
values attained by ∆ on the edges with both endpoints in X, has size exactly
m. Let γ∆(X), or γ(X) in short, denote the size of the set ∆(X
(2)); in other
words, every set X is γ(X)-coloured.
In the last chapter, we studied, for a colouring ∆ : N(2) C of the complete
graph on N, the properties of the set
G∆ = {γ∆(X) : X ⊂ N}.
In the context of Ramsey theory, one is usually interested in finding ‘large’
homogeneous structures with certain properties. With this in mind, for a
colouring ∆ : N(2) C, we define
F∆ = {γ∆(X) : X ⊂ N such that X is infinite}.
27
When ∆ is an infinite-colouring, it might so happen that for each infinite subset
X of N, the set ∆(X(2)) is infinite; consequently, it is only really meaningful to
study the set F∆ in the case of colourings using finitely many colours. This
question of finding infinite m-coloured complete subgraphs was first considered
by Erickson [52]. If ∆ : N(2) [k] is a k-colouring of the edges of the complete
graph on the natural numbers, then clearly k ∈ F∆ as ∆ is surjective, and
Ramsey’s Theorem tells us that 1 ∈ F∆. Erickson [52] noted that a fairly
straightforward application of Ramsey’s Theorem enables one to show that
2 ∈ F∆. Erickson conjectured however that with the exception of 1, 2 and k,
no other elements are guaranteed to be in F∆.
Conjecture 1.1. Let k,m ∈ N with k > m > 2. Then there exists a
k-colouring ∆ : N(2) [k] such that m /∈ F∆.
Stacey and Weidl [104] settled this conjecture in the case where k is much
bigger than m. More precisely, for any m > 2, they showed that there exists
a constant Cm such that if k > Cm, then there is a k-colouring ∆ such that
m /∈ F∆.
Erickson’s conjecture, if true, would suggest that it is hopeless to look
for particular values in the set F∆ given a k-colouring ∆ : N(2) [k]. It is
natural then to consider other properties of the set F∆. The first question
which arises is that of the set of possible sizes of F∆. Since F∆ ⊂ [k], it follows
that |F∆| ≤ k and it is easy to see that equality is in fact possible. Things are
not so clear when we turn to the question of lower bounds. Let us define
ψ(k) = min
∆:N(2)[k]
|F∆|.
We are able to prove the following lower bound for ψ(k).
Theorem 1.2. Let n ≥ 2 be the largest natural number such that k ≥ (n
2
)
+1.
Then ψ(k) ≥ n.
It is not hard to check that Theorem 1.2 is tight when k =
(
n
2
)
+ 1 for some
n ≥ 2. To this end, we consider the ‘small-rainbow colouring’ ∆ which colours
28
all the edges with both endpoints in [n] with
(
n
2
)
distinct colours and all the
remaining edges with the one colour that has not been used so far. Clearly
F∆ = {
(
i
2
)
+ 1 : i ≤ n}, and so Theorem 1.2 is best possible for infinitely many
values of k.
Turning to the question of upper bounds for ψ, the small-rainbow colouring
demonstrates that ψ(k) = O(
√
k) for infinitely many values of k. When k is not
of the form
(
n
2
)
+1, there are two obvious ways of generalising the small-rainbow
colouring described above: we could replace the rainbow coloured clique in
the construction either with a disjoint union of cliques, or with a clique along
with an extra vertex attached to some vertices of the clique. It is not hard
to check that both these generalisations fail to give us good upper bounds for
ψ(k) for general k; in particular, we are unable to decide if ψ(k) = o(k) for all
k ∈ N. However, by considering colourings that colour all the edges of a small
complete bipartite graph with distinct colours (as opposed to a small complete
graph) and making use of some number theoretic estimates of Tenenbaum [105]
and Ford [56], we get reasonably close to such a statement.
Theorem 1.3. There exists a subset A of the natural numbers of asymptotic
density one such that for all k ∈ A,
ψ(k) = O
(
k
(log log k)δ(log log log k)3/2
)
where δ = 1− 1+log log 2
log 2
≈ 0.086 > 0.
The rest of this chapter is organised as follows. In the next section, we
prove Theorem 1.2. We remark that we do not prove Theorem 1.2 as stated.
Instead, we prove a stronger structural result that implies the theorem. We
postpone the statement of this result since it depends on a certain notion of
homogeneity that we shall introduce in the next section. In Section 3, we
describe how Theorem 1.3 follows from certain divisor estimates. We conclude
by mentioning some open problems in Section 4.
29
2. Lower bounds
In this section, we prove Theorem 1.2 by proving a stronger structural
result, namely Theorem 2.3.
We first introduce a notational convenience. Given a colouring ∆ of N(2),
a vertex v ∈ N, and a subset X ⊂ N \ {v}, we say that a colour c is a new
colour from v into X if some edge from v to X is coloured c by ∆ and also, no
edge of X(2) is coloured c by ∆. We write N∆(v,X), or just N(v,X) when the
colouring ∆ in question is clear, for the set of new colours from v into X.
2.1. Proof of Theorem 1.2. Before we prove Theorem 1.2, we note that
Erickson’s argument showing that 2 ∈ F∆ can be generalised to give a quick
proof that ψ(k) = Ω(log k).
Lemma 2.1. Let ∆ : N(2) [k] be a k-colouring and suppose l ∈ F∆ and
l < k. Then there is an m ∈ F∆ such that l + 1 ≤ m ≤ 2l.
Proof of Lemma 2.1. The collection of infinite l-coloured sets is non-
empty and so by Zorn’s lemma, there is a maximal infinite l-coloured set;
let X ⊂ N be such a set. As l < k, X 6= N. Pick v ∈ N \ X. Note that
N(v,X) 6= ∅ since otherwise X ∪ {v} is l-coloured, which contradicts the
maximality of X.
If |N(v,X)| ≤ l, then X ∪ {v} is m-coloured for some l + 1 ≤ m ≤ 2l. So
suppose |N(v,X)| ≥ l + 1. By the pigeonhole principle, there is an infinite
subset Y of X such that all the vertices of Y are connected to v by edges of a
single colour, say c.
We consider two cases. If c ∈ N(v,X), we pick l− 1 vertices from X which
are joined to v by edges coloured with l− 1 distinct colours from N(v,X) \ {c}.
If on the other hand c /∈ N(v,X), we pick l vertices from X which are joined
to v by edges coloured with l distinct colours from N(v,X). Call this set of
l − 1 or l vertices Z.
30
In both cases, it is easy to check that Y ∪ Z ∪ {v} is m-coloured with
l + 1 ≤ m ≤ 2l since the number of colours appearing in Y ∪ Z is between 1
and l and v introduces precisely l new colours into this set.
Note that Lemma 2.1, coupled with the fact that we always have 1 ∈ F∆,
implies that ψ(k) ≥ 1 + log2 k. By applying Lemma 2.1 to the largest element
of F∆ in [2n], we have the following corollary.
Corollary 2.2. If ∆ : N(2) [k] is a k-colouring and n is a natural
number such that k ≥ 2n + 1, then F∆ ∩ ([2n+1] \ [2n]) 6= ∅.
We shall show that for any k-colouring ∆ : N(2) [k] with k ≥ (n
2
)
+ 1
for some n, we can find n nested subsets A1 ( A2 ( · · · ( An of N such that
∆(A
(2)
1 ) ( ∆(A
(2)
2 ) ( · · · ( ∆(A(2)n ). To do this, we introduce the notion of
n-homogeneity on which our first structural result, Theorem 2.3, hinges.
For an ordered n-tuple X = (X1, X2, . . . , Xn), write X̂i for the set X1 ∪
X2 · · · ∪Xi. Given a colouring ∆, we call X = (X1, X2, . . . , Xn), with each Xi
a non-empty subset of N, n-homogeneous with respect to ∆ if the following
conditions are met:
(1) Xi ∩Xj = ∅ for i 6= j,
(2) X1 is infinite and 1-coloured,
(3) ∆(X̂
(2)
1 ) ( ∆(X̂
(2)
2 ) ( · · · ( (X̂(2)n ),
(4) for each Xi with 2 ≤ i ≤ n, every v ∈ Xi satisfies
N(v, X̂i−1) = ∆
(
X̂
(2)
i
)
\∆
(
X̂
(2)
i−1
)
, and
(5) γ(X̂n) ≤
(
n
2
)
+ 1.
Rather than proving Theorem 1.2, we prove the following stronger statement.
Theorem 2.3. Let ∆ : N(2) [k] be a k-colouring and suppose n is a
natural number such that k ≥ (n
2
)
+ 1. Then there exists an n-homogeneous
tuple with respect to ∆.
31
Proof. We proceed by induction on n. The case n = 1 is Ramsey’s
Theorem. Suppose that k ≥ (n+1
2
)
+ 1 and assume inductively that at least one
n-homogeneous tuple exists; let X = (X1, X2, . . . , Xn) be such a tuple. Note
that k ≥ (n+1
2
)
+ 1 >
(
n
2
)
+ 1. Since ∆ is surjective and attains at most
(
n
2
)
+ 1
different values inside X̂n, clearly N \ X̂n 6= ∅. We consider two cases.
Case 1: N(v, X̂n) 6= ∅ for some v ∈ N \ X̂n. If |N(v, X̂n)| ≤ n, then it is
easy to check that (X1, X2, . . . , Xn, {v}) is an (n+ 1)-homogeneous tuple and
we are done. So, assume without loss of generality that |N(v, X̂n)| ≥ n+ 1.
Let j be the smallest index such that N(v, X̂j) 6= ∅. Since N(v, X̂n) 6= ∅,
this minimal index j exists. We now build our (n + 1)-homogeneous tuple
Y = (Y1, Y2, . . . , Yn+1) as follows.
Set Y1 = X1, Y2 = X2, . . . , Yj−1 = Xj−1. We define Yj as follows. First,
choose c ∈ N(v, X̂j); note that by the minimality of j, N(v, X̂j−1) = ∅ and so
all the edges between v and X̂j coloured c are actually edges between v and
Xj. Take Yj ⊂ Xj to be the (non-empty) set of vertices u ∈ Xj such that the
edge between v and u is either coloured c or with a colour from ∆(X̂
(2)
j ) (and
hence a colour not in N(v, X̂j)). Note that if j = 1, we can always choose c
such that Y1 is an infinite subset of X1.
Next, set Yj+1 = {v}. Now, note that the only colour from ∆(Ŷ (2)j+1) that
might possibly occur in N(v, X̂n) is c. So we can now choose v1, v2, . . . , vn−j
from Xn ∪Xn−1 · · · ∪Xj+1 ∪ (Xj \ Yj) such that these n− j vertices are joined
to v by edges which are all coloured by distinct elements of N(v, X̂n) \ {c}. Set
Yj+2 = {v1}, Yj+3 = {v2}, . . . , Yn+1 = {vn−j}.
We claim that Y is an (n+ 1)-homogeneous tuple. Indeed, conditions (1)
and (2) are obviously satisfied.
To check condition (3), first note that ∆(Ŷ
(2)
1 ) ( ∆(Ŷ
(2)
2 ) ( · · · ( ∆(Ŷ (2)j−1)
follows from the n-homogeneity of X since Yi = Xi for 1 ≤ i ≤ j − 1. Also,
∆(Ŷ
(2)
j−1) ( ∆(Ŷ
(2)
j ) since Yj is a non-empty subset of Xj. Next, ∆(Ŷ
(2)
j ) (
∆(Ŷ
(2)
j+1) since v is joined to at least one vertex of Yj by an edge coloured with
32
Xn Xj+1 Xj X1
v
N(v, X̂j)
u
N(u, X̂j)
Figure 1. Inserting v into X.
c and we know that c is a new colour from v into Ŷj. Finally, ∆(Ŷ
(2)
j+1) (
∆(Ŷ
(2)
j+2) ( · · · ( ∆(Ŷ (2)n+1) because the vertices v1, v2, . . . , vn−j are all joined to
v by edges of distinct colours and none of these colours belong to ∆(X̂
(2)
n ). So
condition (3) is also satisfied.
Condition (4) for each of Y1, Y2, . . . , Yj is equivalent to the same condition
for X1, X2, . . . , Xj respectively. Furthermore, condition (4) is also satisfied by
each of Yj+1, Yj+2, . . . , Yn+1 since they each contain exactly one vertex.
Finally, we check condition (5). Clearly, ∆(Ŷ
(2)
n+1) is a subset of ∆(X̂
(2)
n )∪ T
for some subset T of N(v, X̂n) of size at most n. Hence, we see that γ(Ŷn+1) ≤(
n
2
)
+ 1 + n =
(
n+1
2
)
+ 1.
Case 2: N(v, X̂n) = ∅ for every v ∈ N \ X̂n. To deal with this case, we
will need the following lemma.
Lemma 2.4. Let X be an n-homogeneous tuple and suppose N(v, X̂n) = ∅
for some v ∈ N\ X̂n. Then, there either exists an (n+ 1)-homogeneous tuple Y,
or an n-homogeneous tuple Z such that Zj = Xj ∪ {v} for some j ∈ [n], and
Zi = Xi for each 1 ≤ i ≤ n with i 6= j.
Proof. If N(v, X̂i) = ∅ for 1 ≤ i ≤ n, then (X1 ∪ {v}, X2, . . . , Xn) is
n-homogeneous and we have Z as required. Hence, let j < n be the largest
index such that N(v, X̂j) 6= ∅. So by the definition of j, N(v, X̂i) = ∅
for j < i ≤ n. Let Z = (X1, X2, . . . , Xj, Xj+1 ∪ {v}, Xj+2, . . . , Xn) and let
Y = (X1, X2, . . . , Xj, {v}, Xj+1, Xj+2, . . . , Xn); we claim that either Z is n-
homogeneous or Y is (n+ 1)-homogeneous.
33
Consider a colour c that belongs to N(v, X̂j). Since N(v, X̂j+1) = ∅, this
means that c must occur in ∆(X̂
(2)
j+1) \∆(X̂(2)j ). But, by condition (4), for each
u ∈ Xj+1, N(u, X̂j) = ∆(X̂(2)j+1) \ ∆(X̂(2)j ). Hence, N(v, X̂j) ⊂ N(u, X̂j) for
u ∈ Xj+1.
We first show that if N(v, X̂j) = N(u, X̂j) for u ∈ Xj+1, then Z is n-
homogeneous. Conditions (1) and (2) are clearly satisfied by Z. To see that
conditions (3) and (4) hold, first note that these conditions hold for all the Zi
with 1 ≤ i ≤ j since Zi = Xi for 1 ≤ i ≤ j. Both conditions hold for Zj+1 since
we have assumed that N(v, X̂j) = N(u, X̂j) for u ∈ Xj+1. Next, observe that
since N(v, X̂i) = ∅ for j < i ≤ n, we have N(u, X̂i−1) = N(u, X̂i−1 ∪ {v}) for
each u ∈ Xi with j + 1 < i ≤ n. From this observation, it follows that both
conditions hold for all the Zi with j + 1 < i ≤ n. Finally, condition (5) holds
since N(v, X̂n) = ∅.
If we instead have N(v, X̂j) ( N(u, X̂j) for u ∈ Xj+1, then we claim that
Y is (n+ 1)-homogeneous.
Clearly, conditions (1) and (2) are satisfied by Y. To check conditions
(3) and (4), we proceed as we did previously for Z. First note that these
conditions hold for all the Yi such that 1 ≤ i ≤ j since Yi = Xi for 1 ≤ i ≤ j.
Both conditions hold for the Yj+1 since Yj+1 consists of a single vertex v
and since N(v, X̂j) 6= ∅. To see that condition (3) holds for Yj+2, note that
∆(Ŷ
(2)
j+1) ( ∆(Ŷ
(2)
j+2) since N(v, X̂j) ( N(u, X̂j) for u ∈ Xj+1. We know that
N(v, X̂j+1) = ∅. Hence, condition (4) also holds for Yj+2 since for any vertex
u ∈ Yj+2 = Xj+1, we see that N(u, Ŷj+1) = N(u, X̂j) \ N(v, X̂j) = ∆(Ŷ (2)j+2) \
∆(Ŷ
(2)
j+1). Finally, both conditions also hold for all Yi with j + 2 < i ≤ n + 1.
This follows from the fact that N(u, X̂i−1 ∪ {v}) = N(u, X̂i−1) 6= ∅ for each
u ∈ Xi with j + 1 < i ≤ n. Finally, it is easy to see that condition (5) holds
since N(v, X̂n) = ∅.
34
We have assumed that N(v, X̂n) = ∅ for each v ∈ N \ X̂n. Now, ∆ is
surjective, so there must exist two vertices v1 and v2 in N \ X̂n such that the
edge joining v1 and v2 is coloured with a colour c not in ∆(X̂
(2)
n ).
We apply Lemma 2.4 to X and v1. If we find an (n + 1)-homogeneous
tuple Y, we are done. So suppose that the lemma yields n-homogeneous
tuple Z. Then clearly N(v2, Ẑn) = {c}. Thus, (Z1, Z2, . . . , Zn, {v2}) is an
(n+ 1)-homogeneous tuple. This completes the proof of the theorem.
3. Upper bounds
Erdo˝s proved in [45] that for a natural number n, the set Pn = {ab : a, b ≤ n}
has size o(n2). We base the proof of Theorem 1.3 on the observation that Pn is
exactly the set of sizes of all induced subgraphs of a complete bipartite graph
between two equal vertex classes of size n.
Let H(x, y, z) be the number of natural numbers n ≤ x having a divisor in
the interval (y, z]. Tenenbaum [105] showed that
H(x, y, z) = (1 + o(1))x if log y = o(log z), z ≤ √x. (1)
Ford [56] proved that
H(x, y, 2y) = Θ
(
x
(log y)δ(log log y)3/2
)
if 3 ≤ y ≤ √x, (2)
where δ = 1 − 1+log log 2
log 2
. Armed with these two facts, we can now prove
Theorem 1.3.
Proof of Theorem 1.3. We shall take
A = {k : ∃ a, b ∈ N with k − 1 = ab and log k ≤ a ≤ b}.
It follows from (1) that H(x, log x,
√
x) = (1 + o(1))x; as an easy consequence,
A has asymptotic density one. Now, for a fixed k ∈ A with k− 1 = ab, consider
a surjective k-colouring ∆ of the complete graph on N which colours all the
edges of the complete bipartite graph between [a] and [b + a] \ [a] with ab
35
distinct colours and all the other edges with the one colour not used so far. It
is easy to then see that
F∆ = {a′b′ + 1 : 1 ≤ a′ ≤ a, 1 ≤ b′ ≤ b} ∪ {1}.
Now, for any element a′b′ + 1 ∈ F∆, a/2i+1 < a′ ≤ a/2i for some i ≥ 0 and
so a′b′ ≤ ab/2i. Thus,
|F∆| ≤ 1 +
∑
i≥0
H
(
ab
2i
,
a
2i+1
,
a
2i
)
.
Using Ford’s estimate (2) for H(x, y, 2y) and the fact that a ≥ log k, we obtain
that
ψ(k) = O
(
k
(log log k)δ(log log log k)3/2
)
for all k ∈ A.
4. Concluding remarks
We suspect that something much stronger than Corollary 2.2 is true.
Conjecture 4.1. Let ∆ : N(2) [k] be a k-colouring and suppose n ≥ 2 is
a natural number such that k ≥ (n
2
)
+ 2. Then F∆∩ ([
(
n+1
2
)
+ 1]\ [(n
2
)
+ 1]) 6= ∅.
We return to this conjecture in the next chapter. There, we shall prove this
conjecture and we shall also study some generalisations of this conjecture to
uniform hypergraphs.
We strongly suspect that the function ψ studied in this chapter quite far from
being monotone. We have shown that ψ(
(
n
2
)
+ 1) = n and ψ(
(
n+1
2
)
+ 1) = n+ 1,
and it is an easy consequence of our results that ψ(
(
n
2
)
+ 2) = n+ 1. It would
appear that even ψ(
(
n
2
)
+ 3) is much bigger than n.
Conjecture 4.2. There is an absolute constant c > 0 such that ψ(
(
n
2
)
+3) >
(1 + c)n for all natural numbers n ≥ 2.
The problem of determining ψ completely is of course still open. We cannot
answer even the following question in its full generality.
36
Problem 4.3. Is ψ(k) = o(k) for all k ∈ N?
37
CHAPTER 4
Approximations to infinite m-coloured complete
hypergraphs
Joint work with Teeradej Kittipassorn.
1. Introduction
In the last chapter, we mentioned in passing that Stacey and Weidl, partially
resolving a conjecture of Erickson, showed that there exists, for every fixed
natural number m > 2 and all sufficiently large k ∈ N, a k-colouring of the
complete graph on N with no infinite m-coloured complete subgraph. In
the light of this result, we study how close we can get to finding an infinite
m-coloured complete subgraph (and more generally, an infinite m-coloured
complete subhypergraph) in this chapter.
We briefly describe how the notations and definitions of the previous two
chapters extend to the setting of hypergraphs. For a set X, we write X(r) for
the family of all subsets of X of cardinality r; equivalently, X(r) is the complete
r-uniform hypergraph on the vertex set X. By a colouring of a hypergraph, we
mean a colouring of the edges of the hypergraph.
Let ∆ : N(r) [k] be a surjective k-colouring of the edges of the complete
r-uniform hypergraph on the natural numbers. As before, we say that a subset
X ⊂ N is (exactly) m-coloured if ∆(X(r)), the set of values attained by ∆ on
the edges induced by X, has size exactly m. Let γ∆(X), or γ(X) in short,
denote the size of the set ∆(X(r)); in other words, every set X is γ(X)-coloured.
In this chapter, we shall study for fixed r and large k, the set of values m
for which there exists an infinite m-coloured set with respect to a k-colouring
39
∆ : N(r) [k]. As before, let us define
F∆ = {γ∆(X) : X ⊂ N such that X is infinite}.
In the case of graphs, i.e., when r = 2, Stacey and Weidl [104], partially
resolving a previously discussed conjecture of Erickson [52], showed using a
probabilistic construction that for every m > 2, there is a constant Cm such
that if k > Cm, then there is a k-colouring ∆ of N(2) such that m /∈ F∆. Since
an infinite m-coloured complete subgraph is not guaranteed to exist, we are
naturally led to the question of whether we can find, given m, an infinite
mˆ-coloured complete subgraph for some mˆ close to m. In this chapter, we
establish the following result.
Theorem 1.1. For any k-colouring ∆ : N(r) [k] and any natural number
m ≤ k, there exists an mˆ ∈ F∆ such that
|m− mˆ| ≤ crm1−1/r +O(m1−2/r)
where cr = r/(2(r!)
1/r).
Theorem 1.1 is tight up to the O(m1−2/r) term. To see this, let k =
(
n
r
)
+ 1
for some n ∈ N. We consider the ‘small-rainbow colouring’ ∆ which colours
all the edges induced by [n] with
(
n
r
)
distinct colours and all the remaining
edges with the one colour that has not been used so far. In this case, we see
that F∆ = {
(
i
r
)
+ 1 : i ≤ n}. Now let m be the positive integer closest to
(
(
l
r
)
+
(
l+1
r
)
+ 2)/2 for some natural number l such that l < n. It follows that
|m− mˆ| ≥ ( l
r−1
)
/2− 1 for each mˆ ∈ F∆; furthermore, it is easy to check that(
l
r−1
)
/2 = (cr − o(1))m1−1/r.
In the case of graphs where r = 2, Theorem 1.1 tells us that for any
finite colouring of the edges of the complete graph on N with m or more
colours, there is an infinite mˆ-coloured complete subgraph for some mˆ satisfying
|m− mˆ| ≤√m/2 +O(1); a careful analysis of the proof of Theorem 1.1 in this
case allows us to replace the O(1) term with an explicit constant, 1/2.
40
We know from Theorem 1.1 that F∆ cannot contain very large gaps. Another
natural question we are led to ask is if there are any sets, and in particular,
intervals, that F∆ is guaranteed to intersect. More precisely, it was conjectured
(see [91] and also, the previous chapter) that the small-rainbow colouring
described above is extremal for graphs in the following sense.
Conjecture 1.2. Let ∆ : N(2) [k] be a k-colouring of the complete
graph on N and suppose n is a natural number such that k >
(
n
2
)
+ 1. Then
F∆ ∩ (
(
n
2
)
+ 1,
(
n+1
2
)
+ 1] 6= ∅.
In this chapter, we shall prove this conjecture. There are two natural
generalisations of this conjecture to r-uniform hypergraphs which are equivalent
to Conjecture 1.2 in the case of graphs.
The first comes from considering small-rainbow colourings; indeed we can
ask whether F∆ ∩ Ir,n 6= ∅ when k >
(
n
r
)
+ 1, where Ir,n is the interval
(
(
n
r
)
+ 1,
(
n+1
r
)
+ 1].
The second comes from considering a different family of colourings which
we call ‘small-set colourings’. Let k =
∑r
i=0
(
n
i
)
and consider the surjective
k-colouring ∆ of N(r) defined by ∆(e) = e ∩ [n]. Note that in this case,
F∆ = {
∑r
i=0
(
j
i
)
: j ≤ n}. Consequently, we can ask whether F∆ ∩ Jr,n 6= ∅
when k >
∑r
i=0
(
n−1
i
)
, where Jr,n is the interval (
∑r
i=0
(
n−1
i
)
,
∑r
i=0
(
n
i
)
].
Note that both these questions are identical when r = 2. Indeed
(
n
2
)
+
(
n
1
)
+(
n
0
)
=
(
n+1
2
)
+ 1 and so I2,n = J2,n. When r ≥ 3, we see that Jr,n is longer than
Ir,n; furthermore, for any fixed r ≥ 3 and all sufficiently large n, we note that
Jr,n always intersects, and lies to the right of, Ir,n.
We shall demonstrate that the correct generalisation is the former. We shall
first prove that the answer to the first question is in the affirmative, provided
n is sufficiently large.
Theorem 1.3. For every r ≥ 2, there exists a natural number nr ≥ r − 1
such that for any natural number n ≥ nr and any k-colouring ∆ : N(r) [k]
with k >
(
n
r
)
+ 1, F∆ ∩ Ir,n 6= ∅.
41
Using a result of Baranyai [21] on factorisations of uniform hypergraphs, we
shall exhibit an infinite family of colourings that answer the second question
negatively for every r ≥ 3.
Theorem 1.4. For every r ≥ 3, there exist infinitely many values of n for
which there exists a k-colouring ∆ : N(r) [k] with k >
∑r
i=0
(
n−1
i
)
such that
F∆ ∩ Jr,n = ∅.
The rest of this chapter is organised as follows. In the next section, we shall
prove Theorems 1.1, 1.3 and 1.4 and deduce Conjecture 1.2 from the proof of
Theorem 1.3. We then conclude by mentioning some open problems.
2. Proofs of the main results
We start with the following lemma which we shall later use to prove both
Theorems 1.1 and 1.3.
Lemma 2.1. Let m ≥ 2 be an element of F∆. Then there exists a natural
number a = a(m,∆) such that
(1)
∑r
i=0
(
a
i
) ≥ m, and
(2) F∆ ∩ [m−min(
∑r−1
i=0
(
a−1
i
)
, r(m− 1)/a),m) 6= ∅.
Futhermore, if
m =
r∑
i=t+1
(
a
i
)
+ s+ 1
for some s ≥ 0 and 0 ≤ t+ 1 ≤ r, then
F∆ ∩
[
r∑
i=t+1
(
a− 1
i
)
+
(
1− t
a
)
s+ 1,m
)
6= ∅.
Proof. We start by establishing the following claim.
Claim 2.2. There is an infinite m-coloured set X ⊂ N with a finite subset
A ⊂ X such that
(1) the colour of every edge of X is determined by its intersection with A,
i.e., if e1 ∩ A = e2 ∩ A, then ∆(e1) = ∆(e2), and
42
(2) γ(X \ {v}) < m for all v ∈ A.
Proof. To see this, let W ⊂ N be an infinite m-coloured set. For each
colour c ∈ ∆(W (r)), pick an edge ec in W of colour c and let A =
⋃
c ec be
the set of vertices incident to these edges. So A ⊂ W is a finite m-coloured
set. Let A1, A2, . . . , Al be an enumeration of the subsets of A of size at most
r. Note that this is the complete list of possible intersections of an edge with
A. We now define a descending sequence of infinite sets B0 ⊃ B1 ⊃ · · · ⊃ Bl
as follows. Let B0 = W \ A. Having defined the infinite set Bi−1, we induce
a colouring of the (r − |Ai|)-tuples T of Bi−1, by giving T the colour of the
edge Ai ∪ T . By Ramsey’s Theorem, there is an infinite monochromatic subset
Bi ⊂ Bi−1 with respect to this induced colouring, and so the edges of A ∪Bi
whose intersection with A is Ai have the same colour.
Hence, X = A ∪ Bl is an infinite m-coloured set satisfying property (1).
Now, if we have a vertex v ∈ A such that γ(X \ {v}) = m, we delete v from A.
We repeat this until we are left with an m-coloured set X satisfying (1) and
(2).
Let X and A be as guaranteed by Claim 2.2. Note that A is nonempty since
m ≥ 2. We shall prove the lemma with a(m,∆) = |A|. From the structure of
X and A, we note that
∑r
i=0
(
a
i
) ≥ m. That
F∆ ∩
[
m−min
(
r−1∑
i=0
(
a− 1
i
)
,
r(m− 1)
a
)
,m
)
6= ∅
is a consequence of the following claim.
Claim 2.3. There exist infinite sets X1, X2 ⊂ X for which we have m −∑r−1
i=0
(
a−1
i
) ≤ γ(X1) < m and m− r(m− 1)/a ≤ γ(X2) < m.
Proof. Let X1 = X \ {v} for any v ∈ A. We know from Claim 2.2 that
γ(X1) < m. We shall now prove that γ(X1) ≥ m −
∑r−1
i=0
(
a−1
i
)
; that is, the
number of colours lost by removing v from X is at most
∑r−1
i=0
(
a−1
i
)
. Since
the colour of an edge is determined by its intersection with A, the number of
43
colours lost is at most the numbers of subsets of A containing v of size at most
r, which is precisely
∑r−1
i=0
(
a−1
i
)
.
Next, we shall prove that there is a subset X2 ⊂ X such that m− r(m−
1)/a ≤ γ(X2) < m. Let A = {v1, v2, . . . , va} and let
Ci = ∆
(
X(r)
) \∆((X \ {vi})(r))
be the set of colours lost by removing vi from X; since γ(X \ {vi}) < m for all
vi ∈ A, it follows that Ci 6= ∅. For each colour c ∈ ∆(X(r)), pick an edge ec
of colour c, and let Ac = ec ∩ A; in particular, we take Ac∅ = ∅, where c∅ is
the colour corresponding to an empty intersection with A. Since every edge
of colour c ∈ Ci contains vi, we double count the number of times a colour is
counted in the sum
∑a
i=1 |Ci| to obtain
a∑
i=1
|Ci| ≤
∑
c 6=c∅
|Ac| ≤ r(m− 1),
and so there exists an i such that 0 < |Ci| ≤ r(m− 1)/a; the claim follows by
taking X2 = X \ {vi}.
We finish the proof of the lemma by establishing the following claim.
Claim 2.4. If we can write m =
∑r
i=t+1
(
a
i
)
+ s+ 1, then
F∆ ∩
[
r∑
i=t+1
(
a− 1
i
)
+
(
1− t
a
)
s+ 1,m
)
6= ∅.
Proof. As in the proof of Claim 2.3, for each colour c ∈ ∆(X(r)), pick
an edge ec of colour c, and let Ac = ec ∩ A; in particular, let Ac∅ = ∅. We
know from Claim 2.2 that edges of X of distinct colours cannot have the same
intersection with A. Consequently, all the Ac are distinct subsets of A, each of
size at most r. Hence,
∑
c6=c∅
|Ac| ≤
r∑
i=t+1
i
(
a
i
)
+ ts.
44
Arguing as in the proof of Claim 2.3, we conclude that there exists a vertex
v ∈ A such that the number of colours lost by removing v from X is at most
(
∑r
i=t+1 i
(
a
i
)
+ ts)/a. Therefore
γ(X \ {v}) ≥ m− 1
a
(
r∑
i=t+1
i
(
a
i
)
+ ts
)
= m−
(
r∑
i=t+1
(
a− 1
i− 1
)
+
ts
a
)
=
r∑
i=t+1
(
a− 1
i
)
+
(
1− t
a
)
s+ 1,
and so
F∆ ∩
[
r∑
i=t+1
(
a− 1
i
)
+
(
1− t
a
)
s+ 1,m
)
6= ∅.
The lemma follows from Claims 2.2, 2.3 and 2.4. We are done.
Having established Lemma 2.1, it is easy to deduce both Theorem 1.1
and 1.3 from the lemma.
Proof of Theorem 1.1. Let t = m + crm
1−1/r. We may assume that
m > rr/r! since otherwise m = O(1) and there is nothing to prove. Also, if
t ≥ k, then the result follows easily by taking mˆ = k so we may assume that
t < k. Let tˆ be the smallest element of F∆ greater than t. Applying Lemma 2.1
to tˆ, we find an mˆ ∈ F∆ such that mˆ ≤ t and
mˆ ≥ tˆ−min
(
r−1∑
i=0
(
a− 1
i
)
,
r(tˆ− 1)
a
)
for some natural number a. Now if a ≥ (r!m)1/r > r, then
mˆ ≥ tˆ− r(tˆ− 1)
a
≥ tˆ
(
1− r
a
)
≥ t
(
1− r
a
)
45
and so it follows that mˆ ≥ m− crm1−1/r −O(m1−2/r). If a < (r!m)1/r on the
other hand, then using the fact that
mˆ ≥ tˆ−
r−1∑
i=0
(
a− 1
i
)
≥ t− a
r−1
(r − 1)! −O(a
r−2)
≥ t− (r!m)
1−1/r
(r − 1)! −O(m
1−2/r),
it follows once again that mˆ ≥ m− crm1−1/r −O(m1−2/r).
Proof of Theorem 1.3. If k ≤ (n+1
r
)
+ 1, we are done since k ∈ F∆. So
suppose that k >
(
n+1
r
)
+ 1. Let m be the smallest element of F∆ such that
m >
(
n+1
r
)
+ 1; hence, F∆ ∩ (
(
n+1
r
)
+ 1,m) = ∅. Now, since m ≥ 2, there exists
by Lemma 2.1, a natural number a such that
F∆ ∩
[
m− r(m− 1)
a
,
(
n+ 1
r
)
+ 1
]
6= ∅.
To prove the theorem, it is sufficient to show that m− r(m− 1)/a > (n
r
)
+ 1.
We know from Lemma 2.1 that
∑r
i=0
(
a
i
) ≥ m > (n+1
r
)
+ 1. If n is sufficiently
large, we must have a ≥ n. Indeed, if a ≤ n− 1, then(
n+ 1
r
)
+ 1−
r∑
i=0
(
a
i
)
≥
(
n+ 1
r
)
−
(
n− 1
r
)
−
(
n− 1
r − 1
)
−
r−2∑
i=1
(
n− 1
i
)
=
(
n
r − 1
)
−
r−2∑
i=1
(
n− 1
i
)
> 0,
where the last inequality holds for all sufficiently large n since coefficient of the
highest power of n in the expression is positive; this is a contradiction.
If a ≥ n+ 1, then
m− r(m− 1)
a
= (m− 1)
(
1− r
a
)
+ 1
>
(
n+ 1
r
)(
1− r
n+ 1
)
+ 1
46
=(
n
r
)
+ 1
since m >
(
n+1
r
)
+ 1 and n ≥ r − 1.
We now deal with the case a = n. First, we write m =
(
n
r
)
+
(
n
r−1
)
+ s+ 1.
Since m >
(
n+1
r
)
+1 and
(
n
r
)
+
(
n
r−1
)
=
(
n+1
r
)
, we see that s > 0. By Lemma 2.1,
it follows that
F∆ ∩
[(
n
r
)
+
(
1− r − 2
n
)
s+ 1,m
)
6= ∅.
Since n ≥ r − 1 and s > 0, the result follows.
A careful inspection of the proof of Theorem 1.3 shows that when r = 2,
the statement holds for all n ∈ N. Indeed, we only need n to be large enough
to ensure that
(
n
r−1
) −∑r−2i=1 (n−1i ) > 0; when r = 2, this holds for all n ∈ N.
We hence obtain a proof of Conjecture 1.2.
We now turn to the proof of Theorem 1.4. We require a result of Baranyai [21]
which states that the set of edges of the complete r-uniform hypergraph on l
vertices can be partitioned into perfect matchings when r | l.
Proof of Theorem 1.4. We shall show that if n is sufficiently large
and (r − 1) | (n + 1), then there is a surjective k-colouring ∆ of N(r) with
k >
∑r
i=0
(
n−1
i
)
and F∆ ∩ Jr,n = ∅. We shall define a colouring of N(r) such
that the colour of an edge e is determined by its intersection with a set A of
size n+ 1, say A = [n+ 1]. Let B be the family of all subsets of A of size at
most r. For B ∈ B, we denote the colour assigned to all the edges e such that
e ∩ A = B by cB.
To define our colouring, we shall construct a partition B = B1 ∪ B2 with
∅ ∈ B2. Then for every B ∈ B2, we set cB to be equal to c∅. Finally, we take
the colours cB for B ∈ B1 to all be distinct and different from c∅. Hence, the
number of colours used is k = |B1|+ 1. It remains to construct this partition
of B.
47
Since (r − 1) | (n+ 1), by Baranyai’s theorem there exists an ordering
B1, B2, . . . , B(n+1r−1)
of the subsets of A of size r − 1 such that for all 0 ≤ t ≤ ( n
r−2
)
, the family{
B(n+1r−1 )t+1
, B(n+1r−1 )t+2
, . . . , B(n+1r−1 )(t+1)
}
is a perfect matching. Let B1 = {B1, B2, . . . , Bs} ∪ {B ∈ B : |B| = r}, where
s =
r∑
i=0
(
n
i
)
−
(
n+ 1
r
)
=
r−2∑
i=0
(
n
i
)
.
Our colouring is well defined because 0 ≤ s ≤ (n+1
r−1
)
for all sufficiently large n;
here, the second inequality follows immediately by considering the coefficient
of the highest power of n. Observe that
k = |B1|+ 1 =
(
n+ 1
r
)
+ s+ 1 =
r∑
i=0
(
n
i
)
+ 1.
We shall show that the second largest element of F∆ is at most
∑r
i=0
(
n−1
i
)
.
Note that any X ⊂ N with γ(X) < k cannot contain A. As before, let Ci be
the set of colours lost by removing i ∈ A from N, i.e.,
Ci = ∆
(
N(r)
) \∆((N \ {i})(r)).
We shall complete the proof by showing that k − |Ci| ≤
∑r
i=0
(
n−1
i
)
for all
i ∈ A.
Note that our construction ensures that ||Ci| − |Cj|| ≤ 1 for all i, j ∈ A.
Now, observe that
n+1∑
i=1
|Ci| =
∑
B∈B1
|B| = r
(
n+ 1
r
)
+ (r − 1)s,
and so |Ci| ≥ (r
(
n+1
r
)
+ (r − 1)s)/(n+ 1)− 1 for all i ∈ A. Hence,
k − |Ci| ≤
((
n+ 1
r
)
+ s+ 1
)
− 1
n+ 1
(
r
(
n+ 1
r
)
+ (r − 1)s
)
+ 1
48
=(
n
r
)
+
(
1− r − 1
n+ 1
)
s+ 2
=
(
n
r
)
+
(
1− r − 1
n+ 1
)( r∑
i=0
(
n
i
)
−
(
n+ 1
r
))
+ 2
≤
r∑
i=0
(
n− 1
i
)
,
where the last inequality holds when r ≥ 4 for all sufficiently large n. To see
this, we note that verifying the last inequality reduces to checking that(
1− r − 1
n+ 1
)( r−2∑
i=0
(
n
i
))
+ 2 ≤
r−2∑
i=0
(
n− 1
i
)
.
To check this, we first note that for each 0 ≤ i ≤ r − 3, we have(
1− r − 1
n+ 1
)(
n
i
)
=
n(n+ 2− r)
(n+ 1)(n− i)
(
n− 1
i
)
≤
(
n− 1
i
)
.
and that furthermore, we have(
n− 1
r − 2
)
−
(
1− r − 1
n+ 1
)(
n
r − 2
)
=
1
n+ 1
(
n− 1
r − 2
)
> 2
for all sufficiently large n since r ≥ 4.
When r = 3, it is easy to check that s = n + 1 and so s is divisible by
(n+ 1)/(r − 1) = (n+ 1)/2. Consequently, in this case, |Ci| = |Cj| for i, j ∈ A.
Hence,
k − |Ci| ≤
((
n+ 1
3
)
+ s+ 1
)
− 1
n+ 1
(
r
(
n+ 1
3
)
+ 2s
)
=
(
n
3
)
+
(
1− 2
n+ 1
)
(n+ 1) + 1
=
3∑
i=0
(
n− 1
i
)
.
This completes the proof.
49
3. Concluding remarks
We conclude by mentioning two open problems. We proved that for any
k-colouring ∆ : N(r) [k] and every sufficiently large natural number n,
F∆ ∩ Ir,n 6= ∅ provided k >
(
n
r
)
+ 1. A careful analysis of our proof shows that
the result holds when n ≥ (5/2 + o(1))r; we chose not to give details to keep
the presentation simple. However, we suspect that the result should hold as
long as n ≥ r − 1 but a proof eludes us.
To state the next problem, let us define
ψr(k) = min
∆:N(r)[k]
|F∆|.
A consequence of Theorem 1.3 is that ψr(k) ≥ (1− o(1))(r!k)1/r. Turning to
the question of upper bounds for ψr, the small-rainbow colouring shows that
the lower bound that we get from Theorem 1.3 is tight infinitely often, i.e.,
when k is of the form
(
n
r
)
+ 1 for some n ∈ N. However, when k is not of this
form, the obvious generalisations of the small-rainbow colouring fail to give us
good upper bounds for ψr(k). We saw in the previous chapter that
ψ2(k) = O
(
k
(log log k)δ(log log log k)3/2
)
for almost all natural numbers k and some absolute constant δ > 0. For every
r ≥ 2, by colouring a copy of N(2) in N(r) (corresponding to all the r-element
subsets of N containing some fixed (r − 2)-element set) as in the previous
chapter, and all the other edges of N(r) with a different colour, we see that
ψr(k) = o(k) almost all natural numbers k. It would be very interesting to
decide if, in fact, ψr(k) = o(k) for all k ∈ N.
50
Part 2
Probabilistic combinatorics
CHAPTER 5
Transference for the Erdo˝s–Ko–Rado theorem, I
Joint work with Be´la Bolloba´s and Andrei Raigorodskii.
1. Introduction
In this chapter, our aim is to investigate the stability of a central result in
extremal set theory due to Erdo˝s, Ko and Rado [46] about uniform intersecting
families of sets. A family of sets A is said to be intersecting if A ∩B 6= ∅ for
all A,B ∈ A. We are interested in intersecting families where all the sets have
the same size; writing [n] for the set {1, 2, . . . , n} and [n](r) for the family of
all the subsets of [n] of cardinality r, the Erdo˝s–Ko–Rado theorem asserts that
if A ⊂ [n](r) is intersecting and n ≥ 2r, then |A| ≤ (n−1
r−1
)
and that equality is
only achieved, if n > 2r, when A is a star ; for x ∈ [n], the star centred at x
is the family of all the r-element subsets of [n] containing x. Extending this
result, Hilton and Milner [68] determined, when n > 2r, the largest size of a
uniform intersecting family not contained entirely in a star. Many extensions
of the Erdo˝s–Ko–Rado theorem and the Hilton–Milner theorem have since
been proved; furthermore, very general stability results about the structure of
intersecting families have been proved by Friedgut [58], Dinur and Friedgut [43],
and Keevash and Mubayi [74].
Here, we shall investigate a different notion of stability and prove a ‘sparse
random’ analogue of the Erdo˝s–Ko–Rado theorem which strengthens the Erdo˝s–
Ko–Rado theorem significantly when r is small compared to n.
To translate the Erdo˝s–Ko–Rado theorem to the random setting, it will be
helpful to reformulate the theorem as a statement about Kneser graphs. For
53
natural numbers n, r ∈ N with n ≥ r, the Kneser graph K(n, r) is the graph
whose vertex set is [n](r) where two r-element sets A,B ∈ [n](r) are adjacent
if and only if A ∩B = ∅. Observe that a family A ⊂ [n](r) is an intersecting
family if and only if A is an independent set in K(n, r). Writing α(G) for the
size of the largest independent set in a graph G, the Erdo˝s–Ko–Rado theorem
asserts that α(K(n, r)) =
(
n−1
r−1
)
when n ≥ 2r; furthermore, when n > 2r, the
only independent sets of this size are stars.
Let us now randomly delete the edges of the Kneser graph K(n, r) retaining
them with some probability p, independently of each other. When is the
independence number of this random subgraph equal to
(
n−1
r−1
)
? It turns out
that when r is much smaller than n, an analogue of the Erdo˝s–Ko–Rado
theorem continues to be true even after we delete practically all the edges of
the Kneser graph!
This kind of phenomenon, namely the validity of classical extremal results
for surprisingly sparse random structures, has received a lot of attention over
the past twenty five years.
Perhaps the first result of this kind in extremal graph theory was proved by
Babai, Simonovits, and Spencer [8] who showed that an analogue of Mantel’s
Theorem is true for certain random graphs. Mantel’s Theorem states that
the largest triangle free subgraph and the largest bipartite subgraph of Kn,
the complete graph on n vertices, have the same size. Babai, Simonovits, and
Spencer proved that the same holds for the Erdo˝s-Re´nyi random graph G(n, p)
with high probability when p ≥ 1/2− δ for some absolute constant δ > 0. In
other words, they show that Mantel’s theorem is ‘stable’ in the sense that it
holds not only for the complete graph but that it holds exactly for random
subgraphs of the complete graph as well. Improving upon results of Brightwell,
Panagiotou and Steger [34], DeMarco and Kahn [41] have recently shown that
this phenomenon continues to hold even when the random graph G(n, p) is
very sparse; they show in particular that it suffices to take p ≥ C(log n/n)1/2
54
for some absolute constant C > 0, and that this is best possible up to the value
of the absolute constant.
The first such transference results in Ramsey theory were proved by Ro¨dl
and Rucin´ski [97, 98] and there have been many related Ramsey theoretic
results since; see, for example, [59, 99, 79].
Phenomena of this kind have also been observed in additive combinatorics.
Roth’s theorem [101], a central result in additive combinatorics, states that for
every δ > 0 and all sufficiently large n, every subset of [n] = {1, 2, . . . , n} of
density δ contains a three-term arithmetic progression. Kohayakawa, Ro¨dl and
Luczak [78] proved a random analogue, showing that such a statement holds
not only for [n] but also, with high probability, for random subsets of [n] of
density at least Cn−1/2, where C > 0 is an absolute constant.
Another classical result in additive combinatorics, due to Diananda and
Yap [42], is that the largest sum-free subset of Z2n is the set of odd numbers.
Balogh, Morris and Samotij [20] proved that the same is true of random subsets
of Z2n of density at least (1 + ε)(log n/3n)1/2 with high probability (for any
fixed ε > 0 and n sufficiently large), and also that this no longer the case when
the density is less than (1− ε)(log n/3n)1/2. Thus, there is a sharp threshold at
(log n/3n)1/2 for the stability of this extremal result; an extension of this sharp
threshold result to all even-order Abelian groups has recently been proved by
Bushaw, Collares Neto, Morris and Smith [35].
Perhaps the most striking application of such transference principles in
additive combinatorics is the Green–Tao theorem [66] on primes in arithmetic
progressions.
These results constitute a tiny sample of the large number of beautiful results
which have been proved in this setting. Very general transference theorems have
been proved by Conlon and Gowers [40] and Schacht [103], and more recently,
by Balogh, Morris and Samotij [19] and Saxton and Thomason [102]. We refer
the interested reader to the surveys of Luczak [87] and Ro¨dl and Schacht [100]
for a more detailed account of such results.
55
Returning to the question at hand, our aim in this chapter, as we remarked
before, is to investigate the independence number of random subgraphs of
K(n, r); for related work on the independence number of random induced
subgraphs of K(n, r), see the paper of Balogh, Bohman and Mubayi [13]. Let
Kp(n, r) denote the random subgraph of K(n, r) obtained by retaining each
edge of K(n, r) independently with probability p. The main question of interest
is the following.
Problem 1.1. For what p > 0 is α(Kp(n, r)) =
(
n−1
r−1
)
with high probability?
For constant r and n sufficiently large, a partial answer was provided by
Bogolyubskiy, Gusev, Pyaderkin and Raigorodskii [25, 24]: they studied random
subgraphs of K(n, r, s), where K(n, r, s) is the graph whose vertex set is [n](r)
where two r-element sets A,B ∈ [n](r) are adjacent if and only if |A ∩B| = s;
in the case s = 0 (which corresponds to the Kneser graph), they established
that α(K1/2(n, r)) = (1 + o(1))
(
n−1
r−1
)
with high probability.
We shall do much more and answer Question 1.1 exactly when r is small
compared to n (more precisely, when r = o(n1/3)). To state our result, it will
be convenient to define the threshold function
pc(n, r) =
(r + 1) log n− r log r(
n−1
r−1
) . (3)
As we shall see, this is the threshold density at which one expects to find a
vertex in Kp(n, r) which has no edges to a maximal independent set of the
original Kneser graph K(n, r). With this definition in place, we can now state
our main result.
Theorem 1.2. Fix a real number ε > 0 and let r = r(n) be a natural
number such that 2 ≤ r(n) = o(n1/3). Then as n→∞,
P
(
α(Kp(n, r)) =
(
n− 1
r − 1
))
→
1 if p ≥ (1 + ε)pc(n, r)0 if p ≤ (1− ε)pc(n, r).
56
Furthermore, when p ≥ (1 + ε)pc, with high probability, the only independent
sets of size
(
n−1
r−1
)
in Kp(n, r) are the trivial ones, namely, stars.
The rest of this chapter is organised as follows. We establish some notation
and collect together some standard facts in Section 2. Most of the work involved
in proving Theorem 1.2 is in establishing the upper bound on the critical density;
we do this in Section 3. We complete the proof of Theorem 1.2 by proving
a matching lower bound in Section 4. We conclude with some discussion in
Section 5.
2. Preliminaries
2.1. Notation. Given x ∈ [n] and A ⊂ [n](r), we write Sx for the star
centred at x, and Ax for the subfamily of A consisting of those sets (of A) that
contain x, i.e., Ax = A∩ Sx. The maximum degree d(A) of a family A ⊂ [n](r)
is defined to be the maximum cardinality, over all x ∈ [n], of the subfamily Ax,
and we write e(A) for the number of edges induced by A in K(n, r). Since any
pair of intersecting sets A,B ∈ A both belong to at least one subfamily Ax, we
get the following estimate for e(A) which is useful when the maximum degree
of A is small.
Proposition 2.1. For any A ⊂ [n](r),
e(A) ≥
(|A|
2
)
−
∑
x∈[n]
(|Ax|
2
)
.
To ease the notational burden, in the rest of this chapter, we shall write
V =
(
n
r
)
for the size of [n](r), and N =
(
n−1
r−1
)
for the size of a star. Also, given
x ∈ [n] and a set A ∈ [n](r) not containing x, we shall write M = (n−r−1
r−1
)
for
the number of sets of Sx disjoint from A.
A word on asymptotic notation; we use the standard o(1) notation to denote
any function that tends to zero as n tends to infinity. Here and elsewhere,
the variable tending to infinity will always be n unless we explicitly specify
otherwise.
57
2.2. Estimates. Next, we collect some standard estimates that we shall
use repeatedly; for ease of reference, we list them as propositions below. We
refer the reader to Chapter 1 of [27] for the proofs of these claims.
Let us start with a weak form of Stirling’s approximation for the factorial
function.
Proposition 2.2. For all n ∈ N,
√
2pin
(n
e
)n
≤ n! ≤ e1/12n
√
2pin
(n
e
)n
.
In fact, the following crude bounds for the binomial coefficients will often
be sufficient for our purposes.
Proposition 2.3. For all n, r ∈ N,(n
r
)r
≤
(
n
r
)
≤ n
r
r!
≤
(en
r
)r
.
Also, we will need the following standard inequality concerning the expo-
nential function.
Proposition 2.4. For every x ∈ R such that |x| ≤ 1/2,
ex−x
2 ≤ 1 + x ≤ ex.
Although our last proposition is also very simple, we prove it here for the
sake of completeness. Recall that N =
(
n−1
r−1
)
and M =
(
n−r−1
r−1
)
.
Proposition 2.5. If r = r(n) = o(n1/2), then N−M = o(N). Furthermore,
if r = o(n1/3), then N−M = o(N/r).
Proof. Both claims follow from the observation that
N−M =
(
n− 1
r − 1
)
−
(
n− r − 1
r − 1
)
=
r∑
i=1
(
n− i
r − 1
)
−
(
n− i− 1
r − 1
)
58
=
r∑
i=1
(
n− i− 1
r − 2
)
≤ r
(
n− 2
r − 2
)
=
r(r − 1)
n− 1 N.
3. Upper bound for the critical threshold
We now turn to our proof of Theorem 1.2. In this section, we shall bound
the critical threshold from above, i.e., we shall prove that a random analogue
of the Erdo˝s–Ko–Rado theorem holds if p > (1 + ε)pc(n, r) where pc(n, r) is
given by (3).
Let us remind the reader before we begin that for us, a star in the Kneser
graph is a maximal trivial intersecting family of sets (and this should not be
confused with the graph-theoretic notion of a star).
Proof of the upper bound in Theorem 1.2. Let 0 < ε < 1/2 and
set p = p(n) = (1 + ε)pc(n, r). We shall prove that with high probability,
the independence number of Kp(n, r) is N, and that furthermore, the only
independent sets of size N in Kp(n, r) are stars. Since we are working with
monotone properties, it suffices to prove this result for ε small enough and so
we lose nothing by assuming 0 < ε < 1/2.
For each i ≥ 1, let Xi be the number of families A ⊂ [n](r) inducing an
independent set in Kp(n, r) such that |A| = N and d(A) = N− i. Also, let Y
be the number of independent families A ⊂ [n](r) such that |A| = N + 1 and
d(A) = N; in other words, independent families of size N + 1 which contain an
entire star.
Our aim is to show that with high probability, the random variables defined
above are all equal to zero. This then implies the lower bound on the critical
threshold; since every Xi is equal to zero, every independent set in Kp(n, r) of
cardinality at least N must contain an entire star, and since Y is also equal to
zero, the only independent sets of cardinality at least N are stars.
59
We start by computing E[Y ]. We know that for any star S, any A ∈ [n](r)\S
is disjoint from M elements of S, and so,
E[Y ] =
(
n
1
)(
V −N
1
)
(1− p)M. (4)
When r = o(n1/3) (indeed, when r = o(n1/2)), we know from Proposition 2.5
that M = (1 + o(1))N. Since p = (1 + ε)((r+ 1) log n− r log r)/N, we see that
E[Y ] ≤ nV(1− p)(1+o(1))N
≤ n
(en
r
)r
exp ((−1 + o(1))pN)
≤ n
(en
r
)r
exp ((1 + ε+ o(1))(r log r − (r + 1) log n))
≤
(er
n
)(ε+o(1))r
≤ n−(ε+o(1))2r/3 = o(1).
By Markov’s inequality, we know that P(Y > 0) ≤ E[Y ] and it follows that
Y is zero with high probability.
We now turn our attention to the Xi. To keep our argument simple, we
distinguish three cases: we first deal with small values of i where the Xi count
families of very large maximum degree, then we consider families of large (but
not huge) maximum degree, and in the final case, we deal with families of small
maximum degree.
Case 1: Very large maximum degree. Unfortunately, when i is small,
it is not true that E[Xi] goes to zero as n grows. For constant i, E[Xi] ≥
n
(
N
i
)(
V−N
i
)
(1− p)(i+o(1))N. When r = 3 and i = 2 for example, it follows that
E[X2] ≥ n
((n−1
2
)
2
)((n
3
)− (n−1
2
)
2
)
(1− p)(2+o(1))N
≥ no(1) n
11
n8(1+ε)
≥ n3−8ε+o(1),
which grows with n when ε is small enough. However, if we compute Var [X2],
we are encouraged to find that Var [X2]/E[X2]2 is bounded away from zero;
60
indeed, we observe similar behaviour for any fixed value of i and larger r as
well. We therefore adopt a different strategy to bound P(Xi > 0) for small i.
For j ≥ i, let Xi,j be the number of families A ⊂ [n](r) inducing a maximal
independent set in Kp(n, r) such that d(A) = N− i and |A| = N + j − i. If
Xi > 0, then clearly Xi,j > 0 for some j ≥ i. To compute E[Xi,j], we note
that any family A counted by Xi,j can be described by specifying a star S, a
subfamily A1 ⊂ S of i sets missing from S, and another family A2 of cardinality
j disjoint from S such that
(1) all the edges between S \ A1 and A2 in K(n, r) are absent in Kp(n, r)
(since A is independent), and
(2) each set in A1 is adjacent to at least one set in A2 in Kp(n, r) (because
A is a maximal independent set).
The number of edges between S \ A1 and A2 is at least j(M− i) since any
set not in a star is adjacent to precisely M sets in the star in K(n, r). Also,
the probability that a set in A1 has a neighbour in A2 in Kp(n, r) is at most
jp. Therefore, we have
E[Xi,j] ≤ n
(
N
i
)(
V
j
)
(1− p)j(M−i)(jp)i.
We look at the ratio of the upper bounds for E[Xi,j+1] and E[Xi,j] above
and note that this ratio is at most
V(1− p)M−i(1 + 1/j)i.
When 1 ≤ i ≤ εN/2 and j ≥ i, we see, using the fact that M = (1 + o(1))N,
that
V(1− p)M−i(1 + 1/j)i ≤ e
(en
r
)r
exp
(−(1 + ε/2− ε2/2 + o(1))pc(n, r)N)
≤ er+1
( r
n
)εr/5
= o(1).
61
Consequently, we have
P[Xi > 0] ≤
∑
j≥i
E[Xi,j] ≤ 2n
(
N
i
)(
V
i
)
(1− p)i(M−i)(ip)i
≤ 2n
(
eN
i
)i(
eV
i
)i
exp (−i(1 + ε/5)pc(n, r)N)
(
i(r + 1) log n
N
)i
≤ 2e2in((r + 1) log n)i
(
V
i
)i
exp (−i(1 + ε/5)pc(n, r)N)
≤ 2
(
er+2(r + 1) log n
i
( r
n
)εr/5)i
≤ 2
(
er+2(r + 1) log n
( r
n
)εr/5)i
.
Summing this estimate for i ≤ εN/2, we get
εN/2∑
i=1
P(Xi > 0) ≤
εN/2∑
i=1
2
(
er+2(r + 1) log n
( r
n
)εr/5)i
≤ 4
(
er+2(r + 1) log n
( r
n
)εr/5)
= o(1),
and so by the union bound, with high probability, for each 1 ≤ i ≤ εN/2, the
random variable Xi is zero.
Case 2: Large maximum degree. Next, we consider the Xi with
εN/2 < i ≤ N
(
1− 1− ε/2
r + 1
)
.
As noted earlier, for any star S, the number of edges in K(n, r) between
a set A ∈ [n](r) \ S and a family A ⊂ S is at least |A| − (N−M). We know
from Proposition 2.5 that N−M = o(N/r) when r = o(n1/3); consequently,
it follows that if A ⊂ [n](r) has cardinality N and d(A) ≥ (1− ε/2)N/(r + 1),
then e(A) ≥ (1 + o(1))d(A)(N− d(A)).
To simplify calculations, let us define α by setting i = αN = αrV/n where
ε/2 < α ≤ (r + ε/2)/(r + 1).
In this range, we see that
E[Xi] ≤ n
(
N
i
)(
V
i
)
(1− p)(1+o(1))i(N−i)
62
≤ n
( e
α
)αN(en
rα
)αN
exp
(−(1 + ε+ o(1))α(1− α)pc(n, r)N2)
≤ n
(
nr(1+ε+o(1))(1−α)r
rn(1+ε+o(1))(1−α)(r+1)
)αN
≤ n
( r
n
)(ε2/4−ε3/4+o(1))N
.
The last two inequalities above are obtained by first collecting the O(1) terms
in the bound into the o(1) terms in the exponent, and by then using the bounds
on α. It follows that
(2r+ε)N
2(r+1)∑
i=εN/2
P(Xi > 0) ≤ nN
( r
n
)(ε2/4−ε3/4+o(1))N
= o(1),
and so with high probability, for each εN/2 < i ≤ (r + ε/2)N/(r + 1), the
random variable Xi is zero.
Case 3: Small maximum degree. We shall complete the proof of the
lower bound by showing that ∑
i>
(2r+ε)N
2(r+1)
E[Xi] = o(1).
It turns out that in this range of i, somewhat surprisingly, it is significantly
easier to deal with the case where r tends to infinity with n as opposed to the
case where r is small.
Suppose first that r ≥ log n. Then
(1− ε/2)
r + 1
<
1
r + 4
for all large enough n. Observe that subgraph of K(n, r) induced by a family
A of cardinality N has minimum degree at least N− rd(A) and consequently,
if d(A) < N/(r + 4), then
e(A) ≥ N
2
(
N− rN
r + 4
)
=
2N2
r + 4
.
63
In this case, it follows that∑
i>
(2r+ε)N
2(r+1)
E[Xi] ≤
(
V
N
)
(1− p)2N2/(r+4)
≤
(en
r
)N( r
n
)2rN/(r+4)
≤
(er
n
)(1+o(1))N
= o(1)
which completes the proof when r ≥ log n.
Next, suppose that r ≤ log n. When r ≤ log n, it is not necessarily true
(if r = O(1) and ε is sufficiently small, for instance) that (1− ε/2)/(r + 1) <
1/(r + 4). It turns out that in this case, we need a more careful estimate.
For a family A ⊂ [n](r) and each x ∈ [n], define αx = |Ax|/N. Note that∑n
x=1 αx = r. Recall that Proposition 2.1 tells us that
e(A) ≥
(|A|
2
)
−
∑
x∈[n]
(|Ax|
2
)
≥
(
N
2
)(
1−
∑
x∈[n]
α2x
)
.
Let A ⊂ [n](r) be such that |A| = N and d(A) < (1− ε/2)N/(r + 1). For
such a family A, let D = DA be the set of x ∈ [n] such that αx ≥ (log n)−2.
Since
∑n
x=1 αx = r, we see that |D| ≤ r(log n)2 ≤ (log n)3.
Lemma 3.1. Fix D = DA and the values of |Ax| for x ∈ D. Subject to these
restrictions, the expected number of families A ⊂ [n](r) of maximum degree at
most (1− ε/2)N/(r + 1) which induce independent sets in Kp(n, r) is at most
(r/n)(3/10+o(1))N.
Proof. Since
∑n
x=1 αx = r, it follows (by convexity, for example) that∑
x∈[n]\D α
2
x is at most r(log n)
−2 ≤ (log n)−1 = o(1). Consequently,
e(A) ≥ N
2
2
(
1 + o(1)−
∑
x∈[n]
α2x
)
≥ N
2
2
(
1 + o(1)−
∑
x∈D
α2x
)
,
64
and so the probability that a family A as in the statement of the lemma induces
an independent set is at most
(1− p)e(A) ≤ exp
(
− pN
2
2
(
1 + o(1)−
∑
x∈D
α2x
))
≤
(
r(1+o(1))r
n(1+o(1))(r+1)
∏
x∈D
(
nr+1
rr
)α2x)N/2
. (5)
Next, we bound the number of ways in which we can choose A as in
Lemma 3.1. Using the fact that r ≤ log n and |D| ≤ (log n)3, we first note that
N ≥
∣∣∣⋃
x∈D
Ax
∣∣∣ ≥∑
x∈D
|Ax| −
∑
x,y∈D
x
(2r+ε)N
2(r+1)
E[Xi] ≤ (log n)3n(logn)3(2N)(logn)3
( r
n
)(3/10+o(1))N
. (10)
It is easy to check that the right-hand side of (10) is o(1) for every 2 ≤ r ≤ log n.
Hence, with high probability, for each i > (r + ε/2)N/(r + 1), the random
variable Xi is zero; this completes the proof of the lower bound.
4. Lower bound for the critical threshold
As in the previous section, let Y be the number of independent families in
Kp(n, r) of size N + 1 which contain an entire star.
Proof of the lower bound in Theorem 1.2. Turning to the lower
bound, we shall assume that p = (1 − ε)pc(n, r) for some fixed real number
ε > 0 and we show using a simple second moment calculation that Y > 0 with
high probability; consequently, the independence number of Kp(n, r) is at least
N + 1.
Recall (4) which says that
E[Y ] =
(
n
1
)(
V −N
1
)
(1− p)M.
Note that N = o(V) when r = o(n1/3); it follows that
E[Y ] ≥ (1 + o(1))nV(1− p)N
≥ (1 + o(1))n
r+1
r!
exp
(−(p+ p2)N)
≥ n
r+1
r!
exp ((1− ε+ o(1))(r log r − (r + 1) log n))
≥
(n
r
)(ε+o(1))r
,
and so E[Y ]→∞ when p = (1− ε)pc(n, r).
67
Therefore, to show that Y > 0 with high probability, it suffices to show
that Var[Y ] = o(E[Y ]2) or equivalently, that E[(Y )2] = (1 + o(1))E[Y ]2, where
E[(Y )2] = E[Y (Y − 1)] is the second factorial moment of Y .
Note that
E[(Y )2] =
∑
x,y,A,B
P(Sx ∪ {A} andSy ∪ {B} are independent),
the sum being over ordered 4-tuples (x, y, A,B) with x, y ∈ [n], A ∈ [n](r) \ Sx
and B ∈ [n](r) \ Sy such that (x,A) 6= (y,B). Now, observe that∑
x 6=y
P(Sx ∪ {A} andSy ∪ {B} are independent) ≤ (n2)(V −N)2(1− p)(2−o(1))M
= (1 + o(1))E[Y ]2,
and∑
x=y,A6=B
P(Sx ∪ {A} andSy ∪ {B} are independent) ≤ n(V −N)2(1− p)2M
= o(E[Y ]2).
By Chebyshev’s inequality, we conclude that Y > 0 with high probability
and so, the independence number of Kp(n, r) is at least N + 1.
5. Concluding remarks
The condition r = o(n1/3) in our results seems somewhat artificial; we would
expect the same formula for the critical threshold to hold for much larger r as
well. We suspect that this formula in fact gives the exact value of the critical
threshold when r = o(n) but we are unable to prove this presently.
The size of the critical window also merits study. Our proof (for large r)
works even when we are a factor of (1 + 6/r) away from the critical threshold;
it is possible that the critical window is much smaller and it is an interesting
problem to determine the size of the critical window precisely.
68
Of course, one would be interested to know what happens for larger r as
well. When r/n is bounded away from 1/2, we suspect it should be possible
to demonstrate stability of the Erdo˝s–Ko–Rado theorem at p = 1/2, say. We
return to this question in the next chapter.
69
CHAPTER 6
Transference for the Erdo˝s–Ko–Rado theorem, II
Joint work with Jo´zsef Balogh and Be´la Bolloba´s.
1. Introduction
In this chapter, we shall continue the work begun in the last chapter and
once again, our objective will be a transference result the Erdo˝s–Ko–Rado
theorem. Recall that for natural numbers n, r ∈ N with n ≥ r, the Kneser
graph K(n, r) is the graph whose vertex set is [n](r) where two r-element sets
A,B ∈ [n](r) are adjacent if and only if A ∩ B = ∅. Observe that a family
A ⊂ [n](r) is an intersecting family if and only if A induces an independent set
in K(n, r). Writing α(G) for the size of the largest independent set in a graph
G, the Erdo˝s–Ko–Rado theorem asserts that α(K(n, r)) =
(
n−1
r−1
)
when n ≥ 2r
and furthermore, when n > 2r, the only independent sets of this size are stars.
Let Kp(n, r) denote the random subgraph of K(n, r) obtained by retaining
each edge of K(n, r) independently with probability p. In the previous chapter,
we asked the following natural question: is α(Kp(n, r)) =
(
n−1
r−1
)
? We proved,
when r = r(n) = o(n1/3), that the answer to this question is in the affirmative
even after practically all the edges of the Kneser graph have been deleted.
More precisely, we showed that in this range, there exists a (very small) critical
probability pc(n, r) with the following property: as n→∞, if p/pc > 1 then
with high probability, α(Kp(n, r)) =
(
n−1
r−1
)
and the only independent sets of this
size in Kp(n, r) are stars, while if p/pc < 1, then α(Kp(n, r)) >
(
n−1
r−1
)
with high
probability. In this chapter, we shall prove a transference theorem that holds
for much bigger values of r = r(n); however, unlike in the previous chapter, we
are unable to establish a sharp threshold. Our main result is the following.
71
Theorem 1.1. For every ε > 0, there exist constants c = c(ε) > 0 and
c′ = c′(ε) > 0 with c < c′ such that for all n, r ∈ N with r ≤ (1/2− ε)n,
P
(
α(Kp(n, r)) =
(
n− 1
r − 1
))
→
1 if p ≥
(
n−1
r−1
)−c
0 if p ≤ (n−1
r−1
)−c′
as n→∞. In particular, with high probability, α(K1/2(n, r)) =
(
n−1
r−1
)
.
All the work in proving Theorem 1.1 is in showing that c(ε) exists. The
existence of c′(ε), on the other hand, is an easy exercise. Indeed, a second
moment calculation identical to that in Section 4 of Chapter 5 shows that
if p ≤ (n−r−1
r−1
)−1
, then with high probability, there exists a star and an r-set
not contained in the star all the edges between which are absent in Kp(n, r).
We can then check that if r ≤ (1/2− ε)n, then there exists a c′ = c′(ε) such
that
(
n−r−1
r−1
) ≥ (n−1
r−1
)c′
. Indeed, using Stirling’s approximation, this reduces
to verifying that (n− r) log(r/(n− r))/n log(r/n) is uniformly bounded away
from zero when r ≤ (1/2 − ε)n; this is straightforward because the function
decreases with r. Hence, if p ≤ (n−1
r−1
)−c′
, then α(Kp(n, r)) ≥
(
n−1
r−1
)
+ 1 with
high probability.
Let us briefly describe some of the ideas that go into the proof of Theorem 1.1.
We shall prove two results which, taken together, show that a large family
A ⊂ [n](r) without a large intersecting subfamily must necessarily contain many
pairs of disjoint sets, or in other words, must induce many edges in K(n, r);
we do this in Section 3. We put together the pieces and give the proof of
Theorem 1.1 in Section 4. In Section 5, we briefly describe some approaches
to improving the dependence of c(ε) on ε in Theorem 1.1. We conclude with
some discussion in Section 6.
2. Preliminaries
Henceforth, a ‘family’ will be a uniform family on [n] unless we specify
otherwise. To ease the notational burden, we adopt the following notational
72
convention: when n and r are clear from the context, we write V =
(
n
r
)
,
N =
(
n−1
r−1
)
, M =
(
n−r−1
r−1
)
and R =
(
2r
r
)
.
We need a few results from extremal set theory, some classical and some
more recent. The first result that we will need, due to Hilton and Milner [68],
bounds the cardinality of a nontrivial uniform intersecting family. Writing Ax
for the subfamily of a family A that consists of those sets containing x, we
have the following.
Theorem 2.1. Let n, r ∈ N and suppose that n > 2r. If A ⊂ [n](r) is an
intersecting family with |A| ≥ N −M + 2, then there exists an x ∈ [n] such
that A = Ax.
The next result we shall require, due to Friedgut [58], is a quantitative
extension of the Hilton–Milner theorem which says that any sufficiently large
uniform intersecting family must resemble a star.
Theorem 2.2. For every ε > 0, there exists a C = C(ε) > 0 such that for
all n, r ∈ N with εn ≤ r ≤ (1/2− ε)n, the following holds: if A ⊂ [n](r) is an
intersecting family and |A| = N − k, then there exists an x ∈ [n] for which
|Ax| ≥ N− Ck.
We will also need the following well-known inequality for cross-intersecting
families due to Bolloba´s [26].
Theorem 2.3. Let (A1, B1), . . . , (Am, Bm) be pairs of disjoint r-element
sets such that Ai ∩Bj 6= ∅ for i, j ∈ [m] whenever i 6= j. Then m ≤ R.
Finally, we shall require a theorem of Kruskal [80] and Katona [72]. For
a family A ⊂ [n](r), its shadow in [n](k), denoted ∂(k)A, is the family of those
k-sets contained in some member of A. For x ∈ R and r ∈ N, we define the
generalised binomial coefficient
(
x
r
)
by setting(
x
r
)
=
x(x− 1) . . . (x− r + 1)
r!
.
73
The following convenient formulation of the Kruskal–Katona theorem is due to
Lova´sz [86].
Theorem 2.4. Let n, r, k ∈ N and suppose that k ≤ r ≤ n. If the cardinality
of A ⊂ [n](r) is (x
r
)
for some real number x ≥ r, then |∂(k)A| ≥ (x
k
)
.
To avoid clutter, we omit floors and ceilings when they are not crucial. We
use the standard o(1) notation to denote any function that tends to zero as
n tends to infinity; the variable tending to infinity will always be n unless we
explicitly specify otherwise.
3. The number of disjoint pairs
Given a family A, we write e(A) for the number of disjoint pairs of sets in
A; equivalently, e(A) is the number of edges in the subgraph of the Kneser
graph induced by A. In this section, we give some bounds for e(A).
We denote by A∗ the largest intersecting subfamily of a family A; if this
subfamily is not unique, we take any subfamily of maximum cardinality. We
write `(A) = |A| − |A∗| for the difference between the cardinality of A and the
largest intersecting subfamily of A.
Trivially, we have e(A) ≥ `(A). Our first lemma says that we can do much
better than this trivial bound when `(A) is large.
Lemma 3.1. Let n, r ∈ N. For any A ⊂ [n](r),
e(A) ≥ `(A)
2
2R
.
To prove this lemma, we need the notion of an induced matching. An
induced matching of size m in a graph G is a set of 2m vertices inducing a
subgraph consisting of m independent edges; equivalently, we refer to these m
edges as an induced matching of size m. The induced-matching number of G,
in notation, m(G), is the maximal size of an induced matching in G.
74
Proposition 3.2. Let G = (V,E) be a graph with m(G) = m ≥ 1. Then
|E| ≥ k
2
4m
where k = |V | − α(G).
Proof. Let us choose X = {x1, . . . , xm} and Y = {y1, . . . , ym} so that the
edges x1y1, . . . , xmym constitute an induced matching. Let Z = Γ(X∪Y ) be the
set of neighbours of the vertices in X ∪ Y ; thus X ∪ Y ⊂ Z. Since m(G) = m,
the set V (G) \ Z is independent, and so |Z| ≥ k. Since some vertex in X ∪ Y
has at least |Z|/2m neighbours, we conclude that ∆(G) ≥ |Z|/2m ≥ k/2m
where ∆(G) is the maximum degree of G.
Now define a sequence of graphs G = G0 ⊃ G1 ⊃ · · · ⊃ Gk and a sequence
of vertices x0, x1, . . . , xk by taking xi to be a vertex of Gi of maximal degree and
Gi+1 to be the graph obtained from Gi by deleting xi. We know from our earlier
arguments that ∆(Gi) ≥ (k − i)/2m, and so |E| ≥
∑k
i=0 ∆(Gi) ≥ k2/4m.
To apply the previous proposition, we need the following corollary of
Theorem 2.3 the proof of which is implicit in [18]; we include the short proof
here for completeness.
Proposition 3.3. For n ≥ 2r, the induced-matching number of K(n, r) is
m(K(n, r)) =
(
2r − 1
r − 1
)
=
R
2
.
Proof. Let A1B1, . . . , AmBm be an induced matching in K(n, r). For
m+ 1 ≤ i ≤ 2m, we set Ai = Bi−m and Bi = Ai−m. We apply Theorem 2.3 to
the pairs (A1, B1), . . . , (A2m, B2m) and conclude that 2m ≤ R.
The R/2 partitions of [2r] into disjoint r-sets form an induced matching,
and so m(K(n, r)) = R/2, as claimed.
Proof of Lemma 3.1. The lemma follows by applying Proposition 3.2
to GA, the subgraph of the Kneser graph K(n, r) induced by A.
75
Note that Lemma 3.1 is only effective when `(A) ≥ 2R. The next, somewhat
technical, lemma complements Lemma 3.1 by giving a better bound when `(A)
is small provided the size of A is large.
Lemma 3.4. For every ε, η > 0, there exist constants δ = δ(ε, η) > 0 and
C = C(ε) > 0 with the following property: for all n, r ∈ N with εn ≤ r ≤
(1/2− ε)n, we have
e(A) ≥ `(A)1+δ − C`(A)
for any family A ⊂ [n](r) with |A| = N and `(A) ≤ N1−η.
To clarify, the C(ε) in the statement of the lemma above is the same as the
C(ε) guaranteed by Theorem 2.2.
Proof of Lemma 3.4. First, let us note that since we always have e(A) ≥
`(A), it suffices to prove the lemma under the assumption that n is sufficiently
large; indeed, the lemma would then follow for all n ∈ N with an appropriately
smaller value of δ.
Let ` = `(A). We start by observing that most of A must be contained in
a star. Indeed, as before, let A∗ denote the largest intersecting subfamily of A;
by definition, |A∗| = N− `. Since we have assumed that εn ≤ r ≤ (1/2− ε)n,
we may assume, by Theorem 2.2, that |A∗n| ≥ N− C` where C = C(ε) is as
guaranteed by Theorem 2.2. Hence, |An| ≥ |A∗n| ≥ N− C`.
We also know that |An| ≤ |A∗| ≤ N − `; let B be a subset of A \ An of
cardinality exactly `. We shall bound e(A) by counting the number of edges
between B and An in K(n, r).
Let us define
A′ = {A \ {n} : A ∈ An} ⊂ [n− 1](r−1)
and
B′ = {[n− 1] \B : B ∈ B} ⊂ [n− 1](n−r−1).
76
Clearly, to count the number of edges between An and B in K(n, r), it suffices
to count the number of pairs (A′, B′) in A′×B′ with A′ ⊂ B′. This quantity is
obviously bounded below by the number of sets A′ ∈ A′ contained in at least
one B′ ∈ B′.
Since A′ ⊂ [n − 1](r−1) and |A′| ≥ N − C`, the number of sets A′ ∈ A′
contained in some B′ ∈ B′ is at least |∂(r−1)B′| − C`. Consequently,
e(A) ≥ |∂(r−1)B′| − C`.
We shall show that there exists a δ = δ(ε, η) > 0 such that, under the conditions
of the lemma, |∂(r−1)B′| ≥ `1+δ.
We deduce the existence of such a δ from Theorem 2.4, the Kruskal–Katona
theorem. We may assume that
` = |B′| =
(
x
n− r − 1
)
for some real number x ≥ n− r − 1. It follows from Theorem 2.4 that
|∂(r−1)B′| ≥
(
x
r − 1
)
.
Let us put r = (1/2− β)n and x = ϑn. We now calculate what values β and ϑ
can take. We know that ε ≤ β ≤ 1/2− ε. Since x ≥ n− r − 1, we also know
that ϑ ≥ 1/2 + β − 1/n ≥ 1/2 + β/2. On the other hand, since(
ϑn
(1/2 + β)n
)
= ` ≤ N1−η =
(
n− 1
r − 1
)1−η
≤
(
n
r
)1−η
=
(
n
(1/2− β)n
)1−η
,
it follows from Stirling’s approximation for the factorial function that there
exists some δ′(ε, η) > 0 such that ϑ ≤ 1− δ′.
Hence it suffices to check that there exists a δ = δ(ε, η) > 0 for which the
inequality (
ϑn
(1/2− β)n− 1
)
≥
(
ϑn
(1/2 + β)n− 1
)1+δ
holds for all β ∈ [ε, 1/2 − ε] and ϑ ∈ [1/2 + β/2, 1 − δ′] as long as n is
sufficiently large. This is easily checked using Stirling’s formula. Indeed, let
77
H(x) = −x log2(x)− (1− x) log2(1− x) be the binary entropy function. We
know from Stirling’s approximation that(
ϑn
(1/2− β)n− 1
)
= exp
(
(ϑ+ o(1))H
(
1/2− β
ϑ
)
n
)
,
and similarly that(
ϑn
(1/2 + β)n− 1
)
= exp
(
(ϑ+ o(1))H
(
1/2 + β
ϑ
)
n
)
.
Hence, it suffices to show that there exists a δ = δ(ε, δ′) such that H((1/2−
β)/ϑ) > (1+δ)H((1/2+β)/ϑ) for all β ∈ [ε, 1/2−ε] and ϑ ∈ [1/2+β/2, 1−δ′].
This follows easily from the fact that H is a concave function attaining its
maximum at 1/2 and the fact that H(x) = H(1− x).
4. Proof of the main result
Armed with Lemmas 3.1 and 3.4, we are now ready to prove Theorem 1.1.
Proof of Theorem 1.1. Let us fix ε > 0 and assume that r ≤ (1/2−ε)n.
Clearly, it is enough to prove Theorem 1.1 for all sufficiently small ε; it will
be convenient to assume that ε < 1/10. As mentioned earlier, Bolloba´s,
Narayanan and Raigorodskii have proved Theorem 1.1 in a much stronger form
when r = o(n1/3). So to avoid having to distinguish too many cases, we shall
assume that r grows with n; for concreteness, let us suppose that r ≥ n1/4. A
consequence of these assumptions is that in this range, V, N and M all grow
much faster than any polynomial in n.
Recall that Kp(n, r) is the random subgraph of the Kneser graph K(n, r)
where we retain each edge of K(n, r) independently with probability p. For
each ` ≥ 1, let X` denote the (random) number of independent sets A ⊂ [n](r)
in Kp(n, r) with |A| = N and `(A) = `.
To prove Theorem 1.1, it clearly suffices to show that for some c = c(ε) > 0,
all of the X` are zero with high probability provided p ≥ N−c. We shall
78
prove this by distinguishing three cases depending on which of Theorem 2.1,
Lemma 3.1 and Lemma 3.4 is to be used.
Let C = C(ε) be as in Theorem 2.2. Note that since r ≤ (1/2 − ε)n, it
is easy to check using Stirling’s approximation that we can choose positive
constants cm = cm(ε) and cr = cr(ε) such that M ≥ Ncm and R ≤ N1−cr .
We now set Lm = N
cm/2 and Lr = N
1−cr/4 and distinguish the following
three cases.
Case 1: ` ≤ Lm . Let A ⊂ [n](r) be a family of cardinality N with `(A) = `.
Since
` ≤ Lm = Ncm/2 ≤M− 2,
we see that A∗, the largest intersecting subfamily of A, satisfies
|A∗| = N− ` ≥ N−M + 2.
It follows from Theorem 2.1 that there is an x ∈ [n] for which A∗ is contained
in the star centred at x. Consider the ` sets in A \A∗. Any such set is disjoint
from exactly M members of the star centred at x and hence from at least M−`
members of A∗. This tells us that e(A) ≥ `(M− `). Since ` ≤M/2, it follows
that
E[X`] ≤ n
(
N
`
)(
V
`
)
(1− p)`(M−`)
≤ n
(
2n
`
)2
exp(−p`M/2)
≤ exp(2n`− p`M/2).
Hence, if c ≤ cm/2 so that p ≥ N−cm/2, it is clear that
Lm∑
`=1
E[X`] ≤
Lm∑
`=1
exp
(
2n`− `N
cm/2
2
)
= o(1).
So with high probability, for each 1 ≤ ` ≤ Lm, the random variable X` is zero.
79
Case 2: ` ≥ Lr. Again, let A ⊂ [n](r) be a family of cardinality N with
`(A) = `. We know from Lemma 3.1 that
e(A) ≥ `
2
2R
≥ N
2−cr/2
2N1−cr
=
N1+cr/2
2
.
So it follows that∑
l≥Lr
E[X`] ≤
(
V
N
)
exp
(
−pN
1+cr/2
2
)
≤ exp
(
nN− pN
1+cr/2
2
)
.
Hence if c ≤ cr/4 so that p ≥ N−cr/4, we have∑
l≥Lr
E[X`] ≤ exp
(
nN− N
1+cr/4
2
)
= o(1).
So once again, with high probability, the sum
∑
`≥Lr X` is zero.
Before we proceed further, let us first show that that we may now assume
without loss of generality that r ≥ εn. This is because one can check that
the arguments in Cases 1 and 2 together prove Theorem 1.1 when r ≤ εn for
all sufficiently small ε. It is easy to check using Stirling’s formula that if ε is
sufficiently small, indeed if ε < 1/10 for example, then it is possible to choose
positive constants c′m(ε) and c
′
r(ε) so that for all r ≤ εn, we have M ≥ Nc′m ,
R ≤ N1−c′r and Nc′m/2 ≥ N1−c′r/4. So the arguments above yield a proof of
Theorem 1.1 when r ≤ εn. Therefore, in the following, we assume that r ≥ εn.
Case 3: Lm ≤ ` ≤ Lr. As before, consider any family A ⊂ [n](r) of
cardinality N with `(A) = `. First note that since εn ≤ r ≤ (1/2 − εn) and
` ≤ Lr = N1−cr/4 where cr is a constant depending only on ε, by Lemma 3.4,
there exists a δ = δ(ε) such that
e(A) ≥ `1+δ − C`.
Since ` ≥ Lm = Ncm/2, it follows that
e(A) ≥ `1+δ − C` ≥ `1+δ/2
for all sufficiently large n.
80
Next, consider A∗, the largest intersecting subfamily of A, of cardinality
N − `. We know from Theorem 2.2 that there exists an x ∈ [n] such that
|A∗x| ≥ N− C` and so |Ax| ≥ N− C`. It is then easy to see that
E[X`] ≤ n
(
N
C`
)(
V
C`
)
(1− p)`1+δ/2
≤ exp(`(2Cn− p`δ/2)).
Hence, if c ≤ cmδ/4 so that p ≥ N−cmδ/4, it follows that
Lr∑
`=Lm
E[X`] ≤
Lr∑
`=Lm
exp
(
`
(
2Cn−Ncmδ/4/2)) = o(1)
and so with high probability, for each Lm ≤ ` ≤ Lr, the random variable X` is
zero.
Putting the different parts of our argument together, we find that if 0 <
ε < 1/10,
c = c(ε) = min
(
cm(ε)
2
,
c′m(ε)
2
,
cr(ε)
4
,
c′r(ε)
4
,
cm(ε)δ(ε)
2
)
and p ≥ N−c, then for all r = r(n) ≤ (1/2− ε)n, we have
P
(
α(Kp(n, r)) =
(
n− 1
r − 1
))
→ 1
as n→∞. This completes the proof of Theorem 1.1.
5. Avenues for improvement
We briefly discuss how one might tighten up the arguments in Theorem 1.1
so as to improve the dependence of c(ε) on ε in the result. However, since it
seems unlikely to us that these methods will be sufficient to determine the
precise critical threshold at which Theorem 1.1 ceases to hold, we shall keep
the discussion in this section largely informal.
81
5.1. Containers for sparse sets in the Kneser graph. The first ap-
proach we sketch involves using ideas from the theory of ‘graph containers’ to
count large sparse sets in the Kneser graph more efficiently.
The theory of graph containers was originally developed to efficiently count
the number of independent sets in a graph satisfying some kind of ‘supersatu-
ration’ condition. The basic principle used to construct containers for graphs
can be traced back to the work of Kleitman and Winston [77]. A great deal of
work has since gone into refining and generalising their ideas, culminating in
the results of Balogh, Morris and Samotij [19] and Saxton and Thomason [102];
these papers also give a detailed account of the history behind these ideas and
we refer the interested reader there for details about how the general method-
ology was developed. Here we shall content ourselves with a brief discussion
of how these ideas might be used to improve the dependence of c(ε) on ε in
Theorem 1.1.
Let us write Ym = Ym(n, r) for the number of families A ⊂ [n](r) with
|A| = N and e(A) = m. Clearly, to show that α(Kp(n, r)) = N with high
probability, it suffices to show that
∑
m≥1 Ym(1− p)m = o(1). Hence, it would
be useful to have good estimates for Ym. We shall derive some bounds for Ym;
see Theorem 5.2 below. These bounds are not strong enough (especially for
small values of m) to prove Theorem 1.1. However, note that in our proof of
Theorem 1.1, we use the somewhat cavalier bound of
(
V
N
)
for the number of
families A of size N for which `(A) is equal to some prescribed value (in Case 2
of the proof); we can instead use Theorem 5.2 to count more efficiently.
To prove an effective container theorem, one needs to first establish a
suitable supersaturation property. Lova´sz [85] determined the second largest
eigenvalue of the Kneser graph; by combining Lova´sz’s result with the expander
mixing lemma, Balogh, Das, Delcout, Liu and Sharifzadeh [18] (see also [62])
proved the following supersaturation theorem for the Kneser graph.
Proposition 5.1. Let n, r, k ∈ N and suppose that n > 2r and k ≤ V−N.
If A ⊂ [n](r) has cardinality N + k, then e(A) ≥ kM/2.
82
Using Proposition 5.1, we prove the following container theorem for the
Kneser graph.
Theorem 5.2. For every ε > 0, there exists a Cˆ = Cˆ(ε) > 0 such that for
every β > 0 and all n, r,m ∈ N with εn ≤ r ≤ (1/2− ε)n and m ≤ V(n−r
r
)
/2,
the following holds: writing
k1 = Cˆ
(
N
βM
+
(
mN
βM
)1/2)
and
k2 = k1 + CˆβN,
there exist, for 1 ≤ i ≤ ∑k1j=0 (Vj ), families Bi ⊂ [n](r) each of cardinality at
most N + k2 with the property that each A ⊂ [n](r) with e(A) ≤ m is contained
in one of these families.
The advantage of this formulation of Theorem 5.2 in terms of k1, k2 and β
is that we can apply the theorem with a value of β > 0 suitably chosen for the
application at hand.
It is easy to check from Theorem 5.2 that Ym = Ym(n, r), the number of
families A ⊂ [n](r) with |A| = N and e(A) = m, satisfies
Ym(n, r) ≤
(
k1∑
j=0
(
V
j
))(
N + k2
N
)
= 2
(
V
k1
)(
N + k2
k2
)
≤ 2
(
V
k1
)(
V
k2
)
≤ 2 exp
(
Cˆn
(
βN +
2N
βM
+
(
4mN
βM
)1/2))
for all β > 0 such that k1 ≤ V/2. (Indeed, there are
∑k1
j=0
(
V
j
)
ways of choosing
a container B, and there are at most (N+k2
N
)
sets of size N in B.) We can then
optimise this bound by choosing β depending on how large m is in comparison
to M and N.
Proof of Theorem 5.2. We start by proving a lemma whose proof is
loosely based on the methods of Saxton and Thomason [102]. Before we
state the lemma, let us have some notation. Given a graph G = (V,E) and
83
U ⊂ V (G), we write
µ(U) =
|E(G[U ])|
|V | ;
in other words, µ(U) is the number of edges induced by U divided by the
number of vertices of G. Also, we write P(X) for the collection of all subsets
of a set X.
Lemma 5.3. Let G = (V,E) be a graph with average degree d and maximum
degree ∆. For every a ≥ 0 and b > 0, there is a map C : P(V )→ P(V ) with
the following property: for every U ⊂ V with µ(U) ≤ a, there is a subset T ⊂ V
such that
(1) T ⊂ U ⊂ C(T ),
(2) |T | ≤ 2|V |(a/bd)1/2 + |V |/bd, and
(3) µ(C(T )) ≤ 2∆(a/bd)1/2 + ∆/bd+ bd.
Proof. We shall describe an algorithm that constructs T given U . The
algorithm will also construct C(T ) in parallel; it will be clear from the algorithm
that C(T ) is entirely determined by T and in no way depends on U .
Fix a linear ordering of the vertex set V of G. If u and v are adjacent and u
precedes v in our ordering, we call v a forward neighbour of u and u a backward
neighbour of v. For a vertex v ∈ V , we write F (v) for the set of its forward
neighbours.
We begin by setting T = ∅ and A = V . We shall iterate through V in the
order we have fixed and add vertices to T and remove vertices from A as we go
along; at any stage, we write Γ(T ) to denote the set of those vertices which,
at that stage, have k or more backward neighbours in T where k is the least
integer strictly greater than (abd)1/2.
As we iterate through the vertices of V in order, we do the following when
considering a vertex v.
(1) If v ∈ Γ(T ), we remove v from A; if it is also the case that v ∈ U , then
we add v to T .
84
(2) If v /∈ Γ(T ), we consider the size of S = F (v) \ Γ(T ).
(a) If |S| ≥ bd, we remove v from A; if it is also the case that v ∈ U ,
then we add v to T .
(b) If |S| < bd, we do nothing.
The algorithm outputs T and A when it terminates; we then set C(T ) =
A ∪ T . It is clear from the algorithm that C(T ) is uniquely determined by
T and that T ⊂ U ⊂ C(T ). To see this, note that the decision to remove
a vertex v from A depends only on which vertices preceding v belong to T .
Therefore, we can reconstruct A, and hence C(T ), using only the set T without
any knowledge of the set U .
We first show that |T | ≤ 2|V |(a/bd)1/2 + |V |/bd. Consider the partition
T = T1 ∪ T2 where T1 consists of those vertices which were added to T on
account of condition (1) and T2 of those vertices which were added to T when
considering condition (2a). The upper bound for |T | follows from the following
two claims.
Claim 5.4. |T1| ≤ |E(G[U ])|/k.
Proof. Clearly, each vertex of T1 has at least k backward neighbours in
T ⊂ U . Hence, k|T1| ≤ |E(G[U ])|.
Claim 5.5. |T2| ≤ k|V |/bd.
Proof. Let us mark all the edges from v to F (v) \ Γ(T ) when a vertex v
gets added to T on account of condition (2a). The number of marked edges is
clearly at least bd|T2| since the left end of each marked edge is in T2 (by the
definition of T2) and each such left end contributes at least bd marked edges.
On the other hand, by the definition of Γ(T ), each vertex in G is joined to at
most k of its backward neighbours by a marked edge. Hence, bd|T2| ≤ k|V |.
Consequently, since (abd)1/2 < k ≤ (abd)1/2 + 1, we have
|T | ≤ |T1|+ |T2| ≤ a|V |
k
+
k|V |
bd
85
≤ a|V |
(abd)1/2
+
((abd)1/2 + 1)|V |
bd
≤ |V |
(
2
( a
bd
)1/2
+
1
bd
)
.
It remains to show that µ(C) ≤ 2∆(a/bd)1/2 + ∆/bd + bd. To see this, recall
that C(T ) = A ∪ T and notice that
|E(G[C(T )])| ≤ ∆|T |+ |E(G[A])| ≤ ∆|T |+ bd|V |.
To see the last inequality, i.e., |E(G[A])| ≤ bd|V |, note that a vertex v is
removed from A by our algorithm unless we have |F (v) \ Γ(T )| < bd at the
stage where we consider v. Since each member of Γ(T ) is (eventually) removed
from A, we see that each vertex of A has at most bd forward neighbours in A
and the inequality follows. The claimed bound for µ(C) then follows from our
previously established upper bound for |T |.
To prove Theorem 5.2, we now combine Lemma 5.3 with Proposition 5.1.
First note that the Kneser graph K(n, r) has V = nN/r vertices and is
(n− r)M/r regular.
Let us take Cˆ(ε) = 20/ε2. It is easy to check that given β > 0 and a family
A ⊂ [n](r) with e(A) ≤ m, we can apply Lemma 5.3 with a = m/V and b = β
to get families T ⊂ [n](r) and C(T ) ⊂ [n](r) such that T ⊂ A ⊂ C(T ),
|T | ≤ 2V
(
rm
β(n− r)VM
)1/2
+
rV
(n− r)M
≤ 2
(
nmN
β(n− r)M
)1/2
+
nN
(n− r)M ≤ k1,
and
e(C(T )) ≤ Vµ(C(T )) ≤ 2
(
(n− r)mVM
rβ
)1/2
+
V
β
+
(n− r)βVM
r
≤M
(
2
(
n(n− r)mN
r2βM
)1/2
+
nN
rβM
+
n(n− r)βN
r2
)
≤ k2M/2,
where in the last inequality, we use the fact that n(n− r)/r2 ≤ 1/2ε2.
86
Hence, by Proposition 5.1, we see that |C(T )| ≤ N + k2. The theorem then
follows by taking the families C(T ) for every T ⊂ [n](r) with |T | ≤ k1.
5.2. Stability for the Kruskal–Katona theorem. An important ingre-
dient in our proof of Theorem 1.1 is Lemma 3.4 which gives a uniform lower
bound, using Theorem 2.2 and the Kruskal–Katona theorem, for e(A) in terms
of `(A) when the size of A is large.
However, there is a price to be paid for proving such a uniform bound: the
bound is quite poor for most families to which the lemma can be applied. Indeed,
the families which are extremal for the argument in the proof of Lemma 3.4
must possess a great deal of structure. Instead of the Kruskal–Katona theorem,
one should be able to use a stability version of the Kruskal–Katona theorem,
as proved by Keevash [73] for example, to prove a more general result that
accounts for the structure of the family under consideration.
6. Concluding remarks
Several problems related to the question considered here remain. First of
all, it would be good to determine the largest possible value of c(ε) with which
Theorem 1.1 holds. It is likely that one needs new ideas to resolve this problem.
Second, one would also like to know what happens when r is very close
to n/2. Perhaps most interesting is the case when n = 2r + 1; one would
like to know the values of p for which we have α(Kp(2r + 1, r)) =
(
2r
r−1
)
with
high probability. A simple calculation shows that p = 3/4 is the threshold at
which we are likely to find a star and an r-set not in the star all the edges
between which are missing in Kp(2r + 1, r) which suggests that the critical
threshold should be 3/4. However, it would even be interesting to show that
α(Kp(2r + 1, r)) =
(
2r
r−1
)
with high probability for, say, all p ≥ 0.999.
87
CHAPTER 7
Line percolation
Joint work with Paul Balister, Be´la Bolloba´s and Jonathan Lee.
1. Introduction
Bootstrap percolation models and arguments have been used to study a
range of phenomena in various areas, ranging from crack formation, clustering
phenomena, the dynamics of glasses and sandpiles to neural nets and economics;
see [84, 6, 53] for a small sample of such applications. In this chapter, we
shall study a new geometric bootstrap percolation model defined on the d-
dimensional grid [n]d with infection parameter r ∈ N which we call r-neighbour
line percolation. Given v ∈ [n]d, write L(v) for the set of d axis parallel lines
through v and let
L([n]d) =
⋃
v∈[n]d
L(v)
be the set of all axis parallel lines that pass through the lattice points of [n]d.
In line percolation, infection spreads from a subset A ⊂ [n]d of initially infected
lattice points as follows: if there is a line L ∈ L([n]d) with r or more infected
lattice points on it, then every lattice point of [n]d on L gets infected. In other
words, we have a sequence A = A(0) ⊂ A(1) ⊂ . . . A(t) ⊂ . . . of subsets of [n]d
such that
A(t+1) = A(t) ∪ {v ∈ [n]d : ∃L ∈ L(v) such that |L ∩ A(t)| ≥ r}.
The closure of A is the set [A] =
⋃
t≥0A
(t) of eventually infected points. We
say that the process terminates when no more newly infected points are added,
89
i.e., when A(t) = [A]. If all the points of [n]d are infected when the process
terminates, i.e., if [A] = [n]d, then we say that A percolates.
The classical model of r-neighbour bootstrap percolation on a graph was
introduced by Chalupa, Leath and Reich [37] in the context of disordered
magnetic systems and has since been extensively studied not only by mathe-
maticians but also by physicists and sociologists; for a small sample of papers,
see, for instance, [1, 55, 64, 107]. In this model, a vertex of the graph gets
infected if it has at least r previously infected neighbours in the graph. The
model is usually studied in the random setting, where the main question is to
determine the critical threshold at which percolation occurs. If the elements
of the initially infected set are chosen independently at random, each with
probability p, then one aims to determine the value pc at which percolation
becomes likely. In this regard, the r-neighbour bootstrap percolation model on
[n]d, with edges induced by the integer lattice Zd, has been the subject of large
body of work; see [70, 15, 14], and the references therein.
On account of its inherent geometric structure, it is possible to construct
other interesting bootstrap percolation models on the d-dimensional grid. In
the past, this has involved endowing the grid with a graph structure other than
the one induced by the integer lattice (a Cartesian product of paths).
In this direction, Holroyd, Liggett and Romik [71] considered r-neighbour
bootstrap percolation on [n]2 where the neighbourhood of a lattice point v is
taken to be a ‘cross’ centred at v, consisting of r − 1 points in each of the four
axis directions. Sharp thresholds for a model with an anisotropic variant of
these cross neighbourhoods were obtained recently by Duminil-Copin and van
Enter [44]. Gravner, Hoffman, Pfeiffer and Sivakoff [65] studied the r-neighbour
bootstrap percolation model on [n]d with the edges induced by the Hamming
torus where u, v ∈ [n]d are adjacent if and only if u− v has exactly one nonzero
coordinate; the Hamming torus, in other words, is the Cartesian product of
complete graphs, which is perhaps the second most natural graph structure
on [n]d after the grid. They obtained bounds on the critical exponents (i.e.,
90
logn(pc)) which are tight in the case d = 2 and for small values of the infection
parameter when d = 3.
The line percolation model we consider is a natural variant of the bootstrap
percolation model on the Hamming torus studied by Gravner, Hoffman, Pfeiffer
and Sivakoff. However, we should note that while all the other models mentioned
above are r-neighbour bootstrap percolation models on some underlying graph,
the line percolation model is not.
Morally, line percolation is better thought of as coming from the very
general neighbourhood family percolation model introduced by Bolloba´s, Smith
and Uzzell [31]. In the neighbourhood family percolation model, one starts by
specifying a homogeneous, finite collection of subsets of the grid for each point
of the grid; a point of the grid becomes infected if all the points of some set in
the collection associated with the point are previously infected. In their paper,
Bolloba´s, Smith and Uzzell prove a classification theorem for two-dimensional
neighbourhood family models and show that every such model is of one of
three types: supercritical, critical or subcritical. In particular, they show that
a model is supercritical if and only if there exist finite sets from which the
infection can spread to the whole lattice. While line percolation cannot be
described by associating a finite family of neighbourhoods with each point of
the lattice, there do exist, as we shall see, finite sets from which the infection
can spread to the whole lattice in the line percolation model, and our results
about the critical probabilities of the line percolation model are in agreement
with the general bounds for the critical probabilities of supercritical models
proved in [31]. For some related work concerning subcritical models, see the
paper of Balister, Bolloba´s, Przykucki and Smith [12].
2. Our results
In this chapter, our main aim is to investigate what happens in the line
percolation model when the initial set A = Ap ⊂ [n]d of infected points is
determined by randomly selecting points from [n]d, each independently with
91
probability p. It would be natural to determine the values of p for which
percolation is likely to occur. Let ϑp(n, r, d) denote the probability that such a
randomly chosen initial set Ap percolates. We note that ϑp(n, r, d) increases
with p and define the critical probability pc(n, r, d) by setting
pc(n, r, d) = inf{p : ϑp(n, r, d) ≥ 1/2}.
The primary question of interest is to determine the asymptotic behaviour of
pc(n, r, d) as n→∞ for every d, r ∈ N. Note that when the infection parameter
equals one, a set A of initially infected lattice points percolates if and only if
|A| > 0 which implies that pc(n, 1, d) = Θ(n−d); we restrict our attention to
r ≥ 2.
Before we state our results, a few remarks about asymptotic notation are
in order. We shall make use of standard asymptotic notation; the variable
tending to infinity will always be n unless we explicitly specify otherwise. When
convenient, we shall also make use of some notation (of Vinogradov) that might
be considered non-standard: given functions f(n) and g(n), we write f g
if f = O(g), f g if g = O(f), and f ∼ g if f = (1 + o(1))g. Constants
suppressed by the asymptotic notation are allowed to depend on the fixed
infection parameter r, but of course, not on n or p.
In two dimensions, we are able to estimate the probability of percolation
ϑp(n, r, 2) up to constant factors for all 0 ≤ p ≤ 1. We also determine pc(n, r, 2)
up to a factor of 1 + o(1) as n→∞.
Theorem 2.1. Fix r, s ∈ N, with r ≥ 2 and 0 ≤ s ≤ r − 1. Then as
n→∞,
ϑp(n, r, 2) = Θ
(
n2s+1(np)r(2s+1)−s(s+1)
)
(11)
when n−1−
1
r−s−1 p n−1− 1r−s , with the convention that n−1− 1r−s−1 is zero
when s = r − 1. Also, ϑp(n, r, 2) = Θ(1) when p n−1− 1r . Furthermore,
pc(n, r, 2) ∼ λn−1− 1r
92
A(0) A(1) A(2)
Figure 1. The spread of infection from A = [3]2 in the 3-
neighbour line percolation process on [8]2.
where λ is the unique positive real number satisfying exp(−2λr/r!) = 1/2.
The techniques used to obtain the above formula for ϑp(n, r, 2) allow us to
prove the following result about the critical probability in three dimensions,
which is the main result of this chapter.
Theorem 2.2. Fix r ∈ N, with r ≥ 2, and let s = b√r + 1/4− 1/2c. Then
as n→∞,
pc(n, r, 3) = Θ
(
n−1−
1
r−γ
)
where γ = (r + s2 + s)/2(s+ 1).
The nature of the threshold at the critical probability is also worth investi-
gating. We say that the model exhibits a sharp threshold at pc = pc(n, r, d) if
for any fixed ε > 0, ϑ(1+ε)pc(n, r, d) = 1 − o(1) and ϑ(1−ε)pc(n, r, d) = o(1). It
is not difficult to see from our proofs of Theorems 2.1 and 2.2 that in stark
contrast to the classical r-neighbour bootstrap percolation model on the grid,
there is no sharp threshold at pc when d = 2, 3. We expect similar behaviour
in higher dimensions but we do not have a proof of such an assertion.
It is also an interesting question to determine the size of a minimal percolat-
ing set for r-neighbour line percolation on [n]d for any d, r ∈ N and n ≥ r. It is
easy to check that the set [r]d percolates (see Figure 1). We shall demonstrate
that this is in fact optimal.
93
Theorem 2.3. Let d, r, n ∈ N, with n ≥ r. Then the minimum size of a
percolating set in the r-neighbour line percolation process on [n]d is rd.
Establishing this fact turns out to be harder than it appears at first glance.
The result is trivial when d = 1. When d = 2, it is not hard to demonstrate that
any percolating set has size at least r2. Consider a generalised two-dimensional
line percolation model on [n]2 where the infection thresholds for horizontal
and vertical lines are rh and rv respectively; we recover the r-neighbour line
percolation model when rh = rv = r. Let M(rh, rv) denote the size of a
minimal percolating set in this generalised model. Consider the first line L to
be infected: if L is horizontal, then L must contain rh initially infected points
and furthermore, if the set of initially infected points is a percolating set, then
the set of initially infected points not on L must constitute a percolating set for
the generalised process with infection parameters rh and rv − 1. An analogous
statement holds if L is vertical. It follows that
M(rh, rv) ≥ min(rv +M(rh − 1, rv), rh +M(rh, rv − 1)).
We obtain by induction that M(rh, rv) ≥ rhrv which implies in particular that
M(r, r) ≥ r2. The argument described above depends crucially on the fact
that a line has codimension one in a two-dimensional space. The incidence
geometry of a collection of lines in the plane is essentially straightforward; this
is no longer the case in higher dimensions and we need more delicate arguments
to prove Theorem 2.3.
The rest of this chapter is organised as follows. We collect together some
useful facts about binomial random variables in Section 3. We consider line
percolation in two dimensions in Section 4, and prove Theorem 2.1. In Section 5,
we turn to line percolation in three dimensions and prove Theorem 2.2, thus
obtaining an estimate for the critical probability which is tight up to multiplica-
tive constants. In Section 6, we determine the size of minimal percolating sets
for r-neighbour line percolation on [n]d and prove Theorem 2.3. We conclude
the chapter in Section 7 with some discussion.
94
3. Probabilistic preliminaries
We will need some standard facts about binomial random variables. We
collect these here for the sake of convenience. As is usual, for a random variable
with distribution Bin(N, p), we write µ = Np for its mean.
The first proposition we shall require is an easy consequence of the fact
that e−2x ≤ 1− x ≤ e−x for all 0 ≤ x ≤ 1/2.
Proposition 3.1. Let X be a random variable with distribution Bin(N, p),
with p ≤ 1/2. Then for any 1 ≤ k ≤ n,
exp(−2µ)(µ/k)k ≤ P(X = k) ≤ exp(−µ)(2eµ/k)k.
Also, exp(−2µ) ≤ P(X = 0) ≤ exp(−µ).
Proof. We have P(X = k) =
(
N
k
)
pk(1 − p)N−k. The required bounds
follow from the fact that exp(−2p) ≤ 1− p ≤ exp(−p) for 0 ≤ p ≤ 1/2 and the
fact that (N/k)k ≤ (N
k
) ≤ (eN/k) for all k ≥ 1.
The following proposition is an immediate corollary of Proposition 3.1.
Proposition 3.2. Let X be a random variable with distribution Bin(N, p).
Then for any fixed k ≥ 0, as N →∞,
P(X ≥ k) =
Θ(P(X = k)) = Θ(µ
k) if µ 1,
Θ(1) if µ 1.
where µ = Np is the mean of X.
We shall also make use of the following standard concentration result; see
Appendix A of [5] for example.
Proposition 3.3. Let X be a random variable with distribution Bin(N, p).
Then for any 0 < δ < 1,
P(|X − µ| > δµ) ≤ exp
(−δ2µ
3
)
.
95
Finally, we shall also need the following simple consequence of Harris’s
Lemma. Given a set A ⊂ [n], we say that E ⊂ {0, 1}[n] is decreasing on A if
ω ∈ E implies that ω′ ∈ E for all ω′ ∈ {0, 1}[n] such that ω′x ≤ ωx for x ∈ A
and ω′x = ωx for all x /∈ A.
Proposition 3.4. Let A ⊂ [n] and let P be a product measure on {0, 1}[n].
Then for any increasing event F which depends only on the coordinates in A
and any event E which is decreasing on A, we have P(F |E) ≤ P(F ).
Proof. For v ∈ {0, 1}[n]\A, denote by Iv the event that the coordinates in
[n] \ A are given by v. Then, since E is decreasing on A and F is increasing
on A, we see by applying Harris’s Lemma to the induced product measure on
{0, 1}A that P(E ∩ F | Iv) ≤ P(E | Iv)P(F | Iv) for every v ∈ {0, 1}[n]\A. Since
F does not depend on the coordinates in [n] \A, we also have P(F | Iv) = P(F )
for every v ∈ {0, 1}[n]\A. Therefore, by summing over all v ∈ {0, 1}[n]\A, we see
that
P(E ∩ F ) =
∑
v
P(Iv)P(E ∩ F | Iv)
≤
∑
v
P(Iv)P(E | Iv)P(F | Iv)
=
∑
v
P(Iv)P(E | Iv)P(F ) = P(E)P(F )
and the proposition follows.
4. Line percolation in two dimensions
The proof of the following proposition is essentially identical to the proof
of Theorem 2.1 in [65]; we reproduce it here for completeness.
Proposition 4.1. Fix r ∈ N, with r ≥ 2, and let C > 0 be a positive
constant. If p ∼ Cn−1−1/r, then
ϑp(n, r, 2) ∼ 1− exp (−2Cr/r!).
96
Proof. The probability that a given line has r+1 or more initially infected
points on it is bounded above by
(
n
r+1
)
pr+1 which implies that the probability
that any line has r + 1 or more initially infected points on it is bounded above
by
2n
(
n
r + 1
)
pr+1 = O
(
nr+2pr+1
)
= O
(
n−1/r
)
.
Consequently, with high probability, no line has r + 1 or more initially infected
points on it.
Let Eh denote the event that some horizontal line contains r initially infected
points and define Ev analogously. Clearly, the process terminates on the first
step if neither Eh nor Ev hold; so ϑp ≤ P(Eh ∪ Ev).
The number of horizontal lines with r initially infected points is binomially
distributed (since the events corresponding to distinct horizontal lines are
independent) and it is easily seen to converge in distribution to a Poisson
random variable with mean Cr/r! since the expected number of such horizontal
lines is n
(
n
r
)
pr(1 − p)n−r ∼ Cr/r!. Thus P(Eh) ∼ 1 − exp(−Cr/r!); similarly,
P(Ev) ∼ 1− exp(−Cr/r!).
We now estimate P(Eh ∩ Ev). Let Eh ◦ Ev denote the event that Eh and
Ev occur disjointly. Now, Eh and Ev are increasing events, and so it follows
from Harris’s Lemma and the BK inequality that P(Eh ∩Ev) ≥ P(Eh)P(Ev) ≥
P(Eh ◦ Ev). Observe that (Eh ∩ Ev) \ (Eh ◦ Ev) happens only if some lattice
point v is initially infected and each of the two axis parallel lines through v
contain r − 1 initially infected points. It follows that
P((Eh ∩ Ev) \ (Eh ◦ Ev)) = O
(
n2p(np)2r−2
)
= O
(
n−1+1/r
)
and so P((Eh∩Ev)\ (Eh ◦Ev)) = o(1). Consequently, we see that P(Eh∩Ev) ∼
P(Eh)P(Ev). Hence,
P(Eh ∪ Ev) ∼ P(Eh) + P(Ev)− P(Eh)P(Ev) ∼ 1− exp (−2Cr/r!)
and so ϑp ≤ 1− exp (−2Cr/r!) + o(1).
97
To bound ϑp from below, we generate the initial configuration in two
rounds, first by sprinkling infected points with density p′ = p(1− 1/ log n) and
then (independently) with density p′′ = p/ log n; clearly, this configuration is
dominated by an initial configuration where points are infected independently
with density p, and so it suffices to lower bound the probability of percolation
starting from this configuration.
Let E ′ be the event that some line contains r initially infected points from
the first sprinkling of points. It is easy to check from the argument above that
P(E ′) ∼ 1− exp(−2Cr/r!).
Let us now condition on E ′ and suppose that some line L has r infected
points on it from the first sprinkling. The probability that a particular line
perpendicular to L has r− 1 initially infected points from the second sprinkling
of points (none of which are on L) is Θ(((n−1)p′′)r−1) = Θ(n−1+1/r(log n)−r+1).
Thus, the number of such lines is a binomial random variable with mean
µ = Ω(n1/r(log n)−r). Since µ → ∞ as n → ∞, by Proposition 3.3, the
probability that there exist at least r such lines in the second sprinkling is
1 − o(1). Hence conditional on E ′, the probability of percolating using the
points infected in the second round is 1− o(1). Hence
ϑp ≥ (1− o(1))P(E ′) = 1− exp (−2Cr/r!)− o(1)
and the result follows.
We shall now prove Theorem 2.1.
Proof of Theorem 2.1. It follows from Proposition 4.1 that pc(n, r, 2) ∼
λn−1−1/r where λ is the unique positive real number satisfying exp(−2λr/r!) =
1/2. So we know that ϑp(n, r, 2) = Θ(1) when p n−1−1/r.
Let us now suppose that p n−1−1/r. We fix s ∈ {0, 1, . . . , r − 1} to be
the least natural number for which n(np)r−(s+1) 1; hence n(np)r−i 1 for
each 0 ≤ i ≤ s.
98
We first bound ϑp(n, r, 2) from below. To do so, we set p
′ = p/(2s + 2)
and generate our initial configuration by sprinkling infected points in 2s+ 2
rounds where we infect points independently with probability p′ in each of these
rounds; such a configuration is clearly dominated by a configuration where we
infect each point independently with probability p, so a lower bound for the
probability of percolating from such a configuration is also a lower bound for
ϑp.
Let us estimate the probability that we can find distinct lines L1, . . . ,L2s+1
such that
(1) For 0 ≤ j ≤ s, the line L2j+1 is a horizontal line containing r − j
infected points from the sprinkling in round 2j + 1, none of which lie
on L2,L4, . . . ,L2j, and
(2) for 1 ≤ j ≤ s, the line L2j is a vertical line containing r − j in-
fected points from the sprinkling in round 2j, none of which lie on
L1,L3, . . . ,L2j−1.
Indeed, conditional on finding L1, . . . ,L2j in the first 2j rounds, the prob-
ability that a given horizontal line has r − j infected points on it from the
sprinkling in round 2j + 1, none of which lie on L2,L4, . . . ,L2j is clearly
Θ(((n − j)p′)r−j) = Θ((np)r−j). Since j ≤ s, we have n(np)r−j 1, so the
probability that we can find a suitable horizontal line L2j+1 distinct from
L1, . . . ,L2j−1 in round 2j+ 1 is Θ((n− j+ 1)(np)r−j) = Θ(n(np)r−j) by Propo-
sition 3.2. The probability that we can find L2j as required conditional on
finding L1, . . . ,L2j−1 is similarly seen to be Θ(n(np)r−j).
So the probability that we can find L1, . . . ,L2s+1 as required in the first
2s+ 1 rounds is thus, up to constant factors, at least
n(np)r × n(np)r−1 × · · · × n(np)r−s × n(np)r−s = n2s+1(np)r(2s+1)−s(s+1).
Conditional on finding L1, . . . ,L2s+1, we claim that with probability Θ(1),
there are at least r vertical lines distinct from L2, . . . ,L2s each containing
99
r − s− 1 infected points from the sprinkling in round 2s+ 2, none of which lie
on L1,L3, . . . ,L2s+1. Indeed, the number of such lines is binomially distributed
with mean µ = Ω(n(np)r−s−1), and we know that µ 1 by the definition of s,
so we are done by Proposition 3.2.
Such a configuration clearly percolates. Indeed, first the line L1 gets infected,
then the line L2, and so on, until all of L1, . . . ,L2s+1 are infected. At this point,
the r vertical lines distinct from L2, . . . ,L2s each containing r − s− 1 infected
points none of which lie on L1,L3, . . . ,L2s+1 get infected. Of course, once we
have r parallel fully infected lines, every point gets infected. Thus, we deduce
from this sprinkling argument that ϑp = Ω(n
2s+1(np)r(2s+1)−s(s+1)).
We now give a matching upper bound for ϑp(n, r, 2). To do so, it will be
convenient to work with a modified two-dimensional line percolation process
Ap = G
(0) ⊂ G(1) ⊂ . . . G(t) ⊂ . . .
where G(2t+1) is obtained from G(2t) by spreading the infection (only) along
horizontal lines and G(2t+2) is obtained from G(2t+1) by spreading the infection
along vertical lines. Since G(t) ⊂ A(t) and A(t) ⊂ G(2t), percolation occurs in
the original process if and only if it occurs in the modified process.
Note that Ap percolates if and only if some G
(t) contains r or more fully
infected lines; indeed, in this case G(t+2) = [n]2. In particular, since s+ 1 ≤ r,
if Ap percolates, then some G
(t) contains s + 1 parallel fully infected lines.
Let us stop the modified process as soon it produces s + 1 or more parallel
fully infected lines (or reaches termination). Note that we necessarily stop the
process in at most 2s+ 2 ≤ 2r steps.
Let us clarify what we mean by a ‘fully infected line’. Formally, a line
becomes fully infected when we examine its direction and find that there are r
or more infected points on the line, and hence infect the rest of the line. Note
that, unlikely as it might be, all the points on a line could become infected
before we inspect the direction corresponding to the line; in this case, we declare
the line to be fully infected only after we examine its direction.
100
hr − h
v v′
Figure 2. The conditioning argument.
Let E∗ denote the event that we stop the process because it generated s+ 1
parallel fully infected lines; clearly ϑp ≤ P(E∗).
The following lemma will allow us to bound P(E∗) from above.
Lemma 4.2. Let t, h, v ∈ N and suppose that t is odd and that (n(np)r−h)
1. Let E be the event that the numbers of fully infected horizontal and vertical
lines after the first t steps are h and v respectively and F denote the event that
the process generates v′ or more vertical lines on step t+ 1. Then
P(F |E) = O
((
n(np)r−h
)v′)
.
Proof. We prove this with a conditioning argument. Consider any set
H of h horizontal lines and any set V of v vertical lines and fix a partition
H = H1 ∪ H3 ∪ · · · ∪ Ht and V = V2 ∪ V4 ∪ · · · ∪ Vt−1. Let E be the event
that the lines infected in the first t steps of the process are precisely those in
H1,V2, . . . ,Ht. Since E is the disjoint union of such events E, it suffices to
show that P(F |E) = O((n(np)r−h)v′) for every such event E.
Let S denote the subgrid consisting of those points not on any of the lines in
H∪V . Let F denote the event that there are v′ or more vertical lines in S with
r−h or more initially infected points on them. Note that conditional on E, the
101
event F occurs if and only if F occurs; clearly, P(F |E) = P(F |E). Note that
F is an increasing event and P(F ) = O((n(np)r−h)v′) since (n(np)r−h) 1.
If E were a decreasing event, we could conclude immediately from the
Harris’s Lemma that P(F |E) ≤ P(F ). Though E is in itself not decreasing,
we claim that E is decreasing on S.
Let ω ∈ {0, 1}[n]2 be an initial configuration that belongs to E and let
ω′ ∈ {0, 1}[n]2 be such that ω′x ≤ ωx for x ∈ S and ω′x = ωx for x /∈ S. We now
check that ω′ ∈ E. We first note that since the percolation process is monotone
and ω′ ≤ ω, the set of fully infected lines at any stage when we start from ω′ is
a subset of the set of fully infected lines at that stage when we start from ω.
Next, note that since ω ∈ E, when we start the line percolation process from
ω, none of the lines through any of the points in S are infected after the first t
steps; in other words, none of these points participate in the spread of infection
during the first t steps. Therefore, since ω′x = ωx for all x /∈ S, it follows that
the set of fully infected lines after the first t steps when we start from ω′ is
actually identical to the set of fully infected lines after the first t steps when
we start from ω. Thus, ω′ ∈ E and it follows that E is decreasing on S.
It follows by Proposition 3.4 that P(F |E) ≤ P(F ); the lemma follows.
Let ht and vt be the numbers of horizontal and vertical lines infected when
going from G(2t) and G(2t+1) and from G(2t+1) to G(2t+2) respectively; the pair
(h = (ht)t≥0,v = (vt)t≥0) is called the line-count of the modified percolation
process.
Given two sequences h = (ht)
k
t=0 and v = (vt)
k
t=0 of positive integers with
k ≤ s+ 1, we say that (h,v) is a vertical line-count if (h,v) is the line-count of
a process which generates s+ 1 fully infected vertical lines before it generates
s+ 1 fully infected horizontal lines, and does so in exactly 2k+ 2 steps; in other
words, if
(1)
∑
t r, it is not hard to
104
check that γ = (r + s2 + s)/(2s+ 2) satisfies
r − s− 1 ≤ γ ≤ r − s
and hence
n−1−
1
r−s−1 n−1− 1r−γ n−1− 1r−s , (12)
and so it follows from Theorem 2.1 that
ϑp(n, r, 2) = Θ
(
n2s+1(np)r(2s+1)−s(s+1)
)
= Θ
(
Cr(2s+1)−s(s+1)n−1
)
.
We say that a plane P is internally spanned if A(0) ∩ P percolates in the
line percolation process restricted to P. Choose any direction and consider
the n (parallel) planes perpendicular to this direction. The number of such
planes which are internally spanned is a binomial random variable with mean
µ = Ω(Cr(2s+1)−s(s+1)). Since µ→∞ as C →∞, we see from Proposition 3.3
that there exist r parallel internally spanned planes with probability at least
1/2 if C is greater than some sufficiently large constant. So it follows that
pc(n, r, 3) = O(n
−1−1/(r−γ)).
Case 2: C 1. We claim that the probability of percolation is at most
1/2, provided C is less than some sufficiently small constant.
We shall demonstrate that the probability of percolation is at most 1/2 by
proving something much stronger. We shall track, as the infection spreads,
the number of planes with k or more parallel fully infected lines for each
1 ≤ k ≤ s+ 1 and show that, with probability at least 1/2, these numbers are
not too large when the process terminates; in particular, we shall show that
there are no planes with s + 1 or more parallel fully infected lines when the
process reaches termination and consequently, that there is no percolation.
As we did in the two-dimensional case, we shall work with a modified
three-dimensional line percolation process in which the infection spreads along
a single direction at each step. More precisely, denoting the standard basis for
105
R3 by {e0, e1, e2}, in the modified process, we have a sequence
Ap = H
(0) ⊂ H(1) ⊂ · · · ⊂ H(t) ⊂ . . .
of subsets of [n]3 where H(t+1) is obtained from H(t) by spreading the infection
(only) along lines parallel to ei where i ≡ t (mod 3). Clearly, H(t) ⊂ A(t) ⊂
H(3t) and so Ap percolates in the original process if and only if it percolates in
this modified process.
We run the modified three-dimensional process starting from Ap and we
stop the process after step t if either
(A) the number of planes containing k or more parallel fully infected lines now
exceeds n1−kγ/(r−γ) for some 1 ≤ k ≤ s+ 1, or
(B) the process has terminated, i.e., H(t) = [Ap].
Let EA be the event that we the stop the modified process on account of
condition (A).
Lemma 5.1. In the modified process,
P(EA) = O
( ∑
1≤k≤s
Crk + Cr(2s+1)−s(s+1)
)
.
Let us fix a plane P. For concreteness, we shall assume that P contains
lines parallel to e0 and e1, and that e2 is perpendicular to P. We shall prove
Lemma 5.1 by estimating the probability that P contains k or more parallel
fully infected lines when we stop the process.
The spread of infection within P resembles the two-dimensional line per-
colation process, with the key distinction that some points in P also become
infected during the process by virtue of lying on a fully infected line perpendic-
ular to P . However, since we are interested in estimating the probability that
k or more parallel lines in P get infected before we stop the process, we shall
not have to worry about there being too many such points.
106
For 1 ≤ k ≤ s + 1, let Ek denote the event that k or more parallel lines
in P get infected before we stop the process. We shall prove Lemma 5.1 by
bounding P(Ek) from above.
As before, we shall estimate the probability that k or more parallel lines
in P get infected before we stop the process by estimating the probability
that this happens according to a particular line-count. Note that unlike in the
two-dimensional process, a large number of steps may elapse before a new line
in P gets infected. Consequently, the precise notion of a line-count that we use
here differs slightly from the notion used previously.
We call a step of the modified three-dimensional process an epoch if a
non-empty subset of the lines in P (along a particular direction) get infected
on that step. A line-count ` = ((li, di))i≥0 is a sequence of pairs (li, di) such
that each li is a positive integer and each di ∈ {e0, e1} is a direction, with the
property that either
(1)
∑
i:di=e0
li ≥ k, or
(2)
∑
i:di=e1
li ≥ k.
Given a line-count ` = ((li, di))i≥0, we define its preface `
∗ = ((li, di))mi=0 by
taking m to be largest index j such that
(1)
∑
i≤j:di=e0 li < k, and
(2)
∑
i≤j:di=e1 li < k.
Note that if Ek occurs, there is a line-count ` = ((li, di))i≥0 such that the
number and direction of the lines infected on the i-th epoch are given by li
and di respectively. Consequently, given a preface `
∗, let us write Ek(`
∗) for
the event that Ek occurs and that the preface of the associated line-count is `
∗.
Clearly,
P(Ek) =
∑
`∗
P(Ek(`∗)),
107
where the sum above is over all valid prefaces. Since the length of a valid
preface is at most 2k, the number of valid prefaces is at most (2k)2k. Therefore,
it suffices to bound the largest of the probabilities P(Ek(`∗)).
The following lemma allows us to estimate P(Ek(`∗)). We think of the lines
in P parallel to e0 as being horizontal, and the ones parallel to e1 as being
vertical.
Lemma 5.2. Let i, h, v ∈ N and suppose that n(np)r−h 1. Let E be the
event that after the i-th epoch, the numbers of fully infected horizontal and
vertical lines in P are h and v respectively. Also, let F denote the event that v′
or more vertical lines in P get infected on the (i+ 1)-th epoch. Then
P(F |E) = O
((
n(np)r−h
)v′)
.
Proof. The proof is very similar to that of Lemma 4.2. However, we also
need to account for points that might not be infected initially but which get
infected at some stage before the (i+ 1)-th epoch. We call a point of P a boost
if the line perpendicular to P through that point is fully infected before the
(i+ 1)-th epoch.
Let L1,L2, . . . ,Li be disjoint non-empty sets of parallel lines in P such that
the numbers of horizontal and vertical lines in L1 ∪ L2 ∪ · · · ∪ Li are h and
v respectively. Let S denote the subgrid consisting of those points of P not
on any of the lines in L1 ∪ L2 ∪ · · · ∪ Li and let B be a subset of S. Let E
be the event that the lines infected in the first i epochs are precisely those in
L1,L2, . . . ,Li; also let E ′ denote the event that set of boosts in S is precisely
B. Since E is the disjoint union of such events E, it suffices to show that
P(F |E) = O((n(np)r−h)v′) for every such event E. We shall demonstrate the
stronger assertion that P(F |E ∩E ′) = O((n(np)r−h)v′) for every pair of events
E and E ′ as above.
Let Vj be the set of those vertical lines of S which meet B in j points and
let Nj = |Vj|.
108
SFigure 3. Boosts on a line in S.
By conditioning on E ′, we are assuming that there are at least Nj planes
with j or more parallel fully infected lines before the (i+1)-th epoch. Therefore,
if Nj > n
1−jγ/(r−γ) for some 1 ≤ j ≤ s+ 1, then this implies that the modified
three-dimensional process gets stopped before the (i+ 1)-th epoch and so we
trivially have P(F |E ∩ E ′) = 0 in this case. Hence, we may assume that
Nj ≤ n1−jγ/(r−γ) for each 1 ≤ j ≤ s + 1. Observe that (s + 1)γ/(r − γ) > 1
since (s+ 1)(s+ 2) > r and so Nj = 0 for j ≥ s+ 1 since n1−(s+1)γ/(r−γ) < 1.
Let vj be the number of lines of Vj whose intersection with S \ B contains
r−h−j or more initially infected points. Let F be the event that ∑sj=0 vj ≥ v′.
Note that a point of S which is infected before the (i+ 1)-th epoch is either
initially infected or belongs to B. Hence, P(F |E ∩ E ′) = P(F |E ∩ E ′). Note
that F is an increasing event that depends only on the points in S \ B.
We claim that E ∩E ′ is decreasing on S \B. Let ω ∈ {0, 1}[n]3 be an initial
configuration that belongs to E∩E ′ and let ω′ ∈ {0, 1}[n]3 be such that ω′x ≤ ωx
for x ∈ S \ B and ω′x = ωx for x /∈ S \ B. We now check that ω′ ∈ E ∩ E ′.
As before, we first note that since the percolation process is monotone and
ω′ ≤ ω, the set of fully infected lines (not just in P , but rather in all of [n]3) at
any stage when we start from ω′ is a subset of the set of fully infected lines
at that stage when we start from ω. Next, note that since ω ∈ E ∩ E ′, when
we start the line percolation process from ω, none of the lines through any of
the points in S \ B are infected before the (i + 1)-th epoch; in other words,
109
none of these points participate in the spread of infection before the (i+ 1)-th
epoch. Therefore, since ω′x = ωx for all x /∈ S \B, it follows that the set of fully
infected lines at any stage before the (i+ 1)-th epoch when we start from ω′ is
actually the same as the set of fully infected lines at that stage when we start
from ω. Thus, ω′ ∈ E ∩ E ′ and it follows that E ∩ E ′ is decreasing on S \ B.
It follows from Proposition 3.4 that P(F |E ∩ E ′) ≤ P(F ). Therefore, it
suffices to show that P(F ) ≤ O((n(np)r−h)v′).
We first consider P(v0 ≥ l). The probability that there exist l or more
vertical lines in V0 which meet S \ B in r − h initially infected points is
O
((
N0
l
)(
(np)r−h
)l)
= O
((
n(np)r−h
)l)
since N0 ≤ n. On the other hand, for 1 ≤ j ≤ s, we have
P(vj ≥ l) = O
((
Nj
l
)(
(np)r−h−j
)l)
= O
((
n(np)r−h
)l(
n1−γ/(r−γ)p
)−jl)
= O
((
n(np)r−h
)l)
since Nj ≤ n1−jγ/(r−γ) and n1−γ/(r−γ)p = Cn−(γ+1)/(r−γ) = o(1) as γ ≥ 0. It
follows that
P(F ) = P
(
s∑
j=0
vj ≥ v′
)
≤
∑
x0,x1,...,xs
P(v0 ≥ x0, v1 ≥ x1, . . . , vs ≥ xs),
where the sum above is over all non-negative integer solutions to the equation
x0 + x1 + · · ·+ xs = v′. First, note that the number of such solutions is at most
(v′ + 1)s. Next, note that since the sets Vj are disjoint, we have
P(v0 ≥ x0, v1 ≥ x1, . . . , vs ≥ xs) =
s∏
j=0
P(vi ≥ xi) = O
((
n(np)r−h
)∑s
j=0 xj
)
.
It follows that P(F ) ≤ O((n(np)r−h)v′) and this completes the proof of
Lemma 5.2.
110
Given a preface `∗ = ((li, di))mi=0, we shall mimic the proof of Theorem 2.1
to bound P(Ek(`∗)). Let us write h =
∑
i≤m:di=e0 li and v =
∑
i≤m:di=e1 li; note
that h, v < k since `∗ is a preface. Recall that s is the greatest natural number
such that s(s + 1) ≤ r and that p = Cn−1−1/(r−γ) satisfies n(np)r−s 1 and
n(np)r−s−1 1. Hence, by applying Lemma 5.2 repeatedly, we see that the
probability of Ek(`
∗), up to constant factors, is bounded above by
(n(np)r)l0 × · · · ×
(
n(np)
r−∑j 0, that if G is a graph on n vertices, then f(G) ≥ n/2−o(n) provided
G has at most n2−α edges (or non-edges). Axenovich, Martin and Ueckerdt [7]
later showed that the same holds for graphs with at most o(n2/(log n)2) edges.
Our main aim in this chapter is to narrow considerably the gap between the
best known upper and lower bounds for f(n), and thereby answer a question
of Caro and Yuster [36].
Theorem 1.1. For every ε > 0, there exists a natural number N = N(ε)
such that for any graph G on n > N vertices, f(G) ≥ n/2− εn. Consequently,
n/2− o(n) ≤ f(n) ≤ n/2− Ω(log log n).
We remark that much research has been done on the family of induced
subgraphs of a graph. For example, call a graph k-universal if it contains every
graph of order k as an induced subgraph. Very crudely, if G is a k-universal
graph with n vertices, then (
n
k
)
≥ 2
(k2)
k!
,
and so n ≥ 2(k−1)/2. As remarked in [32], almost all graphs with k22k/2 vertices
are k-universal, and the Paley graphs come close to providing examples which
are almost as good. Hajnal conjectured that if a graph only has a ‘small’
number of distinct (non-isomorphic) induced subgraphs, then it contains a
trivial (complete or empty) subgraph with linearly many vertices. This was
proved, shortly after the conjecture was made, by Alon and Bolloba´s [3], and
Erdo˝s and Hajnal [48], the latter in a stronger form. In [3] only a few parameters,
118
like order, size and maximal degree, were used to distinguish non-isomorphic
graphs.
Erdo˝s and Hajnal [49] then went much further: they realised that forbidding
a single graph as an induced subgraph severely constrains the structure of a
graph. More precisely, they made the major conjecture that for every graph
H, there is a positive constant γ(H) such that if a graph of order n does not
contain H as an induced subgraph, then the graph contains a trivial subgraph
with at least nγ(H) vertices. In spite of all the work on this conjecture (for a
small sample, see [38, 57, 94]) we are very far from the desired bound.
Let us finally mention another interesting line of research about finding dis-
joint isomorphic (not necessarily induced) subgraphs. Jacobson and Scho¨nheim
(see [50, 83]) independently raised the question of finding edge-disjoint iso-
morphic subgraphs. Improving on results of Erdo˝s, Pyber and Pach [50], Lee,
Loh and Sudakov [83] showed that every graph on m edges contains a pair
of edge-disjoint isomorphic subgraphs with at least Ω((m logm)2/3) edges and
that this is best possible up to a multiplicative constant.
The rest of this chapter is organised as follows. We give an overview of our
approach in Section 3, and then fill in the details and prove Theorem 1.1 in
Section 4. There are many natural questions about induced subgraphs which
are close to Theorem 1.1 in spirit; we conclude in Section 5 by mentioning some
of these.
2. Preliminaries
Our objective in this section is to establish some notational conveniences
and collect together, for easy reference, some simple propositions that we shall
make use of when proving our main result.
2.1. Notation. A pair (x, y) will always mean an unordered pair with
x 6= y, and a collection of pairs P will always mean a set of disjoint pairs; for
example, P = {(1, 2), (3, 4)} is a collection of pairs, but Q = {(1, 2), (2, 3)} is
119
not. For a collection of pairs denoted by P , we shall write P for the underlying
ground set of elements, i.e., P =
⋃
(x,y)∈P{x, y}; in other words, we reserve
the corresponding upper case letter for the ground set. We shall say that
two collections of pairs P and Q are disjoint if P ∩Q = ∅; for example, the
collections P1 = {(1, 2), (3, 4)} and Q1 = {(5, 6), (7, 8)} are disjoint, while the
collections P2 = {(1, 2), (3, 4)} and Q2 = {(1, 3), (2, 4)} are not.
As usual, given a graph G = (V,E), we write deg(v) and Γ(v) respectively
for the degree and for the neighbourhood of a vertex v in G. For a subset
U ⊂ V , we write G[U ] for the subgraph induced by U , e(U) for the number of
edges of G[U ], and deg(U) for the sum of the degrees (in G) of the vertices of
U . Given two disjoint subsets A,B ⊂ V , we write e(A,B) for the number of
edges with one endpoint each in A and B.
We shall also use the following less common terminology and notation. For
any two vertices x, y ∈ V , we write δ(x, y) for the degree difference between
x and y, namely the quantity | deg(x)− deg(y)|. We say that two vertices x
and y disagree on a vertex v 6= x, y if v is adjacent to exactly one of x and y;
otherwise x and y agree on v. For any two vertices x, y ∈ V , the difference
neighbourhood Γ(x, y) of x and y is the set of vertices v 6= x, y on which x and
y disagree; we write ∆(x, y) for the size of the difference neighbourhood, so
that δ(x, y) ≤ ∆(x, y). If two vertices x and y agree on every vertex v 6= x, y,
we say that the pair (x, y) is a clone pair. When the graph G in question is
not clear from the context, we shall, for example, write δ(x, y,G) to denote the
degree difference between x and y in G.
We say that a graph G is splittable if there is a partition V = A ∪ B of
its vertex set into two sets A and B of equal size with e(A) = e(B); in this
case, we call (A,B) a splitting of G. Note that e(A) = e(B) if and only if
deg(A) = deg(B), since deg(A) = 2e(A) + e(A,B).
Our conventions for asymptotic notation are largely standard; in particular,
we we write ok→∞(1) to denote a function (of k) that goes to 0 as k →∞, and
that when we write, say Ωk(.), we mean that the constant suppressed by the
120
asymptotic notation is allowed to depend on (but is completely determined by)
the parameter k. For the sake of clarity of presentation, we systematically omit
floors and ceilings whenever they are not crucial.
2.2. Preliminary observations. We shall make use of the following sim-
ple observation repeatedly when constructing a splitting.
Proposition 2.1. Given positive real numbers x1, x2, . . . , xt in the interval
[a, b] with 0 ≤ a ≤ b and y ∈ [−ta, ta], we may choose signs ζi ∈ {−1,+1} such
that |y +∑ ζixi| ≤ b.
Proof. We may assume without loss of generality that y ≥ 0. Let j be
the largest index such that y >
∑j
i=1 xi; since y ≤ ta, we must have j < t.
Set ζi = −1 for 1 ≤ i ≤ j. Now, clearly y −
∑j
i=1 xi ∈ [−b, b]. Given a real
number z ∈ [−b, b] and a positive real x ≤ b, one of z + x or z − x always lies
in [−b, b]. Consequently, we may choose the signs of xj+1, . . . , xt one-by-one,
always ensuring that the partial sum is in the interval [−b, b], thus proving the
claim.
The following first moment bound will prove useful; it is easily checked that
the bound is the best possible.
Proposition 2.2. Let X be a random variable such that X ≤ N and
E[X] ≥ Np. Then
P
(
X ≥ E[X]
2
)
≥ p
2− p.
Proof. Let us write t = P(X ≥ E[X]/2). We know that E[X] ≤ tN +
(1− t)E[X]/2. This implies that t(N − E[X]/2) ≥ E[X]/2. The result follows
from the fact that E[X] ≥ Np.
We will also need the following two easy propositions.
Proposition 2.3. Given x1, x2, . . . , xt in the interval [0, a], a positive real
b and a natural number N , it is possible to find bt/Nc − da/be disjoint subsets
121
of {x1, x2, . . . , xt}, each of size N , such that |xi − xj| ≤ b for any xi and xj
belonging to the same subset.
Proof. Suppose that x1 ≤ x2 ≤ · · · ≤ xt. Let i0 = 1 and define ij to be the
smallest index such that xij > xij−1 +b with the convention that if no such index
exists, we set ij = t+1 and stop. Consider the sets Sj = {xij , xij+1, . . . , xij+1−1}.
Since x1 ≥ 0 and xt ≤ a, there are at most da/be such sets. Now, by discarding
at most N numbers from each Sj if necessary, we can assume that N divides
|Sj| for each j. We now partition each Sj into subsets of size N . Clearly,
|xi − xj| ≤ b for any xi and xj belonging to the same subset. The number of
elements we have discarded is at most Nda/be. So the number of subsets of
size N we are left with is at least bt/Nc − da/be.
Remark. We shall often apply Proposition 2.3 to the degrees of a subset of
vertices of a graph; we consequently obtain disjoint groups of vertices such that
the degree difference of any two vertices in the same group is suitably bounded.
Proposition 2.4. Let x, y and z be three vertices and U some subset of
vertices of a graph G. Then some two of the vertices x, y and z disagree on at
most two thirds of the vertices of U .
Proof. Any vertex v ∈ U belongs to at most two of the three difference
neighbourhoods Γ(x, y), Γ(y, z) and Γ(z, x). The claim follows by averaging.
2.3. Binomial random variables. We will need some easily proven state-
ments about binomial random variables. We collect these here. As usual, for a
random variable with distribution Bin(N, p), we write µ(= Np) for its mean
and σ2(= Np(1− p)) for its variance.
We begin by recalling the following proposition from the previous chapter.
Proposition 2.5. Let X be a random variable with distribution Bin(N, p),
with p ≤ 1/2. Then for any 1 ≤ k ≤ n,
exp(−2µ)(µ/k)k ≤ P(X = k) ≤ exp(−µ)(2eµ/k)k.
122
Also, exp(−2µ) ≤ P(X = 0) ≤ exp(−µ).
We shall make use of the following standard concentration result which first
appeared in a paper of Bernstein and was later rediscovered by Chernoff and
Hoeffding; see Appendix A of [5] for example.
Proposition 2.6. Let X be a random variable with distribution Bin(N, p).
Then
P(|X −Np| > t) ≤ exp
( −t2
N/2 + 2t/3
)
.
Proposition 2.7. Let X be a random variable with distribution Bin(N, p).
Then
P(X is even) =
1
2
(1 + (1− 2p)N).
To prove the next two propositions, it will help to define θ(N, p) =
maxk P(X = k) where X has distribution Bin(N, p). It follows from Stirling’s
approximation, see [27], that θ(N, p) = O(1/
√
p(1− p)N).
Proposition 2.8. Let X1 and X2 be two independent random variables
both with distribution Bin(N, p). Then
P(X1 = X2) = oσ→∞(1).
In particular, when p ≤ 1/2, P(X1 = X2) = oµ→∞(1).
Proof. The proof follows simply by noting that
P(X1 = X2) =
∑
k
P(X1 = k)P(X2 = k)
≤ θ(N, p)
∑
k
P(X2 = k) = θ(N, p) = O(1/σ).
Proposition 2.9. Let X1 and X2 be two independent random variables
with distributions Bin(N1, p) and Bin(N2, p) respectively, with p ≥ 1/2. Then
P(|X1 −X2| < |N1 −N2|1/3) = o|N1−N2|→∞(1).
123
Proof. Assume, without loss of generality, that N2 ≥ N1 and write t =
N2 − N1 and q = 1 − p. If q ≥ t4/5/N2, then we proceed as follows. The
probability that X2 lies in an interval of size 2t
1/3 + 1 is, independently of the
interval, at most
(2t1/3 + 1)θ(N2, p) = O
(
t1/3√
pqN2
)
= O(t−1/15) = o(1);
the claim follows immediately in this case. Hence, suppose that q < t4/5/N2. In
this case, we see from the standard Chernoff bound that P(X2 < N2 − 2t4/5) =
o(1). This implies that P(X2 < N1 + t1/3) = o(1); since X1 ≤ N1, the claim
follows.
Proposition 2.10. Let X1 and X2 be two independent random variables
with distributions Bin(N1, p) and Bin(N2, p) respectively, with p ≥ 1/2. Suppose
N1 ≤ N , N2 ≤ N and |N1 −N2| ≤ cN1/2 for some absolute constant c. Then
P(|X1 −X2| > N2/3) = O
(
exp
(−N1/3
5
))
.
Proof. If |X1 − X2| > N2/3, then since |N1 − N2| ≤ cN1/2, we must
necessarily have either |X1 − E[X1]| ≥ N2/3/3 or |X2 − E[X2]| ≥ N2/3/3
assuming N is sufficiently large. By the Chernoff bound, we have
P(|X1 − E[X1]| ≥ N2/3/3) ≤ exp
( −N4/3/9
N1/2 + 2N2/3/9
)
≤ exp
(−N1/3
5
)
,
where the last inequality holds for all large enough N since N1 ≤ N . We have
an analogous bound for P(|X2 − E[X2]| ≥ N2/3/3); the claim follows.
3. Overview of our strategy
To prove Theorem 1.1, we need to show that if ε > 0 and n is sufficiently
large, then any graph G on n vertices contains two disjoint subsets of vertices
of the same size, each of cardinality at least (1/2− ε)n, which induce the same
number of edges. Equivalently, we need to show that it is possible to transform
124
G into a splittable graph by deleting at most 2εn vertices from G. Recall that
a graph is splittable if and only if there is a partition of its vertex set into two
sets of equal size such that the sums of the degrees of the vertices in the two
sets are equal.
We shall show that there is a probability 0 < p ≤ ε (depending on G) such
that if we delete vertices from G with probability p, then the resulting graph
H is splittable with positive probability.
To show that this random subgraph H is splittable, we shall exhibit a large
collection of ‘gadgets’ in H. Given 0 ≤ a ≤ b, by an [a, b]-gadget, we mean a
pair of vertices (x, y) such that a ≤ δ(x, y) ≤ b; a gadget, in other words, is
just a pair of vertices whose degree difference we can control.
Once we have found sufficiently many suitable gadgets in H, we construct
a splitting of H as follows: we use Proposition 2.1 to decide, one-by-one for
each gadget, which way round to assign the vertices of the gadget to the sides
of the splitting. The following lemma makes this idea precise.
Lemma 3.1. Let H be a graph on an even number of vertices and suppose
that we can partition V (H) into disjoint collections of pairs P1,P2, . . . ,Pk such
that the pairs in Pi are [ai, bi]-gadgets, where 0 ≤ a1 ≤ b1 and 0 < ai ≤ bi for
2 ≤ i ≤ k. If bi−1 ≤ ai|Pi| for each 2 ≤ i ≤ k, then V (H) can be partitioned
into two sets A,B of the same size such that | deg(A) − deg(B)| ≤ bk. In
particular, if bk = 1, then H is splittable.
Proof. We show by induction on i that it is possible to partition the
vertices of the gadgets in P1, . . . ,Pi into two sets Ai and Bi of equal size such
that | deg(Ai) − deg(Bi)| ≤ bi. The lemma follows by taking A = Ak and
B = Bk.
We set b0 = 0 and A0 = B0 = ∅ and so the claim is trivially true when i = 0.
So suppose that i ≥ 1 and that we have constructed Ai−1 and Bi−1. Denote
the [ai, bi]-gadgets in Pi by (xj, yj), where deg(xj) ≥ deg(yj) for 1 ≤ j ≤ |Pi|.
Using the fact that bi−1 ≤ ai|Pi|, it follows from Proposition 2.1 that there is a
125
choice of signs ζj ∈ {−1,+1} for 1 ≤ j ≤ |Pi| such that∣∣(deg(Ai−1)− deg(Bi−1)) +∑
j
ζjδ(xj, yj)
∣∣ ≤ bi.
Given ζj as above, we construct Ai and Bi from Ai−1 and Bi−1 as follows: for
each 1 ≤ j ≤ |Pi|, we add xj to Ai−1 and yj to Bi−1 if ζj = 1, and yj to Ai−1
and xj to Bi−1 if ζj = −1. The claim follows.
If bk = 1, notice that we have a partition of V (H) into two sets A and B of
equal size such that | deg(A)− deg(B)| ≤ 1. As deg(A) + deg(B) is the sum of
all the vertex degrees, we conclude that deg(A) = deg(B) since deg(A)−deg(B)
must be even.
Lemma 3.1 tells us that a graph is splittable if we can find the right gadgets
in the graph. The majority of the work in proving Theorem 1.1 is in showing
that it is possible to find a good collection of gadgets.
4. Proof of the main result
We now try and make the intuition presented in Section 3 precise. We shall
show that if ε > 0 and n is sufficiently large, it is possible to transform any
graph G on n vertices into a splittable graph by deleting at most 2εn vertices
from G. Before we begin, we remark that the various constants suppressed
by the asymptotic notation throughout the proof are allowed to depend on
ε. We shall use c1, c2, . . . to represent small constants depending on ε and
C1, C2, . . . for large constants depending on ε. All our estimates will hold when
n is sufficiently large.
Proof of Theorem 1.1. Let ε > 0 be fixed. By deleting an arbitrary
vertex of G if necessary, assume that n = |V (G)| is even. Let β = β(ε) be a
small constant whose value we shall fix at the end of the argument in Case 1.
Call a pair of vertices (x, y) a ‘large’ pair if δ(x, y) ∈ [n1/3, βn]. Let c1 = ε/2.
We distinguish two cases depending on how many disjoint large pairs we can
126
find in G. We first deal with the case when G contains many disjoint large
pairs.
Case 1: G contains c1n disjoint large pairs of vertices. In this case,
we shall show that G either trivially has a large splittable induced subgraph or
that G has an induced subgraph H of even order on at least (1− 2ε)n vertices
that contains
(1) a collection SH of [1, 1]-gadgets of size Ω(n/ log n),
(2) a collection MH of [1, n2/3]-gadgets of size at least 2βn, and
(3) a collection LH of [n1/9, 2βn]-gadgets of size Ω(n)
such that the collections SH ,MH , and LH are disjoint. It is straightforward to
check that such a graph H is splittable using Lemma 3.1. Indeed, pair up the
vertices V (H)\(LH∪MH∪SH) arbitrarily; any such pair is a [0, n]-gadget and so
we have a partition of V (H) into disjoint collections of [0, n]-gadgets, [n1/9, 2βn]-
gadgets, [1, n2/3]-gadgets and [1, 1]-gadgets. The sizes of these collections satisfy
the conditions of Lemma 3.1 if n is sufficiently large and it follows that H is
splittable.
We shall now show that G does indeed contain such an induced subgraph
H. We shall construct H by deleting vertices from G at random.
To avoid notational clutter, in the rest of the argument in Case 1, we shall
write large-gadget for an [n1/9, 2βn]-gadget, medium-gadget for a [1, n2/3]-gadget
and one-gadget for a [1, 1]-gadget.
Let L be a collection of c1n large pairs of vertices of G. The pairs in L will
be the candidates for the large-gadgets we hope to find in H. Our next task is
to find a large collectionM of ‘medium’ pairs and a reasonably large collection
S of ‘small’ pairs; the collections M and S will provide the candidate pairs for
the medium-gadgets and one-gadgets that we would like to find in H.
Now, |V \ L| = (1 − 2c1)n; recall that in our notation, L denotes the
underlying ground set of L. If we find more than (1/2− ε)n disjoint clone pairs
(x, y) in G[V \ L], we are done. Indeed, we can delete all the other (≤ 2εn)
127
vertices not in any of these clone pairs to get a splittable graph: we split this
graph by assigning different vertices of each clone pair to different halves of
the partition. So we may assume that we can find a set V ′ ⊂ V \ L of vertices
of G such that any two vertices of V ′ disagree on some vertex of V \ L and
|V ′| ≥ (2ε− 2c1)n ≥ εn.
Let C1 = 4/ε and let c2 = ε/12. We now apply Proposition 2.3 to the
degrees of the vertices of V ′; by our choice of C1 and c2, we see that we can
find c2n disjoint groups of three vertices from V
′ such that δ(x, y) ≤ C1 for any
two vertices x and y in the same group. By Proposition 2.4, from each of these
triples, we may choose a pair of vertices (x, y) such that ∆(x, y) ≤ 2n/3. Write
P for this collection of c2n pairs.
For 0 ≤ i ≤ log n− 1, let Pi be the collection of those pairs (x, y) in P such
that ∆(x, y) ∈ [2i, 2i+1). There are two possibilities that we need to consider. It
might be that no collection Pi contains too many pairs; we deal with this case
next. The case where one of these collections contains many pairs is easier; we
deal with this scenario later with a modification of the argument that follows.
Let C2 ≥ 4 be a (large) constant depending on ε; we shall fix the value of
C2 later in the proof at the end of Case 1A. Also, let c3 = c2/3C2 ≤ c2/12.
Case 1A: None of the collections P0,P1, . . . ,Plogn−1 contains c3n
pairs. It is clear that at least one of the collections P0,P1, . . . ,Plogn−1 contains
at least c2n/ log n pairs. Let k be the smallest index such that |Pk| ≥ c3n/ log n
and let us define our collection of small pairs S by setting S = Pk. We now
define our collection of medium pairs M by setting
M = Pk+C2 ∪ · · · ∪ Plogn−1.
Since k is minimal and c3 ≤ c2/12, we see that |M| ≥ c2n/2.
We shall now restrict our attention to the collections S, M and L; note
that they are disjoint. We shall make use of the following facts about these
collections.
128
(1) S contains c3n/ log n pairs of vertices (x, y) such that δ(x, y) ≤ C1,
∆(x, y) ∈ [2k, 2k+1), and ∆(x, y) ≤ 2n/3.
(2) M contains c2n/2 pairs of vertices (x, y) such that δ(x, y) ≤ C1, and
∆(x, y) ≥ 2k+C2 .
(3) L contains c1n pairs of vertices (x, y) with δ(x, y) ∈ [n1/3, βn].
(4) For any pair of vertices (x, y) in S or M, there exists at least once
vertex in V \ L on which x and y disagree.
We are now in a position to describe how we intend to construct a splittable
graph from G. We shall delete vertices from G independently with a fixed
probability. We shall show that with positive probability, many of the small
pairs from S form one-gadgets in the resulting graph, many of the medium
pairs from M form medium-gadgets, and many of the large pairs from L form
large-gadgets in the resulting graph.
Fix p = min{ε, 2−k}. We now delete vertices from G independently with
probability p. Let H be the resulting graph. We shall show that with probability
Ω(1), the graph H is splittable and contains at least (1− 2ε)n vertices; this
clearly implies the result we are trying to prove.
Note that for a graph to be splittable, it must necessarily contain an even
number of vertices. With this in mind, let E be the event that an even number
of vertices have been deleted, in other words, E is the event that |V (H)| is even.
By Proposition 2.7, we see that P(E) ≥ 1/2. We now analyse what happens to
the degree differences of the pairs in S, M and L in the graph H.
One-gadgets. We first show that many of the pairs in S form one-gadgets
in H.
Lemma 4.1. For any pair (x, y) ∈ S,
P((x, y) is a one-gadget in H |E) ≥ f(ε) > 0.
The crucial fact about Lemma 4.1 is that the lower bound on the probability
is independent of C2.
129
Proof of Lemma 4.1. Let A = Γ(x)\(Γ(y)∪{y}) and B = Γ(y)\(Γ(x)∪
{x}). Thus, δ(x, y) = ||A| − |B|| and ∆(x, y) = |A| + |B|. Note that since x
and y disagree on at least one vertex of V \ L, it cannot be the case that both
A and B are empty. Suppose without loss of generality that |A| ≥ |B| and
that in particular, A 6= ∅.
Let E1 be the event that both x and y are not deleted, E2 the event that
no vertices are deleted from B, E3 the event that exactly |δ(x, y)− 1| vertices
are deleted from A, and E4 the event that the number of vertices deleted from
V \ (A ∪B ∪ {x, y}) has the same parity as |δ(x, y)− 1|. It is obvious that the
family {E1, E2, E3, E4} is independent since these events correspond to disjoint
sets of vertices, and it is easy to check that
P((x, y) is a 1-gadget in H |E) ≥ P({(x, y) is a 1-gadget in H} ∩ E)
≥
4∏
i=1
P(Ei).
To complete our proof of the claim, we shall bound the factors on the right
one by one. Clearly, P(E1) ≥ (1− ε)2.
We trivially have |A|, |B| ≤ ∆(x, y) < 2k+1. Furthermore |A|, |B| ≥ 2k−1 −
C1/2, since 0 ≤ δ(x, y) ≤ C1. Also, we know that ε2−k ≤ p ≤ 2−k. To bound
P(E2), first note that p|B| ≤ 2. Now, P(E2) = P(Bin(|B|, p) = 0) and so, by
Proposition 2.5, P(E2) ≥ exp (−4).
We now bound P(E3). Clearly, p|A| ≤ 2. If 2k ≥ 2C1, then |A| ≥ 2k−2 and
so p|A| ≥ ε/4. If 2k ≤ 2C1, then p ≥ ε2−k ≥ ε/2C1 and so p|A| ≥ ε/2C1 since
|A| ≥ 1. Consequently,
min{ε/4, ε/2C1} ≤ p|A| ≤ 2.
Now, P(E3) = P(Bin(|A|, p) = |δ(x, y) − 1|). Using the above estimates for
p|A| and the fact that 0 ≤ δ(x, y) ≤ C1 in Proposition 2.5, we see that
P(E3) = Ωε,C1(1).
130
Finally, since ∆(x, y) ≤ 2n/3, it follows that |V \ (A∪B)| ≥ n/3 and hence
by Proposition 2.7, P(E4) ≥ 1/6 for sufficiently large n. The claim follows.
From Lemma 4.1 and Proposition 2.2 we see that, conditional on E, the
number of one-gadgets in H from S is Ω(n/ log n) with probability at least
f(ε)/2; furthermore, and crucially, we note that this lower bound on the
probability is independent of the choice of C2.
Medium-gadgets. We next shift our attention to the pairs in M.
Lemma 4.2. For any pair (x, y) ∈M,
P(1 ≤ δ(x, y,H) ≤ n2/3 |x, y ∈ V (H)) = 1− oC2→∞(1)− o(1).
Proof. Let N1 = |Γ(x) \ (Γ(y) ∪ {y})| and let N2 = |Γ(y) \ (Γ(x) ∪ {x})|
and suppose without loss of generality that N1 ≥ N2. Note that δ(x, y) =
|N1 − N2| ≤ C1. Let X1 and X2 be independent random variables with
distributions Bin(N1, 1 − p) and Bin(N2, 1 − p) respectively. Observe that
δ(x, y,H) has the same distribution as |X1 −X2|.
We condition on x, y ∈ V (H). Let E1 be the event that δ(x, y,H) = 0.
Clearly, P(E1) = P(X1 = X2). Let E2 denote the event that δ(x, y,H) ≥ n2/3.
It is enough to show that P(E1 ∪ E2) = oC2→∞(1) + o(1).
For any fixed values of p and N2, it is not hard to check that P(X1 = X2)
attains its maximum when N1 = N2; indeed, to see this, note that P(X1 =
X2) =
∑N2
i=0 P(X1 = i)P(X2 = i) and the required conclusion follows from
Cauchy–Schwarz inequality. Thus P(E1) is bounded above by the probability
of two independent random variables with the distribution Bin(N2, 1− p), or
equivalently Bin(N2, p), being equal. Now, N2 ≥ 2k+C2−1 −C1/2 and p ≥ ε2−k.
Recall that C1 = 4/ε; therefore, pN2 ≥ ε2C2−1 − 2−k+1 which, since k ≥ 0,
means that pN2 ≥ ε2C2−1 − 2. As ε is fixed, we note that pN2 can be made
arbitrarily large by choosing C2 large enough. Since p ≤ 1/2, by Proposition 2.8,
we see that P(E1) = oC2→∞(1).
131
Clearly P(E2) = P(|X1−X2| ≥ n2/3). Applying Proposition 2.10 to X1 and
X2, we conclude that P(E2) = O(exp(−n1/3/5)).
Let M′ be the collection of those pairs (x, y) ∈M such that both x and y
survive in H. Since the family of events {x, y ∈ V (H)} is a family of mutually
independent events for different pairs (x, y) ∈M and since P(x, y ∈ V (H)) ≥
(1 − ε)2, it follows from Proposition 2.6 that P(|M′| < (1 − ε)2|M|/2) =
exp(−Ω(n)).
From Lemma 4.2, it follows that for any pair (x, y) ∈M,
P
(
1 ≤ δ(x, y,H) ≤ n2/3
∣∣∣ (x, y) ∈M′) = 1− oC2→∞(1)− o(1).
Thus, by Markov’s inequality, the number of medium-gadgets in H fromM′ is at
least |M′|/2 with probability 1−oC2→∞(1)−o(1). Thus, the number of medium-
gadgets in H is at least (1− ε)2|M|/4 with probability 1− oC2→∞(1)− o(1).
Thus, conditional on the event E, the number of medium-gadgets in H from
M is Ω(n) with probability 1− oC2→∞(1)− o(1).
Large-gadgets. We finally consider the pairs of vertices in L. Recall
that every pair (x, y) ∈ L is such that δ(x, y) ∈ [n1/3, βn] where β is a (small)
constant whose value we have yet to fix. (Indeed, the value of β has so far
played no role in our calculations.)
Lemma 4.3. For any pair (x, y) ∈ L,
P(n1/9 ≤ δ(x, y,H) ≤ 2βn |x, y ∈ V (H)) = 1− o(1).
Proof. We condition on x, y ∈ V (H). Let E1 denote the event that
δ(x, y,H) < n1/9. Since δ(x, y) ≥ n1/3, it follows immediately from Proposi-
tion 2.9 that P(E1) = o(1).
Let E2 be the event that δ(x, y,H) > 2βn. Let A = Γ(x) \ (Γ(y)∪{y}) and
B = Γ(y) \ (Γ(x) ∪ {x}), and let X1 and X2 be random variables that denote
the the number of vertices from A and B respectively which survive in H.
132
Clearly, the distributions of X1 and X2 are Bin(|A|, 1− p) and Bin(|B|, 1− p)
respectively.
If E2 were to occur, i.e., it were the case that |X1 − X2| > 2βn, then
this would imply that either |X1 − (1− p)|A|| ≥ βn/2 or |X2 − (1− p)|B|| ≥
βn/2, since (1 − p)||A| − |B|| ≤ δ(x, y) ≤ βn. It follows that P(E2) = o(1)
since the probability of either of the above two possibilities is exp (−Ω(n)) by
Proposition 2.6.
Arguing as in the case of medium-gadgets, we see from Lemma 4.3 that
conditional on the event E, the number of large-gadgets in H from L is Ω(n)
with probability 1− o(1).
Constructing a splitting. We now have a reasonably clear picture of
what the degree differences in H of the pairs of vertices in S, M and L look
like. In summary, conditional on E, we have demonstrated that in H, we can
find
(1) a collection SH of Ω(n/ log n) one-gadgets with probability f(ε)/2,
(2) a collection MH of Ω(n) medium-gadgets with probability 1− o(1)−
oC2→∞(1), and
(3) a collection LH of Ω(n) large-gadgets with probability 1− o(1)
such that the collections SH ,MH and LH are disjoint.
Thus by choosing C2 to be a sufficiently large constant depending on ε, by
the union bound, we find all of the above with probability Ω(1) conditional
on E, provided n is sufficiently large. Also, the expected number of vertices
deleted is at most εn and so by Proposition 2.6, the probability that we have
deleted more than 2εn vertices is exp (−Ω(n)).
Consequently, we see that H, with probability Ω(1), has the aforementioned
collections of gadgets, and furthermore, also has an even number of vertices and
at least (1− 2ε)n vertices. We are done if we can guarantee that 2βn ≤ |MH |;
this is possible if we choose β = β(ε) to be a suitably small constant because
|MH | = Ω(n).
133
We now consider the case where one of the sets Pi contains many pairs.
Case 1B: One of the sets P0,P1, . . . ,Plogn−1 contains c3n pairs. This
case is easier to deal with than the previous one We shall argue exactly as
before; however we shall have no need of medium-gadgets and it will suffice to
consider one-gadgets and large-gadgets alone.
Let k be any index such that |Pk| ≥ c3n (while we chose k to be minimal
previously, any index k such that |Pk| ≥ c3n will do in this case). As before, we
set p = min{ε, 2−k} and S = Pk. We now delete vertices from G independently
with probability p. Let H be the resulting graph; as before, we condition
on deleting an even number of vertices. We claim that H is splittable with
probability Ω(1).
It is not hard to check that Lemma 4.1 and Lemma 4.3 hold in this case as
well. We conclude that we can delete an even number of vertices from G to
obtain a graph H with |V (H)| ≥ (1− 2ε)n in such a way that in H, we can
find
(1) a collection SH of Ω(n) one-gadgets, and
(2) a collection LH of Ω(n) large-gadgets
such that SH and LH are disjoint. As before, it follows from Lemma 3.1 that
H is splittable when n is sufficiently large provided 2βn ≤ |SH |; this is possible
if we choose β = β(ε) to be a suitably small constant because |SH | = Ω(n).
Thus, for sufficiently small β (chosen so as to satisfy the conditions from
both Case 1A and 1B), we see that we are done if G contains many disjoint
large pairs. Note that we have now fixed the value of β. We now deal with the
case G does not contain many disjoint large pairs.
Case 2: G does not contain c1n disjoint large pairs. In this case,
we shall show that G has an induced subgraph H of even order on at least
(1− 2ε)n vertices such that V (H) may be partitioned into
(1) a collection SH of [1, 1]-gadgets of size Ω(n/ log n), and
(2) a collection MH of [0, n2/3]-gadgets.
134
In the rest of the argument in Case 2, we shall, as before, call [1, 1]-gadgets
one-gadgets and we call [0, n2/3]-gadgets (as opposed to [1, n2/3]-gadgets as we
did earlier) medium-gadgets.
It is easily seen from Lemma 3.1 that any graph H as above is splittable
if n is sufficiently large. We construct our splitting by starting with the pairs
in MH - we can use these pairs to construct a partition such that sums of the
degrees of the vertices of the two halves of the partition differ by at most n2/3.
We then use the the pairs in SH to reduce the difference to at most one; we are
done by parity considerations.
We now show how to find such a subgraph H. We start by describing how
to find pairs of vertices which will be the candidates for the medium-gadgets
we hope to find in H.
Let L be a maximal collection of large pairs in G. Note that since L is
maximal, we have either δ(x, y) < n1/3 or δ(x, y) > βn for any two vertices
x, y ∈ V \ L. As βn > 2n1/3 for all sufficiently large n, there is a partition
V \L = K1 ∪K2 ∪ · · · ∪Km into ‘clumps’ Ki with m ≤ 1/β in such a way that
δ(x, y) < n1/3 for any x, y ∈ Ki and δ(x, y) > βn if x ∈ Ki and y ∈ Kj with
i 6= j.
We ignore the way in which vertices are originally paired in L and focus on
the ground set L. By Proposition 2.3, we can find from L, at least |L|/2− n1/2
disjoint pairs (x, y) such that δ(x, y) ≤ n1/2; call this collection of pairs Q.
Let F be the graph obtained from G as follows. Delete every vertex of
L \Q. Delete one vertex from every clump K which contains an odd number
of vertices. Having done this, delete a clump K (i.e., delete all the vertices of
K) if |K| ≤ n1/2.
Note that the vertex set of F consists of the surviving clumps, each of
which has even size and cardinality at least n1/2, and the (possibly empty) set
of pairs Q. Since we had at most 1/β clumps initially, we have deleted O(n1/2)
vertices in total from G to obtain F . Hence, for any two vertices x, y ∈ V (F ),
135
K1 K2 K3 Km L
Figure 1. The graph F with small clumps removed and the
vertices in L re-paired.
|δ(x, y, F )− δ(x, y,G)| = O(n1/2). Hence, if either x and y both belong to the
same (surviving) clump or if the pair (x, y) is in Q, then δ(x, y, F ) = O(n1/2).
Let us say that two vertices x, y ∈ V (F ) are proximate if either both x and
y belong to the same clump in F or if (x, y) ∈ Q; these proximate pairs of
vertices will be our candidates for medium-gadgets in H.
We now show how to find pairs of vertices which will be the candidates for
the one-gadgets we hope to find in H. We shall henceforth work with F as
opposed to G. We shall write V for V (F ) and all degrees and degree differences,
unless specified otherwise, will be with respect to F .
Since |L| ≤ c1n = εn/2 and since we have only deleted O(n1/2) vertices so
far, note that |V \Q| ≥ (1− 3ε/2)n for n sufficiently large.
If we find at least (1/2 − ε)n disjoint clone pairs (x, y) in F [V \ Q], this
means that G trivially contains a large splittable induced subgraph we are
done. So we may assume that we can find a set V ′ ⊂ V \ Q of vertices of F
with |V ′| ≥ (2ε− 3ε/2)n = εn/2 such that any two vertices of V ′ disagree on
some vertex in V \Q.
We claim that if C3 is sufficiently large (as a function of β), then we can
find from any subset of C3 vertices of V
′, two vertices x and y such that for
each clump K, the number of vertices of K on which x and y disagree is at
most 2|K|/3. To see this, suppose that we have found C3 vertices such that
any two of them x and y disagree on more than two thirds of some clump Kx,y.
Applying Ramsey’s theorem (with 1/β colours) to the complete graph on these
136
C3 vertices where the edge between x and y is labelled by the clump Kx,y, we
see that we can find a monochromatic triangle provided C3 is large enough.
But by Proposition 2.4, out of any three vertices, at least two disagree on at
most two thirds of the vertices of K. We have a contradiction.
Choose C3 as described above and set C4 = 4C3/ε and c4 = β/2C4. By
Proposition 2.3, we can find from V ′, at least n/C4 disjoint groups of size C3
such that that δ(x, y) ≤ C4 for any two vertices x and y in the same group.
From each of these n/C4 groups of size C3, choose a pair of vertices (x, y)
such that x and y disagree on at most two thirds of every clump. Choose a
clump K∗ such that at least a β fraction of these pairs (x, y) are such that x
and y disagree on at least one vertex in K∗; this is possible because any two
vertices of V ′ disagree on V (F )\Q and consequently, on at least one clump and
furthermore, there are at most 1/β clumps. Let P be this collection of pairs
which all disagree on at least one vertex in K∗; clearly |P| ≥ βn/C4 = 2c4n.
We shall proceed as in Case 1 by pigeonholing the pairs in P into different
boxes based on the size of their difference neighbourhoods, but with one
important difference. Note that while any two vertices in the same clump have
a small (O(n1/2)) degree difference, we can only guarantee that two vertices of
Q have small (O(n1/2)) degree difference if the pair belongs to Q. Consequently,
when we later delete vertices at random, we shall either delete both vertices
of a pair in Q or retain both; hence we shall treat a pair of vertices in Q as
a single vertex when it comes to pigeonholing the pairs in P. This is made
precise below.
Let FQ be the multigraph without loops obtained from F by contracting
every pair (x, y) in Q (we ignore the loops that might arise). Note that there
are at most two parallel edges between any two vertices of FQ. In FQ, we say
that two vertices x and y disagree on a vertex v 6= x, y if the number of edges
between v and x is not equal to the number of edges between v and y. For
0 ≤ i ≤ log n− 1, let Pi be the collection of those pairs (x, y) in P such that
137
∆(x, y, FQ) ∈ [2i, 2i+1) where ∆(x, y, FQ) is the number of vertices of FQ on
which x and y disagree.
As before, let k be any index such that |Pk| ≥ 2c4n/ log n; take S = Pk and
set p = min{ε, 2−k}.
In summary, S consists of pairs (x, y) such that
(1) x and y disagree on at most two thirds of every clump,
(2) x and y disagree on at least one vertex of K∗,
(3) δ(x, y) ≤ C4, and
(4) ∆(x, y, FQ) ∈ [2k, 2k+1).
Furthermore, since δ(x, y) ≤ C4 = o(n1/2) for any (x, y) ∈ S, both members of
any pair in S must belong to the same clump.
Consider the partition S = So ∪ Se where So is the set of those pairs
(x, y) ∈ S such that δ(x, y) is odd. Recall that |S| ≥ 2c4n/ log n and so one of
So or Se contains more than c4n/ log n pairs. At this point, we need slightly
different arguments depending on whether we have more pairs with odd degree
difference or even degree difference in S.
Case 2A: S contains many odd pairs. We first consider the case where
|So| ≥ c4n/ log n. We shall delete vertices from F as follows. We pick vertices
of FQ independently with probability p = min{ε, 2−k}. For every vertex of FQ
that we pick, we delete (as appropriate) either the corresponding vertex or
both vertices of the corresponding pair of vertices from Q in FQ. Let H be the
resulting graph. Our aim is to show that H is splittable with probability Ω(1).
Earlier, we conditioned on deleting an even number of vertices from G. In
this case, we need a little more. Let E∗ be the event that an even number
of vertices were deleted from each clump. By Proposition 2.7, we see that
P(E∗) ≥ (1/2)1/β. Note that a consequence of E∗ is that |V (H)| is even.
One-gadgets. First, we shall show that many of the pairs in So become
one-gadgets in H.
138
Lemma 4.4. For any pair (x, y) ∈ So,
P((x, y) is a one-gadget in H |E∗) = Ω(1).
Proof. In FQ, let A be the set of those vertices v 6= x, y such that number
of edges between v and x is more than the number of edges between v and y
and let B be defined analogously by interchanging x and y. Let A = A1 ∪ A2
where A1 and A2 are respectively those vertices v in A such that the number
of edges between v and x is one, respectively two, more than the number of
edges from v to y; define B1 and B2 analogously.
The proof follows that of Lemma 4.1. Clearly,
2k ≤ |A1|+ |A2|+ |B1|+ |B2| < 2k+1.
Furthermore, δ(x, y) = ||A1|+ 2|A2| − |B1| − 2|B2|| and so,
−C4 ≤ |A1|+ 2|A2| − |B1| − 2|B2| ≤ C4.
Using the above two inequalities, it is not hard to check that
max{|A1|, |A2|},max{|B1|, |B2|} ≥ 2k−3 − C4/4.
Since δ(x, y) is odd, suppose without loss of generality that deg(x) > deg(y).
Let E1 be the event that both x and y are not picked to be deleted, E2 the event
that no vertices are picked from B, E3 the event that X1 + 2X2 = δ(x, y)− 1
where X1 and X2 are the number of vertices picked from A1 and A2 respectively,
and E4 the event that the number of vertices picked from K \ (A ∪B ∪ {x, y})
has the same parity as the number of vertices picked from K ∩ (A∪B ∪ {x, y})
for every clump K. The collection of events {E1, E2, E3} is clearly independent,
and it is easy to check that
P((x, y) is a 1-gadget in H |E∗) ≥ P({(x, y) is a 1-gadget in H} ∩ E∗)
≥ P(E1 ∩ E2 ∩ E3 ∩ E4)
= P(E1)P(E2)P(E3)P(E4 |E1, E2, E3).
139
Clearly, P(E1) ≥ (1 − ε)2. As in Lemma 4.1, note that p|B| ≤ 2 and so, by
Proposition 2.5, P(E2) ≥ exp (−4).
We now bound P(E3). First suppose that 2k−3 − C4/4 > C4. Recall that
δ(x, y) is odd. If |A2| ≥ |A1|, we consider the event that (δ(x, y)− 1)/2 vertices
are picked from A2 and no vertices are picked from A1 in FQ; as in Lemma 4.1,
we see that p|A2| = Θ(1) and so this event occurs with probability Ω(1). Hence
E3 occurs with probability Ω(1). If |A1| > |A2|, we consider the event that
δ(x, y)− 1 vertices are picked from |A1| and no vertices are picked from A2 and
note that this event occurs with probability Ω(1) and hence E3 occurs with
probability Ω(1).
If, on the other hand, 2k−3 − C4/4 ≤ C4, then clearly k = Θ(1) and
hence p, |A1|, |A2| are all Θ(1). In this case, we consider the event that t =
min{(δ(x, y) − 1)/2, |A2|} vertices are picked from A2 and δ(x, y) − 1 − 2t
vertices are picked from A1. Now, |A1| + 2|A2| ≥ δ(x, y) since we assumed
that deg(x) > deg(y) and so |A1| ≥ δ(x, y) − 1 − 2t. Also, as noted above,
p, |A1|, |A2| are all Θ(1). So this event occurs with probability Ω(1). Hence the
event E3 occurs with probability Ω(1).
Since x and y disagree on at most two thirds of every clump and since every
clump has size at least n1/2, it follows from Proposition 2.7 that for sufficiently
large n, P(E4 |E1, E2, E3) ≥ (1/6)1/β.
Let SH be the set of pairs from So that form one-gadgets in H. From
Lemma 4.4 and Proposition 2.2, we see that conditional on E∗, |SH | ≥
E[|SH |]/2 = Ω(n/ log n) with probability Ω(1).
Medium-gadgets. We now show that the degree difference of any pair of
vertices which are proximate in F cannot become too large in H.
Lemma 4.5. Conditional on E∗ and |SH | ≥ E[|SH |]/2, the probability that
there exist x, y ∈ V (H) which are proximate in F and satisfy δ(x, y,H) > n2/3
is o(1).
140
Proof. Recall that for any two vertices x and y which are proximate in F ,
δ(x, y) = O(n1/2). For such a pair of vertices x and y, note by Proposition 2.10
that
P(δ(x, y,H) > n2/3 |x, y ∈ V (H)) = O(exp(−n1/3/5)).
Consequently, since we have conditioned on an event with probability Ω(1), the
probability that there exist some vertices x, y ∈ V (H) such that x and y are
proximate and δ(x, y,H) > n2/3 is O(n2 exp(−n1/3/5)) = o(1).
Constructing a splitting. We now describe how to construct a splitting
of H. Let QH be the set of pairs from Q that survive in H. For a clump K
in F , let KH denote the set (K \ SH) ∩ V (H). Clearly V (H) is the disjoint
union of SH , QH and the clumps KH . Note that conditional on E
∗, the size
of KH is even for every clump K since both members of any pair in SH must
necessarily belong to the same clump. Since each KH has even cardinality, we
may group the vertices of each KH into pairs. Pair up the vertices in each
KH arbitrarily; let MH be the collection consisting of these pairs and the
pairs in QH . Clearly, every pair of vertices in MH are proximate in F and
by Lemma 4.5, the probability that there exists some pair (x, y) ∈MH with
δ(x, y,H) > n2/3 is o(1).
The expected number of vertices deleted from F is at most εn and the
number of vertices deleted from G to obtain F is O(n1/2). Hence, by Proposi-
tion 2.6, the probability that we have deleted more than 2εn vertices from G is
exp (−Ω(n)).
We conclude that there exists an induced subgraph H of G such that
|V (H)| ≥ (1−2ε)n, and with the further property that V (H) may be partitioned
into
(1) a collection SH of one-gadgets of size Ω(n/ log n), and
(2) a collection MH of medium-gadgets.
It follows from Lemma 3.1 that H is splittable and we are done.
141
Case 2B: S contains many even pairs. Now we consider the case where
|Se| ≥ c4n/ log n.
Note that since we intend to delete either both vertices of a pair in Q or
neither, it might be the case that it is impossible to make the parity of the
degree difference of a pair in Se odd in H. Consequently, in this case, we
will need to work with [2, 2]-gadgets, or two-gadgets for short, in addition to
one-gadgets. With the exception of this slight change of tack to account for
parity considerations, the argument is quite similar to the one in the previous
case and proceeds as follows.
Let c5 be a (small) constant depending on ε; the value of c5 will be chosen
later, following the statement of Lemma 4.6.
Recall that every pair of vertices in Se disagree on some vertex in the clump
K∗. Suppose there exists a vertex v ∈ K∗ such that c5n/ log n pairs from Se all
disagree on v. In this case, we may complete the proof as follows. Let Sv ⊂ Se
be the collection of pairs in Se that disagree on v. We shall delete vertices
from F as follows. We first delete v and then delete one other vertex uniformly
at random from K∗. Following this, we proceed as before by picking vertices
of FQ independently with probability p and then deleting the corresponding
vertices or pairs of vertices from Q in F . Let H be the resulting graph. Note
that when we delete v, the degree difference of every pair in Sv changes parity
and becomes odd. When we then delete another vertex uniformly at random
from K∗, the parity of the degree difference of a pair in Sv is unaltered with
probability at least 1/3 since every pair in S disagree on at most two thirds
of any clump. Arguing as in Lemma 4.4, for any pair in Sv, we see that the
probability that this pair forms a one-gadget in H, conditional on deleting
an even number of vertices from every clump, is Ω(1) (albeit with a smaller
constant than in Case 2A). Since |Sv| ≥ c5n/ log n, we can conclude the proof
exactly as in the case where S contains many odd pairs.
Hence we may assume that for every vertex v ∈ K∗, the number of pairs
in Se that disagree on v is at most c5n/ log n. We delete vertices from F as
142
before by picking vertices of FQ independently with probability p and then
deleting the corresponding vertices or pairs of vertices from Q in G. Let H be
the resulting graph.
As before, let E∗ be the event that an even number of vertices were deleted
from each clump. The proof of Lemma 4.4, with minor modifications for the
change in parity, yields a proof of the following lemma.
Lemma 4.6. For any (x, y) ∈ Se, P((x, y) is a two-gadget in H |E∗) = Ω(1).
Let SH be the collection of pairs from Se that form two-gadgets in H.
From Lemma 4.6 and Proposition 2.2, we see that there exists a small positive
constant c6 such that, conditional on E
∗, |SH | ≥ c6n/ log n with probability
Ω(1). Recall that we still have not fixed the value of c5; let us now fix c5 = c6/4.
Constructing a splitting. As before, let QH be the collection of pairs
from Q that survive in H and for each clump K in F , let us write KH for the
set (K \ SH) ∩ V (H).
We have shown that with probability Ω(1), the graph H is such that
(1) |KH | is even for every clump K, and
(2) |SH | ≥ c6n/ log n.
Consider any pair (x, y) ∈ SH and note that in F , x and y disagree on at
most two thirds of any clump; in particular, x and y agree on at least a third
of K∗. Consequently, the probability that x and y disagree on every vertex of
K∗H is exp (−Ω(n1/2)). Hence, with probability 1− o(1), for every (x, y) ∈ SH ,
there exists some vertex in K∗H on which x and y agree.
Next, it follows from Lemma 4.5 that with probability 1− o(1), any two
vertices x, y ∈ V (H) which are proximate satisfy δ(x, y,H) ≤ n2/3. Finally, the
probability that we have deleted more that 2εn − 2 vertices of total from G
is, by Proposition 2.6, exp (−Ω(n)). It follows that with probability Ω(1), the
143
graph H, in addition to possessing the aforementioned properties, also has the
following properties.
(3) For every (x, y) ∈ SH , there exists some vertex in K∗H on which x and
y agree.
(4) For any x, y ∈ V (H) such that x and y are proximate in F , δ(x, y,H) ≤
n2/3.
(5) |V (H)| ≥ (1− 2ε)n+ 2.
With a view to making the graph H splittable, we alter H as follows. Fix
a pair (x∗, y∗) ∈ SH and a vertex v ∈ K∗ on which x∗ and y∗ disagree. We
know that there is a vertex u ∈ K∗H on which x∗ and y∗ agree. Delete u from
H. If v ∈ V (H), delete v from H and if v /∈ V (H), add v back. After these
alterations, note that H still has an even number of vertices. Note also that
now, |V (H)| ≥ (1− 2ε)n and δ(x∗, y∗, H) ∈ {1, 3}.
Before we altered H, at most c5n/ log n pairs in SH disagreed on any vertex
in K∗; since c6 = 4c5, the alterations above change the degree differences of
at most 2c5n/ log n = c6n/2 log n pairs in SH . Hence, H contains a collection
SH of least c6n/2 log n− 1 pairs of vertices (x, y) such that δ(x, y,H) = 2 and
a pair (x∗, y∗) such that δ(x∗, y∗, H) ∈ {1, 3}. Furthermore, all the vertices of
V (H) \ (SH ∪ {x∗, y∗}) may be grouped into pairs (x, y) such that δ(x, y,H) ≤
n2/3 + 2; let MH denote this collection of pairs.
It is now easy to check that H is splittable using the argument used to prove
Lemma 3.1. Indeed, we can use pairs inMH to construct a partition such that
sums of the degrees of the vertices of the two halves of the partition differ by
at most n2/3 + 2. For n sufficiently large, we can then reduce the difference
to at most two by using all but one of the pairs in SH . Finally, using the one
remaining pair in SH and the pair (x∗, y∗), we can reduce the difference to at
most one; we are done constructing a splitting of H by parity considerations.
This completes the proof of Theorem 1.1.
144
5. Concluding remarks
We have shown that f(n) ≥ n/2 − o(n). In fact, it should be possible
to read out a bound of f(n) ≥ n/2 − n/(log log n)c from our proof for some
absolute constant c > 0; we chose not to include a proof of this fact to keep the
presentation simple, and because we do not believe that such a bound is close
to the truth. While we have managed to pin down f up to its first order term,
there is still a large gap between the upper and lower bounds for n/2− f(n).
Problem 5.1. What is the asymptotic behaviour of n/2− f(n)?
We know that n/2 − f(n) = Ω(log log n) and n/2 − f(n) = o(n); we
suspect that the truth lies closer to the lower bound and that in particular,
n/2 − f(n) = o(nε) for every ε > 0. Indeed, it is not inconceivable that
n/2− f(n) = Θ(log n).
It is natural to generalise the problem to the case where we have more
than one type of edge, or ask for more than two disjoint subgraphs. For any
r, l ∈ N, given an edge colouring ∆ of the complete graph on n vertices with r
colours, let g(∆) be the largest integer k for which we can find l disjoint subsets
V1, V2, . . . , Vl of [n], each of cardinality k, such that for each 1 ≤ i ≤ r, the
number of edges induced by Vj of colour i is the same for every 1 ≤ j ≤ l. Let
g(n, r, l) be the minimum value of g(∆) taken over all edge colourings of the
complete graph on n vertices. In particular, note that g(n, 2, 2) = f(n). We
conjecture that g(n, r, 2) = n/2− o(n) and more generally, ask the following
question.
Problem 5.2. For r, l ∈ N, what is the asymptotic behaviour of g(n, r, l)?
Finally, we mention a question about digraphs that we find particularly
appealing. Given a digraph D on n vertices, let h(D) denote the largest integer
k for which there exist disjoint subsets A,B ⊂ V such that |A| = |B| = k and
the number of directed edges from A to B is equal to the number of directed
145
edges from B to A. Let h(n) be the minimum value of h(D) taken over all
digraphs on n vertices.
Problem 5.3. Determine h(n).
146
CHAPTER 9
Catching a fast robber on the grid
Joint work with Paul Balister, Scott Binski and Be´la Bolloba´s
1. Introduction
The game of Cops and Robbers, introduced almost thirty years ago in-
dependently by Nowakowski and Winkler [93] and Quilliot [95], is a perfect
information pursuit-evasion game played on an undirected graph G as follows.
There are two players, a set of cops and one robber. The game begins with
the cops being placed onto vertices of their choice in G and then the robber,
being fully aware of the placement of the cops, positions himself at a vertex
of his choosing. Afterward, they move alternately, first the cops and then the
robber along the edges of the graph G. In the cops’ turn, each cop may move
to an adjacent vertex, or remain where he is, and similarly for the robber; also,
multiple cops are allowed to occupy the same vertex. The cops win if at some
time there is a cop at the same vertex as the robber; otherwise, the robber wins.
The minimum number of cops for which the cops have a winning strategy, no
matter how the robber plays, is called the cop number of G.
Perhaps the most well known problem concerning the game of cops and
robbers is Meyniel’s conjecture which asserts that O(
√
n) cops are sufficient
to catch the robber on any n-vertex graph. While Meyniel’s conjecture has
attracted a great deal of attention (see [9] and the references therein), progress
towards the conjecture in its full generality has been rather slow.
In this chapter, we shall be concerned with a variant of the question where
the robber is allowed to move faster than the cops. Let us suppose that the cops
147
move normally as before while the robber is allowed to move at speed R ∈ N;
in other words, the robber may, on his turn, take any walk of length at most R
from his current position that does not pass through a vertex occupied by a cop.
The definition of the cop number in this setting is analogous. This variant was
originally considered by Fomin, Golovach, Kratochv´ıl, Nisse and Suchan [54]
and following them, Frieze, Krivelevich and Loh [60], Mehrabian [90], and Alon
and Mehrabian [4] have obtained results about how large the cop number of an
n-vertex graph can be when the robber has a fixed speed R > 1.
It is natural to ask how the cop number of a given graph changes, if at
all, when the speed of the robber increases from 1 to some R > 1. The most
natural example of a graph where this question is interesting is the n× n grid
of squares where two squares of the grid are adjacent if and only if they share
an edge. Let us write fR(n) for the minimum number of cops needed to catch
a robber of speed R on an n × n grid. Maamoun and Meyniel [88] showed,
amongst other things, that f1(n) = 2 for all n ≥ 2. However, the flavour of the
problem changes completely as soon as the robber is allowed to move faster
than the cops. Nisse and Suchan [92] showed that f2(n) = Ω(
√
log n). Our aim
in this chapter is to prove the following extension.
Theorem 1.1. There exists an R ∈ N and a cR > 0 such that for all
sufficiently large n ∈ N,
fR(n) ≥ exp
(
cR log n
log log n
)
.
To keep the presentation simple, we shall make no attempt to optimise the
speed of the robber; we prove Theorem 1.1 with R = 1025.
Note that fR(n) ≤ n for every R ∈ N since n cops can catch a robber of
any speed on the n× n grid by lining up on the bottom edge of the grid and
then marching upwards together. We suspect that this trivial upper bound is
closer to the truth than Theorem 1.1; we believe that for all sufficiently large
R ∈ N, fR(n) = n1−o(1) as n→∞.
148
We give a sketch of the proof of Theorem 1.1 and then the proof proper in
Section 2. We conclude with some discussion in Section 3.
2. Proof of the main result
Our proof of Theorem 1.1 is inspired by the strategy used by Bolloba´s
and Leader [29] and Kutz [81] to resolve Conway’s angel problem in three
dimensions.
We fix a large positive integer R ∈ N which will denote the speed of the
robber in what follows. We also fix two other positive integers C,N ∈ N such
that C, N and R together satisfy C ≥ 40, N > 100eC and R > 50N . We may,
for example, take C = 40, N = 1020 and R = 1025.
Define a sequence of grids as follows: let A0 be an N ×N grid and for k ≥ 1
let Ak be a (2k + 1)2 × (2k + 1)2 array of copies of Ak−1.
We shall imagine that our n× n grid is tiled with copies of A0, with these
copies of A0 themselves fitting together to form copies of A1, and so on. We
call each copy of Ak in our grid a k-cell. Our strategy for the robber will be
inductive: we shall describe how the robber may run from k-cell to adjacent
k-cell, the path of the robber within a k-cell being inductively determined, all
the while avoiding k-cells where there are too many cops.
Let us suppose that the robber is situated on the bottom edge of a ‘safe’
k-cell and wishes to get to the bottom edge of the k-cell above. Assume for
the moment that the robber’s k-cell is guaranteed to be ‘safe’ for a reasonably
large number of steps.
Here then is an outline of a strategy for the robber: he plots a straight line
from his current (k − 1)-cell to a (k − 1)-cell in the k-cell above that he wishes
to get to. He runs across each of the (k − 1)-cells on the way until he reaches
his destination; within each (k − 1)-cell, his path is determined inductively. Of
course, there is a problem with this strategy: along the way, a (k − 1)-cell that
the robber needs to run across might not be ‘safe’ when he gets to it, or worse,
149
a (k − 1)-cell might become ‘unsafe’ while the robber is running through it.
To address these issues, the robber alters his path dynamically and detours
around any (k− 1)-cell along his planned straight line path that he finds might
become ‘unsafe’ while he is running through it. Our definition of ‘safety’ will
ensure that the robber does not have to take too many detours. It will follow,
and it is here that we use the fact that a k-cell is a (2k + 1)2 × (2k + 1)2 array
of (k − 1)-cells, that the ‘average speed’ of the robber is large despite the fact
that he has to take the occasional detour (and detours within detours and so
on). This will provide us with enough elbow room to prove what we need by
induction.
We now go about making the above sketch precise. First, we define a
sequence (Lk)k≥0 of natural numbers by setting Lk =
∏k
j=0(2j + 1)
2; clearly
a k-cell is an NLk ×NLk grid of squares. Next, we define another sequence
(Tk)k≥0 of natural numbers by setting T0 = 1 and Tk = (2k + 1)2Tk−1 + CTk−1
for k ≥ 1.
An observation that we shall use repeatedly is that each k ≥ 0,
Tk = Lk
k∏
j=1
(
1 +
C
(2j + 1)2
)
< Lk exp
(
C
∞∑
j=1
1
(2j + 1)2
)
< eCLk.
We need to define some notions of ‘safety’. We say that a k-cell is safe
at some point in time if the number of cops (at that point in time) within
the k-cell is strictly less than 2k. Also, we say that a k-cell is safe for t steps
(at some point) if the set of cops at distance at most t from the k-cell has
cardinality strictly less than 2k. Note that a k-cell safe for t steps is necessarily
safe for t′ steps for every 0 ≤ t′ ≤ t as well.
Next, we say that a square is k-safe if for each 0 ≤ k′ ≤ k, the k′-cell
containing the square is safe for Tk′ steps; also, a square is completely k-safe if
it is guaranteed to be k-safe after a single cop move.
150
Figure 1. The bottom landing zone of a 1-cell; each square
here represents a 0-cell.
Notice that if a k-cell is safe, then it contains at most one unsafe (k−1)-cell.
We shall require a straightforward extension of this simple observation. Let us
say that two cells are separated if they share neither an edge nor a corner.
Proposition 2.1. Let X be a k-cell and assume that X is safe for t steps
where 2t < NLk−1. If P and Q are a separated pair of (k − 1)-cells within X,
then either P or Q is safe for t steps.
Proof. Simply notice that since P and Q are separated, the distance
between them is at least NLk−1. Consequently, the set of cops at distance at
most t from P and the set of cops at distance at most t from Q are disjoint
and the proposition follows.
To help with the induction, we shall demarcate certain regions as ‘landing
zones’. For k ≥ 1, the landing zone of a k-cell is the union of its bottom, top,
right and left landing zones; the bottom landing zone of a k-cell consists of the
3× 1 sub-grid of (k − 1)-cells at the middle of the bottom edge of the k-cell as
shown in Figure 1 and the top, right and left landing zones are analogously
defined by symmetry. Also, a square is called a k-landing square, if the square
is contained in the landing zone of each k′-cell containing it for 1 ≤ k′ ≤ k.
Our proof of Theorem 1.1 hinges on the following lemma.
151
Lemma 2.2. Let k ≥ 1 and suppose that it is the robber’s turn to move.
Suppose further that the robber is positioned on a k-safe, k-landing square inside
a k-cell X. If the k-cell Y above X is safe for 2Tk + 1 steps, then the robber has
a strategy to reach, in at most Tk steps and without getting caught, a k-landing
square in the bottom landing zone of Y which is completely k-safe on his arrival
there.
Let us point out that there is some asymmetry in how Lemma 2.2 is stated.
The lemma assumes something about the grid when the robber is about to
move, and says something about the grid after a sequence of moves ending with
the a move for the robber. However, note that a square is completely k-safe
only if it is k-safe after a single cop move; hence, if the robber moves using
the strategy given by Lemma 2.2, then no matter how the cops move on their
turn following his final move, his new location is k-safe (and the lemma may
be applied once again).
Proof of Lemma 2.2. Note that Lemma 2.2 is really a collection of four
different statements, one each for when the robber starts in the bottom, top,
right and left landing zones of his k-cell X. Indeed, Lemma 2.2 says that under
certain conditions, it is possible for the robber to safely move from the landing
zone of a k-cell to (the landing zone of) any of its four neighbouring k-cells in
Tk steps.
We prove the lemma by induction on k. The case k = 1 is easy to check.
Assume that it is the robber’s turn to move, that he is on a 1-safe square in
the landing zone of his 1-cell X, and that the 1-cell Y above him is safe for
2T1 + 1 = 19 + 2C steps. We need to show that he can move in at most T1
steps to a square in the bottom landing zone of Y which is completely 1-safe
on his arrival. The robber can in fact do this in one step as we now describe.
Since the robber’s square is 1-safe, note there are no cops in his 0-cell, say P .
Consider a pair of separated 0-cells, call them Q and Q′, in the bottom landing
zone of Y . Note that at least one of Q or Q′, say Q, must be safe for two steps
152
because if not, then since 4 < NL0 = N , it follows from Proposition 2.1 that
Y is not safe for two steps, contradicting our assumption that Y is safe for
19 + 2C steps with room to spare.
Note that a 1-cell is a 9× 9 array of 0-cells. It is easy to check that there
are N disjoint paths, each wholly contained within the union of X and Y and
of length at most 36N , from P to any 0-cell in Y . Since both X and Y are safe
when the robber is about to move, there are at most two cops in total within
X and Y . Hence, there are at least N − 2 paths between P and Q containing
no cops on them. Note that the speed of the robber R is greater than 36N ,
and hence the robber, on his turn, can follow one of these N − 2 paths from his
square in P to a square in Q. Note that Q is safe for two steps and Y is safe
for 19 + 2C ≥ T1 + 1 steps; hence, it clear that any square in Q is completely
1-safe on the robber’s arrival there.
Now assume k > 1 and that we have proved the claim for each 1 ≤ k′ < k.
We describe the robber’s strategy when he starts in the bottom landing zone
of his k-cell. The strategy for the three other landing zones are very similar
and we only highlight the very minor differences.
We shall divide the robber’s journey into two parts. We first describe how
the robber should travel from the bottom landing zone of his k-cell X to the
top landing zone of X. This journey will require at most (2k+ 1)2Tk−1 + 3Tk−1
steps. We then show that robber can dash across from the top landing zone of
X into the bottom landing zone of Y in at most 13Tk−1 steps. Hence, the total
number of steps required will be bounded above by
(2k + 1)2Tk−1 + 16Tk−1 ≤ (2k + 1)2Tk−1 + CTk−1 ≤ Tk
as required.
In what follows, when we speak of the robber arriving at a square in a
(k − 1)-cell, it is implied that the square is a (k − 1)-landing square.
153
SF
PPl Pr
Q
Q′
Figure 2. The planned path to the top landing zone and the
detouring strategy.
The robber begins by plotting a straight line path from his (k − 1)-cell, say
S, to the nearest (k − 1)-cell, say F , in the top landing zone of X as shown in
Figure 2. The robber’s square is k-safe; this means that X is safe for Tk steps
and that the robber’s square is (k − 1)-safe. If the (k − 1)-cell above him is
safe for 2Tk−1 + 1 steps, then the robber may inductively run, in at most Tk−1
steps and without getting caught, to a square in the (k − 1)-cell above him
which is completely (k − 1)-safe on his arrival there. Following the subsequent
cop turn, his square is (k − 1)-safe. The robber may repeat this process until
he gets to F , provided that every time the robber arrives at a (k − 1)-cell (and
the cops have subsequently moved), the (k − 1)-cell above is safe for 2Tk−1 + 1
steps at that point. In this case, the robber reaches the top landing zone of X
in at most (2k + 1)2Tk−1 steps, and we are done.
So we may assume that at some stage of his journey, the robber is on a
(k− 1)-safe square in a (k− 1)-cell P within X, it is his turn to move, and that
the (k − 1)-cell Q above P is not safe for 2Tk−1 + 1 steps. We claim that the
robber only has to deal with such a situation once.
Let us consider the first time such a situation arises. Clearly, the robber has
taken at most (2k+1)2Tk−1 steps from S; as X was safe for Tk = (2k+1)2Tk−1 +
CTk−1 steps to begin with, X is now safe for at least CTk−1 steps. The robber
154
FFigure 3. The final stretch.
takes a detour around Q as follows. He considers the two paths around Q to
a (k − 1)-cell Q′ located above (and separated from) Q as shown in Figure 2;
call these paths Zl and Zr. We claim that each of the (k − 1)-cells along one
of these two paths is safe for 8Tk−1 + 1 steps. Indeed, all the (k − 1)-cells on
these paths with the exception of the two initial (k − 1)-cells Pl and Pr are
separated from Q. If one of these (k − 1)-cells is not safe for 8Tk−1 + 1 steps,
then since Q is not safe for 2Tk−1 + 1 steps and
2(8Tk−1 + 1) ≤ 18Tk−1 < 18eCLk−1 < NLk−1,
if follows by Proposition 2.1 that X is not safe for 8Tk−1 + 1 ≤ 9Tk−1 steps,
contradicting the fact that X is in fact, safe for CTk−1 steps. Again, by
Proposition 2.1, one of Pl and Pr is necessarily safe for 8Tk−1 + 1 steps since Pl
and Pr are separated. So suppose that all the (k− 1)-cells along Zl are safe for
8Tk−1 + 1 steps. Then it is easy to check that the robber may inductively run
along Zl, in at most 7Tk−1 steps and without getting caught, from P to Q′ so
that he reaches a square in Q′ which is completely (k − 1)-safe on his arrival
there.
Since Q was not safe for 2Tk−1 + 1 steps when the robber was at P , we
know that there are at least 2k−1 cops at distance at most 2Tk−1 + 1 from Q; let
us mark these cops. The robber takes 7Tk−1 steps to reach Q′ from P . In those
7Tk−1 steps, the 2k−1 marked cops may move at most 7Tk−1 steps up. However,
since the distance between Q and Q′ is NLk−1 > 100eCLk−1 > 100Tk−1, it is
clear that these 2k−1 marked cops can never overtake the robber vertically, and
155
hence the robber will, after this detour, always find that when he arrives at a
(k − 1)-cell, the (k − 1)-cell above him is safe for 2Tk−1 + 1 steps.
It is therefore clear that the robber can safely reach some (k − 1)-cell F in
the top landing zone of X (though, on account of his detours, not necessarily
his initial choice) in at most (2k + 1)2Tk−1 + 3Tk−1 steps. This completes the
first leg of the robber’s journey.
Let us now pause and survey the robber’s situation after the cops have
moved. He is now on a (k− 1)-safe, (k− 1)-landing square in a (k− 1)-cell F in
the top landing zone of his k-cell X. Also, X is now safe for at least (C−3)Tk−1
steps and Y , the k-cell above X, is safe for at least Tk + (2C − 3)Tk−1 + 1 steps.
We now show that the robber can safely reach, in at most 13Tk−1 steps, a
square in the bottom landing zone of Y which is completely (k − 1)-safe when
the robber arrives there; that this square is also completely k-safe follows from
the fact that Y is safe for at least Tk + (2C− 3)Tk−1 + 1 steps before the robber
starts the second leg of his journey.
Consider the set of four paths, as shown in Figure 3, from F to the (k − 1)-
cells in the bottom landing zone of Y . We claim that it follows from the
fact that X is safe for (C − 3)Tk−1 steps, and the fact that Y is safe for
Tk + (2C − 3)Tk−1 + 1 steps, that all the (k − 1)-cells along one of these four
paths are all safe for 14Tk−1 + 1 steps. To see this, note that if a (k− 1)-cell in
X lying on one of the two paths to, say, the right of F is not safe for 14Tk−1 + 1
steps, then we know from Proposition 2.1 that all the (k − 1)-cells in X on
both paths to the left of F are safe for 14Tk−1 + 1 steps; the two paths to the
left of F are completely separated within Y and hence, all the (k − 1)-cells
on one of these two paths must be safe for 14Tk−1 + 1 steps. Since each of
these four paths is composed of at most thirteen (k − 1)-cells, it is clear that
the robber can then complete his journey by following one of these paths in at
most 13Tk−1 steps. This completes the second leg of the robber’s journey.
Clearly this also shows how the robber may proceed if he is initially located
in the top landing zone of X. A similar strategy to the what has just been
156
SF Q′
QP
Figure 4. Getting to the top landing zone from the left landing
zone.
described (see Figure 4) can be easily shown to work when the robber starts
on either the right or the left landing zone of X; the robbers path becomes
slightly longer than before if he needs to make a detour as he is ‘turning’, but
our choices of C and N are large enough to ensure that the detouring strategy
works with room to spare.
Armed with Lemma 2.2, it is a simple exercise to deduce Theorem 1.1.
Proof of Theorem 1.1. We show that if n ≥ 2NLk for some k ≥ 1,
then fR(n) ≥ 2k. It is easy to check by estimating Lk =
∏k
j=0(2j+ 1)
2 in terms
of 2k that this implies the result.
Since n ≥ 2NLk, we may fix a 2 × 2 array of k-cells in the grid. If the
number of cops on the grid is strictly less than 2k, each of these k-cells is
guaranteed to be safe forever. After the cops have placed themselves on the
grid, the robber positions himself on a k-safe, k-landing square in one of these
four k-cells; that the robber can actually find such a square is easily checked
by Proposition 2.1. The robber now wins by repeatedly using Lemma 2.2 to
run around this 2× 2 array in a clockwise loop forever.
157
3. Concluding remarks
As remarked earlier, it seems exceedingly unlikely that Theorem 1.1 is
close to the truth; it should be the case that there exists an R ∈ N for which
fR(n) = n
1−o(1) as n→∞.
Our proof of Theorem 1.1 is built on ideas used to solve Conway’s angel
problem in three dimensions. We conclude by mentioning that it is not incon-
ceivable that one can, by suitably adapting one of the solutions (see [89, 33, 61])
to the angel problem in two dimensions, prove the existence of an R ∈ N and a
cR > 0 such that fR(n) ≥ ncR for all sufficiently large n ∈ N.
158
Bibliography
1. J. Adler and U. Lev, Bootstrap Percolation: visualizations and applications,
Braz. J. Phys. 33 (2003), 641–644.
2. N. Alon, Combinatorial Nullstellensatz, Combin. Probab. Comput. 8
(1999), 7–29.
3. N. Alon and B. Bolloba´s, Graphs with a small number of distinct induced
subgraphs, Discrete Math. 75 (1989), 23–30.
4. N. Alon and A. Mehrabian, On a generalization of Meyniel’s conjecture
on the Cops and Robbers game, Electron. J. Combin. 18 (2011), Paper 19.
5. N. Alon and Joel H. Spencer, The probabilistic method, 3rd ed., Wiley-
Interscience Series in Discrete Mathematics and Optimization, John Wiley
& Sons, Inc., Hoboken, NJ, 2008.
6. H. Amini, Bootstrap percolation in living neural networks, J. Stat. Phys.
141 (2010), 459–475.
7. M. Axenovich, R. R. Martin, and T. Ueckerdt, Twins in graphs, European
J. Combin. 39 (2014), 188–197.
8. L. Babai, M. Simonovits, and J. Spencer, Extremal subgraphs of random
graphs, J. Graph Theory 14 (1990), 599–622.
9. William Baird and Anthony Bonato, Meyniel’s conjecture on the cop
number: a survey, J. Comb. 3 (2012), 225–238.
10. P. Balister, S. Binski, B. Bolloba´s, and B. P. Narayanan, Catching a fast
robber on the grid, Preprint.
11. P. Balister, B. Bolloba´s, J. Lee, and B. P. Narayanan, Line percolation,
Random Structures Algorithms, To appear.
12. P. Balister, B. Bolloba´s, M. Przykucki, and P. Smith, Subcritical neighbour-
hood family percolation models have non-trivial phase transitions, Preprint,
159
arXiv:1311.5883.
13. J. Balogh, T. Bohman, and D. Mubayi, Erdo˝s-Ko-Rado in random hyper-
graphs, Combin. Probab. Comput. 18 (2009), 629–646.
14. J. Balogh, B. Bolloba´s, H. Duminil-Copin, and R. Morris, The sharp
threshold for bootstrap percolation in all dimensions, Trans. Amer. Math.
Soc. 364 (2012), 2667–2701.
15. J. Balogh, B. Bolloba´s, and R. Morris, Bootstrap percolation in three
dimensions, Ann. Probab. 37 (2009), 1329–1380.
16. J. Balogh, B. Bolloba´s, R. Morris, and O. Riordan, Linear algebra and
bootstrap percolation, J. Combin. Theory, Ser. A 119 (2012), 1328–1335.
17. J. Balogh, B. Bolloba´s, and B. P. Narayanan, Transference for the Erdo˝s–
Ko–Rado theorem, Submitted to the Transactions of the American Mathe-
matical Society.
18. J. Balogh, S. Das, M. Delcourt, H. Liu, and M. Sharifzadeh, The typ-
ical structure of intersecting families of discrete structures, Preprint,
arXiv:1408.2559.
19. J. Balogh, R. Morris, and W. Samotij, Independent sets in hypergraphs,
Preprint, arXiv:1204.6530.
20. , Random sum-free subsets of Abelian groups, Israel J. Math., To
appear.
21. Zs. Baranyai, On the factorization of the complete uniform hypergraph,
Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdo˝s on
his 60th birthday), Colloq. Math. Soc. Ja´nos Bolyai, vol. 10, North-Holland,
Amsterdam, 1975, pp. 91–108.
22. M. Beiglbo¨ck, V. Bergelson, N. Hindman, and D. Strauss, Some new
results in multiplicative and additive Ramsey theory, Trans. Amer. Math.
Soc. 360 (2008), 819–847.
23. I. Ben-Eliezer and M. Krivelevich, Perfectly balanced partitions of smoothed
graphs, Electron. J. Combin. 16 (2009), Note 14.
160
24. L. I. Bogolyubskiy, A. S. Gusev, M. M. Pyaderkin, and A. M. Raigorodskii,
The independence numbers and the chromatic numbers of random subgraphs
of some distance graphs, Mat. Sb., To appear.
25. , The independence numbers and the chromatic numbers of random
subgraphs of some distance graphs, Doklady Math. 457 (2014), 383–387.
26. B. Bolloba´s, On generalized graphs, Acta Math. Acad. Sci. Hungar 16
(1965), 447–452.
27. , Random graphs, 2nd ed., Cambridge Studies in Advanced Mathe-
matics, vol. 73, Cambridge University Press, Cambridge, 2001.
28. B. Bolloba´s, T. Kittipassorn, B. P. Narayanan, and A. D. Scott, Disjoint
induced subgraphs of the same order and size, European J. Combin., To
appear.
29. B. Bolloba´s and I. Leader, The angel and the devil in three dimensions, J.
Combin. Theory Ser. A 113 (2006), 176–184.
30. B. Bolloba´s, B. P. Narayanan, and A. M. Raigorodskii, On the stability of
the Erdo˝s–Ko–Rado theorem, Submitted to the Journal of Combinatorial
Theory, Series A.
31. B. Bolloba´s, P. Smith, and A. Uzzell, Monotone cellular automata in a
random environment, Combin. Probab. Comput., To appear.
32. B. Bolloba´s and A. Thomason, Graphs which contain all small graphs,
European J. Combin. 2 (1981), 13–15.
33. B. H. Bowditch, The angel game in the plane, Combin. Probab. Comput.
16 (2007), 345–362.
34. G. Brightwell, K. Panagiotou, and A. Steger, Extremal subgraphs of random
graphs, Random Structures Algorithms 41 (2012), 147–178.
35. N. Bushaw, M. Collares Neto, R. Morris, and P. Smith, The sharp threshold
for maximum size sum-free subsets in even-order Abelian groups, Combin.
Probab. Comput., To appear.
36. Y. Caro and R. Yuster, Large disjoint subgraphs with the same order and
size, European J. Combin. 30 (2009), 813–821.
161
37. J. Chalupa, P. L. Leath, and G. R. Reich, Bootstrap percolation on a
Bethe lattice, J. Phys. C. 12 (1979), 31–35.
38. M. Chudnovsky and S. Safra, The Erdo˝s-Hajnal conjecture for bull-free
graphs, J. Combin. Theory Ser. B 98 (2008), 1301–1310.
39. D. Conlon, A new upper bound for diagonal Ramsey numbers, Ann. of
Math. 170 (2009), 941–960.
40. D. Conlon and T. Gowers, Combinatorial theorems in sparse random sets,
Ann. of Math., To appear.
41. B. DeMarco and J. Kahn, Mantel’s theorem for random graphs, Preprint,
arXiv:1206.1016.
42. P. H. Diananda and H. P. Yap, Maximal sum-free sets of elements of finite
groups, Proc. Japan Acad. 45 (1969), 1–5.
43. I. Dinur and E. Friedgut, Intersecting families are essentially contained in
juntas, Combin. Probab. Comput. 18 (2009), 107–122.
44. H. Duminil-Copin and A. C. D. Van Enter, Sharp metastability threshold
for an anisotropic bootstrap percolation model, Ann. Probab. 41 (2013),
1218–1242.
45. P. Erdo˝s, Some remarks on number theory, Riveon Lematematika 9 (1955),
45–48.
46. P. Erdo˝s, C. Ko, and R. Rado, Intersection theorems for systems of finite
sets, Quart. J. Math. Oxford 12 (1961), 313–320.
47. P. Erdo˝s and R. Rado, A combinatorial theorem, J. London Math. Soc.
25 (1950), 249–255.
48. P. Erdo˝s and A. Hajnal, On the number of distinct induced subgraphs of a
graph, Discrete Math. 75 (1989), 145–154.
49. , Ramsey-type theorems, Discrete Appl. Math. 25 (1989), 37–52.
50. P. Erdo˝s, J. Pach, and L. Pyber, Isomorphic subgraphs in a graph, Com-
binatorics (Eger, 1987), Colloq. Math. Soc. Ja´nos Bolyai, vol. 52, North-
Holland, Amsterdam, 1988, pp. 553–556.
162
51. P. Erdo˝s, M. Simonovits, and V. T. So´s, Anti-Ramsey theorems, Infinite
and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdo˝s on his
60th birthday), Colloq. Math. Soc. Ja´nos Bolyai, vol. 10, North-Holland,
Amsterdam, 1975, pp. 633–643.
52. M. Erickson, A conjecture concerning Ramsey’s theorem, Discrete Math.
126 (1994), 395–398.
53. A. Fey, L. Levine, and Y. Peres, Growth rates and explosions in sandpiles,
J. Stat. Phys. 138 (2010), 143–159.
54. F. V. Fomin, P. A. Golovach, J. Kratochv´ıl, N. Nisse, and K. Suchan,
Pursuing a fast robber on a graph, Theoret. Comput. Sci. 411 (2010),
1167–1181.
55. L. R. Fontes, R. H. Schonmann, and V. Sidoravicius, Stretched exponential
fixation in stochastic Ising models at zero temperature, Comm. Math. Phys.
228 (2002), 495–518.
56. K. Ford, The distribution of integers with a divisor in a given interval,
Ann. of Math. 168 (2008), 367–433.
57. J. Fox and B. Sudakov, Induced Ramsey-type theorems, Adv. Math. 219
(2008), 1771–1800.
58. E. Friedgut, On the measure of intersecting families, uniqueness and
stability, Combinatorica 28 (2008), 503–528.
59. E. Friedgut, V. Ro¨dl, and M. Schacht, Ramsey properties of random
discrete structures, Random Structures Algorithms 37 (2010), 407–436.
60. A. Frieze, M. Krivelevich, and P. Loh, Variations on cops and robbers, J.
Graph Theory 69 (2012), 383–402.
61. P. Gacs, The angel wins, Preprint, arXiv:0706.2817.
62. M. M. Gauy, H. Ha`n, and I. C. Oliveira, Erdo˝s-Ko-Rado for random
hypergraphs: asymptotics and stability, Preprint, arXiv:1409.3634.
63. R. L. Graham, B. L. Rothschild, and J. H. Spencer, Ramsey theory, 2nd
ed., Wiley-Interscience Series in Discrete Mathematics and Optimization,
John Wiley & Sons, Inc., New York, 1990.
163
64. M. Granovetter, Threshold models of collective behavior, American J.
Sociology 83 (1978), 1420–1443.
65. J. Gravner, C. Hoffman, J. Pfeiffer, and D. Sivakoff, Bootstrap percolation
on the hamming torus, Ann. Appl. Probab., To appear.
66. B. Green and T. Tao, The primes contain arbitrarily long arithmetic
progressions, Ann. of Math. 167 (2008), 481–547.
67. L. Guth, Unexpected applications of polynomials in combinatorics, The
Mathematics of Paul Erdo˝s, Springer New York, 2013, pp. 493–522.
68. A. J. W. Hilton and E. C. Milner, Some intersection theorems for systems
of finite sets, Quart. J. Math. Oxford 18 (1967), 369–384.
69. N. Hindman, I. Leader, and D. Strauss, Forbidden distances in the rationals
and the reals, J. London Math. Soc. 73 (2006), 273–286.
70. A. E. Holroyd, Sharp metastability threshold for two-dimensional bootstrap
percolation, Probab. Theory Related Fields 125 (2003), 195–224.
71. A. E. Holroyd, T. M. Liggett, and D. Romik, Integrals, partitions, and
cellular automata, Trans. Amer. Math. Soc. 356 (2004), 3349–3368.
72. G. Katona, A theorem of finite sets, Theory of graphs (Proc. Colloq.,
Tihany, 1966), Academic Press, New York, 1968, pp. 187–207.
73. P. Keevash, Shadows and intersections: stability and new proofs, Adv.
Math. 218 (2008), no. 5, 1685–1703.
74. P. Keevash and D. Mubayi, Set systems without a simplex or a cluster,
Combinatorica 30 (2010), 175–200.
75. T. Kittipassorn and B. P. Narayanan, Approximations to m-coloured
complete infinite hypergraphs, J. Graph Theory, To appear.
76. , A canonical Ramsey theorem for exactly m-coloured complete
subgraphs, Combin. Probab. Comput. 23 (2014), 102–115.
77. D. J. Kleitman and K. J. Winston, On the number of graphs without
4-cycles, Discrete Math. 41 (1982), 167–172.
78. Y. Kohayakawa, T. Luczak, and V. Ro¨dl, Arithmetic progressions of length
three in subsets of a random set, Acta Arith. 75 (1996), 133–163.
164
79. Y. Kohayakawa, M. Schacht, and R. Spo¨hel, Upper bounds on proba-
bility thresholds for asymmetric Ramsey properties, Random Structures
Algorithms 44 (2014), 1–28.
80. J. B. Kruskal, The number of simplices in a complex, Mathematical
optimization techniques, Univ. of California Press, Berkeley, Calif., 1963,
pp. 251–278.
81. M. Kutz, Conway’s angel in three dimensions, Theoret. Comput. Sci. 349
(2005), 443–451.
82. I. Leader, P. A. Russell, and M. Walters, Transitive sets in Euclidean
Ramsey theory, J. Combin. Theory Ser. A 119 (2012), 382–396.
83. C. Lee, P. Loh, and B. Sudakov, Self-similarity of graphs, SIAM J. Discrete
Math. 27 (2013), 959–972.
84. I. H. Lee and A. Valentinyi, Noisy contagion without mutation, Rev.
Econom. Stud. 67 (2000), 47–56.
85. L. Lova´sz, On the Shannon capacity of a graph, IEEE Trans. Inform.
Theory 25 (1979), 1–7.
86. , Combinatorial problems and exercises, 2nd ed., AMS Chelsea
Publishing, Providence, RI, 2007.
87. T. Luczak, Randomness and regularity, International Congress of Mathe-
maticians. Vol. III, Eur. Math. Soc., Zu¨rich, 2006, pp. 899–909.
88. M. Maamoun and H. Meyniel, On a game of policemen and robber, Discrete
Appl. Math. 17 (1987), 307–309.
89. A. Ma´the´, The angel of power 2 wins, Combin. Probab. Comput. 16
(2007), 363–374.
90. A. Mehrabian, Lower bounds for the cop number when the robber is fast,
Combin. Probab. Comput. 20 (2011), 617–621.
91. B. P. Narayanan, Exactly m-coloured complete infinite subgraphs, J. Com-
bin. Theory Ser. B 106 (2014), 163–173.
92. N. Nisse and K. Suchan, Fast robber in planar graphs, Graph-Theoretic
Concepts in Computer Science, Lecture Notes in Computer Science, vol.
165
5344, Springer Berlin Heidelberg, 2008, pp. 312–323.
93. R. Nowakowski and P. Winkler, Vertex-to-vertex pursuit in a graph, Dis-
crete Math. 43 (1983), 235–239.
94. H. J. Pro¨mel and V. Ro¨dl, Non-Ramsey graphs are c log n-universal, J.
Combin. Theory Ser. A 88 (1999), 379–384.
95. A Quilliot, Jeux et pointes fixes sur les graphes, Ph.D. thesis, Ph. D.
Dissertation, Universite´ de Paris VI, 1978.
96. F. P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30
(1930), 264–286.
97. V. Ro¨dl and A. Rucin´ski, Threshold functions for Ramsey properties, J.
Amer. Math. Soc. 8 (1995), 917–942.
98. , Rado partition theorem for random subsets of integers, Proc.
London Math. Soc. 74 (1997), 481–502.
99. , Ramsey properties of random hypergraphs, J. Combin. Theory
Ser. A 81 (1998), 1–33.
100. V. Ro¨dl and M. Schacht, Extremal results in random graphs, Preprint,
arXiv:1302.2248.
101. K. F. Roth, On certain sets of integers, J. London Math. Soc. 28 (1953),
104–109.
102. D. Saxton and A. Thomason, Hypergraph containers, Preprint,
arXiv:1204.6595.
103. M. Schacht, Extremal results for random discrete structures, Ann. of Math.,
To appear.
104. A. Stacey and P. Weidl, The existence of exactly m-coloured complete
subgraphs, J. Combin. Theory Ser. B 75 (1999), 1–18.
105. G. Tenenbaum, Sur la probabilite´ qu’un entier posse`de un diviseur dans
un intervalle donne´, Compositio Math. 51 (1984), 243–263.
106. A. Thomason, An upper bound for some Ramsey numbers, J. Graph
Theory 12 (1988), 509–517.
166
107. D. J. Watts, A simple model of global cascades on random networks, Proc.
Nat. Acad. Sci. 99 (2002), 5766–5771.
167