The size-Ramsey number of cubic graphs

David Conlon∗ Rajko Nenadov† Miloš Trujić‡

Abstract

We show that the size-Ramsey number of any cubic graph with n vertices is Opn8{5 q,
arXiv:2110.01897v2 [math.CO] 23 Apr 2023

improving a bound of n5{3`op1q due to Kohayakawa, Rödl, Schacht, and Szemerédi. The heart
of the argument is to show that there is a constant C such that a random graph with Cn
vertices where every edge is chosen independently with probability p ě Cn´2{5 is with high
probability Ramsey for any cubic graph with n vertices. This latter result is best possible up
to the constant.

1 Introduction

We say that a graph G is Ramsey for another graph H, and write G Ñ H, if every colouring of
the edges of G with two colours contains a monochromatic copy of H. In this paper, we study
the quantity r̂pHq, the size-Ramsey number of H, defined as the smallest m P N such that there
exists a graph G with m edges which is Ramsey for H. As any sufficiently large complete graph
is Ramsey for H, this notion is well-defined.
The study of size-Ramsey numbers was initiated by Erdős, Faudree, Rousseau, and Schelp [14]
in 1978. Their paper already contains the observation, which they attribute to Chvátal, that
r̂pKn q “ rpK2 n q , where rpKn q is the usual Ramsey number, i.e., the smallest integer N such
` ˘

that KN Ñ Kn . In other words, when H “ Kn one cannot do better than taking G to be

the smallest complete graph that is Ramsey for H. A significantly more interesting example
is when H “ Pn , the path on n vertices, for which Beck [4] has shown that r̂pPn q “ Opnq.
Subsequent work has extended this result to many other familes of graphs, including bounded-
degree trees [15], cycles [21], and, more recently, powers of paths and bounded-degree trees [6]
and long subdivisions [12]. For some further recent developments, see [8, 19, 20, 23, 26].
Moving away from trees and tree-like graphs, Beck [5] asked whether the size-Ramsey number
of every bounded-degree graph is linear in its order. Rödl and Szemerédi [31] answered this in
the negative by showing that there exists a constant c ą 0 and, for every n, an n-vertex cubic
graph H, that is, a graph with maximum degree three, such that r̂pHq ě nplog nqc . To date, this
remains the best known general lower bound for the size-Ramsey number of bounded-degree
graphs. Despite this, the conjecture of Rödl and Szemerédi [31] that there exists a constant ε ą 0
and, for every n, an n-vertex cubic graph H such that r̂pHq ě n1`ε is widely believed.
∗
Department of Mathematics, California Institute of Technology, Pasadena, CA 91125, USA. Email:
[email protected]. Research supported by NSF Award DMS-2054452.
†
Google Zürich. Email: [email protected].
‡
Institute of Theoretical Computer Science, ETH Zürich, 8092 Zürich, Switzerland. Email:
[email protected]. Research supported by grant no. 200020 197138 of the Swiss National Science Foundation.

1
Regarding upper bounds, a result of Kohayakawa, Rödl, Schacht, and Szemerédi [25] shows that
r̂pHq ď n2´1{∆`op1q for any graph H on n vertices with maximum degree ∆. Here we improve
this bound for cubic graphs.

Theorem 1.1. There exists a constant K such that r̂pHq ď Kn8{5 for every cubic graph H with
n vertices.

Seeing as there is still a very large gap between the upper and lower bounds for size-Ramsey
numbers of cubic graphs, our result warrants some justification. The key point is that all previous
work on upper bounds for size-Ramsey numbers has relied upon showing that suitable random
graphs (or, in some cases, graphs derived from random graphs by taking appropriate powers
and blow-ups) are, with high probability,1 Ramsey for the required target graph H. Recall that
Gn,p stands for the probability distribution over all graphs with n P N vertices in which each
pair of vertices forms an edge independently with probability p “ ppnq P p0, 1q. We will use Gn,p
interchangeably to describe both this distribution and an actual graph sampled from it. With
this notation, our real main result is then the following theorem about Ramsey properties of
random graphs.

Theorem 1.2. There exist c, K ą 0 such that if p ě Kn´2{5 , then, with high probability,
Gn,p Ñ H for every cubic graph H with at most cn vertices.

It is easy to see that Theorem 1.2 implies Theorem 1.1, since Gn,p typically has Θpn2 pq edges, by
standard concentration inequalities. Moreover, Theorem 1.2 is optimal: a classic result of Rödl
and Ruciński [29, 30] shows that if p “ opn´2{5 q, then, with high probability, Gn,p is not Ramsey
for K4 . Hence, the statement of Theorem 1.1 is the most one can get out of using vanilla random
graphs (that is, without modifying them further). We will come back to this point, and a further
discussion on the limits of our method, in Section 6.
The rest of the paper is organised as follows. In the next section, we give a high-level overview of
our argument. In Section 3, we collect several results about random graphs and sparse regular
pairs that will be needed in the proof. Section 4 contains our two main building blocks, which
will allow us to thread trees and cycles through prescribed sets of vertices. In Section 5, we then
combine these building blocks with a decomposition result for cubic graphs to complete the proof
of Theorem 1.2. Finally, as mentioned above, we will discuss the limits of our method and the
potential next steps in Section 6.

2 Overview of the proof

Assume that the host graph Γ „ Gn,p satisfies a number of the properties that typically hold in
random graphs, such as expansion, no dense spots, concentration of degrees and number of edges
in subsets, etc. In their proof, Kohayakawa, Rödl, Schacht, and Szemerédi [25] start by showing
that in any red/blue colouring of the edges of Γ, one can find disjoint sets V1 , . . . , V20 Ď V pΓq,
each of order αn for some α ą 0, such that each pair pVi , Vj q is pε, pq-regular with at least
|Vi ||Vj |p{3 edges between Vi and Vj in one of the colours, say red. That is, the density of edges
between any two sufficiently large sets Ui Ď Vi and Uj Ď Vj is roughly the same as the density
1
We say that a property holds with high probability (or w.h.p. for brevity) if the probability it holds tends to 1
as n Ñ 8.

2
between Vi and Vj , with a discrepancy of at most εp (see Definition 3.2 below). This is a standard
step in the regularity method and we refer the reader to [7, 25] for more details.
Suppose, therefore, that we have a collection of large sets of vertices such that the distribution
of red edges between any two of them is fairly uniform. We wish to use this structure to show
that R, the subgraph of Γ consisting of all the red edges, contains any particular cubic graph
H on at most cn vertices. The strategy used in [25] at this point follows an idea of Alon and
Füredi [2]: split the vertex set of H into, say, 20 independent sets and then embed these sets one
at a time using Hall’s matching criteria, with the i-th set being embedded into Vi . When we
come to embed the last such set, every remaining vertex of degree three has to be mapped into
the common neighbourhood of three previously embedded vertices. However, if p “ opn´1{3 q,
three typical vertices in the random graph will have an empty common neighbourhood. It is for
this reason that the methods of [25] break down at this point.
To circumvent this issue, we borrow an idea from the work of the first two authors together with
Ferber and Škorić [10]. Assume that H is connected and remove from it an induced cycle of
length at least four. This leaves us with a 2-degenerate graph H 1 . That is, we can order the
vertices of H 1 in such a way that every vertex has at most two of its neighbours preceding it. One
might then hope that p " n´1{2 is sufficient to embed H 1 . Having embedded H 1 , we then need to
replace the deleted cycle, which we suppose for illustration is a C4 . As the graph is cubic, each
vertex v of such a C4 already has at most one embedded neighbour, so there will be a candidate
set of order roughly np in which we can embed v. If all four candidate sets are disjoint and
span four pε, pq-regular pairs of density Θppq in the correct cyclic order, then a result of Gerke,
Kohayakawa, Rödl, and Steger [16] implies that we can find the desired copy of C4 between
these sets, provided p " pnpq´2{3 (see Lemma 3.7 below). Rearranging, this gives p " n´2{5 —
precisely the bound promised by Theorem 1.2. Note that, crucially, the cycle we embed at the
end is of length at least four. If it were a triangle instead, we would need p " pnpq´1{2 in the
last step, which leads back to the bound p " n´1{3 .
In practice, our actual approach takes the idea of partitioning even further. Instead of taking out
one cycle and relying on the fact that the remaining graph H 1 is 2-degenerate, we partition H
(which we may assume contains no K4 ’s, since they can be set aside and dealt with separately)
into blocks: first removing a maximal collection of disjoint induced cycles of length at least four
and then partitioning what remains into induced paths (see Lemma 5.1 below). Moreover, these
blocks B1 , . . . , Bt can be placed in a ‘1-degenerate ordering’, meaning that each vertex in Bi has
at most one neighbour in B1 Y ¨ ¨ ¨ Y Bi´1 for every i P t2, . . . , tu. We then find a copy of H by
embedding one whole block at a time. Crucially, whenever we are about to embed a block Bi ,
every v P Bi has at most one previously embedded neighbour, so the candidate set for v has
order Ωpnpq. This is large enough that the regularity property is inherited by any relevant pair
of candidate sets, which then allows us to embed Bi , which is either a path or a cycle, in one
sweep (see Lemmas 4.1 and 4.2 below).

3 Preliminaries

In this section, we collect several results about random graphs that we will need, with a particular
focus on the properties of regular pairs in random graphs. For a thorough, although now
somewhat outdated, treatment of the latter topic, we refer the reader to the survey of Gerke
and Steger [18]. Though many of the results hold in greater generality, we have tailored the

3
statements towards their later use in the proof of Theorem 1.2. Where statements depart from
their usual form in the literature, we also give, at the very least, a sketch of the proof.
We begin with a standard concentration result, which easily follows from combining Chernoff’s
inequality (see, e.g., [22, Corollary 2.3]) with a union bound. Here and throughout we write
N̂G pX, Y q for the set of common neighbours of the vertices from X in Y , that is, N̂G pX, Y q :“
Ş
Y X xPX NG pxq and N̂G pXq “ N̂G pX, V pGq r Xq.

Lemma 3.1. For every d P N and δ P p0, 1q, there exists a positive constant K such that, for
p ě pK log n{nq1{d , the random graph Γ „ Gn,p w.h.p. has the following property. For every
family of disjoint d-sets P Ď V pΓq
` ˘
d of size |P| ď δ{pd ,
ˇď ˇ
N̂ ˇ “ p1 ˘ δq|P|npd .
ˇ ˇ
ˇ Γ pSq
SPP

3.1 Properties of pε, pq-regular pairs

We have already referred to pε, pq-regular pairs several times. The formal definition is as follows.

Definition 3.2. Let G be a graph and let V1 , V2 Ď V pGq be disjoint subsets. We say that
the pair pV1 , V2 q is pε, pq-regular for some 0 ă ε, p ď 1 if, for every U1 Ď V1 , U2 Ď V2 with
|U1 | ě ε|V1 |, |U2 | ě ε|V2 |, we have
ˇ ˇ
ˇdG pU1 , U2 q ´ dG pV1 , V2 qˇ ď εp,

where dG pA, Bq “ eG pA, Bq{p|A||B|q denotes the edge density of a given pair.

It follows from the definition that if d “ dG pV1 , V2 q “ Θppq and ε is sufficiently small, then there
cannot be more than ε|V1 | vertices in V1 which have fewer than, say, d|V2 |{2 neighbours in V2 .
The next result shows that we can even find large subsets V11 Ď V1 and V21 Ď V2 such that each
vertex in V11 has at least d|V2 |{2 neighbours in V21 and vice versa and, moreover, that this property
can be achieved for many pairs simultaneously.

Lemma 3.3. For every ∆ P N and γ ą 0, there exists ε0 ą 0 such that the following holds for
any 0 ă ε ď ε0 and p P p0, 1q. Let H be a graph with maximum degree ∆ and let tVi uiPV pHq
be a family of subsets of some graph G such that pVi , Vj q is pε, pq-regular of density d ě γp
(with respect to G) for every ij P H. Then, for every i P V pHq, there exists Vi1 Ď Vi of order
|Vi1 | ě p1 ´ ∆εq|Vi | such that degG pv, Vj1 q ě d|Vj |{2 for every v P Vi1 and all ij P H.

Sketch of the proof. Set Bi “ ∅ for every i P V pHq and repeat the following process: as long
as there is an edge ij P H and a vertex v P Vi r Bi which has fewer than d|Vj |{2 neighbours
in Vj r Bj , add v to Bi . Suppose that at some point one of the sets Bi becomes larger than
∆ε|Vi | and, once this happens, we terminate the process. By the pigeonhole principle, there must
be a subset Bi1 Ď Bi of order |Bi1 | ě ε|Vi | and an edge ij P H such that every v P Bi1 satisfies
degG pv, Vj r Bj q ă d|Vj |{2. This implies that the density of the pair pBi1 , Vj r Bj q is less than
d{2. On the other hand, as |Vj r Bj | ě p1 ´ ∆εq|Vj |, the pε, pq-regularity property tells us that
this density is close to d, a contradiction. In particular, the procedure terminates with each Bi
being of order at most ∆ε|Vi | and the statement of the lemma follows.

4
3.1.1 Regularity inheritance

The following lemma is usually referred to as the slicing lemma and follows directly from the
definition of pε, pq-regularity.

Lemma 3.4. Let 0 ă ε1 ă ε2 ď 1{2, p P p0, 1q, and let pX, Y q be an pε1 , pq-regular pair.
Then any two subsets X 1 Ď X and Y 1 Ď Y of order |X 1 | ě ε2 |X| and |Y 1 | ě ε2 |Y | form an
pε1 {ε2 , pq-regular pair of density dpX, Y q ˘ ε1 p.

In other words, sufficiently large subsets of a regular pair again induce a regular pair. This then
allows us to take subsets of our regular pairs and yet still assume that they are pε, pq-regular
with ε sufficiently small, a fact that we will use implicitly in our main proof.
The next lemma captures a key feature of sparse regularity, that, for subgraphs of random graphs,
the regularity property is typically inherited between neighbourhoods of vertices.

Lemma 3.5. For all ε1 , α, γ, δ ą 0, there exist ε0 “ ε0 pε1 , γ, δq and K “ Kpε1 , α, γq such that,
for every 0 ă ε ď ε0 and p ě Kplog n{nq1{2 , the random graph Γ „ Gn,p w.h.p. has the following
property.
Suppose G Ď Γ and V1 , V2 Ď V pΓq are disjoint subsets of order ñ “ αn such that pV1 , V2 q is
pε, pq-regular of density d ě γp with respect to G. Then there exists B Ď V pΓq of order |B| ď δñ
such that for each v, w P V pΓq r pV1 Y V2 Y Bq (not necessarily distinct) the following holds: for
any two subsets Nv Ď NΓ pv, V1 q and Nw Ď NΓ pw, V2 q of order ñd{4, both pNv , V2 q and pNv , Nw q
are pε1 , pq-regular of density p1 ˘ ε1 qd with respect to G.

To prove Lemma 3.5, we need the following lemma of Škorić, Steger, and Trujić [33], itself based
on an earlier result of Gerke, Kohayakawa, Rödl, and Steger [16]. It enables us to say something
about regularity inheritance for subsets of order opnq, a regime in which Lemma 3.4 tells us
nothing.

Lemma 3.6 (Corollary 3.5 in [33]). For all 0 ă β, ε1 , γ ă 1, there exist positive constants
ε0 “ ε0 pβ, ε1 , γq and D “ Dpε1 q such that, for every 0 ă ε ď ε0 and p “ ppnq P p0, 1q, the random
graph Γ „ Gn,p w.h.p. has the following property. Suppose G Ď Γ and pV1 , V2 q is an pε, pq-regular
pair of density d ě γp with respect to G. Then, for all q1 , q2 ě Dp´1 log n, there are at least
ˆ ˙ˆ ˙
` mintq1 ,q2 u
˘ |V1 | |V2 |
1´β
q1 q2

sets Qi Ď Vi of order |Qi | “ qi , i P t1, 2u, which induce an pε1 , pq-regular pair of density p1 ˘ ε1 qd
with respect to G.

Intuitively, Lemma 3.6 tells us that if we have an pε, pq-regular pair pV1 , V2 q with respect to
a subgraph of Gn,p and two vertices v and w which have neighbourhoods of order Θpnpq in
V1 and V2 , respectively, then, for p “ Ωpplog n{nq1{2 q, it is extremely unlikely that these two
neighbourhoods do not inherit regularity. In fact, it is so unlikely that a union bound over all
possible situations suffices to prove Lemma 3.5.

Proof of Lemma 3.5. We only prove that there exists a B which ensures that pNv , Nw q is always
pε1 , pq-regular with the required density. The other case follows from similar calculations, so we
omit it.

5
For two disjoint subsets V1 , V2 Ď V pΓq of order ñ, let EpV1 , V2 q be the event that there exists
G Ď Γ for which the conclusion of the lemma fails for this particular choice of V1 and V2 . We
will show that PrrEpV1 , V2 qs ď expp´cñ2 pq for some c ą 0, which is more than enough to beat
the union bound over all choices of V1 and V2 .
Suppose G is a witness for EpV1 , V2 q. Consider the following process: start with B “ ∅ and
B “ ∅ and, as long as there exist (not necessarily distinct) vertices v, w P V pGq r pB Y V1 Y V2 q
which violate the desired property, add the pair pv, wq to B and add v and w to B. As soon as
|B| becomes at least δñ, we stop the procedure. Note that the procedure must go on at least
this long, by the choice of G. Then B contains at least δñ{2 and at most δñ pairs.
Therefore, if G is a witness for EpV1 , V2 q, then there exists a set of pairs of vertices B of size
δñ{2 ď |B| ď δñ such that all elements of B are pairwise disjoint and, for every pv, wq P B, there
exist Nv Ď NΓ pv, V1 q and Nw Ď NΓ pw, V2 q, both of order ñd{4, such that pNv , Nw q does not
span an pε1 , pq-regular pair of density p1 ˘ ε1 qd with respect to G. Let us bound the probability
that such a configuration exists in Gn,p .
We first expose the edges between V1 and V2 in Γ. Choose a subset E 1 Ď EΓ pV1 , V2 q of these
edges such that pV1 , V2 q is pε, pq-regular of density d ě γp with respect to E 1 . Conditioning on
|EΓ pV1 , V2 q| ď 2ñ2 p (which we may assume holds w.h.p. by a standard application of Chernoff’s
2
inequality and the union bound), there are at most 22ñ p choices for E 1 . Next, there are at
most δñ ¨ pn!q2 ă 23n log n choices for B. Finally, for each pv, wq P B, choose the ‘bad’ subsets
Nv Ď V1 and Nw Ď V2 of order x “ ñd{4. As pV1 , V2 q satisfies the conclusion of Lemma 3.6 and
ñd{4 ě D3.6 pε1 qp´1 log n by the assumption on p from the statement of the lemma and the fact
that K is sufficiently large, there are at most
ˆ ˆ ˙2 ˙|B|
ñ
βx
x

such choices. But we also need that each such set Nv lies in the neighbourhood of v in Γ and
similarly for Nw and w. Using the fact that any two pairs in B are disjoint and, within each pair,
we consider neighbours into disjoint sets V1 and V2 , the probability of this happening is exactly
p2|B|x . Putting all this together, we get that

ñ 2|B| 2|B|ñd{4
ˆ ˙
2ñ2 p 3n log n |B|ñd{4
PrrEpV1 , V2 qs ď 2 ¨2 ¨β ¨p .
ñd{4

Using the standard bound ab ď p ea

` ˘ b
b q , we conclude that by taking β sufficiently small we can
make this be at most expp´cñ2 pq, as desired.

3.1.2 The KLR conjecture in random graphs

The following result from [11] gives sufficient conditions for the existence of a small, fixed graph
between an appropriate collection of pε, pq-regular pairs in a random graph. This result also
follows from a celebrated conjecture of Kohayakawa, Luczak, and Rödl [24] (the so-called KLR
conjecture), which was fully resolved by Balogh, Morris, and Samotij [3] and, independently,
Saxton and Thomason [32] (though see the recent paper [28] for another proof). However, we
will only invoke the lemma when H is either a cycle or K4 , both of which were known before the
full conjecture was proved (see [16] and [17], respectively).

6
Lemma 3.7 (The KLR conjecture). For every graph H and every γ ą 0, there exist ε0 , K ą 0
such that, for every 0 ă ε ď ε0 and p ě Kn´1{m2 pHq , where
! epF q ´ 1 )
m2 pHq “ max : F Ď H, vpF q ě 3 ,
vpF q ´ 2
the random graph Γ „ Gn,p w.h.p. has the following property.
Suppose G Ď Γ and tVi uiPV pHq is a family of disjoint subsets of V pGq, each of order ñ ě
maxtpK{pqm2 pHq , K log n{pu. Suppose also that, for each ij P H, the pair pVi , Vj q is pε, pq-regular
of density at least γp with respect to G. Then there exists a copy of H in G which maps each
vertex i to Vi .

Sketch of the proof. Theorem 1.6 in [11] gives K ą 1 such that the conclusion of the lemma holds
with probability at least 1 ´ expp´bn2 pq in the special case where ñ “ n{vpHq, for some constant
b ą 0 depending on H and γ. As every subgraph of Gn,p with s vertices is distributed as Gs,p , we
can apply the above to such a subset as long as p ě Ks´1{m2 pHq or, equivalently, s ě pK{pqm2 pHq .
In particular, a subgraph of Gn,p induced by a vertex subset S of order s ě pK{pqm2 pHq fails to
have the required property in the case ñ “ s{vpHq with probability at most expp´bs2 pq. By
the assumption ñ ě K log n{p, and as we may assume K is sufficiently large in terms of b, this
probability is at most n´2s , which is sufficient to take a union bound over all possible choices of
S. As every pε, pq-regular constellation with each set of order ñ naturally lies in a subset S of
order vpHqñ, the claimed statement follows.

4 Trees and cycles through prescribed sets

In this section, we provide the two main building blocks used in the proof of Theorem 1.2. Both
results are stated in greater generality that what is needed for Theorem 1.2, with the goal of
making further claims in Section 6 more transparent.
Our first building block says that, under appropriate conditions, one can embed bounded-degree
trees so that each vertex is mapped into a prescribed set. The embedding strategy used both here
and in the main theorem, which we dub first-free-bucket embedding, originates from the second
author’s PhD thesis [27]. While the bound on p here could be lowered to, say, n´1{2 log3 n, we
have decided not to complicate the proof any further.
Lemma 4.1. For every α, γ, ξ ą 0 and ∆ P N, there exist c “ cpα, γ, ξ, ∆q, ε0 “ ε0 pγ, ∆q ą 0
such that, for every 0 ă ε ď ε0 and p ě n´1{2`ξ , the random graph Γ „ Gn,p w.h.p. has the
following property.
Let T be a tree with t ď cn vertices and maximum degree ∆. Let G Ď Γ and, for each v P V pT q,
let sv P V pGq be a specific vertex such that every s P V pGq is chosen at most ∆ times. Then,
for any collection of subsets Nv Ď NG psv q of order αnp such that pNv , Nw q is pε, pq-regular of
density d ě γp (with respect to G) for each vw P T , there exists a copy of T in G which maps
each v P V pT q to Nv .

Proof. By applying Lemma 3.3 and renaming the sets if necessary, we may assume that each
vertex in Nv has at least d|Nw |{2 neighbours in Nw for each vw P T and |Nv | ě ñ :“ 0.9αnp.
Ť
Let U “ vPV pT q Nv and take an equipartition U “ U0 Y U1 Y ¨ ¨ ¨ Y Uz uniformly at random,
where z “ r1{ξs. Let Nvj :“ Uj X Nv for all v P V pT q and j P t0, . . . , zu. By Chernoff’s inequality

7
and the union bound, there exists a choice for the Uj such that every vertex in Nv has at least
d|Nw |{p4zq neighbours in each Nwj for all vw P T . In other words, for every u P Nv , we have

|N̂G ptu, sw u, Nwj q| “ |NG pu, Nwj q| ě dñ{p4zq. (1)

Let tv1 , . . . , vt u be an ordering of the vertices of T such that each vi , for i ě 2, has exactly one
preceding neighbour and denote this neighbour by ai . For brevity, rename Nvji as Vij and svi as
si and, for every i P rts, let T ăi :“ tv1 , . . . , vi´1 u. We construct the desired copy of T by defining
an embedding ϕ as follows:
(E1) assign ϕpv1 q :“ x for an arbitrary vertex x P V10 ,
(E2) for every i ě 2, sequentially, take an arbitrary vertex x from the first (smallest j P
t0, . . . , zu) non-empty set NG pϕpai q, Vij q r ϕpT ăi q and assign ϕpvi q :“ x, or
(E3) if all such sets are empty, terminate.
If the process never reaches (E3), the embedding ϕ gives the desired copy of T . Therefore,
suppose towards a contradiction that there is some i P rts for which the process enters (E3), that
is, such that NG pϕpai q, Vij q r ϕpT ăi q “ ∅ for all j P t0, . . . , zu.
Let Xj :“ Uj X ϕpT ăi q, for all j P t0, . . . , zu, be the set of vertices in Uj ‘taken’ by the images of
tv1 , . . . , vi´1 u under ϕ. We claim that
cj n
|Xj | ď (‹)
pnp2 qj

for constants cj with c0 “ c “ α2 γ 2 {p106 ∆z 2 q and cj “ 400∆zcj´1 {pαγq for all j ě 1.

Under this assumption, since pnp2 qz ě n2 , we get that Xz “ ∅ and thus NG pϕpai q, Viz qrϕpT ăi q ‰
∅, contradicting our assumption that (E3) happens at step i. Therefore, in order to complete
the proof, it only remains to show (‹).
Clearly, |X0 | ď c0 n as t ď cn. Consider now the smallest j P rzs for which (‹) is violated.
Without loss of generality, we may assume that |Xj | “ rcj n{pnp2 qj s (if not, we can take a subset
of Xj of precisely that order). Let I Ď ri ´ 1s be the set of indices of vertices vk P T ăi that are
embedded into Xj , i.e.,
I :“ tk P ri ´ 1s : ϕpvk q P Xj u.
Since ∆pT q ď ∆ and each sk P V pGq is chosen at most ∆ times, there exists (by greedily taking
indices) I 1 Ď I of size at least |I|{p4∆q such that the sets tϕpak q, sk u are pairwise disjoint for all
k P I 1 . For simplicity in our notation, we will assume that I already has this property, noting
that |I| ě |Xj |{p4∆q. For every k P I, we set Pk “ tϕpak q, sk u.
Since, for every k P I, the vertex vk is embedded into Xj and not Xj´1 , we have
ˇď ˇ
N̂G pPk , Vkj´1 qˇ.
ˇ ˇ
|Xj´1 | ě ˇ
kPI

Our goal is to show that this implies Xj´1 is larger than what is claimed in (‹), contradicting
our assumption that j is the smallest index violating (‹).
As N̂G pPk , Vkj´1 q Ď N̂G pPk q Ď N̂Γ pPk q, we have
ˇď ˇ ˇď ˇ ˇď` ˘ˇˇ
N̂G pPk , Vkj´1 qˇ ě ˇ N̂Γ pPk qˇ ´ ˇ N̂Γ pPk q r N̂G pPk , Vkj´1 q ˇ. (2)
ˇ ˇ ˇ ˇ ˇ
ˇ
kPI kPI kPI

8
Note that |I| ď |Xj | and that |Xj | ď rc1 {p2 s for j “ 1 and |Xj | “ op1{p2 q for j ě 2. Hence, by
Lemma 3.1 with d “ 2, δ “ 2c1 , and P “ tPk ukPI , the first term on the right-hand side of (2)
can be bounded by ˇď ˇ
N̂Γ pPk qˇ ě p1 ´ δq|I|np2 .
ˇ ˇ
ˇ
kPI

Lemma 3.1 also gives |N̂Γ pPk q| ď p1 ` δqnp2 . Combining the previous two bounds with (1), we
get that

|Xj´1 | ě p1 ´ δq|I|np2 ´ |I| p1 ` δqnp2 ´ dñ{p4zq ě |I|dñ{p8zq ą |I|αγnp2 {p100zq,

` ˘

where we used that c1 ď αγ{p300zq. Finally, from |I| ě |Xj |{p4∆q and |Xj | “ rcj n{pnp2 qj s, we
arrive at
cj n αγnp2 cj´1 n
|Xj´1 | ą 2 j
¨ ě ,
4∆pnp q 100z pnp2 qj´1
which contradicts our assumption that j was the smallest index violating (‹).

The following lemma gives the same statement when T is a cycle Ct instead of a tree. Here, the
bound on p comes from the fact that we apply Lemma 3.7 with ñ “ Θpnpq, for which we need
` ˘
p “ Ω pnpq´1{m2 pCt q .

Lemma 4.2. For every α, γ ą 0 and ` ě 3, there exist ε0 “ ε0 pγ, `q, c “ cpα, γ, `q, K “
Kpα, γ, `q ą 0 such that the statement of Lemma 4.1 holds if T is a cycle of length t P r`, cns
and p ě Kn´p`´2q{p2`´3q .

Sketch of the proof. We first deal with the case where T is a cycle of length t P r`, 4`s. Greedily
take Nv1 Ď Nv , each of order |Nv1 | “ |Nv |{p2tq, such that they are pairwise disjoint. By Lemma 3.4,
these sets are pε1 , pq-regular with density close to d and so Lemma 3.7 implies the existence of
the desired copy of T .
The case t ą 4` requires a bit more work. Let us denote the vertices of T by v1 , . . . , vt , in the
natural order. Again, for each i P t1, . . . , ` ` 1u Y tt, . . . , t ´ ` ` 1u, choose a subset Nv1 i Ď Nvi of
order |Nv1 i | “ |Nvi |{p4`q such that they are pairwise disjoint. Let V 1 be the union of all these
sets and, for every other v, set Nv1 “ Nv r V 1 . As pnp2 q` " np by the assumption on p, one
can expect that the `-th neighbourhood of each vertex v P Nv1 1 contains almost all vertices in
both Nv1 ``1 and Nv1 t´``1 . A minor modification of [13, Corollary 2.5] gives precisely this. Namely,
it shows that there exists a vertex v P Nv1 1 such that, for all but ε|Nv1 ``1 | vertices w P Nv1 ``1 ,
there exists a path from v to w (in G) with one vertex in each of Nv1 2 , . . . , Nv1 ` and similarly for
Nv1 t´``1 with paths through Nv1 t , . . . , Nv1 t´``2 . Let us denote the set of such vertices reachable
from v by Nv2``1 and Nv2t´``1 . Now we can apply Lemma 4.1 to find a path with one vertex in
each of Nv2``1 , Nv1 ``2 , . . . , Nv1 t´` , Nv2t´``1 . Together with the paths to v from Nv2``1 and Nv2t´``1 ,
this forms the desired cycle.

5 Proof of Theorem 1.2

Following the overview in Section 2, we first prove a decomposition result for cubic graphs.

Lemma 5.1. Let H be a connected cubic graph which is not isomorphic to K4 . Then there exists
a partition V pHq “ B1 Y ¨ ¨ ¨ Y Bt , for some t which depends on H, such that the following hold:

9
 • the subgraph of H induced by each Bi is either a path (of any length, even 0) or a cycle of
length at least four;
• for every i P t2, . . . , tu, each vertex in Bi has at most one neighbour in B1 Y ¨ ¨ ¨ Y Bi´1 .

Proof. For simplicity in the proof, we specify the Bi ’s in reverse order: for every i P t1, . . . , t ´ 1u,
each vertex in Bi will have at most one neighbour in Bi`1 Y ¨ ¨ ¨ Y Bt .
Let tBi uiPrms , for some m P N, be a maximal family of disjoint sets such that each Bi induces a
cycle of length at least four. Note that no matter how we specify the remaining sets, the desired
degree property holds for B1 , . . . , Bm due to H having maximum degree three.
Ť
Let H 1 “ H r iPrms Bi and set Bm`1 Ď V pH 1 q to be a largest subset which induces a path in
H 1 . We aim to show that each vertex in Bm`1 has at most one neighbour in R “ V pH 1 q r Bm`1 .
Suppose, towards a contradiction, that v P Bm`1 has two neighbours x, y P R, noting that v must
be an endpoint of the path H 1 rBm`1 s. Then both x and y necessarily have at least one more
neighbour in Bm`1 , as otherwise we could extend H 1 rBm`1 s to a longer path. Let vx P Bm`1 be
a neighbour of x in Bm`1 r tvu which is closest to v and define vy similarly, where the distance
is measured along the path H 1 rBm`1 s. If vvx is not an edge, then the path from v to vx in
H 1 rBm`1 s together with xv and xvx forms an induced cycle of length at least four, contradicting
the assumption that H 1 has no such cycle. Therefore, vvx is an edge and, similarly, vvy is an
edge. But then we must have that vx “ vy is the other endpoint of the path H 1 rBm`1 s and so
H 1 rBm`1 s consists of a single edge. Note also that xy is not an edge, as otherwise we would have
that H “ K4 . But then tx, v, yu forms an induced path longer than H 1 rBm`1 s, contradicting the
choice of Bm`1 . Therefore, each vertex in Bm`1 has at most one neighbour in R, as required.
We now repeat this process, first by considering a longest induced path in R, until the entire
vertex set is partitioned.

An example of a partition of V pHq as given by the procedure described above is depicted in

Figure 1.
B8

B3

B9
B6

B2

B4 B5 B
7
B1

Figure 1: An example of a graph H with a partition produced by Lemma 5.1.

We are now in a position to prove our main result. Recall the statement, that there exist c, K ą 0
such that if p ě Kn´2{5 , then, with high probability, Gn,p Ñ H for every cubic graph H with at
most cn vertices.

Proof of Theorem 1.2. As mentioned in Section 2, by following a standard reduction process,

it suffices to show that Γ „ Gn,p with high probability satisfies the following: if a subgraph

10
G Ď Γ contains disjoint sets of vertices V1 , . . . , V20 Ď V pGq, each of order |Vi | “ ñ “ αn for some
constant α ą 0, such that each pair pVi , Vj q is pε, pq-regular of density at least p{3 (with respect
to G), then G contains H. Here we take ε ą 0 to be as small as necessary for all our arguments
to go through. This influences the choice of α and, consequently, decides how small c has to be
(recall that H is a graph on cn vertices), but the exact dependencies are not important. We can
also assume that the density of each pair is exactly d “ p{3 (see [18, Lemma 4.3] or consider
taking a random subset of the edges). We take this as our starting point.
Using Lemma 3.7, we can find cn vertex-disjoint copies of K4 in G. Therefore, from now on we
can assume that H is K4 -free and connected. Let B1 Y ¨ ¨ ¨ Y Bt “ V pHq be a partition of V pHq
as given by Lemma 5.1 and let ϕ : V pHq Ñ r10s be an arbitrary colouring of H such that if v
and w are distinct vertices at distance at most two in H, then ϕpvq ‰ ϕpwq.
Remove from G the ‘bad’ set given by Lemma 3.5 for every choice of pVi , Vj q and, afterwards, take
the subsets given by Lemma 3.3. After ‘cleaning’ the sets V1 , . . . , V20 and subsequently renaming
what remains, we are left with sets tVi0 , Vi1 uiPr10s such that 0.9ñ ď |Vi˚ | ď ñ, for ˚ P t0, 1u, and
the following properties hold for pa, bq P t0, 1u2 :
(P1) degG pv, Vjb q ě ñd{2 for every v P Via and all i ‰ j;
(P2) for each i ‰ j and any two vertices v, w R Vi0 Y Vi1 Y Vj0 Y Vj1 , the pairs pNv , Vjb q and
pNv , Nw q are pε1 , pq-regular with density at least d{2 for any subsets Nv Ď NG pv, Via q and
Nw Ď NG pw, Vjb q of order ñd{4.
We sequentially embed the blocks B1 , . . . , Bt , where for each block Bi we do the following:
(Q1) For each v P Bi , let uv P V pGq be the image of its already embedded neighbour av from
B1 Y ¨ ¨ ¨ Y Bi´1 . Without loss of generality, we can assume that v always has such a
neighbour.
zv
` ˘
(Q2) Choose the smallest zv P t0, 1u such that NG uv , Vϕpvq has at least ñd{4 vertices which
are not already taken by the embedding of any vertex in B1 Y ¨ ¨ ¨ Y Bi´1 . If no zv P t0, 1u
has this property, terminate the procedure. Otherwise, let us denote the set of such ‘free’
neighbours of uv by Fv .
(Q3) As |Fv | ě ñd{4 for each v P Bi , property (P2) ensures that the conditions of Lemma 4.1
(‘tree embedding’) and Lemma 4.2 (‘cycle embedding’) are satisfied, so there exists a copy
of HrBi s in G which maps each vertex v P Bi into its corresponding set Fv . Fix such an
embedding of HrBi s and proceed. (Minor technical detail: here we used the fact that
if w P Bi is a neighbour of v P Bi , then ϕpav q ‰ ϕpwq, so that (P2) can be applied for
zv zw
Fv Ď Vϕpvq and Fw Ď Vϕpwq .)
Assuming that the procedure did not terminate in step (Q2), we have successfully found a copy
of H in G. It therefore remains to show that the process does not terminate early. As in the
proof of Lemma 4.1, we will again use the first-free-bucket embedding strategy. However, the
proof here is simpler as we only have two buckets to consider.
Recall that H has cn vertices, so the set X of all occupied vertices in V10 Y ¨ ¨ ¨ Y V10
0 is of order

at most cn. Let Z1 denote the vertices v P V pHq for which zv “ 1 (as defined in (Q2)) and
let U “ tuv : v P Z1 u. Then |Z1 | is an upper bound on the number of occupied vertices in
V11 Y ¨ ¨ ¨ Y V10
1 . We claim that |Z | “ Op1{pq, which, together with the fact that each u has
1 v
1
at least ñd{2 " 1{p neighbours in Vϕpvq (property (P1)), implies that the procedure does not
terminate in step (Q2).

11
Suppose, towards a contradiction, that |Z1 | “ 3C{p for a sufficiently large constant C and
so |U | ě C{p. Then, by (P1) and (Q2), we have that each vertex in U has at least ñd{4
neighbours in X. Hence, eG pU, Xq ě |U |ñd{4. On the other hand, for C sufficiently large, a
simple application of Chernoff’s inequality and the union bound implies that w.h.p. the number
of edges in Γ „ Gn,p between any set U of order at least C{p and any set X of order cn is at
most 2|U ||X|p. Therefore, since G Ď Γ (and taking a superset of X of sufficient size if necessary),
eG pU, Xq ď eΓ pU, Xq ă 2|U |cnp. Both the upper and lower bounds on eG pU, Xq are of the same
order of magnitude, but only the upper bound depends on c. Thus, for c sufficiently small with
respect to α (which is hidden in ñ), we get a contradiction.

6 Concluding remarks

As in [25], the proof of Theorem 1.2 easily extends to more than two colours and, more importantly,
it actually gives that in every q-colouring of Gn,p one of the colours is universal for the family
of cubic graphs with at most cn vertices, that is, it contains all such graphs simultaneously. It
is known that any graph with this property has to have Ωpn4{3 q edges (see, for instance, [1]).
In other words, in order to go past that bound, one has to consider different host graphs for
different H. However, we are nowhere near that bound yet.
Recall that the argument for why n8{5 is the best one can get from random graphs is that, for
p “ opn´2{5 q, a typical Gn,p is not Ramsey for K4 . However, K4 is the unique connected cubic
graph with a fixed number of vertices which requires such a bound on p: for any other such
graph, p “ Θpn´1{2 q suffices (see [29, 30]). Therefore, it is not inconceivable that by adding some
additional structure on top of the random graph to deal with the K4 ’s, one could obtain a bound
of type n8{5´ε or better.
Note that the only places where we used p ě Kn´2{5 in the proof of Theorem 1.2 were to invoke
Lemma 4.2 to embed C4 and to embed all components of H isomorphic to K4 . In particular,
if H does not contain K4 and we can ensure in Lemma 5.1 that all cycles are of length at
least five, then the same proof goes through with p “ Θpn´3{7 q. For longer cycles, this bound
decreases even further, being governed by the bound in Lemma 4.2. Thus, we have the following
improvements over Theorem 1.1.
Theorem 6.1. There exists a constant K such that r̂pHq ď Kn11{7 for every triangle-free cubic
graph H. Moreover, if H is a cubic bipartite graph, then r̂pHq ď Kn14{9 .

Sketch of the proof. We first show that if H is a connected triangle-free cubic graph with at
least 7 vertices, then it has a decomposition as in Lemma 5.1, but where each cycle is now of
length at least 5. Following the proof of Lemma 5.1, we start by removing from H a maximal
family of disjoint induced cycles of length at least 5. Let H 1 denote the resulting graph and,
for each vertex v P V pH 1 q of degree two (in H 1 ), add a temporary new vertex which is joined
only to v. Therefore, each vertex in this temporarily expanded H 1 has degree either zero, one,
or three. Consider a longest induced path in H 1 , say v1 , . . . , vt . We will show that it has the
desired property that every vi has at most one neighbour in V pH 1 q r tv1 , . . . , vt u, in which case
we can remove it from H 1 , together with all the temporary vertices, and proceed. Note that at
least one vertex in tv1 , . . . , vt u is an ‘original’ vertex, so we indeed make progress.
The only two vertices which can violate the desired property are v1 and vt . Without loss of
generality, consider v1 and suppose it has two neighbours x, y P V pH 1 q r tv2 u. Then both of these

12
vertices need to have a neighbour in tv2 , . . . , vt u, as otherwise we would get a longer induced
path. Let us denote such a neighbour of x closest to v by vx and of y by vy . Then we necessarily
have vx “ vy “ v3 , as otherwise we get an induced cycle of length at least 5. Therefore, the
longest induced path is of length two (i.e., t “ 3). As x has degree three, it must also have
another neighbour z, which, as H is triangle-free, lies outside of ty, v1 , v2 , v3 u (Figure 2).

x v1 v2 v3

z y

Figure 2: Finishing the decomposition.

Now we are almost done: if yz is not an edge, then we get a longer induced path y, v1 , x, z, while
if zv2 is not an edge, then we get the path z, x, v1 , v2 . We must therefore have that yz and zv2
are both edges, which implies that H 1 , without the temporary vertices, is a connected graph with
6 vertices where every vertex has degree three. But then H 1 “ H, contradicting our assumption
that H has at least 7 vertices.
Therefore, there exists a decomposition with each cycle being of length at least 5, as required.
Moreover, if H is bipartite, each such cycle has to have length at least 6. To embed H, we then
proceed by first embedding all connected components with at most 6 vertices using Lemma 3.7,
which is possible already at p “ Θpn´1{2 q, as no such component is isomorphic to K4 . To embed
cycles through subsets of order Θpnpq using Lemma 4.2, we require p “ Θppnpq´3{4 q if they are
of length at least 5 and p “ Θppnpq´4{5 q if they are of length at least 6, estimates which return
the required bounds on p. The rest of the proof is then identical to the proof of Theorem 1.2.

One can also obtain better bounds than those in [25] if H has a special structure. For example,
? ?
Clemens, Miralaei, Reding, Schacht, and Taraz [9] showed that if H is a n ˆ n grid, then
r̂pHq “ Opn3{2`op1q q, which is essentially the best one can get from random graphs in this case.
Our methods immediately imply this result, as the grid graph has a decomposition into induced
paths (given by ‘vertical’ lines) which admit a ‘1-degenerate’ ordering (i.e., the second property
of Lemma 5.1). One notable feature of this argument is that even though H has many copies of
C4 , we do not embed them directly using Lemma 4.2.
Finally, it is worth noting that the problem of improving the bound from [25] for general
bounded-degree graphs remains open. For the class of triangle-free graphs H with maximum
degree ∆, a rather convoluted argument from the second author’s PhD thesis [27] shows that
r̂pHq “ Opn2´1{∆´ε∆ q for some ε∆ ą 0. Regarding the methods presented here, analogues
of Lemmas 4.1 and 4.2 with each Nv now contained in the neighbourhood of at most ∆ ´ 2
vertices go through provided p “ Θpn´1{p∆´0.5q q. Moreover, an easy modification of the proof of
Lemma 5.1 shows that a connected graph H with maximum degree ∆, not isomorphic to K∆`1 ,
admits a decomposition into blocks B1 , . . . , Bt such that each Bi is either a path or a cycle of
length at least four and each vertex in Bi has at most ∆ ´ 2 neighbours in B1 Y ¨ ¨ ¨ Y Bi´1 . But,
since these are the main ingredients of our proof in the ∆ “ 3 case, why does the proof not go
through for larger ∆?
The answer is somewhat technical, but the heart of the matter is that, for ∆ “ 3, no two

13
vertices in Bi can have a common neighbour in Bi`1 Y ¨ ¨ ¨ Y Bt , which means that the inheritance
properties promised by Lemma 3.5 are sufficient to continue the embedding process. If ∆ ą 3,
it can happen that two (or more) vertices in Bi have such a common neighbour, which means
that much more care is needed to ensure that the candidate set for each vertex has the desired
size and that pairs inherit regularity in the correct way. It is entirely possible that this could be
done, but we have chosen not to pursue the matter here. Another, more concrete, reason we did
not pursue the matter further is that, if embedding K∆`1 is again the main obstacle, what one
would really like to show is that there are c, K ą 0 such that if p ě Kn´2{p∆`2q , then, with high
probability, Gn,p Ñ H for any graph H with at most cn vertices and maximum degree ∆. This
is Theorem 1.2 for ∆ “ 3, but it is almost certain that the techniques described here are not
sufficient to meet this bound for larger values of ∆.

References
[1] N. Alon and M. Capalbo. Optimal universal graphs with deterministic embedding. In Proceedings of
the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 373–378. ACM, New
York, 2008.
[2] N. Alon and Z. Füredi. Spanning subgraphs of random graphs. Graphs and Combinatorics, 8(1):91–94,
1992.
[3] J. Balogh, R. Morris, and W. Samotij. Independent sets in hypergraphs. Journal of the American
Mathematical Society, 28(3):669–709, 2015.
[4] J. Beck. On size Ramsey number of paths, trees, and circuits. I. Journal of Graph Theory, 7(1):115–129,
1983.
[5] J. Beck. On size Ramsey number of paths, trees and circuits. II. In Mathematics of Ramsey theory,
volume 5 of Algorithms Combin., pages 34–45. Springer, Berlin, 1990.
[6] S. Berger, Y. Kohayakawa, G. S. Maesaka, T. Martins, W. Mendonça, G. O. Mota, and O. Parczyk.
The size-Ramsey number of powers of bounded degree trees. Journal of the London Mathematical
Society, 103(4):1314–1332, 2021.
[7] C. Chvátal, V. Rödl, E. Szemerédi, and W. Trotter Jr. The Ramsey number of a graph with bounded
maximum degree. Journal of Combinatorial Theory, Series B, 34(3):239–243, 1983.
[8] D. Clemens, M. Jenssen, Y. Kohayakawa, N. Morrison, G. O. Mota, D. Reding, and B. Roberts. The
size-Ramsey number of powers of paths. Journal of Graph Theory, 91(3):290–299, 2019.
[9] D. Clemens, M. Miralaei, D. Reding, M. Schacht, and A. Taraz. On the size-Ramsey number of grid
graphs. Combinatorics, Probability and Computing, 30(5):670–685, 2021.
[10] D. Conlon, A. Ferber, R. Nenadov, and N. Škorić. Almost-spanning universality in random graphs.
Random Structures & Algorithms, 50(3):380–393, 2017.
[11] D. Conlon, W. T. Gowers, W. Samotij, and M. Schacht. On the KLR conjecture in random graphs.
Israel Journal of Mathematics, 203(1):535–580, 2014.
[12] N. Draganić, M. Krivelevich, and R. Nenadov. Rolling backwards can move you forward: on
embedding problems in sparse expanders. In Proceedings of the 2021 ACM-SIAM Symposium on
Discrete Algorithms (SODA), pages 123–134. Society for Industrial and Applied Mathematics (SIAM),
Philadelphia, PA, 2021.
[13] N. Draganić, M. Krivelevich, and R. Nenadov. The size-Ramsey number of short subdivisions.
Random Structures & Algorithms, 59(1):68–78, 2021.
[14] P. Erdős, R. J. Faudree, C. C. Rousseau, and R. H. Schelp. The size Ramsey number. Periodica
Mathematica Hungarica, 9(1-2):145–161, 1978.
[15] J. Friedman and N. Pippenger. Expanding graphs contain all small trees. Combinatorica, 7(1):71–76,
1987.
[16] S. Gerke, Y. Kohayakawa, V. Rödl, and A. Steger. Small subsets inherit sparse ε-regularity. Journal
of Combinatorial Theory, Series B, 97(1):34–56, 2007.

14
[17] S. Gerke, H. J. Prömel, T. Schickinger, A. Steger, and A. Taraz. K4 -free subgraphs of random graphs
revisited. Combinatorica, 27(3):329–365, 2007.
[18] S. Gerke and A. Steger. The sparse regularity lemma and its applications. In Surveys in combinatorics
2005, volume 327 of London Math. Soc. Lecture Note Ser., pages 227–258. Cambridge Univ. Press,
Cambridge, 2005.
[19] J. Han, M. Jenssen, Y. Kohayakawa, G. O. Mota, and B. Roberts. The multicolour size-Ramsey
number of powers of paths. Journal of Combinatorial Theory, Series B, 145:359–375, 2020.
[20] J. Han, Y. Kohayakawa, S. Letzter, G. O. Mota, and O. Parczyk. The size-Ramsey number of
3-uniform tight paths. Advances in Combinatorics, (5):1–12, 2021.
[21] P. E. Haxell, Y. Kohayakawa, and T. Luczak. The induced size-Ramsey number of cycles. Combinat-
orics, Probability and Computing, 4(3):217–239, 1995.
[22] S. Janson, T. Luczak, and A. Ruciński. Random graphs. Wiley-Interscience Series in Discrete
Mathematics and Optimization. Wiley-Interscience, New York, 2000.
[23] N. Kamčev, A. Liebenau, D. R. Wood, and L. Yepremyan. The size Ramsey number of graphs with
bounded treewidth. SIAM Journal on Discrete Mathematics, 35(1):281–293, 2021.
[24] Y. Kohayakawa, T. Luczak, and V. Rödl. On K4 -free subgraphs of random graphs. Combinatorica,
17(2):173–213, 1997.
[25] Y. Kohayakawa, V. Rödl, M. Schacht, and E. Szemerédi. Sparse partition universal graphs for graphs
of bounded degree. Advances in Mathematics, 226(6):5041–5065, 2011.
[26] S. Letzter, A. Pokrovskiy, and L. Yepremyan. Size-Ramsey numbers of powers of hypergraph trees
and long subdivisions. arXiv preprint arXiv:2103.01942, 2021.
[27] R. Nenadov. Ramsey and universality properties of random graphs. PhD thesis, ETH Zürich, 2016.
[28] R. Nenadov. A new proof of the KLR conjecture. arXiv preprint arXiv:2108.05687, 2021.
[29] V. Rödl and A. Ruciński. Lower bounds on probability thresholds for Ramsey properties. In
Combinatorics, Paul Erdős is eighty, Vol. 1, Bolyai Soc. Math. Stud., pages 317–346. János Bolyai
Math. Soc., Budapest, 1993.
[30] V. Rödl and A. Ruciński. Threshold functions for Ramsey properties. Journal of the American
Mathematical Society, 8(4):917–942, 1995.
[31] V. Rödl and E. Szemerédi. On size Ramsey numbers of graphs with bounded degree. Combinatorica,
20(2):257–262, 2000.
[32] D. Saxton and A. Thomason. Hypergraph containers. Inventiones Mathematicae, 201(3):925–992,
2015.
[33] N. Škorić, A. Steger, and M. Trujić. Local resilience of an almost spanning k-cycle in random graphs.
Random Structures & Algorithms, 53(4):728–751, 2018.

15