Project Report: Techniques in Discrete Probability

Topics in Ramsey Theory

Sabyasachi Basu
SR No: 12629
UG, 4th year

Abstract
In this report, we look at some recent results in Ramsey theory and look at the developement
of upper and lower bounds using probabilistic tools. We also look at some sparse graphs and
hypergraph embedding. Another topic of interest is small Ramsey numbers and in particular,
we end with Bohman’s proof of a lower bound of R(3, t) using the triangle-free process.
1 Introduction
Suppose that we are at a party and we want to find out whether there exists a group of 3 people,
none of whom know each other, or all of whom know each other. Turns out, for a sufficiently large
number of people, it is guaranteed that one of these is bound to happen. This is known as the ramsey
number R(3, 3). Given that we have small numbers, it is not to difficult to verify that R(3, 3) = 6
even by explicit construction. However, as the number of vertices increases, this becomes increasingly
infeasible, for instance, R(10, 10) is known to be 23854 [3]. Therefore, it is important that we find
bounds for these; in this area, the bounds have not been great and progress has been slow. However,
we list some useful lemmas and outline some major improvements in the field. Section 3 largely
cites recent developments from a recent survey [4], while in Section 4, we outline a proof given by
Bohman in 2009 [2]. The proofs/sketches in Section 3.3 have been taken from [5] and [6].

2 Some useful lemmas

We here state two useful lemma which have been used later on in multiple places. The first is the
Lovász Local Lemma, for which we have largely referred to [1]. The latter, called the dependent
random choice lemmas, have been taken from [6].

2.1 Lovász Local Lemma

Suppose that we have a collection of events {Ai }i∈I , and we can show, in the usual strategy of a
probabilistic proof, that each holds with positive probability, say pi . In the case where each of these
is mutually independent, we can easily write that all of them hold simutaneously with a probability
equal to the product of the individual probabilities. The Lovász Local Lemma works with the
general idea of attempting to make this more general to the extent when the events are not entirely
independent but have rare dependencies, and gives us a way to show that certain events hold with
small, positive probability.
Definition 2.1. (Dependency Digraph) A dependency digraph for events A1 , . . . An is a directed
graph on the set of vertices V = [n] such that the event Ai is mutually independent of all events Aj
such that i and j are not adjacent.

We want to build valid dependency graphs that are as small as possible, so that we may use the
Lovász Local Lemma at every vertex and do a union bound over all its neighbours; the fewer the
degree of a vertex, the smaller the sum, and thus, the stronger the results.
Theorem 2.1 (Asymmetric Local Lemma). Let A1 , . . . , An be events on an arbitrary probability
space and D = (V, E) its dependency Q digraph, and suppose that there are real numbers x1 , . . . , xn
such that 0 ≤ xi < 1 and P[Ai ] = xi (i,j)∈E (1 − xj ) for all i ∈ [n]. Then
" n # n
^ Y
P Ai ≥ (1 − xi ), (1)
i=1 i=1

which means that no event Ai holds with non zero probability.

Theorem 2.2 (Symmetric Local Lemma). Let A1 , . . . , An be events on an arbitrary probability
space. Suppose that each event Ai is mutually independent of aVset of all other events Aj but at most
n
d, and that P[Ai ] ≤ p for all i ∈ [n]. If ep(d + 1) ≤ 1, then P[ i=1 Ai ] ≥ 0.
The symmetric case follows from Theorem 2.1, and it was proved that e is the best possible
V also holds forQthe weaker condition where for each i and each S2 ⊂ [n] {j :
constant [8]. The result
(i, j) ∈ E}, and P[Ai | j∈S2 Aj ] ≤ xi (i,j)∈E (1 − xj ).

2.2 Dependent Random Choice

Theorem 2.3. Let a, d, m, n, r be positive integers and let G = (V, E) be a graph with |V | = n
|E(G)|
vertices and average degree d = 2 . If there is a positive integer t such that
n
dt
  
n m t
− ≤ a, (2)
nt−1 t n
then G has a subset of at least a vertices such that r vertices in U have at least m common neighbours.

1
 A variant of the dependent random choice theorem is as follows.
Theorem 2.4. Let G be a bipartite graph with parts V1 and V2 , order N , and at least N 2 edges,
1
where N ≥ −k max(bn, 4k). Then there is U ⊂ V1 with |U | ≥ 2− k k N

3 Some Applications in Ramsey Theory

Definition 3.1. (Ramsey Number) For a graph H, the Ramsey number R(H) is the smallest integer
N such that any two colouring of the edges of KN gives a monochromatic copy of H. For H = Kt ,
we also write R(t). The Ramsey number R(Ks , Kt ) is also denoted by R(s, t).
For complete graphs, we have the classical Erdös Szekeres bound, R(s, t) ≤ s+t−2


s−1 . For s = t,
 t
4
this is thus then reduced to R(t) = O √t . This follows from observing that in a graph containing
neither a red Ks not a blue Kt , the maximum red-degree of a vertex is less than R(s − 1, t) and
the maximum blue-degree is less than R(s, t − 1). Similarly, if we are to consider the number of
red/blue triangles an edge belongs to, we can use this information to bound them by R(s − 2, t) and
R(s, t − 2) respectively. We can use this along with Goodman/Schwenk’s formula for the number of
forced monochromatic triangles in a two colouring of Kn to get that R(t, t) ≤  t − 2) + 2. The
 4R(t,t
idea behind this can then be used to improve our previous result to R(t) = O 4t . The observation
used in the previous formula can then be generalised almost analogously to state the following.
Theorem 3.1. In a graph containing neither a red Ks nor a blue Kt , any red copy of Kp must be
contained in fewer than R(s − p, t) red copies of Kp+1 , and similarly in fewer than R(s, t − p) blue
copies for blue Kp+1 .
Conlon used this to arrive at the following superpolynomial improvement on the classical Erdös-
Szekeres bound.
Theorem 3.2. There exists a positive constant c such that R(t) ≤ t−c log t/ log log t 4t .

3.1 Lower bounds for Ramsey Numbers:

In what was one of the first applications of the probabilistic method, Erdös in 1947, the probabilistic
method was used to find a lower bound for the diagonal Ramsey numbers.
k
Theorem 3.3. If nk .21−(2) < 1, then R(k, k) > n, i.e. R(k, k) > b2 2 c∀k ≥ 3.

k

Proof. Kn is edge coloured red and blue independently with each colour equally likely. For a set of
k vertices, R, let the event AR be the event that the induced subgraph on R (which can be choose
k
in nk ) is monochromatic, which has probability 21−(2) . Then,

k
21+ 2 nk
 
n 1−(k2)
2 < . <1 (3)
k k! 2k2 /2
k
which means that R(k, k) > b2 2 c.
This bound can be improved slightly if we notice that AS and AT are independent events unless
|S ∩ T | ≥ 2. Then, we can invoke the symmetric form of the Local Lemma and deduce the following
result.

1−(k) √ k
Theorem 3.4. If e k2 n−2 2


k−2 .2
2 < 1, then R(k, k) > n, i.e. R(k, k) >
e (1 + o(1))k2 .
2

While this is a minor improvement, it is not surprising because the Local Lemma is the most
powerful only when the dependence between events are rare, unlike the case here. This suggests
that the Local Lemma is will be useful in improving the off-diagonal Ramsey numbers, particularly
when one of the parameters is small. We attempt to generalise the statement in Theorem 3.3 to
arrive at the next statement.
Theorem 3.5. If there exists p ∈ [0, 1] such that
   
n (2s) n n
p + (1 − p)( t ) < 1, (4)
p t
then R(s, t) > n.

2
3.2 Small Ramsey Numbers
Let us now look at the asymptotic consequences of Theorem 3.5. We can say that the first term in
s s(s−1)/2
s
, and if p = n− s−1 , we can show that np p(2) < s!
2
the LHS is less than n p s! 1
. Using the fact
t −p(t2 −t)/2
that 1 − p < e−p , we can bound the second term by n e t! . The condition in Theorem 3.5
holds if t − 1 ≥ 2 log
p
n
, which means that asymptotically, for k fixed and t → ∞,
t(s−1)
+o(1)
R(s, t) > t 2 . (5)

Let us take a special case of this, the Ramsey numbers R(3, t). It was known that

ct2 ct2 log log t

< R(3, t) < (6)
(log t)2 logt

where the lower bound was proved by Erdös and the upper bound by Graver and Yackel. This was
further improved by Ajtai, Komlos and Szemerédi, who showed using Turan’s theorem that

ct2 cs ts−1
R(3, t) ≤ ; and R(s, t) ≤ . (7)
log t (log t)s−2

For s = 3, this follows from the statement that any triangle free graph on N vertices with average
degree d contains an independent set of size Ω Nd log d . In a triangle free graph, the neighbourhood

of each vertex must form an independent set and so d < t, which means that the graph must contain
ct2
an independent set of size Ω Nt log t . Thus for c sufficiently large and N ≥ log


t , the graph contains
an independent set of order t. The sharpness of this bound was illustrated by Kim in what is
considered a landmark application of the semi random process. He showed that there exists a
positive constant c0 such that
t2
R(3, t) ≥ c0 . (8)
log t
This was also, more recently proved by Bohman using the triangle free process. Using more precise
estimates of the running time of the triangle free process, Bohman and Keevash, and independently,
Pontiveros, Griffiths and Morris produced the following result.
  2
1 t
R(3, t) ≥ − o(1) . (9)
4 log t

In comparison, the best known upper bound, due to Shearer, is

t2
R(3, t) ≤ (1 + o(1)) . (10)
log t
Bohman also uses a similar method to study the K4 -free process and has been able to provide the
following bound, a slight improvement over a previously know result which was shown by Spencer
using the Local Lemma.
5
t2
R(4, t) > c4 . 2 (11)
log t

3.3 Sparse Graphs

A topic of classical interest in Ramsey theory is the Ramsey numbers of sparse graphs, that is where
the degree of each vertex is bounded. The foundation was laid by Erdös and Burr, who conjectured
that every graph G with maximum degree ∆ and n vertices satisfies

R(H) ≤ c(∆)n (12)

where c(∆) is a constant dependent on ∆. This was proved first by Chvátal, Rödl, Szemerédi and
Trotter using Szemerédi’s regularity lemma. First progress was made by Eaton, who showed that
c∆ 2
c(∆) ≤ 22 , while Graham Rodl and Rucinski later gave a better bound of c(∆) ≤ 2c∆ log ∆ .
Recently, this was further improved to give the following.

R(H) ≤ 2c∆ log ∆ n. (13)

3
3.3.1 Hypergraphs
A hypergraph H = (V, E) consists of a set of vertices V and edges E which has, as elements, subsets
of V . A hypergraph is called k uniform if each edge has exactly k vertices. The Ramsey number
of a k-uniform hypergraph H is the smallest integer n such that any two colouring of the edges of
the complete k − unif orm hypergraph Knk contains a monochromatic copy of H. We say that a
hypergraph is down-closed if e1 ⊂ e2 and e2 ∈ E implies that e1 ∈ E.
Lemma 3.6. Let H be an n vertex hypergraph with maximum degree ∆ such that each edge has

. If G is a down-closed hypergraph on vertex set U with
size at most k and suppose that δ ≤ (4∆)−k
N ≥ 4n vertices and more than (1 − δ) Nk edges of size k, then there is a copy of H in G .

This can be improved by using the Lovász Local Lemma.

Lemma 3.7. Let H be an n vertex hypergraph with maximum degree ∆ such that each edge has
8kn
1
size at most k and suppose that δ ≤ 4k∆ 2− N . If G is a down-closed hypergraph on vertex set U
k edges of size k, then there is a copy of H in G .
with N ≥ 16n vertices and more than (1 − δ) N

Sketch of Proof: For k ≥ 2, take a uniform random mapping f : V (H ) → V (G ). For u, v ∈

V (H ), consider the bad event that Auv : f (u) = f (v) and for e ∈ E(H ), Be : |f (e)| = |e|, f (e) ∈ /
V (G ). For |e| = l due to down-closedness, we can say that the number of l-sets which are not edges
of G is at most δ Nl , i.e. P[Be ] ≤ δ and it is easy to see that P[Auv ] = 1/N . It is also straightforward

that Auv is dependent on at most 2(n − 2) events of the form Aij and 2∆ events of the form Be .
Similarly, for Be , the respective values are n2 − n−l



2 < kn and k∆. One may then use the Local
Lemma to show that the probability that none of the ’bad’ events occurs is positive, which leads us
to the result.

3.3.2 Bipartite Graphs

0
If we assume G to be a bipartite graph on n vertices, then they also show that R(G) ≥ 2c ∆ n for
a constant c0 . This is a tight bound, as Conlon and Fox and Sudakov showed that R(G) ≤ 2c∆ n.
The best known bound was proved by the trio and it states that for every bipartite graph G on n
vertices with maximum degree ∆,R(G) ≤ ∆2∆+5 n .Removing the factor of ∆, we may also say that

R(G) ≤ 2∆+6 n. (14)

Ramsey Number of the Cube :

The r-cube Qr is the r-regular graph with 2r vertices whose vertex set consits of all binary vectors in
2
r dimensions, and two are adjacent iff the differ in only 1 position. Beck showed that R(Qr ) ≤ 2cr ,
r
and this was improve by Graham et al. who showed that R(Qr ) ≤ 8(16r) .
Theorem 3.8. R(Qr ) ≤ 23r .
Proof. Take a complete graph
on n = 23r vertices and two-colour the edges. The denser of the two
colours then has at least 21 n2 ≥ 2−7/3 n2 edges, and thus the average degree of the graph of the
denser color is at least 2−4/3 n. Take t = 32 r, m = 2r , a = 2r−1 . Then,

dt
  
n m t
− ≥ 2r − 1 ≥ 2r−1 .
nt−1 r n

Then we can invoke the dependent random choice lemma (Theorem 2.4) and find in G a subgraph
U of size 2r−1 with at least 2r common neighbours for every set of r vertices. It can be shown that
the hypercube being a bipartite graph is a subgraph of G, which completes the proof.

The following result regarding the Ramsey number of bipartite graphs follow from Theorems 2.4
and 3.7, and it can be seen as a generalisation of Equation 14.

Theorem 3.9. H is a bipartite graph on n vertices such that the maximum degrees of each part is
1
k and ∆ respectively. If G is a bipartite graph with edge density  and at least 16∆ k −k n vertices
1
k+5
in each part, then H is a subgraph of G. As a corollary R(H) ≤ ∆ k 2 n.

4
4 Using the Triangle Free Process to Bound R(3, t)
In this section, we present Tom Bohman’s proof of the lower bound of R(3, t) using what is known
as the triangle free process. Consider the following random graph process: we begin with the empty
graph on [n] vertices, which we call G0 , and we reach Gi by adding an edge chosen uniformly from
the non edges of Gi−1 . If this is done such that it does not create a triangle, then it is known as a
triangle or K3 free process. Then notice that Gi partitions [n]


2 into three parts: the set Ei = E(Gi ),
Oi , all edges adding which the triangle-free property is not violated, and Ci being the rest. An edge
in Oi is called open while one in Ci is called closed. Define the random variable Qi = |Oi |. Also
define for a Gi , Xu,v as the set of vertices w such that both uw and vw are open, Yu,v (i) as the set
of vertices w such that one of uw and vw is open and the other is in Ei , and Zi as the set such that
both are in Ei ; call them open, partial and complete with respect to uv.

4.1 Heuristic of Trajectory

We study a rough trajectory that the random variables defined in the previous paragraph take.
3
We introduce a continuous time variable t(i) = i/n 2 and subsequently define the trajectories
√ by
q(t), x(t), y(t). We suppose that Q(i) ≈ q(t)n2 , |Xuv (i)| ≈ x(t)n, and |Yuv (i)| ≈ y(t) n for all
uv ∈ [n]


2 Ei . Take  > 0 sufficiently small and a fixed step i in the graph process and look
3
at changes over n 2 steps. Notice that if ei+1 = uv, then Q(i + 1) − Q(i) = −1 − |Yuv (i)| ⇒
q(t + )n ≈ (q(t) − y(t))n2 . This suggests that q̇ = −y. Applying similar bounds on the nature of
2

changes of Xuv (i) and Yuv (i), we can conclude that ẋ = −2xy/q and ẏ = (2x − y 2 )/q. Setting the
respective initial values to be 0, 1 and 0, the solution to this system is
2
e−4t 2 2
q(t) = , x(t) = e−8t , y(t) = 4te−4t . (15)
2
Then, if |Oi | were
√ to indeed follow √ this distribution, the triangle
√ free process would come to an
end at t = Θ( log n) with Θ( log n.n3/2 ) edges. Set m = µ log n.n3/2 . We first prove that the
trajectory is followed by the corresponding random variables upto m random edges. We approach
this concentration by introducing ‘error functions’ that slowly deteriorate as the process evolves.
Define:  2
e41t +40t if t ≤ 1 2 2
fq (t) = e41t2 +40t fx (t) = e37t +40t fy (t) = e41t +40t ,
 if x > 1
t
Now set
gq (t) = fq (t)n−1/6 , gx (t) = fx (t)n−1/6 , gy (t) = fy (t)n−1/6 (16)
gy 2
Notice that gq ≤ , and gx = e−4t gy .
t
Let Bj be the event that there exists a step i ≤ j such that |Q(i) − q(t)n2 | ≥ gq (t)n2 or there
√ √
exists uv ∈ [n]


2 Ei such that ||Xuv (i)| − x(t)n| ≥ gx (t)n, or ||Yuv (i)| − y(t) n| ≥ gy (t) n, or
|Zuv (i)| ≥ log2 n.
For ω ∈ Bm , let l be the smallest index such that ω ∈ Bl but ω ∈ / Bl−1 . Define X to be the set
ω ∈ Bm such that uv ∈ / El and |Xuv (l)| ∈/ n[x(t(l)) ± gx (t(l))]; i.e. an atom ω ∈ Bm is in X if there is
some pair of vertices {u, v} such that the number of open vertices with respect to them is a reason
we place ω ∈ Bl , and Y, Z are defined analogously with respect to Y and Z and their corresponding
error functions. We make the following claim.
Theorem 4.1. If n is sufficiently large, then
2
P(Bm(n) ) ≤ e− log n
. (17)
We prove this by showing that
Bm = X ∪ Y ∪ Z, (18)
from where the result follows by bounding the probability of each. Note that if we have ei+1 = uv,
then the number of edges closed when we add it is equal to the number of partial vertices. So,
assuming ω ∈
/ Bj−1 , we have
j−1
n2 − n X
|Oj | = −j− |Yei+1 (i)|
2 i=0
(19)
2
⊆ n [q(t(j)) ± gq (t(j))].

5
This can be shown by substituting from (15). Thus, if |Yuv (j)| is in range for all j ≤ i and all pairs
{u, v}, then |Oi | is in range. This proves (18).

4.2 Open Vertices

Consider a fixed uv ∈ [n]


2 , and let Ai be the number of open vertices at {u, v} that are eliminated
when ei is added to the process. Then, we can write the following:
j
X
|Xuv (j)| = n − 2 − Ai . (20)
i=1

Define the following:

  
A + √1 − 2x(t)y(t) ± (17t + 39)g (t) if ω ∈
/ Bi−1 , uv ∈
/ Ei
i x
A± i = n q(t)
0 if ω ∈ Bi−1 or uv ∈ Ei


j
X
Bj± = A±
i (21)
i=1

It can then be shown using (15) and (20) that the event |Xuv (j)| > n [x(t(j)) + gx (t(j))] is contained
5 5
in the event that Bj+ < −n 6 , and |Xuv (j)| < n [x(t(j)) − gx (t(j))] in the event Bj− > n 6 . To bound
this probability, we use the following claim without proof.
4 √
 
Claim 4.1.1. {Bi± }i is a √ , n -bounded martingale pair.
n
Following this, we use a variant of the Azuma-Höfdding inequality:
Theorem 4.2. Let η ≤ N/2 (respectively N/10) and a < ηm. If 0 ≡ A0 , A1 , . . . is an (η, N )
bounded submartingale (respectively supermartingale), then P[Am ≤ −a] (respectively P[Am ≥ a]) is
a2
less than or equal to e− 3ηmN .
n5/3
−
Using this theorem, we can then claim that P(Bm +
< −n5/6 ), P(Bm > n5/6 ) ≤ e− 12m . Suppose
that ω ∈ X on account of the pair {u, v} at step l. Then either Bl < −n5/6 or Bl− > n5/6 , and
+

Bl± = Bj± for all j ≥ l. Then

 
n − 3ηmN
a2
P(X ) ≤ 2 e . (22)
2

4.3 Partial Vertices

Similar to our treatment of the previous case, we write
j
X
|Yuv (j)| = Ui − V i , (23)
i=1

where Ui is the number of partial vertices at {u, v} created when ei is added and Vi is the number
of partial vertices at {u, v} eliminated by addition of ei (each is 0 if uv ∈ Ei ). Similar to Bj± we
here define
Xj Xj
Wj± = Vi± and Tj± = Ui± , (24)
i=1 i=1

following which, analogously we get to the following claim:

   
4 5
Claim 4.2.1. {Wi± }i is a , log2 n -bounded martingale pair and {Ti± }i is a , 1 -bounded
n n
martingale pair
The difference in bounds comes from the difference in the exact expressions, which can be derived
from (15) to arrive at the conclusion using a similar argument of bounded martingales. Consequently,
2/3
+ − − 48mnlog2 n/n
we can again invoke Theorem 4.2 and say that P(Wm < −n1/3 /2), P(Wm > n1/3 /2) ≤ e

6
 n2/3
and P(Tm +
< −n1/3 /2), P(Tm−
> n1/3 /2) ≤ e− 60m/n . We then return to the random variable |Yuv (i)|
itself and using (15) and (23) say that
j
X
|Yuv (j)| = Ui − Vi
i=1 (25)
√ 1
≥ n[y(t(j)) − gy (t(j))] + n +
3 Tj+ − Wj− .
√ √
Therefore the events |Yuv (j)| < n[y(t(j)) − gy (t(j))] and |Yuv (j)| > n[y(t(j)) + gy (t(j))] are
contained in
n1/3 n1/3 n1/3 n1/3
       
+ − − +
Tj < − ∨ Wj > and Tj < − ∨ Wj > (26)
2 2 2 2

respectively. Considering the fact that the random variables T and W are ‘frozen’ once one of the
random variables leaves the allowed range, we can use the bounds derived preceding (25) to obtain
   
n n2/3 n2/3 n1/6
−
P(Y) ≤ .2 e 48m log2 n/n + e− 60m/n < 2n2 e− 48 . (27)
2

4.4 Complete Vertices

We observe that the probability that ei+1 adds a complete vertex at {u, v} is at most |Yuv (i)|/|Oi |.
Consequently, in the event Bi , we have, by substituting from (15):
9t
P(|Zuv (i + 1)| = |Zuv (i)| + 1) ≤
n3/2
  √ log2 n (28)
2 m 9µ log n − 21 (log2 n) log log n
⇒P(|Zuv (m)| ≥ log n) ≤ ≤e
log2 n n3/2
√
for n sufficiently large and m = µn3/2 log n as defined earlier. Thus we arrive at the bound of
 
n − 1 (log2 n) log log n
P(Z) ≤ e 2 (29)
2

Thus, using the union bound on these events, Theorem 4.1 is proved.

4.5 Bounding the Number of Edges

Theorem 4.1 does not provide a bound on the number of edges in the graph produced by the
triangle-free process. To achieve this bound, we look at the independence number of Gm and make
the following claim:
√ 1/5
Theorem 4.3. For n sufficiently large, P α (Gm ) > γ n log n|Bm < e−n , where γ is a constant

large relative to µ.
To get here, we introduce constants β, ρ; the latter is small, while the former is large relative
√ to
µ and small relative to γ. Let Di be the event that Gi has a vertex of degree greater than β n log n.
Then we claim:
1/5
Claim 4.3.1. For n sufficiently large, P(Di ∧ Bm ) ≤ e−n .
Sketch of Proof: For a vertex v, let Wv (i) be the set of pairs in Oi that contain it, and Ai the
number of open pairs containing v that are removed from Wv upon addition of ei . We then define
(  2
 2
Ai+1 − √1n 8te−4t − 20gy if Wv (i) > e−4t n and ω ∈ / Bi
Bi+1 = (30)
−4t2
0 if Wv (i) ≤ e n and ω ∈ Bi
Pj  √ 
It can be shown that a sequence of the form i=l Bi is a √2n , n -bounded submartingale and
P  n7/4 2
j
thus P i=l B i ≤ −n 7/8
≤ e− 6m . If we consider the event that |Wv (l)| ≤ e−4t(l) n, there is a
maximum l < j for which this holds. We then bound the partial sums of Ai and Bi based on this
condition, look at the probability of its failure, and arrive at the result by computing a union bound.

7
 Another claim, the proof of which follows somewhat similar lines,
requires some definitions. We
define Pj as the event that there exist disjoint subsets A, B ∈ [n]k  i ≤ j such that
anda step
A∪B −4t2 2 γ−β √

1−ρ/3
2 ∩ Ei = φ, and |WA,B (i)| < e k − 2n . Here |A| = |B| = 2 n log n = k and
WA,B (i) is the set of pairs from A × B, open in Gi with respect to both A and B.
1/2
Claim 4.3.2. P(Pm ∧ Bm ) ≤ e−n if n is sufficiently large.
√
Consider a fixed set K of γ n log n vertices. If K is independent in Gi , then the number of pairs
2
in K at least a constant times e−4t |K|2 , which means that the edge ei+1 has a fairly good


2 ∩ O i is
chance of falling in K.

We look at Bi ∧ Di ∧ Pi . For each step of the process such that K

2 ∩ Ei = φ, let Li be the set of
vertices not in K such that |Pi (x)| > nkρ where Pi (x) = {Ni (x) ∩ K}. For x ∈ Li , define Ni = Pi (x).
When not in the event Bi the co-degrees are bounded, so

X, Y ∈ Ni ⇒ |X ∩ Y | ≤ log2 n (31)

Then, the cardinality of f sets in Ni is at least f k/n√ρ

− f 2 log2 n, and thus, |Li | ≤ 2nρ . Moreover,
from out constraint on Di , we can say that |X| ≤ β n log n if it belongs to Ni . We next identify
disjoint sets A, B such that the set of pairs A × B is disjoint from X


2 for all X ∈ Ni . We construct
A ⊆ K such that |A| = k by iteratively adding sets from Ni as long as possible. We construct B
of size k from the remainder of size such that it is disjoint from the X ∈ Ni used to form A. The
following condition then holds:

|X ∩ A| ≤ log2 n.2nρ or |X ∩ B| = 0. (32)

√
Also, the number of edges in WA,B (i) in Ci is at most |Li |(2 log2 n.nρ ).β n log n ≤ 4β log5/2 n.n1/2+2ρ .
Since our event is not in Pi or Bi , we can give the following bounds following the construction of A
and B preceding Claim 4.3.2, and then providing a looser bound:
2
  
Oi ∩ K  ≥ e−4t2 . (γ − β) .n log n,
 
(33)
 2  5

(γ − β)2 log n
  
K
P ei+1 ∈ ≥ . (34)
2 6n
The probability that K remains independent is at most
m
(γ − β)2 log n
 √
(γ−β)2 3/2
1− ≤ e− 6 µ log n. n (35)
6n

And on the other hand, the possible number of sets of vertices with cardinality same as K is
  √
n γ 3/2
≤ e 2 log n. n . (36)
|K|

The proof of Theorem 4.3 then follows from a union bound argument. As a corollary of this, we can
then state the main theorem of interest here:
Theorem 4.4. There exists a constant c3 such that the following holds: If n = n(t) < c3 .t2 / log t,
then asymptotically almost surely, the triangle free process produces an n vertex graph with no inde-
t2
pendent set of size t. Then it follows that R(3, t) ≥ c3 . log t for t sufficiently large.

References
[1] Noga Alon and Joel H. Spencer, The probabilistic method, 4th ed., Wiley Publishing, 2016.
[2] Tom Bohman, The triangle-free process, Advances in Mathematics 221 (2009), no. 5, 1653 –
1677.
[3] Bela Bollobas, Modern graph theory, Springer, 1998.

8
[4] David Conlon, Jacob Fox, and Benny Sudakov, Recent developments in graph ramsey theory,
London Mathematical Society Lecture Note Series, p. 49–118, Cambridge University Press, 2015.
[5] David Conlon, Jacob Fox, and Benny Sudakov, Short proofs of some extremal results ii, Jour-
nal of Combinatorial Theory, Series B 121 (2016), 173 – 196, Fifty years of The Journal of
Combinatorial Theory.
[6] Jacob Fox and Benny Sudakov, Dependent random choice, Random Structures & Algorithms 38,
no. 1-2, 68–99.
[7] Jeong Han Kim, The ramsey number r(3, t) has order of magnitude t2/log t, Random Structures
& Algorithms 7, no. 3, 173–207.

[8] J. B. Shearer, On a problem of spencer, Combinatorica 5 (1985), no. 3, 241–245.

[9] Joel Spencer, Ramsey’s theorem—a new lower bound, Journal of Combinatorial Theory, Series
A 18 (1975), no. 1, 108 – 115.