# Ramsey simplicity of random graphs

Simona Boyadzhiyska Institut für Mathematik, Freie Universität Berlin, Berlin,
Germany. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Dennis
Clemens Hamburg University of Technology, Institute of Mathematics, Hamburg,
Germany. E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>Shagnik
Das11footnotemark: 1 Pranshu Gupta22footnotemark: 2

###### Abstract

A graph $G$ is _$q$ -Ramsey_ for another graph $H$ if in any $q$-edge-
colouring of $G$ there is a monochromatic copy of $H$, and the classic Ramsey
problem asks for the minimum number of vertices in such a graph. This was
broadened in the seminal work of Burr, Erdős, and Lovász to the investigation
of other extremal parameters of Ramsey graphs, including the minimum degree.

It is not hard to see that if $G$ is minimally $q$-Ramsey for $H$ we must have
$\delta(G)\geq q(\delta(H)-1)+1$, and we say that a graph $H$ is _$q$ -Ramsey
simple_ if this bound can be attained. Grinshpun showed that this is typical
of rather sparse graphs, proving that the random graph $G(n,p)$ is almost
surely $2$-Ramsey simple when $\frac{\log n}{n}\ll p\ll n^{-2/3}$. In this
paper, we explore this question further, asking for which pairs $p=p(n)$ and
$q=q(n,p)$ we can expect $G(n,p)$ to be $q$-Ramsey simple. We resolve the
problem for a wide range of values of $p$ and $q$; in particular, we uncover
some interesting behaviour when $n^{-2/3}\ll p\ll n^{-1/2}$.

Keywords: Ramsey Theory, random graphs, minimum degree

##  1 Introduction

###  1.1 Minimum degrees of minimal Ramsey graphs

We say that a graph $G$ is _$q$ -Ramsey_ for another graph $H$, and write
$G\to_{q}H$, if, for any $q$-colouring of the edges of $G$, there exists a
_monochromatic_ copy of $H$, that is, a copy of $H$ whose edges all have the
same colour. The fundamental theorem of Ramsey [23] asserts that
$K_{n}\rightarrow_{q}H$ for sufficiently large $n$, and hence at least one
such graph $G$ exists for any choice of $H$ and $q$. It is then natural to
investigate the nature of graphs $G$ that are $q$-Ramsey for a given graph
$H$. As a first step in this direction, we can ask how large such a graph $G$
needs to be, leading us to the definition of the most well-studied concept
related to Ramsey graphs, the Ramsey number. In this language, the _$q$
-colour Ramsey number_ of a graph $H$, denoted $r_{q}(H)$, is defined as the
minimum number of vertices in a graph that is $q$-Ramsey for $H$. Over the
past few decades, this parameter has been studied extensively for various
choices of the graph $H$. Arguably the most important case is when $H$ is a
complete graph. It was shown by Erdős [10] and Erdős and Szekeres [11] that
$r_{2}(K_{t})$ is exponential in $t$; more precisely, they proved $2^{t/2}\leq
r_{2}(K_{t})\leq 2^{2t}$. Despite considerable effort over the past eighty
years, these remain essentially the best known bounds, with improvements only
in the lower-order terms; the current best lower bound is due to Spencer [28],
while the best upper bound was recently announced by Sah [27] (improving an
earlier bound of Conlon [7]).

In the 1970s, researchers began exploring other properties of Ramsey graphs,
and we shall be interested in the minimum degree, the study of which began
with the paper of Burr, Erdős, and Lovász [5]. Of course, since any supergraph
of a $q$-Ramsey graph for $H$ is itself $q$-Ramsey for $H$, the question of
determining the smallest possible minimum degree among _all_ $q$-Ramsey graphs
for $H$ is rather uninteresting: we can always add an isolated vertex and make
the minimum degree zero. To avoid such trivialities, we restrict our attention
to the subcollection $\mathcal{M}_{q}(H)$ of minimal Ramsey graphs. We say
that $G$ is a _minimal $q$-Ramsey_ graph for $H$ if $G$ is $q$-Ramsey for $H$
and contains no proper subgraph with this property. In other words, removing
any edge or vertex destroys the Ramsey property of the graph. We can then
define the parameter $s_{q}(H)$, introduced in [5] for $q=2$, as the smallest
minimum degree among all minimal $q$-Ramsey graphs for $H$; that is,

$\displaystyle s_{q}(H)=\min\\{\delta(G):G\in\mathcal{M}_{q}(H)\\},$

where as usual $\delta(G)$ denotes the minimum degree of $G$.

When studying this parameter, there are a couple of easy general bounds one
can give. For an upper bound, observe that since, by definition,
$K_{r_{q}(H)}\rightarrow_{q}H$, any minimal $q$-Ramsey subgraph of this
complete graph bears witness to the fact that $s_{q}(H)\leq r_{q}(H)-1$. From
below, as observed by Fox and Lin [14], a simple argument using the pigeonhole
principle shows $s_{q}(H)\geq q(\delta(H)-1)+1$. Note that these bounds are
typically very far apart: when $H=K_{t}$, for instance, the lower bound is
linear in $t$ while the upper bound is exponential.

In the original paper of Burr, Erdős, and Lovász [5], the authors showed that
$s_{2}(K_{t})=(t-1)^{2}$, a surprising result for two reasons. First, while
the two-colour Ramsey number of $K_{t}$ is still unknown for any $t\geq 5$, we
can determine $s_{2}(K_{t})$ precisely. Second, $s_{2}(K_{t})$ is
significantly smaller than $r_{2}(K_{t})$. Informally, this means that a large
Ramsey graph for $K_{t}$ can have a vertex of very low degree whose removal
destroys the Ramsey property.

Since its introduction in [5], the parameter $s_{q}(H)$ has been studied for a
number of different choices of $H$ and for larger $q$; see, for example, [2,
4, 12, 13, 14, 17, 18, 19, 20, 29]. To the best of our knowledge, in all cases
studied the value of $s_{q}(H)$ is far away from the trivial upper bound. On
the other hand, the lower bound of Fox and Lin [14] has been shown to be tight
for many graphs. Following Grinshpun [18], we call such a graph _$q$ -Ramsey
simple_.

######  Definition 1.1.

A graph $H$ without isolated vertices is said to be _$q$ -Ramsey simple_ if

$\displaystyle s_{q}(H)=q(\delta(H)-1)+1.$

If $H$ has isolated vertices, then we say that $H$ is $q$-Ramsey simple if the
graph obtained from $H$ by removing all isolated vertices is $q$-Ramsey
simple.

Observe that adding isolated vertices to a graph does not affect the structure
of the corresponding Ramsey graphs significantly. Indeed, if $H$ is a graph
without isolated vertices and $H+tK_{1}$ is the graph obtained from $H$ by
adding $t\geq 0$ isolated vertices, it is not difficult to check that
$G\in\mathcal{M}_{q}(H)$ if and only if
$G+sK_{1}\in\mathcal{M}_{q}(H+tK_{1})$, where $s=\max\\{0,t-(v(G)-v(H))\\}$.

Previous work by Fox and Lin [14], Szabó, Zumstein, and Zürcher [29], and
Grinshpun [18] has established the $2$-Ramsey simplicity of a wide range of
bipartite graphs. Further results were proven in [4], including the $q$-Ramsey
simplicity of all cycles of length at least four, for any number of colours
$q\geq 2$. Based on these results, it is believed that simplicity is a more
widespread phenomenon.

######  Conjecture 1.2 (Szabó, Zumstein, and Zürcher [29]).

Every bipartite graph is $2$-Ramsey simple.

The conjecture suggests that Ramsey simplicity is quite common, but it is
natural to wonder whether this extends beyond the bipartite setting, given
that we know cliques are not simple. Are cliques an exceptional case, or is
$q$-Ramsey simplicity atypical for non-bipartite graphs? In somewhat more
precise terms, when can we expect the $n$-vertex binomial random graph
$G(n,p)$, where every edge appears independently with probability $p$, to be
$q$-Ramsey simple?

###  1.2 Random graphs

Random graphs have long played an important role in Ramsey Theory: Erdős’s
famous exponential lower bound on the Ramsey numbers of complete graphs in
[10] came from analysing the clique and independence numbers of random graphs,
while a key ingredient in the best modern upper bounds is showing that large
Ramsey graphs must be random-like. When it comes to more general Ramsey
problems, the work of Rödl and Ruciński [24, 25] establishes, for a given
graph $H$ and number of colours $q$, the range of values of $p$ for which we
have $G(n,p)\rightarrow_{q}H$ with high probability.

In these seminal papers, which have inspired a great deal of subsequent
research, the random graph plays the role of the host graph $G$, while the
target graph $H$ is fixed in advance. Surprisingly, there has been
considerably less work in the setting where the target graph $H$ is itself
random. When $H\sim G(n,p)$, Fox and Sudakov [15] and Conlon [8] provide some
lower and upper bounds on $r_{2}(H)$ for different ranges of $p$, while
Conlon, Fox, and Sudakov [9] show that $\log r_{2}(H)$ is well-concentrated.

In this paper we shall focus on the minimum degree of Ramsey graphs for the
random graph $G(n,p)$, with the goal of determining when it is $q$-Ramsey
simple. This line of research was initiated by Grinshpun [18], who proved that
sparse random graphs are 2-Ramsey simple with high probability.

######  Theorem 1.3 (Corollary 2.1.4 in [18]).

Let $p=p(n)\in(0,1)$ and $H\sim G(n,p)$. If $\frac{\log n}{n}\ll p\ll
n^{-2/3}$, then a.a.s. $H$ is $2$-Ramsey simple.

In this range of edge probabilities the random graph is almost surely not
bipartite (in fact, its chromatic number is unbounded), showing that
Conjecture 1.2 does not tell the full story. Moreover, the argument in [18]
can easily be extended to provide, for any fixed $q\in\mathbb{N}$, $q$-Ramsey
simplicity for $G(n,p)$ in the above range of $p$. This begs two natural
questions: what happens when the number of colours $q$ grows with $n$, and
what happens in other ranges of the edge probability $p$?

###  1.3 Results

In this paper, we settle this question for a wide range of parameters, but in
order to present our results, we need to introduce some notation.

We first remark that the parameter $s_{q}(H)$ and the notion of Ramsey
simplicity are not monotone in the graph $H$. As we shall observe in Section
2, a Ramsey simple graph can have both subgraphs and supergraphs that are
themselves not Ramsey simple, while a graph that is not Ramsey simple can have
simple subgraphs and supergraphs. However, we do have monotonicity in the
number of colours $q$, and we shall demonstrate that $(q+1)$-Ramsey simplicity
implies $q$-Ramsey simplicity. Hence, we can ask for a threshold value for
$q$, i.e., the largest number $\tilde{q}$ of colours for which a given graph
is $\tilde{q}$-Ramsey simple. We set

$\tilde{q}(H):=\sup\\{q:\;H\text{ is $q$-Ramsey simple}\\}.$

Note that every graph is, by definition, $1$-Ramsey simple, since the only
minimal $1$-Ramsey graph for $H$ is $H$ itself, and so $s_{1}(H)=\delta(H)$.
Thus, when a graph $H$ is not $q$-Ramsey simple for any number of colours
$q\geq 2$, we have $\tilde{q}(H)=1$. At the other extreme, if $H$ is
$q$-Ramsey simple for any number of colours $q$, we have
$\tilde{q}(H)=\infty$.

Given this notation, we can now state our main theorem, which collects various
bounds we were able to prove for the threshold $\tilde{q}(H)$ when $H\sim
G(n,p)$.

######  Theorem 1.4.

Let $p=p(n)\in(0,1)$ and $H\sim G(n,p)$. Let $u\in V(H)$ be a vertex of
minimum degree $\delta(H)$ and let $F=H[N(u)]$ be the subgraph of $H$ induced
by the neighbourhood of $u$. Denote by $\lambda(F)$ the order of the largest
connected component in $F$. Then a.a.s. the following bounds hold:

  1. (a)

$\tilde{q}(H)=\infty$ if $0<p\ll n^{-1}$.

  2. (b)

$\tilde{q}(H)=\infty$ if $\frac{\log n}{n}\ll p\ll n^{-\frac{2}{3}}$.

  3. (c)

$\tilde{q}(H)\geq(1+o(1))\max\left\\{\frac{\delta(H)}{\lambda(F)^{2}},\frac{\delta(H)}{80\log
n}\right\\}$ if $n^{-\frac{2}{3}}\ll p\ll n^{-\frac{1}{2}}$.

  4. (d)

$\tilde{q}(H)\leq(1+o(1))\min\left\\{\frac{\delta(H)}{\Delta(F)},\frac{\delta(H)^{2}}{2e(F)}\right\\}$
if $n^{-\frac{2}{3}}\ll p\ll 1$.

  5. (e)

$\tilde{q}(H)=1$ if $\left(\frac{\log n}{n}\right)^{1/2}\ll p<1$.

As shown above, we extend Theorem 1.3 by showing that these sparse random
graphs are not just $q$-Ramsey simple for any fixed $q$, but even when the
number of colours $q$ is allowed to grow with $n$. On the other hand, we prove
that much denser random graphs are not simple for any number of colours $q\geq
2$. Thus, both extremes are observed for different edge probabilities. Most
interestingly, though, the simplicity threshold for random graphs of
intermediate density depends on some parameters of the random graph itself —
these graphs are $q$-Ramsey simple for small values of $q$, but not when $q$
grows too large.

######  Remark 1.5.

As suggested by the above bounds, this dependence on $q$ is governed by the
subgraph $F$, and it is the appearance of edges in $F$ that gives rise to a
finite bound on $\tilde{q}(H)$. When $p\ll n^{-\frac{2}{3}}$, then $F$ almost
surely has no edges, while if $p\gg n^{-\frac{2}{3}}$, then $F$ almost surely
does, explaining the distinction between cases (b) and (d). When
$p=\Theta\left(n^{-\frac{2}{3}}\right)$, then $F$ is empty (and $\tilde{q}(H)$
thus infinite) with probability bounded away from $0$ and $1$.

When $n^{-\frac{2}{3}}\ll p\ll\left(\frac{\log n}{n}\right)^{\frac{1}{2}}$, by
analysing the structure of random graphs, we can give quantitative estimates
for the bounds on $\tilde{q}(H)$ in this intermediate range.

######  Corollary 1.6.

Let $k\geq 2$ be a fixed integer and let $f=f(n)$ satisfy $1\ll f=n^{o(1)}$.
Let $p=p(n)$ satisfy $n^{-\frac{2}{3}}\ll p\ll\left(\frac{\log
n}{n}\right)^{\frac{1}{2}}$ and let $H\sim G(n,p)$. Then a.a.s. the following
bounds hold:

  1. (a)

if $n^{-\frac{k}{2k-1}}\ll p\ll n^{-\frac{k+1}{2k+1}}$, then
$(1+o(1))\frac{np}{k^{2}}\leq\tilde{q}(H)\leq(1+o(1))\frac{np}{k-1}$.

  2. (b)

if $p=\Theta\left(n^{-\frac{k+1}{2k+1}}\right)$, then
$(1+o(1))\frac{np}{(k+1)^{2}}\leq\tilde{q}(H)\leq(1+o(1))\frac{np}{k-1}.$

  3. (c)

if $p=n^{-\frac{1}{2}}f^{-1}$, then $(1+o(1))\frac{np}{\log
n}\max\left\\{\frac{16\log^{2}f}{\log
n},\frac{1}{80}\right\\}\leq\tilde{q}(H)\leq(2+o(1))\frac{np\log(f^{2}\log
n)}{\log n}$.

  4. (d)

if $n^{-\frac{1}{2}}\ll p\ll\left(\frac{\log n}{n}\right)^{\frac{1}{2}}$, then
$1\leq\tilde{q}(H)\leq(8+o(1))\frac{1}{p}$.

Corollary 1.6 shows that, for fixed $\varepsilon>0$ and $n^{-\frac{2}{3}}\ll
p\ll n^{-\frac{1}{2}-\varepsilon}$, we determine the threshold up to a
constant factor, while for $n^{-\frac{1}{2}-o(1)}$, we know it up to a
polylogarithmic factor. Most surprisingly, these bounds reveal that the
threshold $\tilde{q}(H)$ evolves in a complicated fashion: while it drops from
$\infty$ to $1$ as $p$ ranges from $\frac{\log n}{n}$ to $1$, it does not do
so in a monotone fashion, as it must increase in the ranges
$p\in\left(n^{-\frac{k}{2k-1}},n^{-\frac{k+1}{2k+1}}\right)$ for each fixed
$k$. These results are illustrated in Figure 1.1.

Figure 1.1: Bounds on the simplicity threshold $\tilde{q}(G(n,p))$

###  1.4 Organisation of the paper

In Section 2 we discuss the monotonicity of Ramsey simplicity, and shall in
particular justify the definition of the threshold $\tilde{q}(H)$. We then
turn to random graphs, and in Section 3 collect properties of random graphs
needed to derive Corollary 1.6 from Theorem 1.4. The constructions of Ramsey
graphs that establish the lower bounds in Theorem 1.4 are provided in Section
4, while the upper bounds on $\tilde{q}(H)$ are proven in Section 5. The final
section, Section 6, is devoted to concluding remarks and open problems.

###  1.5 Notation

The notation used in this paper is mostly standard, except that for a graph
$G$, we write $\lambda(G)$ for the order of the largest connected component in
$G$. Throughout the paper, a $q$-colouring is an edge-colouring of a given
graph with $q$ colours and, unless otherwise specified, we will take $[q]$ to
be our colour palette.

##  2 Monotonicity in $q$

In this section we will prove that the property of being $q$-Ramsey simple is
monotone decreasing in the number of colours; that is, we will show that if a
graph is not $q$-Ramsey simple for some $q$, then it cannot be
$q^{\prime}$-Ramsey simple for any $q^{\prime}\geq q$.

######  Lemma 2.1.

If $H$ is not $q$-Ramsey simple, then $H$ is not $(q+1)$-Ramsey simple.

Note that $q$-Ramsey simplicity does not observe any monotonicity with respect
to the graph $H$. Indeed, we know that any tree on $t$ vertices is $2$-Ramsey
simple, whereas the clique $K_{t}$ is not. Similarly, there exist graphs that
are $q$-Ramsey simple but contain subgraphs that are not. For instance,
Theorem 2.1.3 in [18] shows that any 3-connected graph $H$ containing a vertex
$v$ of minimum degree such that $N(v)$ is contained in an independent set of
size $2\delta(H)-1$ is 2-Ramsey simple. Hence, while $K_{\delta}$ for
$\delta\geq 3$ is not $2$-Ramsey simple, the following supergraph of it is:
add $2\delta-1$ new vertices to $K_{\delta}$ with a complete bipartite graph
connecting them to the clique, and then add another vertex $v$ connected to
exactly $\delta$ of the $2\delta-1$ new vertices.

###### Proof of Lemma 2.1.

Assume $H$ is not $q$-Ramsey simple, that is, $s_{q}(H)>q(\delta(H)-1)+1$.
Suppose for a contradiction that there exists a graph
$G\in\mathcal{M}_{q+1}(H)$ such that $G$ contains a vertex $v$ of degree
$(q+1)(\delta(H)-1)+1$. Let $e$ be an arbitrary edge incident to $v$.

By the minimality of $G$, we know that the graph $G-e$ has an $H$-free
$(q+1)$-colouring $c$. Now, if there are at most $\delta(H)-2$ edges that are
incident to $v$ and have colour $q+1$ under $c$, then we can give $e$ colour
$q+1$ to obtain an $H$-free $(q+1)$-colouring of $G$, contradicting
$G\in\mathcal{M}_{q+1}(H)$. Hence we may assume that there are at least
$\delta(H)-1$ edges incident to $v$ that have colour $q+1$. Let $G_{0}$ be the
subgraph of $G$ containing all edges that have colours in $[q]$ under $c$
together with the edge $e$, i.e., $G_{0}=G-c^{-1}(q+1)$. We then know that
$d_{G_{0}}(v)\leq(q+1)(\delta(H)-1)+1-(\delta(H)-1)=q(\delta(H)-1)+1<s_{q}(H)$.
If $G_{0}$ is not $q$-Ramsey for $H$, then $G_{0}$ has an $H$-free
$q$-colouring $c^{\prime}$, and extending $c^{\prime}$ to the graph $G$ by
colouring the edges in $E(G)\setminus E(G_{0})$ with colour $q+1$ gives an
$H$-free $(q+1)$-colouring of $G$, a contradiction. Therefore,
$G_{0}\rightarrow_{q}H$.

But $d_{G_{0}}(v)<s_{q}(H)$, so $G_{0}$ cannot be minimal $q$-Ramsey for $H$,
and in particular, the vertex $v$ cannot be part of a minimal $q$-Ramsey
subgraph of $G_{0}$. Thus $G_{0}-v\rightarrow_{q}H$. But the restriction of
$c$ to $G_{0}-v$ is $H$-free by our choice of $c$, which again leads to a
contradiction.

Hence, $H$ cannot be $(q+1)$-Ramsey simple. ∎

##  3 Properties of $G(n,p)$

In this section we shall establish various properties of the random graph
$G(n,p)$ needed for the proof of Theorem 1.4 and the deduction of Corollary
1.6.

###  3.1 Facts about $G(n,p)$

We start with some bounds on the degrees and edge distribution in the random
graph, for which we require the following well-known concentration bounds due
to Chernoff (see [22, Theorem 2.3] and [16, Theorem 22.6]).

######  Lemma 3.1.

Let $X\sim Bin(n,p)$ and $\mu=\mathbb{E}[X]$.

  1. (a)

If $0<\varepsilon<1$, then
$\mathbb{P}(X\geq(1+\varepsilon)\mu)\leq\exp{(\frac{-\mu\varepsilon^{2}}{3})}$
and
$\mathbb{P}(X\leq(1-\varepsilon)\mu)\leq\exp{(\frac{-\mu\varepsilon^{2}}{2})}$.

  2. (b)

For all $t\geq 7\mu$ we have $\mathbb{P}(X\geq t)\leq\exp(-t)$.

With these concentration results, we can specify how many edges the random
graph is likely to have. This is done in the following lemmas, which collect
some folklore bounds on the degrees and number of edges in $G(n,p)$. We start
by controlling the degrees.

######  Lemma 3.2 (Degrees in $G(n,p)$).

Let $p=p(n)\in(0,1)$, and let $H\sim G(n,p)$. Then a.a.s. the following bounds
on the maximum degree hold:

  1. (a)

for any fixed integer $k\geq 2$, we have $\Delta(H)\geq k-1$ when $p\gg
n^{-\frac{k}{k-1}}$, and

  2. (b)

for any $f=f(n)$ satisfying $1\ll f=n^{o(1)}$, we have
$\Delta(H)\geq\frac{\log n}{\log(f\log n)}$ when $p=\frac{1}{nf}$.

Moreover, if $p\gg\frac{\log n}{n}$, then with probability at least $1-n^{-2}$
we have

  1. (c)

$d_{H}(v)=(1\pm o(1))np$ for every $v\in V(H)$.

###### Proof.

If $p\gg n^{-\frac{k}{k-1}}$ for any integer $k\geq 2$, then it follows from a
simple second moment calculation that $H$ a.a.s. contains a star with $k-1$
edges, and hence $\Delta(H)\geq k-1$; see Theorem 5.3 in [16] for more
details.

Part (b) can be obtained from a similar application of the second moment
method. For simplicity, we apply Theorem 3.1 (ii) from [3], stating that, if
$n^{-3/2}\ll p\ll 1-n^{-3/2}$ and the expected number of vertices of degree
$d=d(n)$ in $H\sim G(n,p)$ tends to infinity, then with high probability $H$
contains at least one vertex of degree $d$.

For $p=\frac{1}{nf}$ and $d=\frac{\log n}{\log(f\log n)}$, we can lower bound
the expected number of vertices of degree $d$ by

$\displaystyle n\binom{n-1}{d}p^{d}(1-p)^{n-1-d}$ $\displaystyle\geq
n\left(\frac{(n-1)p}{d}\right)^{d}(1-np)\geq\tfrac{1}{2}n\left(\frac{1}{2fd}\right)^{d}$
$\displaystyle=\frac{1}{2}e^{\log n-d\log(2fd)}=\frac{1}{2}e^{\frac{\log
n}{\log(f\log n)}\left(\log\log\sqrt{f\log n}\right)}$

which tends to infinity. Thus we must have at least one vertex of degree $d$,
and hence $\Delta(H)\geq d$.

Part (c) follows by applying Lemma 3.1(a) to the degree of each vertex, and
then taking a union bound over all $n$ vertices. ∎

We can also bound the number of edges, both globally and, provided the edge
probability is not too low, in all large induced subgraphs.

######  Lemma 3.3 (Edge counts in $G(n,p)$).

Let $p=p(n)\in(0,1)$ with $p\gg n^{-2}$, and let $H\sim G(n,p)$. Then a.a.s.
the following statements hold:

  1. (a)

$e(H)=(1\pm o(1))\frac{n^{2}p}{2}$, and

  1. (b)

if $p\gg\frac{\log n}{n}$, then with probability at least $1-n^{-2}$, every
set $S\subseteq V(H)$ of size $s\geq\frac{20\log n}{p}$ satisfies
$e_{H}(S)\geq\frac{1}{4}s^{2}p$.

###### Proof.

Part (a) follows directly from Lemma 3.1(a). For part (b), we take a union
bound over all sets $S$ of $s$ vertices, again applying Lemma 3.1(a) to bound
the probability that such a set contains too few edges. This results in a
bound of

$\displaystyle\sum_{s=\frac{20\log
n}{p}}^{n}\binom{n}{s}e^{-\frac{1}{16}(1-o(1))s^{2}p}\leq\sum_{s=\frac{20\log
n}{p}}^{n}e^{s\log n-\frac{1}{16}(1-o(1))s^{2}p}\leq\sum_{s=\frac{20\log
n}{p}}^{n}e^{-0.2s\log n}<n^{-2},$

proving the lemma. ∎

Aside from knowing how many edges the random graph contains, we shall also
need some knowledge about how they are distributed. The following result
describes the structure of sparse random graphs.

######  Lemma 3.4.

Let $p=p(n)\in(0,1)$ with $p\ll n^{-1}$, and let $H\sim G(n,p)$. Then a.a.s.
$H$ is a forest, and moreover the order $\lambda(H)$ of its largest component
satisfies the following bounds:

  1. (a)

$\lambda(H)\leq\log n$,

  2. (b)

if $p\ll n^{-\frac{k+1}{k}}$ for some constant $k\in\mathbb{N}$, then
$\lambda(H)\leq k$, and

  3. (c)

if $p=\frac{1}{nf}$ for some $f=f(n)$ satisfying $1\ll f=n^{o(1)}$, then
$\lambda(H)\leq(1+o(1))\frac{\log n}{\log f}$.

###### Proof.

That $H$ contains no cycles, and hence is a forest, can be shown by taking a
union bound over all possible cycles; see Theorem 2.1 in [16] for the details.
We now bound the orders of the trees in this forest. For part (a), we refer to
Lemma 2.12(ii) in [16], which asserts that with high probability a random
graph $H^{\prime}\sim G(n,e^{-2}n^{-1})$ contains no trees of order larger
than $\log n$. By monotonicity the same bound holds when $p\ll n^{-1}$. For
the bound in (b), notice that there are only a constant number of non-
isomorphic trees on $k+1$ vertices, and by a simple first moment calculation
(see Theorem 5.3 in [16]) each of these trees appears in $H$ with vanishing
probability when $p\ll n^{-\frac{k+1}{k}}$. The bound in part (c) can again be
obtained by running a first moment calculation, the details of which we now
sketch. As there are $k^{k-2}$ labelled trees on $k$ vertices, the total
possible number of tree components of order $k$ is $\binom{n}{k}k^{k-2}$. For
such a tree to appear as a subgraph, we need its $k-1$ edges to appear in
$G(n,p)$. Hence, the probability of seeing such a tree is at most

$\binom{n}{k}k^{k-2}p^{k-1}\leq\left(\frac{ne}{k}\right)^{k}\frac{(kp)^{k}}{k^{2}p}\leq
p^{-1}(nep)^{k}.$

For $p=\frac{1}{nf}$ and any $\varepsilon>0$, the sum of this expression over
all $k\geq(1+\varepsilon)\frac{\log n}{\log f}$ is at most

$p^{-1}\left(nep\right)^{(1+\varepsilon)\frac{\log n}{\log
f}}\left(\frac{1}{1-nep}\right)\leq 2e^{\log(nf)-(1+\varepsilon)\frac{\log
n}{\log f}(\log f-1)}\leq 2e^{-\frac{\varepsilon}{2}\log n}=o(1)$

and hence a.a.s. the largest component has order at most $(1+o(1))\frac{\log
n}{\log f}$. ∎

Switching to a much denser range, we find that when the edge probability is
sufficiently large, not only does $G(n,p)$ contain cycles, but every edge is
contained in a triangle.

######  Lemma 3.5.

Let $p=p(n)\in(0,1)$ be such that $p\gg\sqrt{\frac{\log n}{n}}$, and let
$H\sim G(n,p)$. Then a.a.s. every edge of $H$ is contained in a triangle.

###### Proof.

An easy application of the union bound gives

$\displaystyle\mathbb{P}\left(\exists e=uv\in E(H):\leavevmode\nobreak\
uv\leavevmode\nobreak\ \text{is not in a triangle}\right)$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}\left(\exists\\{u,v\\}\in\binom{V(H)}{2}:\leavevmode\nobreak\
uw\notin E(H)\leavevmode\nobreak\ \text{or}\leavevmode\nobreak\ vw\notin
E(H)\leavevmode\nobreak\ \text{for all }w\in V(H)\setminus\\{u,v\\}\right)$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\binom{n}{2}\cdot(1-p^{2})^{n-2}<e^{2\log n-p^{2}(n-2)}=o(1)\,,$

which proves the lemma. ∎

Finally, in our construction of minimal Ramsey graphs with vertices of low
degree, we shall make use of some mild pseudorandom properties concerning the
degrees, connectivity, and expansion of the target graph $H$. The required
properties are collected in the definition below.

######  Definition 3.6 (Well-behaved).

We say an $n$-vertex graph $H$ is _well-behaved_ if it satisfies the following
properties:

  1. (W 0 )

$H$ has a unique vertex $u$ of minimum degree $\delta(H)$,

  2. (W 0 )

every pair of vertices in $H$ has codegree at most $\tfrac{1}{2}\delta(H)$,

  3. (W 0 )

$H$ is $3$-connected, and

  4. (W 0 )

removing $\delta(H)$ vertices from $H$ cannot create a component of size
$k\in\left[\tfrac{1}{2}\delta(H),\tfrac{1}{2}n\right]$.

As might be expected, random graphs are highly likely to be well-behaved.

######  Lemma 3.7.

If $\frac{\log n}{n}\ll p\ll 1$ then a.a.s. $H\sim G(n,p)$ is well-behaved.

###### Proof.

The property (W 0 ) is established in Theorem 3.9(i) of [3]. Moreover, by
Lemma 3.2(c) we may condition on $\delta(H)=(1\pm o(1))np$ from now on. For
property (W 0 ), observe that the distribution of the codegree of a given pair
of vertices is $\mathrm{Bin}(n-2,p^{2})$. We consider two cases. If
$p^{2}\geq\frac{10\log n}{n}$ then by applying a Chernoff bound (Lemma 3.1(a))
we obtain $\mathbb{P}(d_{H}(u,v)\geq 2np^{2})\leq
e^{-\frac{1}{3}(n-2)p^{2}}<e^{-3\log n}$ for large $n$. Taking a union bound
over all $\binom{n}{2}$ pairs of vertices, this shows that with high
probability the maximum codegree is at most $2np^{2}<\tfrac{1}{2}\delta(H)$.
Otherwise $p^{2}\leq\frac{10\log n}{n}$ and then Lemma 3.1(b) yields
$\mathbb{P}(d_{H}(u,v)\geq 100\log n)\leq e^{-100\log n}$. We can then again
take a union bound over all pairs to show the maximum codegree is at most
$100\log n$, which, as $\delta(H)=(1\pm o(1))np\gg\log n$, is again less than
half the minimum degree.

Property (W 0 ) is shown to hold with high probability in Theorem 4.3 in [16].

This leaves us with property (W 0 ). Let us fix
$k\in\left[\tfrac{1}{2}\delta(H),\tfrac{1}{2}n\right]$, and bound the
probability that we can create a component $K$ of size $k$ by removing a set
$U$ of $\delta(H)$ vertices. In order for this to happen, there cannot be any
edges between $K$ and $V(H)\setminus\left(K\cup U\right)$. For given $K$ and
$U$, the probability of this is $(1-p)^{k(n-k-\delta(H))}$. Taking a union
bound over all possible components $K$ and cut-sets $U$, the probability that
property (W 0 ) fails for a given $k$ is at most

$\binom{n}{k}\binom{n}{\delta(H)}\left(1-p\right)^{k(n-k-\delta(H))}\leq
n^{k}n^{\delta(H)}e^{-pk(n-k-\delta(H))}\leq e^{(k+\delta(H))\log
n-\tfrac{1}{4}pkn},$

where the last inequality uses the bounds $k\leq\tfrac{1}{2}n$ and
$\delta(H)=(1\pm o(1))np\leq\tfrac{1}{4}n$. Now, since $p\gg\frac{\log n}{n}$,
we have $k\log n\ll pkn$, and, since $k\geq\tfrac{1}{2}\delta(H)$, we also
have $\delta(H)\log n\ll pkn$. Hence, we can bound this error probability by
$e^{-\frac{1}{8}pkn}=o(n^{-1})$, using again the fact that
$pkn\gg\delta(H)\log n$. Therefore, even after taking a union bound over all
possible values of $k$, we see that property (W 0 ) holds with high
probability. ∎

###  3.2 Transference lemma

As is evident in the statement of Theorem 1.4, our bounds on the simplicity of
$H\sim G(n,p)$ depend on the subgraph induced by the neighbourhood of the
minimum degree vertex (which, by virtue of Lemma 3.7 and property (W 0 ), we
may assume to be unique). Our next lemma allows us to transfer what we know
about the random graph $G(\delta(H),p)$ to this subgraph.

######  Lemma 3.8.

Let $p=p(n)\in(0,1)$ be such that $p\gg\frac{\log n}{n}$. For every
$s\in[0.5np,2np]$, let $\mathcal{P}_{s}$ be a graph property, and assume that
a random graph $G_{s}\sim G(s,p)$ satisfies

$\mathbb{P}\left(G_{s}\in\mathcal{P}_{s}\right)=1-o(1).$

Then $H\sim G(n,p)$ a.a.s. has a unique minimum degree vertex $u$ and
$H[N_{H}(u)]\in\mathcal{P}_{d_{H}(u)}$.

###### Proof.

Let us fix some $\beta_{n}=o(1)$ such that

$\displaystyle\mathbb{P}\left(G_{s}\notin\mathcal{P}_{s}\right)=o(\beta_{n})$
(3.1)

for every $s\in[0.5np,2np]$. Moreover, let $X_{\delta}$ denote the event that
$H$ has a unique vertex of minimum degree and $0.5np\leq\delta(H)\leq 2np$. By
Lemma 3.7, specifically property (W 0 ), and Lemma 3.2 we know that
$X_{\delta}$ holds with high probability. In particular, we can find
$\delta_{n}=o(1)$ such that

$\mathbb{P}(0.5np\leq\delta(H)\leq
2np)\geq\mathbb{P}(X_{\delta})=1-\delta_{n}.$

In the following we will condition on the event $X_{\delta}$, and whenever we
do so, we will always let $u$ denote the unique minimum degree vertex in $H$.
We will follow an approach similar to that used in the proof of Corollary
2.1.4 in [18]. Before we proceed with the proof, we introduce some notation
and facts that we will need later on. We begin with the fact that there exists
$\gamma_{n}=o(1)$ such that the following holds:

  1. (1)

For any $d\geq 0$, we have $\mathbb{P}(\delta(H)=d)\leq\gamma_{n}$.

  2. (2)

For any $d\geq 0$, if $H^{\prime}\sim G(n-1,p)$, we have
$\mathbb{P}(\delta(H^{\prime})\geq d-1)\geq\mathbb{P}(\delta(H)\geq
d)-\gamma_{n}$.

Part (1) follows from the proof of Theorem 3.9(i) in [3], while part (2) is
shown in the proof of Corollary 2.1.4 in [18].

Next, let $\varepsilon_{n}=o(1)$ be chosen such that
$\varepsilon_{n}=\omega(\max\\{\beta_{n},\gamma_{n},\delta_{n}\\}).$ We
further let $t_{n}$ be the smallest integer such that
$\mathbb{P}(\delta(H)\leq t_{n})\geq 1-\varepsilon_{n}$. Note that, by the
minimality of $t_{n}$, we then have $\mathbb{P}(\delta(H)\leq
t_{n}-1)<1-\varepsilon_{n}$. Using (1) for $d=t_{n}$, we conclude

$\displaystyle 1-\varepsilon_{n}\leq\mathbb{P}(\delta(H)\leq
t_{n})=\mathbb{P}(\delta(H)\leq t_{n}-1)+\mathbb{P}(\delta(H)=t_{n})\leq
1-\varepsilon_{n}+\gamma_{n}.$ (3.2)

Moreover, since $\varepsilon_{n}>\gamma_{n}+\delta_{n}$, we obtain
$\mathbb{P}(\delta(H)\leq t_{n})<1-\delta_{n}<\mathbb{P}(\delta(H)\leq 2np)$
and thus $t_{n}\leq 2np$.

Since $H\sim G(n,p)$, the subgraph $H-v$, for any fixed vertex $v$, has the
distribution $G(n-1,p)$. However, recall that we are conditioning on the event
$X_{\delta}$, and that in particular there is a unique vertex $u$ of minimum
degree $d=d_{H}(u)$. We will be interested in the subgraph $H^{\prime}=H-u$,
and first need to determine how conditioning on $X_{\delta}$ affects its
distribution.

Suppose $S\subseteq V(H^{\prime})$ is the neighbourhood of $u$. As $u$ is the
only vertex of degree at most $d$ in $H$, we must have $d_{H^{\prime}}(v)\geq
d+1$ for all $v\in V(H^{\prime})\setminus S$, and $d_{H^{\prime}}(v)\geq d$
for all $v\in S$; let $C_{S}$ be the event that these lower bounds on the
degrees in $H^{\prime}$ hold. Aside from $C_{S}$, however, $X_{\delta}$ yields
no further information about the graph $H^{\prime}$, as the edges in $G(n,p)$
are independent. Thus, we have

$\displaystyle\mathbb{P}_{G(n,p)}(H[S]\in\mathcal{P}_{d}|X_{\delta}\land\\{N_{H}(u)=S\\})=\mathbb{P}_{G(n-1,p)}(H^{\prime}[S]\in\mathcal{P}_{d}|C_{S}).$
(3.3)

Now, by the Law of Total Probability,

$\displaystyle\mathbb{P}_{G(n,p)}(H[N_{H}(u)]\in\mathcal{P}_{d_{H}(u)}|X_{\delta})$
$\displaystyle=\sum_{0\leq d\leq
n-1}\sum_{S\in\binom{V(H^{\prime})}{d}}\mathbb{P}_{G(n,p)}\left(H[S]\in\mathcal{P}_{d}|X_{\delta}\land\\{N_{H}(u)=S\\}\right)\cdot\mathbb{P}_{G(n,p)}\left(N_{H}(u)=S|X_{\delta}\right)$
$\displaystyle\geq\sum_{0.5np\leq d\leq
t_{n}}\sum_{S\in\binom{V(H^{\prime})}{d}}\mathbb{P}_{G(n-1,p)}(H^{\prime}[S]\in\mathcal{P}_{d}|C_{S})\cdot\mathbb{P}_{G(n,p)}(N_{H}(u)=S|X_{\delta}).$
(3.4)

To estimate the first factor, we observe that

$\displaystyle\mathbb{P}_{G(n-1,p)}(C_{S})$
$\displaystyle\geq\mathbb{P}(\delta(H^{\prime})\geq
d+1)\geq\mathbb{P}(\delta(H)\geq d+2)-\gamma_{n}$
$\displaystyle\geq\mathbb{P}(\delta(H)\geq
t_{n}+2)-\gamma_{n}\geq\mathbb{P}(\delta(H)\geq
t_{n}+1)-2\gamma_{n}\geq\varepsilon_{n}/2,$ (3.5)

where the second inequality follows from (2), for the third inequality we use
$d\leq t_{n}$, the fourth inequality follows from (1), and the last inequality
comes from (3.2) and since $\varepsilon_{n}=\omega(\gamma_{n})$. Hence we have

$\displaystyle\mathbb{P}_{G(n-1,p)}\left(H^{\prime}[S]\in\mathcal{P}_{d}|C_{S}\right)$
$\displaystyle=1-\mathbb{P}_{G(n-1,p)}\left(H^{\prime}[S]\notin\mathcal{P}_{d}|C_{S}\right)$
$\displaystyle=1-\frac{\mathbb{P}_{G(n-1,p)}\left(\\{H^{\prime}[S]\notin\mathcal{P}_{d}\\}\wedge
C_{S}\right)}{\mathbb{P}_{G(n-1,p)}(C_{S})}$ $\displaystyle\geq
1-\frac{\mathbb{P}_{G(n-1,p)}\left(H^{\prime}[S]\notin\mathcal{P}_{d}\right)}{\mathbb{P}_{G(n-1,p)}(C_{S})}$
$\displaystyle\geq
1-\frac{\mathbb{P}_{G(d,p)}\left(G_{d}\notin\mathcal{P}_{d}\right)}{\varepsilon_{n}/2}=1-o(1),$

where for the second inequality we use (3.2) and that $H^{\prime}[S]\sim
G(d,p)$ and the final estimate uses (3.1) and $\beta_{n}=o(\varepsilon_{n})$.
Putting this into (3.2), we conclude that

$\displaystyle\mathbb{P}_{G(n,p)}(H[N_{H}(u)]\in\mathcal{P}_{d_{H}(u)}|X_{\delta})$
$\displaystyle\geq\sum_{0.5np\leq d\leq
t_{n}}\sum_{S\in\binom{V(H^{\prime})}{d}}(1-o(1))\mathbb{P}_{G(n,p)}(N_{H}(u)=S|X_{\delta})$
$\displaystyle=(1-o(1))\mathbb{P}_{G(n,p)}\left(0.5np\leq\delta(H)\leq
t_{n}|X_{\delta}\right)$
$\displaystyle=(1-o(1))\frac{\mathbb{P}_{G(n,p)}(\\{\delta(H)\leq
t_{n}\\}\land X_{\delta})}{\mathbb{P}(X_{\delta})}$
$\displaystyle\geq(1-o(1))\frac{1-\mathbb{P}_{G(n,p)}(\delta(H)>t_{n})-\mathbb{P}_{G(n,p)}(\overline{X_{\delta}})}{\mathbb{P}(X_{\delta})}$
$\displaystyle\geq(1-o(1))\frac{1-\varepsilon_{n}-\delta_{n}}{1-\delta_{n}}=1-o(1).$

This proves the lemma. ∎

###  3.3 The smallest neighbourhood and quantitative simplicity

We can now combine the results from Section 3.1 with Lemma 3.8 to obtain a
sequence of corollaries describing the subgraph $F$ induced by the
neighbourhood of the minimum degree vertex, which we shall later apply when
proving Theorem 1.4. We will also use these to derive Corollary 1.6 from
Theorem 1.4.

To start with, for the proof of the Ramsey simplicity of $H$ in case (b) of
Theorem 1.4, it will be important that $F$ is an empty graph. This is
guaranteed by the following corollary.

######  Corollary 3.9.

Let $p=p(n)\in(0,1)$ be such that $\frac{\log n}{n}\ll p\ll n^{-\frac{2}{3}}$,
and let $H\sim G(n,p)$. Then a.a.s. $H$ has a unique minimum degree vertex
$u$, and $e(N_{H}(u))=0$.

###### Proof.

By Lemma 3.8 it is enough to prove that, for every $s\in[0.5np,2np]$, with
high probability $G_{s}\sim G(s,p)$ has no edges. This holds, since by the
assumptions on $s$ and $p$ we obtain $\mathbb{E}[e(G_{s})]<s^{2}p\leq
4n^{2}p^{3}=o(1)$. ∎

For larger values of $p$, we can control the number of edges appearing in $F$,
which we will require for the proofs of both simplicity and non-simplicity.

######  Corollary 3.10.

Let $p=p(n)\in(0,1)$ be such that $n^{-\frac{2}{3}}\ll p\ll 1$, and let $H\sim
G(n,p)$. Then a.a.s. $H$ has a unique minimum degree vertex $u$, and the graph
$F=H[N(u)]$ satisfies $\frac{1}{16}n^{2}p^{3}\leq e(F)\leq 4n^{2}p^{3}$.

###### Proof.

For every $s\in[0.5np,2np]$, Lemma 3.3(a) guarantees that $G_{s}\sim G(s,p)$
almost surely has
$(1+o(1))\frac{s^{2}p}{2}\in[\frac{1}{16}n^{2}p^{3},4n^{2}p^{3}]$ edges. The
above statement now follows by an application of Lemma 3.8. ∎

Finally, in the range $n^{-\frac{2}{3}}\ll p\ll n^{-\frac{1}{2}}$, when
determining the $q$-Ramsey simplicity of $H$, we will make use of the fact
that $F$ is typically a forest with small components, while also appealing to
the fact that its maximum degree cannot be too small.

######  Corollary 3.11.

Let $p=p(n)\in(0,1)$ be such that $n^{-\frac{2}{3}}\ll p\ll n^{-\frac{1}{2}}$,
and let $H\sim G(n,p)$. Then a.a.s. $H$ has a unique minimum degree vertex
$u$, the graph $F=H[N(u)]$ induces a forest, and the order $\lambda(F)$ of the
largest component in $F$ satisfies the following bounds:

  1. (a)

$\lambda(F)\leq\frac{1}{2}\log n$,

  2. (b)

if $p\ll n^{-\frac{k+1}{2k+1}}$ for some fixed integer $k\geq 2$, then
$\lambda(F)\leq k$, and

  3. (c)

if $p=n^{-\frac{1}{2}}f^{-1}$ for some $f=f(n)$ satisfying $1\ll f=n^{o(1)}$,
then $\lambda(F)\leq\left(\frac{1}{4}+o(1)\right)\frac{\log n}{\log f}$.

Moreover, the maximum degree $\Delta(F)$ of $F$ a.a.s. satisfies the
following:

  1. (d)

if $p\gg n^{-\frac{k}{2k-1}}$ for some fixed integer $k\geq 2$, then
$\Delta(F)\geq k-1$, and

  2. (e)

if $p=n^{-1/2}f^{-1}$ for some $1\ll f=f(n)=n^{o(1)}$, then
$\Delta(F)\geq\left(\frac{1}{2}-o(1)\right)\frac{\log n}{\log(f^{2}\log n)}$.

###### Proof.

By Lemma 3.8, it suffices to verify that the corresponding bounds on
$\lambda(G_{s})$ and $\Delta(G_{s})$ for $G_{s}\sim G(s,p)$ hold with high
probability when $s\in[0.5np,2np]$. These bounds are obtained as follows: for
property (a) observe that $p\ll n^{-\frac{1}{2}}$ implies $p\ll s^{-1}$ and
$s\ll n^{\frac{1}{2}}$, in which case Lemma 3.4(a) gives that
$\lambda(G_{s})\leq\log s\leq\frac{1}{2}\log n$ holds a.a.s.. For property (b)
we use that $p\ll n^{-\frac{k+1}{2k+1}}$ implies $p\ll s^{-\frac{k+1}{k}}$,
and hence $\lambda(G_{s})\leq k$ holds a.a.s. by Lemma 3.4(b). For properties
(c) and (e) observe that $p=n^{-\frac{1}{2}}f^{-1}$ implies
$\frac{0.5}{sf^{2}}\leq p\leq\frac{2}{sf^{2}}$ and $s=n^{\frac{1}{2}-o(1)}$,
which a.a.s. leads to $\lambda(G_{s})\leq(1+o(1))\frac{\log s}{\log
f^{2}}\leq\left(\frac{1}{4}+o(1)\right)\frac{\log n}{\log f}$ by Lemma 3.4(c),
and to $\Delta(G_{s})\geq(1-o(1))\frac{\log s}{\log(f^{2}\log
s)}\geq\left(\frac{1}{2}-o(1)\right)\frac{\log n}{\log(f^{2}\log n)}$ by Lemma
3.2(b). Finally, for property (d) we note that $p\gg n^{-\frac{k}{2k-1}}$
implies $p\gg s^{-\frac{k}{k-1}}$, and hence Lemma 3.2(a) ensures that
$\Delta(G_{s})\geq k-1$ a.a.s. ∎

With these bounds on the parameters of the subgraph $F$ induced by the
neighbourhood of the minimum degree vertex, we are now in position to deduce
Corollary 1.6, giving quantitative estimates on the value of $\tilde{q}(H)$ in
the intermediate range.

###### Proof of Corollary 1.6.

We start by appealing to Lemma 3.2(c) to observe that a.a.s.
$\delta(H)=(1+o(1))np$.

Let us begin by establishing the lower bounds on $\tilde{q}(H)$. By Theorem
1.4 we have
$\tilde{q}(H)\geq(1+o(1))\max\left\\{\frac{\delta(H)}{\lambda(F)^{2}},\frac{\delta(H)}{80\log
n}\right\\}$, and we can bound $\lambda(F)$ using Corollary 3.11.

When $p\ll n^{-\frac{k+1}{2k+1}}$ for some fixed integer $k\geq 2$, then, by
Corollary 3.11(b), we a.a.s. have $\lambda(F)\leq k$. Thus, in this range, we
have $\tilde{q}(H)\geq(1+o(1))\frac{np}{k^{2}}$ a.a.s., which yields the lower
bounds for parts (a) and (b) of Corollary 1.6 (note that when
$p=\Theta\left(n^{-\frac{k+1}{2k+1}}\right)$, we have $p\ll
n^{-\frac{(k+1)+1}{2(k+1)+1}}$). The lower bound in part (c) follows by
substituting the bound on $\lambda(F)$ from Corollary 3.11(c), while the lower
bound in part (d) is trivial.

For the upper bounds, Theorem 1.4 gives
$\tilde{q}(H)\leq\min\left\\{\frac{\delta(H)}{\Delta(F)},\frac{\delta(H)^{2}}{2e(F)}\right\\}$.
The upper bounds in parts (a), (b), and (c) come from substituting the
appropriate lower bounds on $\Delta(F)$ given by Corollary 3.11. When $p\gg
n^{-\frac{k}{2k-1}}$ for some fixed $k$, Corollary 3.11(d) yields
$\Delta(F)\geq k-1$ a.a.s., which provides the upper bounds in parts (a) and
(b) of Corollary 1.6. The upper bound in part (c) follows similarly, using the
lower bound on $\Delta(F)$ from Corollary 3.11(e). Finally, for the upper
bound in part (d) of Corollary 1.6, we use Corollary 3.10, which asserts that
a.a.s. $e(F)\geq\frac{1}{16}n^{2}p^{3}$. Thus
$\frac{\delta(H)^{2}}{2e(F)}\leq\frac{8+o(1)}{p}$, as required. ∎

##  4 Simplicity and abundance for $G(n,p)$

In this section we prove the lower bounds on $\tilde{q}(G(n,p))$ from Theorem
1.4. These are the positive results, showing that with high probability $H\sim
G(n,p)$ is $q$-Ramsey simple for the appropriate values of $q$.

To begin, we observe that we have nothing new to prove in case (a). By Lemma
3.4 we know $H$ is a forest with high probability when $p\ll n^{-1}$. Szabó,
Zumstein, and Zürcher [29] proved that all forests are $2$-Ramsey simple, and
their proof extends directly to show $q$-Ramsey simplicity for all $q\geq 3$
as well. For completeness, we provide the argument in Appendix A.

For the remaining cases, we will show that $H$ is typically such that one can
construct a minimal $q$-Ramsey graph $G$ for $H$ with
$\delta(G)=q(\delta(H)-1)+1$, provided, in case (c), that $q$ is not too
large. We first establish a general sufficient condition for the existence of
such a graph $G$ in Section 4.1, and then show in Section 4.2 that it is
satisfied with high probability by the random graph $H$. In Section 4.3 we
shall extend these results by showing $H$ admits minimal Ramsey graphs with
arbitrarily many vertices of degree $q(\delta(H)-1)+1$.

Before we start, we introduce a piece of notation we shall use throughout this
section. Given a graph $\Gamma$ with a $q$-colouring
$f:E(\Gamma)\rightarrow[q]$ and any colour $i\in[q]$, the colour-$i$ subgraph
$\Gamma_{i}$ of $\Gamma$ is the graph $\Gamma_{i}=(V(\Gamma),f^{-1}(i))$
consisting of all edges of $\Gamma$ with the colour $i$.

###  4.1 Reducing to the smallest neighbourhood

In this subsection we shall show that when establishing the $q$-Ramsey
simplicity of a well-behaved graph $H$ (recall Definition 3.6), we can focus
our attention on the neighbourhood of the minimum degree vertex.

######  Proposition 4.1.

Let $q\geq 2$, let $H$ be a well-behaved graph, and let $F=H[N(u)]$ be the
subgraph induced by the neighbourhood of the unique minimum degree vertex $u$.
Suppose there exists a $q$-edge-coloured graph $\Gamma$ on $q(\delta(H)-1)+1$
vertices such that:

  1. (i)

for every set $U\subseteq V(\Gamma)$ of $\delta(H)$ vertices and for every
colour $i\in[q]$, there exists a copy $F_{U,i}$ of $F$ in $\Gamma[U]$ whose
edges are all of colour $i$, and

  2. (ii)

for each $i\in[q]$, the colour-$i$ subgraph $\Gamma_{i}$ of $\Gamma$ has
maximum degree at most $\delta(H)-1$.

Then $H$ is $q$-Ramsey simple.

This proposition provides a sufficient condition: to establish the $q$-Ramsey
simplicity of a well-behaved graph, one need only construct the coloured graph
$\Gamma$. Before proceeding with its proof, we remark that the condition is
very close to being necessary as well.

######  Remark 4.2.

Let $H$ be $q$-Ramsey simple with a unique vertex $u$ of minimum degree, and
let $G$ be a minimal $q$-Ramsey graph for $H$ with a vertex $w$ of degree
$q(\delta(H)-1)+1$. Let $\Gamma=G[N(w)]$ be the subgraph of $G$ induced by the
neighbourhood of $w$. By minimality, there is a $q$-colouring $c$ of $G-w$,
and in particular of $\Gamma$, without any monochromatic copies of $H$.

Since $G$ itself is $q$-Ramsey for $H$, no matter how we extend the colouring
$c$ to the edges incident to $w$, we must create a monochromatic copy of $H$.
Given any subset $U$ of $\delta(H)$ vertices in $\Gamma$ and any colour
$i\in[q]$, colour the edges from $w$ to $U$ with colour $i$, and colour the
remaining edges incident to $w$ evenly with the other colours, so that each is
used $\delta(H)-1$ times. Any monochromatic copy of $H$ must involve at least
$\delta(H)$ edges incident to $w$, and hence must be of colour $i$ and contain
all the vertices in $U$. As $w$ has degree $\delta(H)$ in this monochromatic
subgraph, it must play the role of $u$ in $H$, and therefore we must find a
colour-$i$ copy of $F$ in $\Gamma[U]$.

Thus, if $H$ is $q$-Ramsey simple, there must exist a $q$-coloured graph
$\Gamma$ on $q(\delta(H)-1)+1$ vertices satisfying property (i) of Proposition
4.1. While the well-behavedness of $H$ and property (ii) may not be necessary,
they shall enable us to maintain control over potential copies of $H$ when
constructing the minimal $q$-Ramsey graph $G$.

Given the graph $\Gamma$, when we build from it a $q$-Ramsey graph $G$ we
shall, as is common practice in the field, make extensive use of signal
senders, which are gadgets that allow us to prescribe colour patterns on the
edges of a graph.

######  Definition 4.3 (Signal senders).

Given a graph $H$, a number of colours $q\geq 2$, a distance $d\geq 1$, and
two edges $e$ and $f$, a _positive (or negative) signal sender_
$S^{+}(H,q,d,e,f)$ (or $S^{-}(H,q,d,e,f)$) is a graph $S$ that contains $e$
and $f$ and satisfies:

  1. (i)

$S$ can be $q$-coloured without monochromatic copies of $H$,

  2. (ii)

in any such colouring, $e$ and $f$ have the same (or different) colour(s), and

  3. (iii)

the edges $e$ and $f$ are at distance at least $d$ in $S$.

The edges $e$ and $f$ are called the _signal edges_.

Fortunately for us, signal senders exist for all $3$-connected graphs, as
shown by Rödl and Siggers [26], building on earlier work of Burr, Erdős, and
Lovász [5] and Burr, Nešetřil, and Rödl [6].

######  Theorem 4.4 ([26]).

If $H$ is $3$-connected, then for any $q\geq 2$ and $d\geq 1$, there are
positive and negative signal senders $S^{+}(H,q,d,e,f)$ and
$S^{-}(H,q,d,e,f)$.

The utility of signal senders lies in the ability to force pairs of edges in
an $H$-free colouring of a graph $G$ to have the same (or different, in the
negative case) colours. This is achieved through the process of _attachment_ ;
given a graph $G$ and a pair of distinct edges $h_{1},h_{2}\in E(G)$, we
attach to $G$ a signal sender $S^{+}(H,q,d,e,f)$ (or $S^{-}(H,q,d,e,f)$),
defined on a disjoint set of vertices, between $h_{1}$ and $h_{2}$ by
identifying the signal edges $e$ and $f\in E(S)$ with the edges $h_{1}$ and
$h_{2}\in E(G)$. In this next result, we show that attachment cannot create
unexpected copies of our target graph $H$, provided that the signal edges are
sufficiently far apart.

######  Lemma 4.5.

Let $q\geq 2$, let $H$ be any 3-connected graph, and let $d\geq v(H)$. Let
$S=S^{+}(H,q,d,e,f)$ or $S=S^{-}(H,q,d,e,f)$ be a signal sender and let $G$ be
any graph on a disjoint set of vertices. If the graph $G^{\prime}$ is formed
by attaching $S$ to any two distinct edges of $G$, then, for any copy $H_{0}$
of $H$ in $G^{\prime}$, we have either $V(H_{0})\subseteq V(G)$ or
$V(H_{0})\subseteq V(S)$.

###### Proof.

Let $H_{0}$ be a copy of $H$ in $G$ and suppose for the sake of contradiction
that $H_{0}$ is fully contained neither in $G$ nor in $S$. We can then find
vertices $x\in V(H_{0})\cap\left(V(S)\setminus V(G)\right)$ and $y\in
V(H_{0})\cap\left(V(G)\setminus V(S)\right)$. Now, by $3$-connectivity,
$H_{0}$ contains three internally-vertex-disjoint paths between $x$ and $y$.

Since $V(S)\cap V(G)=e\cup f$, each of these paths must pass through a
distinct endpoint of one of the signal edges $e$ and $f$. There must be one
path meeting $e$ and another meeting $f$, and the portions of these paths that
lie within the signal sender contain a path from $e$ to $f$ within
$V(H_{0})\cap V(S)$. However, this contradicts $e$ and $f$ being at distance
$d\geq v(H)$. ∎

Armed with these preliminaries, we can now prove Proposition 4.1.

###### Proof of Proposition 4.1.

We shall take a slightly indirect route to certifying the $q$-Ramsey
simplicity of $H$. Rather than constructing a minimal $q$-Ramsey graph with
minimum degree $q(\delta(H)-1)+1$, we will instead build a graph $G$ such
that:

  * (a)

$G\rightarrow_{q}H$,

  * (b)

$G$ has a vertex $w$ of degree $q(\delta(H)-1)+1$, and

  * (c)

$G-w\not\rightarrow_{q}H$.

Since $G$ is $q$-Ramsey for $H$, it must contain a minimal $q$-Ramsey subgraph
$G^{\prime}\subseteq G$. By virtue of (c), we have $w\in V(G^{\prime})$, and
hence $\delta(G^{\prime})\leq d_{G^{\prime}}(w)\leq
d_{G}(w)=q(\delta(H)-1)+1$. In light of the general lower bound, we must in
fact have equality, and hence $G^{\prime}$ bears witness to the $q$-Ramsey
simplicity of $H$.

To construct this $q$-Ramsey graph $G$, we start with the graph $\Gamma$.
Recall that, for each set $U$ of $\delta(H)$ vertices of $\Gamma$ and for each
colour $i\in[q]$, there is a colour-$i$ copy $F_{U,i}$ of $F$ in $\Gamma[U]$.
We will wish to complete these to potential monochromatic copies of $H$. To
this end, let $R=H-\left(\\{u\\}\cup N(u)\right)$ be the remainder of $H$
after we remove the minimum degree vertex $u$ and its neighbourhood. Then, for
every $U$ and $i$, we include a copy $R_{U,i}$ of $R$ on a disjoint set of
vertices, adding the necessary edges so that $R_{U,i}\cup F_{U,i}$ forms a
copy of $H-u$. We call the resulting graph $\Gamma^{+}$.

Now recall that the graph $\Gamma$ comes with an edge-colouring, which we
extend by colouring the edges in $R_{U,i}$ and between $R_{U,i}$ and $F_{U,i}$
with the colour $i$. Denote by $c$ the resulting colouring of $\Gamma^{+}$. To
force the correct colouring, we shall use signal senders. Note that, since $H$
is well-behaved, property (W 0 ) ensures $H$ is $3$-connected, and hence by
Theorem 4.4 positive and negative signal senders exist.

We introduce a matching $e_{1},e_{2},\ldots,e_{q}$ of $q$ edges, again on a
set of new vertices. For every pair $i<j$, we attach a negative signal sender
$S_{i,j}=S^{-}(H,q,v(H),e_{i},e_{j})$ between $e_{i}$ and $e_{j}$. As we shall
see later, this will ensure that these edges all receive distinct colours in
an $H$-free colouring. Now, for every edge $f$ in $\Gamma^{+}$, we attach a
positive signal sender $S_{f}=S^{+}(H,q,v(H),e_{c(f)},f)$ between $e_{c(f)}$
and $f$. Finally, we introduce a new vertex $w$ and make it adjacent to every
vertex in $\Gamma$. This completes our construction of the graph $G$, which is
depicted in Figure 4.1.

Figure 4.1: Construction of $G$

Observe that $d_{G}(w)=v(\Gamma)=q(\delta(H)-1)+1$, and so condition (b) is
already satisfied. We shall now verify conditions (a) and (c) in the following
claims.

######  Claim 4.6.

The graph $G$ is $q$-Ramsey for $H$.

###### Proof.

Suppose for a contradiction that we have an $H$-free $q$-colouring of $G$.
First observe that, by Definition 4.3(ii), if the signal sender $S_{i,j}$ is
$H$-free, then the edges $e_{i}$ and $e_{j}$ must receive different colours.
As this is true for each pair $i<j$, we may, relabelling colours if necessary,
assume that each edge $e_{i}$ receives colour $i$.

Next, for each edge $f$ in $\Gamma^{+}$, consider the signal sender $S_{f}$.
If this does not contain a monochromatic copy of $H$, then $e_{c(f)}$ and $f$
must have the same colour, and thus $f$ receives the colour $c(f)$. Hence we
have forced the desired colouring on $\Gamma^{+}$.

This brings us to the vertex $w$. Since it has degree $q(\delta(H)-1)+1$,
there must be some colour $i$ and a set $U\subseteq V(\Gamma)$ of size
$\delta(H)$ such that the edges between $w$ and $U$ are all of colour $i$.
However, appealing to condition (i) of Proposition 4.1, we find a colour-$i$
copy $F_{U,i}$ of $F$ in $\Gamma[U]$, which we can complete to a copy of $H$
by attaching $w$ and $R_{U,i}$, contradicting our supposition. ∎

######  Claim 4.7.

The graph $G-w$ is not $q$-Ramsey for $H$.

###### Proof.

We provide an $H$-free $q$-colouring of $G-w$. To start, we give $\Gamma^{+}$
the colouring $c$, and, for each $i\in[q]$, colour the edge $e_{i}$ of the
matching with the colour $i$. Observe that, under this colouring, the signal
edges of each positive signal sender $S_{f}$ in $G$ have the same colour,
while those of negative signal senders $S_{i,j}$ receive different colours. By
Definition 4.3 we can find an $H$-free colouring of each signal sender that
agrees with the colouring of the signal edges. We use these to extend our
colouring to the signal senders as well, thereby obtaining a $q$-colouring of
$G-w$.

Now suppose for a contradiction that this colouring gives rise to a colour-$i$
copy $H_{0}$ of $H$ for some $i\in[q]$. First, observe that it follows from
Lemma 4.5 that $H_{0}$ either is fully contained in a signal sender or is
contained in $\Gamma^{+}\cup\\{e_{i}:i\in[q]\\}$. Since the signal senders
were coloured without monochromatic copies of $H$, and the edges
$\\{e_{i}:i\in[q]\\}$ are isolated in the latter graph, we need only show that
we cannot have $H_{0}\subseteq\Gamma^{+}$.

We next claim that $H_{0}$ can only meet at most one subgraph $R_{U,i}$.
Indeed, suppose instead that there are two sets $U$ and $U^{\prime}$ such that
$V(H_{0})\cap V(R_{U,i})$ and $V(H_{0})\cap V(R_{U^{\prime},i})$ are both
nonempty. As the sets $V(R_{U,i})$ and $V(R_{U^{\prime},i})$ are disjoint, we
may assume without loss of generality that $|V(H_{0})\cap
V(R_{U,i})|\leq\tfrac{1}{2}n$.

Since $R_{U,i}$ is only attached to $\Gamma$ through the vertices in $U$, the
set $U$ must be a cut-set for the subgraph $H_{0}$. Let $x\in V(H_{0})\cap
V(R_{U,i})$ be an arbitrary vertex, and let $K$ be the component of $x$ in
$H_{0}-U$. We clearly have $|K|\leq|V(H_{0})\cap
V(R_{U,i})|\leq\tfrac{1}{2}n$.

On the other hand, observe that $x$ is also in the copy $H_{U,i}$ of $H$
supported on $\\{w\\}\cup V(F_{U,i})\cup V(R_{U,i})$. In $H_{U,i}$, the set
$U$ is the neighbourhood of $w$, and, since $H$ is well-behaved, condition (W
0 ) implies $x$ has at most $\tfrac{1}{2}\delta(H)$ neighbours in $U$. As
$d_{H_{0}}(x)\geq\delta(H)$, this means $x$ must have at least
$\tfrac{1}{2}\delta(H)$ neighbours in $H_{0}-U$. Hence, we also have
$|K|\geq\tfrac{1}{2}\delta(H)$. However, this contradicts condition (W 0 ), as
the removal of the $\delta(H)$ vertices in $U$ cannot create a component in
$H_{0}$ of size between $\tfrac{1}{2}\delta(H)$ and $\tfrac{1}{2}n$.

Thus, $H_{0}$ meets at most one subgraph $R_{U,i}$. Now, by property (ii) of
the colouring $c$ of $\Gamma$, we have that any vertex is incident to fewer
than $\delta(H)$ edges of colour $i$ in $\Gamma$. Thus, in order to be part of
$H_{0}$, a vertex from $\Gamma$ must have neighbours in $R_{U,i}$ as well.
However, the only such vertices are those in $U$, and since $|U\cup
V(R_{U,i})|=n-1$, this does not leave us with enough vertices for a copy of
$H$.

Our colouring is therefore indeed $H$-free, thereby proving the claim. ∎

This shows that the graph $G$ satisfies conditions (a), (b), and (c),
completing the proof. ∎

###  4.2 Constructing coloured neighbourhoods

The path to proving the lower bounds of Theorem 1.4 is now clearly signposted.
By Lemma 3.7, we know that when $\frac{\log n}{n}\ll p\ll 1$, the random graph
$H\sim G(n,p)$ is well-behaved with high probability, and hence we are in
position to apply Proposition 4.1. We shall then use the results of Section 3
to describe the subgraph $F$ induced by the minimum degree vertex in $H$. This
subgraph evolves as the edge probability $p$ increases, and in each range we
will construct an appropriate coloured graph $\Gamma$ that satisfies the
conditions of the proposition.

We start with the sparse range, where $p\ll n^{-\frac{2}{3}}$.

###### Proof of Theorem 1.4(b).

Let $q\geq 2$, let $p$ satisfy $\frac{\log n}{n}\ll p\ll n^{-\frac{2}{3}}$,
and let $H\sim G(n,p)$. By Lemma 3.7 and Corollary 3.9, we have with high
probability that $H$ is well-behaved and the subgraph $F=H[N(u)]$ induced by
the neighbourhood of the minimum degree vertex $u$ is empty. In this case, we
can simply take $\Gamma$ to be an empty graph on $q(\delta(H)-1)+1$ vertices.
Properties (i) and (ii) of Proposition 4.1 are then trivially satisfied, and
so it follows that $H$ is $q$-Ramsey simple. ∎

When $p\gg n^{-\frac{2}{3}}$, we will begin to see edges in the neighbourhood
of the minimum degree vertex. Provided $p\ll n^{-\frac{1}{2}}$, though, the
neighbourhood remains simple in structure, and we can get reasonably sharp
bounds on the number of colours for which the random graph is Ramsey simple.

###### Proof of Theorem 1.4(c), first bound.

Let $n^{-2/3}\ll p\ll n^{-1/2}$ and $H\sim G(n,p)$. By Lemma 3.7, we know that
with high probability $H$ is well-behaved. Let $\lambda(F)$ be the order of
the largest component of the subgraph $F=H[N_{H}(u)]$ induced by the
neighbourhood of the minimum degree vertex $u$. Given any $\varepsilon>0$, we
shall show that, as $n$ tends to infinity, $H$ is with high probability
$q$-Ramsey simple for every
$q\leq\left(1-5\varepsilon\right)\frac{\delta(H)}{\lambda(F)^{2}}$.

By Corollaries 3.10 and 3.11 the graph $F$ is with high probability a very
sparse forest. More precisely, if we denote by $T_{1},T_{2},\ldots,T_{t}$ the
components of $F$ that contain at least one edge, then each $T_{j}$ is a tree
spanning at most $\lambda(F)$ vertices and
$\sum_{j}v(T_{j})\leq\varepsilon\delta(H)$.

To prove simplicity, we provide a geometric construction of an edge-coloured
graph $\Gamma$ on $q(\delta(H)-1)+1$ vertices. Let $s$ be the largest prime
number that is at most
$\left(1-\varepsilon\right)\frac{\delta(H)}{\lambda(F)}$. By the upper bound
of Baker, Harman, and Pintz [1] on prime gaps, we have
$s\geq\left(1-2\varepsilon\right)\frac{\delta(H)}{\lambda(F)}$. Now consider
the finite affine plane $\mathbb{F}_{s}^{2}$, which has $s^{2}$ points. Each
line in the plane consists of $s$ points, and the set of lines can be
partitioned into $s+1$ parallel classes $C_{1},C_{2},\ldots,C_{s+1}$ of $s$
lines each.

To form the graph $\Gamma$, we take as vertices an arbitrary set of
$q(\delta(H)-1)+1$ points from $\mathbb{F}_{s}^{2}$. Note that our choices of
$q$ and $s$ ensure that $q(\delta(H)-1)+1\leq s^{2}$ and $q\leq
s\leq\delta(H)$. Then, given $x,y\in V(\Gamma)$, we add the edge $\\{x,y\\}$
if and only if the line they span lies in one of the first $q$ parallel
classes. We colour the edges by the parallel classes; that is, if the
corresponding line lies in $C_{i}$, for some $i\in[q]$, we give the edge
$\\{x,y\\}$ the colour $i$.

We shall now show that $\Gamma$ satisfies properties (i) and (ii) of
Proposition 4.1, which will show that $H$ is $q$-Ramsey simple. We start with
the latter property. The colour-$i$ subgraph $\Gamma_{i}$ of $\Gamma$ consists
of pairs of points in lines in the parallel class $C_{i}$. Each such line
gives rise to a clique in $\Gamma$, and since the lines are parallel, these
cliques are vertex-disjoint. Finally, since each line has at most $s$ points
in $\Gamma$, it follows that $\Delta(\Gamma_{i})\leq s-1\leq\delta(H)-1$, and
hence property (ii) holds.

For property (i), we need to show that for any $\delta(H)$-set $U\subseteq
V(\Gamma)$ and any colour $i\in[q]$, we can find a copy of $F$ in
$\Gamma_{i}[U]$. We shall embed the trees $T_{j}$ one at a time. Suppose, for
some $j\geq 1$, we have already embedded $T_{1},T_{2},\ldots,T_{j-1}$, and let
$U^{\prime}\subseteq U$ be the set of vertices we have not yet used. Since $F$
has at most $\varepsilon\delta(H)$ non-isolated vertices, it follows that
$|U^{\prime}|\geq\left(1-\varepsilon\right)\delta(H)$.

As observed when showing property (ii), the colour-$i$ subgraph $\Gamma_{i}$
is a disjoint union of at most $s$ cliques. Hence, by the pigeonhole
principle, $U^{\prime}$ meets one of these cliques in at least
$\frac{|U^{\prime}|}{s}$ vertices. By our choice of $s$, this is at least
$\lambda(F)$, and so $\Gamma_{i}[U^{\prime}]$ contains a clique on
$\lambda(F)$ vertices, in which we can freely embed $T_{j}$.

Repeating this process, we can embed all the trees, thereby obtaining a copy
of $F$ in $\Gamma_{i}[U]$. Hence property (i) is satisfied as well, and thus
$H$ is indeed $q$-Ramsey simple. ∎

The above construction allows us to obtain lower bounds on $\tilde{q}(H)$
whenever $n^{-2/3}\ll p\ll n^{-1/2}$. However, when $p=n^{-\frac{1}{2}-o(1)}$
and $\lambda(F)$ gets larger, a probabilistic construction yields a better
bound.

###### Proof of Theorem 1.4(c), second bound.

Let $p\ll n^{-\frac{1}{2}}$, and let $H\sim G(n,p)$. Our goal is to show that
if $q\leq\frac{\delta(H)}{80\log n}$, then with high probability $H$ is
$q$-Ramsey simple. We again start by collecting some information about the
random graph $H$, before constructing an appropriate graph $\Gamma$ for
Proposition 4.1.

By Lemma 3.2(c) and Lemma 3.7, we may assume that $H$ is well-behaved with
$\delta(H)=(1\pm o(1))np$. Furthermore, applying Corollaries 3.10 and 3.11, we
know that with high probability, the subgraph $F=H[N(u)]$ induced by the
neighbourhood of the minimum degree vertex is a forest with
$o\left(\delta(H)\right)$ edges containing no tree on more than $\log n$
vertices. We label the components of $F$ as $T_{1},T_{2},\ldots,T_{t}$.

We now define the $q$-coloured graph $\Gamma$ on $N=q(\delta(H)-1)+1$
vertices. We take $\Gamma\sim G(N,\tfrac{1}{2})$ to be a random graph with
edge probability $\tfrac{1}{2}$. Once we have sampled the graph, we also equip
it with a random colouring, colouring each edge independently and uniformly at
random from the $q$ colours.

Observe that for each colour $i\in[q]$, the colour-$i$ subgraph
$\Gamma_{i}\subseteq\Gamma$ has the distribution $G(N,\tfrac{1}{2q})$. Hence,
it follows from Lemma 3.2(c), combined with a union bound over the number of
colours $q$, that with high probability
$\Delta(\Gamma_{i})\leq\left(1+o(1)\right)\tfrac{N}{2q}<\delta(H)$ for every
$i\in[q]$. This establishes property (ii) of Proposition 4.1.

We now need to show that property (i) also holds with high probability. That
is, we need to ensure that, for every colour $i\in[q]$ and every set
$U\subseteq V(\Gamma)$ of $\delta(H)$ vertices, we can find a copy of $F$ in
$\Gamma_{i}[U]$. We shall once again do this by proving the stronger fact
that, taking $\varepsilon\geq 0$, for any set $U^{\prime}$ of
$(1-\varepsilon)\delta(H)\geq\tfrac{1}{2}np$ vertices, and any tree $T$ on at
most $\log n$ vertices, we can embed a copy of $T$ in
$\Gamma_{i}[U^{\prime}]$. We can then greedily embed the components of $F$ one
at a time; as $F$ only has $o(\delta(H))$ edges, we will always have at least
$(1-\varepsilon)\delta(H)$ vertices remaining when embedding one of its
components.

Applying Lemma 3.3(b) combined with a union bound over the colours $i\in[q]$,
we know that with high probability the monochromatic subgraphs $\Gamma_{i}$
have the property that the number of edges spanned by any set of
$\tfrac{1}{2}np$ vertices is at least
$\tfrac{1}{4}\left(\tfrac{1}{2}np\right)^{2}\tfrac{1}{2q}>2np\log n$.

Since the set $U^{\prime}$ spans at least $2np\log n$ edges, the average
degree in any such subgraph is at least $2\log n$. By repeatedly removing low-
degree vertices, we obtain a subgraph with minimum degree at least $\log n$.
It is then trivial to embed a tree on at most $\log n$ vertices in this
subgraph, as at each vertex, we will always have enough unused neighbours to
embed its children. Thus, we can find disjoint copies of the trees
$T_{1},T_{2},\ldots,T_{t}$, thereby constructing a copy of $F$ in
$\Gamma_{i}[U]$. This proves property (i), and so by Proposition 4.1 it
follows that $H$ is $q$-Ramsey simple. ∎

###  4.3 Abundance

Proposition 4.1 shows that, when establishing the $q$-Ramsey simplicity of a
graph $H$, it suffices to consider the neighbourhood of a minimum degree
vertex $w$. In the construction of the Ramsey host graph $G$, the vertex $w$
will have the desired degree $\delta(G)=s_{q}(H)$, but we can expect all other
vertices to have much higher degree. Indeed, they are all contained in signal
senders, which tend to be large and complicated structures. It is then natural
to ask if this must be the case, or if we can instead find minimal $q$-Ramsey
graphs for $H$ with arbitrarily many vertices of the lowest possible degree.
Following the terminology of [4], we say a graph $H$ is _$s_{q}$ -abundant_
if, for every $k\geq 1$, there is a minimal $q$-Ramsey graph for $H$ with at
least $k$ vertices of degree $s_{q}(H)$. In this section we shall extend the
results of the previous section, showing that in cases (b) and (c), $G(n,p)$
is almost surely not just $q$-Ramsey simple but also $s_{q}$-abundant.

######  Proposition 4.8.

Let $q\geq 2$ and let $H$ be a well-behaved $n$-vertex graph. If there is a
$q$-edge-coloured graph $\Gamma$ on $q(\delta(H)-1)+1$ vertices satisfying the
conditions of Proposition 4.1, and if either $e(\Gamma)=0$ or
$n>q(\delta(H)-1)+2$, then not only is $H$ $q$-Ramsey simple, but it is also
$s_{q}$-abundant.

As we have shown in the previous section, for the ranges of parameters covered
by cases (b) and (c) of Theorem 1.4, $H$ is well-behaved and admits the
construction of a suitable $q$-coloured graph $\Gamma$. Moreover, when $p\ll
n^{-2/3}$, we have $e(\Gamma)=0$, while when $n^{-2/3}\ll p\ll n^{-1/2}$, we
have $\delta(H)=(1+o(1))np$ and $q\leq np$, and so
$q(\delta(H)-1)+2\leq(1+o(1))(np)^{2}\ll n$. Hence, once we prove Proposition
4.8, we will have shown that in these cases $G(n,p)$ is also $s_{q}$-abundant.
To do so, we shall apply the following theorem, a simple corollary of Theorem
3.1 from [4], which gives a sufficient condition for the existence of minimal
$q$-Ramsey graphs with several vertices of a given degree.

######  Theorem 4.9.

Let $H$ be $3$-connected and assume there exists a minimal $q$-Ramsey graph
$G^{\prime}$ for $H$, together with a vertex $v_{0}\in V(G^{\prime})$ and an
edge $e\in E(G^{\prime})$ such that $v_{0}$ end $e$ do not share a copy of $H$
in $G^{\prime}$. Then, for any $k\geq 1$, there exists a minimal $q$-Ramsey
graph for $H$ that has at least $k$ vertices of degree
$d_{G^{\prime}}(v_{0})$.

To prove Proposition 4.8, we shall show that the $q$-Ramsey graph $G$ we built
in the proof of Proposition 4.1 admits a subgraph $G^{\prime}\subseteq G$
satisfying conditions of Theorem 4.9 when we take $v_{0}$ to be the minimum
degree vertex $w\in V(G)$, implying that $H$ is $s_{q}$-abundant.

###### Proof of Proposition 4.8.

Consider the graph $G$ constructed in the proof of Proposition 4.1, and recall
that it in particular contained a vertex $w$ of degree $q(\delta(H)-1)+1$, and
a matching $M=\\{e_{1},e_{2},\ldots,e_{q}\\}$ of edges that were attached to
the rest of the graph by signal senders.

By Claim 4.6, we know $G\rightarrow_{q}H$. Let $G^{\prime}\subseteq G$ be a
minimal subgraph that is still $q$-Ramsey for $H$. Claim 4.7 shows that we
must have $w\in V(G^{\prime})$, and in our application of Theorem 4.9, we
shall take $v_{0}=w$. The following claim, which we shall prove later, shows
that $G^{\prime}$ must contain at least one edge from the matching $M$.

######  Claim 4.10.

The graph $G-M$ is not $q$-Ramsey for $H$.

We thus have $e_{i}\in E(G^{\prime})$ for some $i\in[q]$, and we take
$e=e_{i}$ in Theorem 4.9. Given this preparation, it is simple to verify the
conditions of the theorem. Indeed, we took $G^{\prime}$ to be a minimal
$q$-Ramsey graph. Moreover, recall that the neighbourhood of $w$ in $G$ is the
vertex set of $\Gamma$. As $e_{i}$ is only connected to $\Gamma$ via signal
senders, in which the distance between the signal edges is at least $v(H)$, it
follows that there cannot be any copy of $H$ containing both $e_{i}$ and $w$.
We can therefore apply Theorem 4.9 to deduce the existence of minimal
$q$-Ramsey graphs for $H$ with arbitrarily many vertices of degree
$d_{G^{\prime}}(w)\leq d_{G}(w)=s_{q}(H)$, showing that $H$ is
$s_{q}$-abundant. ∎

All that remains, then, is to prove Claim 4.10, a task we now complete.

###### Proof of Claim 4.10.

We need to exhibit an $H$-free colouring of $G-M$. This graph consists of
three types of edges:

  1. 1.

those incident to $w$ or in the graph $\Gamma$,

  2. 2.

those in the subgraphs $R_{U,i}$ and between $R_{U,i}$ and $\Gamma$, for
$U\in\binom{V(\Gamma)}{\delta(H)}$ and $i\in[q]$, and

  3. 3.

the edges within the signal senders.

We colour all edges of (1) with the colour $1$, and all edges of (2) with the
colour $2$. We finish by extending this colouring to an $H$-free $q$-colouring
of each of the signal senders; note that this is possible, as each signal
sender is missing at least one of its signal edges from $M$.

From Lemma 4.5, we know that any copy of $H$ is either within a signal sender
or outside it, and as we coloured the signal senders in an $H$-free fashion,
it is only the colour-$1$ edges of (1) or the colour-$2$ edges of (2) that
could give rise to a monochromatic copy of $H$.

We can rule out the former immediately. Either $e(\Gamma)=0$, in which case
the edges of (1) are simply a star around the vertex $w$, which cannot contain
a copy of the well-behaved (and therefore $3$-connected) graph $H$, or
$n>q(\delta(H)-1)+2=v(\Gamma)+1$, and so $\Gamma+\\{w\\}$ does not have enough
vertices to support a copy of $H$.

To handle the latter case, observe that the argument in Claim 4.7 shows that
no copy of $H$ can intersect two different subgraphs $R_{U,i}$ and
$R_{U^{\prime},i^{\prime}}$, for $i,i^{\prime}\in[q]$ and
$U,U^{\prime}\in\binom{V(\Gamma)}{\delta(H)}$. Hence, any copy of $H$ among
the edges of (1) and (2) must use vertices of $R_{U,i}$ and $U$ for some
$U\in\binom{V(\Gamma)}{\delta(H)}$ along with some vertex in $\Gamma-U$ or the
vertex $w$. In either case these involve edges from (1) and therefore have the
colour 1, and hence we cannot have a colour-$2$ copy of $H$.

This completes the proof of Claim 4.10 and, with it, the proof of Proposition
4.8. ∎

##  5 Non-simplicity for $G(n,p)$

In this section we prove the upper bounds on $\tilde{q}(H)$ from Theorem 1.4.
These are the negative results, showing that with high probability $H\sim
G(n,p)$ is not $q$-Ramsey simple for large values of $q$.

For the proofs, the centre of attention will again be the neighbourhood of the
minimum degree vertex of $H$. We first prove upper bounds for case (d) of our
theorem. In the proof below, we first establish that, if the neighbourhood of
the minimum degree vertex exhibits a high maximum degree, then $H$ cannot be
$q$-Ramsey simple for a large enough $q$. For this, we will need the following
result from [21].

######  Theorem 5.1 ([21]).

Let $G$ be an $n$-vertex graph of average degree $d$ and let $k\in\mathbb{N}$.
Then there is a set $U$ of at least $(k+1)n/(d+k+1)$ vertices such that
$\Delta(G[U])\leq k$.

###### Proof of Theorem 1.4(d).

Let $n^{-2/3}\ll p\ll 1$ and $H\sim G(n,p)$. By Lemma 3.7, we know that $H$
has a unique vertex $u$ of minimum degree. As before, we set $F=H[N_{H}(u)]$.

Suppose that $H$ is $q$-Ramsey simple and $G$ is a minimal $q$-Ramsey graph
for $H$ with minimum degree $N=q(\delta(H)-1)+1$. Let $w$ be a vertex of
minimum degree in $G$, and $\Gamma=G[N_{G}(w)]$. It follows from Remark 4.2
that there is an edge-colouring of $\Gamma$ such that the induced graph on
every $\delta(H)$-set of vertices contains, in each colour, a copy of $F$.

We are now ready to prove that
$\tilde{q}(H)\leq(1+o(1))\frac{\delta(H)}{\Delta(F)}$. The above observation
implies that the induced graph on each $\delta(H)$-set has, in each colour, a
vertex of degree at least $\Delta(F)$. However, the average degree of the
sparsest colour class in $\Gamma$ is at most
$\frac{2\binom{N}{2}}{qN}=\frac{N-1}{q}=\delta-1$. Thus, by Theorem 5.1,
$\Gamma$ has a set of $\frac{\Delta(F)N}{\delta(H)+\Delta(F)-1}$ vertices that
induce a graph with maximum degree less than $\Delta(F)$ in this colour.
Hence, we must have

$\frac{\Delta(F)N}{\delta(H)+\Delta(F)-1}\leq\delta(H)-1,$

which rearranges to give
$q\leq\frac{\delta(H)+\Delta(F)-1}{\Delta(F)}-\frac{1}{\delta(H)-1}$, from
which the conclusion follows.

We turn our attention to the second bound, namely
$\tilde{q}(H)\leq(1+o(1))\frac{\delta(H)^{2}}{2e(F)}$. For any subset
$U\subseteq V(\Gamma)$ of size $\delta(H)$, there must be a colour $i\in[q]$
such that there are at most $\frac{1}{q}\binom{\delta(H)}{2}$ edges of colour
$i$ inside $U$. Using once again our observation above, we know that
$\Gamma[U]$ contains a copy of $F$ in colour $i$, and therefore we must have
$\frac{1}{q}\binom{\delta(H)}{2}\geq e(F)$, which yields the claimed bound. ∎

We remark that the proofs of both upper bounds in Theorem 1.4(d) do not use
the fact that $H$ is a random graph, and are valid for any graph that has a
unique vertex of minimum degree whose neighbourhood is not an independent set.
We end this section with a proof of Theorem 1.4(e).

###### Proof of Theorem 1.4(e).

Let $p\gg\sqrt{\frac{\log n}{n}}$ and $H\sim G(n,p)$. By Lemma 2.1, it
suffices to show that a.a.s. $H$ is not $q$-Ramsey simple for $q=2$.

For this, following Lemma 3.5, we may assume that every edge in $H$ belongs to
a triangle. Now suppose for a contradiction that $H$ is $2$-Ramsey simple. Let
$G$ be a minimal $2$-Ramsey graph for $H$ such that $G$ has a vertex $w$ with
$d_{G}(w)=2\delta(H)-1$. By the minimality of $G$, we can find an $H$-free
$2$-colouring $c$ of the graph $G-w$. Now fix an arbitrary vertex $v\in
N_{G}(w)$ and observe that, by the pigeonhole principle, there must be a set
$W\subseteq N_{G}(w)\setminus\\{v\\}$ of size $\delta(H)-1$ such that all
edges between $v$ and any of its neighbours in $W$ have the same colour;
without loss of generality, let this be colour $1$ and set $U=W\cup\\{v\\}$.
We can extend the colouring $c$ by giving colour 1 to all edges in from $w$ to
$N_{G}(w)\setminus U$ and giving colour 2 to all edges from $w$ to vertices in
$U$. With this colouring we cannot create a monochromatic copy of $H$ in
colour 1, as $w$ is only incident to $\delta(H)-1$ edges of colour 1. On the
other hand, $w$ is incident to exactly $\delta(H)$ edges of colour 2, which
all lie between $w$ and $U$. Hence, if there were a monochromatic copy of $H$
in colour 2, the edge $wv$ would need to be part of it. However, since all
edges in $U$ involving $v$ are of colour $1$, that means the edge $wv$ is not
contained in any triangle of colour $2$, and hence cannot be in a
monochromatic copy of $H$. ∎

##  6 Concluding remarks and open problems

In this paper we built upon the work of Grinshpun [18] and studied the
$q$-Ramsey simplicity of $H\sim G(n,p)$ for a wide range of values of $p$ and
$q$. We encountered three different types of behaviour: for very sparse
ranges, i.e., when $p\ll\frac{1}{n}$ or $\frac{\log n}{n}\ll p\ll
n^{-\frac{2}{3}}$, we showed that a.a.s. $H$ is $q$-Ramsey simple for every
possible number of colours $q$; for much denser ranges, i.e., when
$p\gg\left(\frac{\log n}{n}\right)^{\frac{1}{2}}$, a.a.s. we do not have
Ramsey simplicity even when $q=2$; in between these ranges, when
$n^{-\frac{2}{3}}\ll p\ll n^{-\frac{1}{2}}$, there exists a finite threshold
value $\tilde{q}(H)\geq 2$ on the number of colours $q$ such that $H$ is
$q$-Ramsey simple if and only if $q\leq\tilde{q}(H)$. We determined this
threshold up to a constant or, when $p=n^{-\frac{1}{2}-o(1)}$, logarithmic
factor. Several natural questions remain open.

First, our main result does not provide any information on the Ramsey
simplicity of $G(n,p)$ when $p$ is between $\frac{1}{n}$ and $\frac{\log
n}{n}$.

######  Question 6.1.

What can be said about $\tilde{q}(H)$ when $H\sim G(n,p)$ and
$\Omega\left(\frac{1}{n}\right)=p=O\left(\frac{\log n}{n}\right)$? In
particular, is $H$ a.a.s. $2$-Ramsey simple in this case?

In the range $p\gg\frac{\log n}{n}$ our simplicity proofs rely heavily on the
fact that a.a.s. $H\sim G(n,p)$ is 3-connected, implying the existence of
signal senders for $H$, which in turn allow us to deduce a fairly general
recipe for constructing suitable Ramsey graphs. When $p\ll\frac{1}{n}$, we
know that $H\sim G(n,p)$ is a.a.s. a forest, and simplicity follows from the
construction of Szabó, Zumstein, and Zürcher [29], which works for certain
bipartite graphs. When $\frac{1}{n}\ll p\ll\frac{\log n}{n}$, however, the
random graph $G(n,p)$ becomes more complex (in particular, it is non-
bipartite) but it is not yet connected. As a result, resolving the
aforementioned question will likely require new ideas.

Second, in the range
$\Omega\left(n^{-\frac{1}{2}}\right)=p=O\left(\left(\frac{\log
n}{n}\right)^{\frac{1}{2}}\right)$, we proved that $\tilde{q}(H)=O(p^{-1})$,
which shows that the threshold value here is of smaller order than when
$p=n^{-\frac{1}{2}-o(1)}$, as demonstrated in Corollary 1.6. However, we did
not provide any nontrivial lower bounds, and we wonder if that might not be
possible.

######  Question 6.2.

Is it true that $H$ is a.a.s. not $2$-Ramsey simple when $H\sim G(n,p)$ with
$\Omega\left(n^{-\frac{1}{2}}\right)=p=O\left(\left(\frac{\log
n}{n}\right)^{\frac{1}{2}}\right)$?

In this case, signal senders for $H$ do exist, but the neighbourhood of the
minimum degree vertex becomes more complex than just a forest, making it
difficult to construct a graph as described in Remark 4.2. On the other hand,
the presence of isolated vertices makes it likely that a more delicate
argument than the one used in part (e) would be needed to show non-simplicity
for smaller $q$. Nevertheless, we tend to believe that a.a.s. $\tilde{q}(H)=1$
for all $p\gg n^{-\frac{1}{2}}$.

The bounds on $\tilde{q}(H)$ presented in cases (a) and (c) are already quite
close, but it would be interesting to close the remaining gaps.

######  Question 6.3.

Let $H\sim G(n,p)$ with $n^{-2/3}\ll p\ll n^{-1/2}$. What are the asymptotics
of $\tilde{q}(H)$?

In this range, as we have seen in Section 4, the question about $q$-Ramsey
simplicity is tightly linked to the problem of finding a $q$-coloured graph
$\Gamma$ on $q(\delta(H)-1)+1$ vertices such that the following holds: For
every set $U\subseteq V(\Gamma)$ of $\delta(H)$ vertices and for every colour
$i\in[q]$, there exists a copy $F_{U,i}$ of $F=H[N(u)]$ in $\Gamma[U]$ whose
edges are all of colour $i$. The proofs of our lower bounds in Section 4 are
obtained by finding such $\Gamma$ (with additional properties as given in
Proposition 4.1) through explicit constructions or probabilistic arguments. In
order to prove that a.a.s. $H$ is not $q$-Ramsey simple, it would suffice to
prove that such $\Gamma$ does not exist, that is, every $q$-coloured graph
$\Gamma$ on $q(\delta(H)-1)+1$ contains at least one subset $U\subseteq
V(\Gamma)$ of size $\delta(H)$ such that $\Gamma[U]$ is missing a copy of $F$
in at least one colour. Note that in the proof of our second bound in case (d)
of Theorem 1.4 we obtain such a result by a simple counting argument which
guarantees that we cannot pack $q$ copies of $F$ into any graph on $\delta(H)$
vertices. Related to this argument, it seems challenging to determine how many
copies of a given random graph can be packed into a complete graph, leading us
to suggest the following question.

######  Question 6.4.

Let $H\sim G(n,p)$ with $0<p<1$. How many copies of $H$ can be packed into
$K_{n}$?

In the densest range, that is, when $p\gg\left(\frac{\log
n}{n}\right)^{\frac{1}{2}}$, we know that $H\sim G(n,p)$ is a.a.s. not
$q$-Ramsey simple for any $q\geq 2$. We wonder, however, what the behaviour of
$s_{q}(H)$ in this case is; in particular, it would be interesting to
determine whether $s_{q}(H)$ is still typically close to the easy lower bound
$q(\delta(H)-1)+1$. Note that the answer is no if $p=1$ and $q\geq 2$, since
$s_{2}(K_{n})=(n-1)^{2}$. However, when $\left(\frac{\log
n}{n}\right)^{\frac{1}{2}}\ll p\ll 1$, we do not know of any bounds other than
the general ones mentioned in the introduction. In particular, we propose the
following problem, similar to one posed by Grinshpun, Raina, and Sengupta
[17].

######  Question 6.5.

How large is $s_{2}(H)$ for $H\sim G(n,\frac{1}{2})$ a.a.s.?

Related to the above discussion, we also note that our methods can be applied
to the 2-colour asymmetric Ramsey setting, in which a graph $G$ is said to be
$2$-Ramsey for a pair of graphs $(H_{1},H_{2})$ if every red-/blue-colouring
of its edges leads to a red copy of $H_{1}$ or a blue copy of $H_{2}$. In this
setting, we define minimal Ramsey graphs and the smallest minimum degree
$s_{2}(H_{1},H_{2})$ in the obvious way; the general lower bound is replaced
by $s_{2}(H_{1},H_{2})\geq\delta(H_{1})+\delta(H_{2})-1$ and again we call a
pair $(H_{1},H_{2})$ 2-Ramsey simple if this lower bound is attained. Our
constructions can be modified to show that for $H_{1}\sim G(n,p_{1})$ and
$H_{2}\sim G(n,p_{2})$ the pair $(H_{1},H_{2})$ is a.a.s. 2-Ramsey simple if
$\frac{\log n}{n}\ll p_{1}\leq p_{2}\ll n^{-1/2}$. When $p_{1},p_{2}\ll
n^{-1}$, then again a modification of the argument of Szabó, Zumstein, and
Zürcher [29] can be used to show that we a.a.s. have 2-Ramsey simplicity.
Still, the following questions remain.

######  Question 6.6.

Let $H_{1}\sim G(n,p_{1})$ and $H_{2}\sim G(n,p_{2})$ with $p_{1}\ll n^{-1}$
and $\frac{\log n}{n}\ll p_{2}\ll n^{-1/2}$. Is the pair $(H_{1},H_{2})$
a.a.s. 2-Ramsey simple? What happens if one of the graphs comes from the dense
range?

We also remark that our ideas from Section 4.3 can be used to resolve a
special case of a conjecture due to Grinshpun [18], stating that all triangle-
free graphs are $2$-Ramsey simple. In [17], Grinshpun, Raina, and Sengupta use
a construction similar to ours to show that the conjecture is true for all
regular 3-connected triangle-free graphs satisfying one extra technical
condition. Our approach allows us to prove that every well-behaved triangle-
free graph is $q$-Ramsey simple for any $q\geq 2$.

Finally, let us emphasise that there has been little study of (minimal) Ramsey
graphs for $G(n,p)$. The only results we are aware of concern the Ramsey
number of $G(n,p)$, as mentioned in Section 1.2. Hence, as a more general
direction for future research, it would be interesting to explore other
aspects of the Ramsey behaviour of $G(n,p)$ as the target graph.

#### Acknowledgements

The first author was supported by the Deutsche Forschungsgemeinschaft
Graduiertenkolleg “Facets of Complexity” (GRK 2434). The third author was
supported by the Deutsche Forschungsgemeinschaft project 415310276.

## References

  * [1] R. C. Baker, G. Harman, and J. Pintz, _The difference between consecutive primes, II_ , Proc. Lond. Math. Soc. 83 (2001), 532–562.
  * [2] J. Bamberg, A. Bishnoi, and T. Lesgourgues, _The minimum degree of minimal Ramsey graphs for cliques_ , arXiv preprint arXiv:2008.02474 (2020).
  * [3] B. Bollobás, _Random graphs_ , no. 73, Cambridge University Press, 2001\.
  * [4] S. Boyadzhiyska, D. Clemens, and P. Gupta, _Minimal Ramsey graphs with many vertices of small degree_ , arXiv preprint arXiv:2009.04159 (2020).
  * [5] S. A. Burr, P. Erdős, and L. Lovász, _On graphs of Ramsey type_ , Ars Combinatoria 1 (1976), no. 1, 167–190.
  * [6] S. A. Burr, J. Nešetřil, and V. Rödl, _On the use of senders in generalized Ramsey theory for graphs_ , Discrete Math. 54 (1985), no. 1, 1–13.
  * [7] D. Conlon, _A new upper bound for diagonal Ramsey numbers_ , Ann. Math. (2009), 941–960.
  * [8] , _The Ramsey number of dense graphs_ , B. Lond. Math. Soc. 45 (2013), no. 3, 483–496.
  * [9] D. Conlon, J. Fox, and B. Sudakov, _Short proofs of some extremal results III_ , Random Struct. Algor. 57 (2020), no. 4, 958–982.
  * [10] P. Erdős, _Some remarks on the theory of graphs_ , Bull. Amer. Math. Soc. 53 (1947), no. 4, 292–294.
  * [11] P. Erdős and G. Szekeres, _A combinatorial problem in geometry_ , Compos. Math. 2 (1935), 463–470.
  * [12] J. Fox, A. Grinshpun, A. Liebenau, Y. Person, and T. Szabó, _What is Ramsey-equivalent to a clique?_ , J. Comb. Theory B 109 (2014), 120–133.
  * [13] , _On the minimum degree of minimal Ramsey graphs for multiple colours_ , J. Comb. Theory B 120 (2016), 64–82.
  * [14] J. Fox and K. Lin, _The minimum degree of Ramsey-minimal graphs_ , J. Graph Theor. 54 (2007), no. 2, 167–177.
  * [15] J. Fox and B. Sudakov, _Two remarks on the Burr-Erdős conjecture_ , Eur. J. Combin. 30 (2009), no. 7, 1630–1645.
  * [16] A. Frieze and M. Karoński, _Introduction to random graphs_ , Cambridge University Press, 2016.
  * [17] A. Grinshpun, R. Raina, and R. Sengupta, _Minimum degrees of minimal Ramsey graphs for almost-cliques_ , J. Graph Theor. 85 (2017), no. 2, 349–362.
  * [18] A. V. Grinshpun, _Some problems in graph Ramsey theory_ , Ph.D. thesis, Massachusetts Institute of Technology, 2015.
  * [19] H. Guo and L. Warnke, _Packing nearly optimal Ramsey $r(3,t)$ graphs_, Combinatorica (2020), 1–41.
  * [20] H. Hàn, V. Rödl, and T. Szabó, _Vertex Folkman numbers and the minimum degree of minimal Ramsey graphs_ , SIAM J. Discrete Math. 32 (2018), no. 2, 826–838.
  * [21] S. Kogan, _New results on $k$-independence of graphs_, Electron. J. Comb. 24 (2017), P2.15.
  * [22] C. McDiarmid, _Concentration_ , Probabilistic methods for algorithmic discrete mathematics, Springer, 1998, pp. 195–248.
  * [23] F. P. Ramsey, _On a problem in formal logic_ , Proc. Lond. Math. Soc. 30 (1930), 264–286.
  * [24] V. Rödl and A. Ruciński, _Lower bounds on probability thresholds for Ramsey properties_ , Combinatorics, Paul Erdős is eighty 1 (1993), 317–346.
  * [25] V. Rödl and A. Ruciński, _Threshold functions for Ramsey properties_ , J. Amer. Math. Soc. 8 (1995), no. 4, 917–942.
  * [26] V. Rödl and M. Siggers, _On Ramsey minimal graphs_ , SIAM J. Discrete Math. 22 (2008), no. 2, 467–488.
  * [27] A. Sah, _Diagonal Ramsey via effective quasirandomness_ , arXiv preprint arXiv:2005.09251 (2020).
  * [28] J. Spencer, _Ramsey’s theorem – a new lower bound_ , J. Comb. Theory A 18 (1975), no. 1, 108–115.
  * [29] T. Szabó, P. Zumstein, and S. Zürcher, _On the minimum degree of minimal Ramsey graphs_ , J. Graph Theor. 64 (2010), no. 2, 150–164.

##  Appendix A Forests are Ramsey simple

######  Lemma A.1.

For every forest $F$ without isolated vertices and every integer $q\geq 2$, we
have $s_{q}(F)=1$.

For two colours, Lemma A.1 follows from the general result for bipartite
graphs of Szabó, Zumstein, and Zürcher [29, Theorem 1.3 and Corollary 1.5].
Their proof generalises easily to more colours. For the sake of completeness,
we include a simplified version of that proof here, dealing only with the case
of forests.

###### Proof.

Given $F$, fix a bipartition $V(F)=A\cup B$, where $|A|\leq|B|$ and the size
of $A$ is minimised. Set $a=|A|$, $b=|B|$, $B_{1}=\\{v\in
B:\leavevmode\nobreak\ d_{F}(v)=1\\}$, and $B_{\geq 2}=B\setminus B_{1}$. We
start by showing that $|B_{\geq 2}|\leq a-1$. Indeed, let $T_{1},\ldots,T_{k}$
be the components of $F$ and, for each $i\in[k]$, let $r_{i}$ be an arbitrary
vertex in $A\cap V(T_{i})$. Viewing $T_{i}$ as a tree rooted at $r_{i}$, we
note that each element of $B_{\geq 2}\cap V(T_{i})$ must have a child in
$A\cap V(T_{i})$ and, since $T_{i}$ is a tree, all of these children must be
different. Thus, $|A\cap V(T_{i})|\geq|B_{\geq 2}\cap V(T_{i})|+1$ for all
$i\in[k]$, and summing up over all components yields $|A|\geq|B_{\geq 2}|+1$.

Now, set $r=q(a-1),s=q^{r+1}v(F),$ and $t=sbq$, and let $G$ be the graph
constructed as follows:

  * •

let $V(G)=X\dot{\cup}Y\dot{\cup}Z$, where $|X|=r$, $|Y|=s$, and $|Z|=t$,

  * •

add a complete bipartite graph between $X$ and $Y$, and

  * •

partition $Z$ into $s$ subsets of size $bq$, indexed by the elements of $Y$.
That is, let $Z=\bigcup\limits_{y\in Y}Z_{y}$, where $|Z_{y}|=bq$. For each
$y\in Y$, connect $y$ to all vertices of $Z_{y}$.

Each vertex $v\in Z$ then satisfies $d_{G}(v)=1$. We will now show that (i)
$G-Z\not\rightarrow_{q}F$, and (ii) $G\rightarrow_{q}F$. From this it follows
directly that $G$ must contain a graph from $\mathcal{M}_{q}(F)$ with minimum
degree one, and hence that $s_{q}(F)=1$.

To see property (i), colour $E(G-Z)$ as follows: take any partition
$X=X_{1}\cup\ldots\cup X_{q}$ with $|X_{i}|=a-1$ for every $i\in[q]$, and
colour $E(X_{i},Y)$ in colour $i$. Then each colour class is a bipartite graph
with a partite set of size smaller than $a$. By the definition of $a$, there
cannot be a monochromatic copy of $F$.

We prove (ii) next. Consider any $q$-colouring $\varphi:E(G)\rightarrow[q]$.
Each vertex $y\in Y$ has $bq$ neighbours in $Z_{y}$, and hence there must be a
subset $Z_{y}^{\prime}\subseteq Z_{y}$ of size $b$ such that the edges from
$y$ to $Z_{y}^{\prime}$ are monochromatic. As we use only $q$ colours, there
must be a subset $Y^{\prime}\subseteq Y$ of $\frac{s}{q}$ vertices
$y_{1},\ldots,y_{s/q}$ such that, without loss of generality, the edges
between $y_{i}$ and $Z_{y_{i}}^{\prime}$ are all colour $1$ for each
$i\in[s/q]$. Further, set $Z^{\prime}=\bigcup\limits_{y_{i}\in
Y^{\prime}}Z_{y_{i}}^{\prime}$. Next, let $X=\\{x_{1},\ldots,x_{r}\\}$. For
every $y_{i}\in Y^{\prime}$, we consider the vector
$c_{i}:=(\varphi(x_{1}y_{i}),\ldots,\varphi(x_{r}y_{i}))\in[q]^{r}$, the
_colour profile_ of $y_{i}$. As $|Y^{\prime}|=s/q=q^{r}v(F)$, there must be at
least $v(F)$ vertices in $Y^{\prime}$ with the same colour profile $c$. By
symmetry, we may assume that $c_{1}=c_{2}=\ldots=c_{v(F)}=c$. We consider two
cases.

Case 1: There is a colour $i\in[q]$ that appears at least $a$ times in $c$.
This gives a copy of $K_{a,v(F)}$ between $X$ and
$\\{y_{1},\ldots,y_{v(F)}\\}$ that is monochromatic in colour $i$. As
$K_{a,v(F)}$ contains a copy of $F$, we are done.

Case 2: Every colour is used exactly $(a-1)$ times in $c$. In particular, we
find a subset $X^{\prime}\subseteq X$ of size $a-1$ such that the edges
between $X^{\prime}$ and $\\{y_{1},\ldots,y_{v(F)}\\}$ are monochromatic in
colour $1$. Using the edges between $y_{i}$ and $Z_{y_{i}}^{\prime}$, for
$i\in[v(F)]$, we find a monochromatic copy of $F$: embed $A$ into
$\\{y_{1},\ldots,y_{v(F)}\\}$ arbitrarily, embed $B_{1}$ into $Z^{\prime}$ by
respecting adjacency relation, and embed $B_{\geq 2}$ into $X^{\prime}$
arbitrarily. ∎