Ramsey simplicity of random graphs

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) \ge 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 first extend Grinshpun’s result by showing that $G(n,p)$ is not just $2$-Ramsey simple, but is in fact $q$-Ramsey simple for any $q = q(n)$, provided $p \ll n^{-1}$ or $\frac{\log n}{n} \ll p \ll n^{-2/3}$. Next, when $p \gg \left ( \frac{\log n}{n} \right )^{1/2}$, we find that $G(n,p)$ is not $q$-Ramsey simple for any $q \ge 2$. Finally, we uncover some interesting behaviour for intermediate edge probabilities. When $n^{-2/3} \ll p \ll n^{-1/2}$, we find that there is some finite threshold $\tilde{q} = \tilde{q}(H)$, depending on the structure of the instance $H \sim G(n,p)$ of the random graph, such that $H$ is $q$-Ramsey simple if and only if $q \le \tilde{q}$. Aside from a couple of logarithmic factors, this resolves the qualitative nature of the Ramsey simplicity of the random graph over the full spectrum of edge probabilities.

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 [1] 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 [2] and Erdős and Szekeres [3] that $r_2(K_t)$ is exponential in $t$ ; more precisely, they proved that $2^{t/2}\leq r_2(K_t) \leq 2^{2t}$ . Despite decades of continuous effort, the first improvement in the bases of these exponential bounds came only in 2023, when Campos, Griffiths, Morris, and Sahasrabudhe [4] announced an upper bound of $({4 - \varepsilon })^t$ (subsequently optimised by Gupta, Ndiaye, Norin, and Wei [5]). Prior to this breakthrough, all improvements had been in the lower-order terms, with Sah [6] building on previous work of Conlon [7] to reduce the upper bound by a superpolynomial factor; from below, Spencer [8] proved the best known lower bound, a mere factor of two larger than the original bound of Erdős.

In a bid to better understand the Ramsey property, researchers began exploring other parameters of Ramsey graphs in the 1970s, and we shall be interested in the minimum degree, the study of which began with the paper of Burr, Erdős, and Lovász [9]. 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 [9] for $q=2$ , as the smallest minimum degree among all minimal $q$ -Ramsey graphs for $H$ , that is,

\begin{align*} s_q(H) = \min \{\delta (G)\,:\, G\in \mathcal{M}_q(H)\}, \end{align*}

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) \le r_q(H) - 1$ . From below, as observed by Fox and Lin [10], a simple argument using the pigeonhole principle shows that $s_q(H) \ge 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 their original paper, Burr, Erdős, and Lovász [9] 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 \ge 5$ , we can determine $s_2(K_t)$ precisely for every $t$ . 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 [9], the parameter $s_q(H)$ has been studied for a number of different choices of $H$ and for larger $q$ ; see, for example, [10–20]. 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 [10] has been shown to be tight for many graphs. Following Grinshpun [17], we call such graphs $q$ -Ramsey simple.

Definition 1.1. A graph $H$ without isolated vertices is said to be $q$ -Ramsey simple if

\begin{align*} s_q(H) = q(\delta (H) - 1)+1. \end{align*}

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 \ge 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 [10], Szabó, Zumstein, and Zürcher [20], and Grinshpun [17] has established the $2$ -Ramsey simplicity of a wide range of bipartite graphs. Further results were proven in [13], including the $q$ -Ramsey simplicity of all cycles of length at least four, for any number of colours $q \ge 2$ . Based on these results, it is believed that simplicity is a more widespread phenomenon.

Conjecture 1.2 (Szabó, Zumstein, and Zürcher [20]). 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. We know that cliques are not simple, but are they an exceptional case, or is $q$ -Ramsey simplicity atypical for non-bipartite graphs? For a more concrete question, 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 [2] came from analysing the clique and independence numbers of random graphs, while a key ingredient in the best modern upper bounds is showing that graphs without large cliques or independent sets must be random-like. When it comes to more general Ramsey problems, the work of Rödl and Ruciński [21, 22] 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 [23] and Conlon [24] provided some lower and upper bounds on $r_2(H)$ for different ranges of $p$ , while Conlon, Fox, and Sudakov [25] showed 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 [17], who proved that sparse random graphs are 2-Ramsey simple with high probability.

Theorem 1.3 (Corollary 2.1.4 in [17]). 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 [17] can easily be extended to prove, 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, uncovering some unexpected behaviour in the process. Our main result qualitatively describes the Ramsey simplicity of the random graph $G(n,p)$ as the edge probability $p$ grows.

Theorem 1.4. Let $p = p(n) \in (0,1)$ and $H \sim G(n,p)$ . Then the following statements hold asymptotically almost surely.

1. (a) If $0 \lt p \ll n^{-1}$ or $\frac{\log n}{n} \ll p \ll n^{-\frac 23}$ , then $H$ is $q$ -Ramsey simple for all $q = q(n)$ .

2. (b) If $n^{-\frac 23} \ll p \ll n^{-\frac 12}$ , there is some finite $\tilde{q}(H)$ such that $H$ is $q$ -Ramsey simple if and only if $q \le \tilde{q}(H)$ .

3. (c) If $\left ( \frac{\log n}{n} \right )^{\frac 12} \ll p \lt 1$ , then $H$ is not $q$ -Ramsey simple for any $q \ge 2$ .

There are a few comments to be made at this point. First, observe that these results suggest some monotonicity in $q$ – in parts (a), (b), and (c), we have that, if $H$ is $q$ -Ramsey simple, then it is also $(q-1)$ -Ramsey simple. This is in fact a general phenomenon, true for all graphs $H$ and all numbers of colours $q$ , and we shall show this in Section 2. Given this monotone behaviour, we define the Ramsey simplicity threshold

\begin{equation*} \tilde {q}(H) \,:\!=\, \sup \{q\,:\, \; H \text { is } q\text{-Ramsey simple} \} \end{equation*}

for every graph $H$ . 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 \ge 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$ .

On the other hand, as we shall also remark in Section 2, we do not have monotonicity in $H$ . Indeed, a Ramsey simple graph can have subgraphs and supergraphs that are not Ramsey simple, and vice versa. However, Theorem1.4 shows that in the random graph, there is some large-scale negative correlation between the density of the graph and its Ramsey simplicity. That is, part (a) shows that very sparse random graphs are always Ramsey simple, while (c) asserts that somewhat denser random graphs are never Ramsey simple.

Meanwhile, part (b) shows that random graphs of intermediate density lie somewhere between these two extremes, as they are simple when we have few colours and not simple when we have many. We shall in fact prove a more precise version of this theorem (see Theorem5.1), which shows that the Ramsey simplicity of $H$ is essentially determined by the subgraph $F$ induced by the neighbourhood of the vertex of minimum degree, and will give lower and upper bounds on $\tilde{q}(H)$ in terms of $F$ . By analysing the random graph, we can then give quantitative bounds on $\tilde{q}(H)$ in this middle range.

Corollary 1.5. Let $k \ge 2$ be a fixed integer, let $n^{-\frac{k}{2k-1}} \ll p \ll n^{-\frac{k+1}{2k+1}}$ , and let $H \sim G(n,p)$ . Then, asymptotically almost surely, we have

\begin{equation*} (1 + o(1)) \frac {np}{k^2} \le \tilde {q}(H) \le (1 + o(1)) \frac {np}{k-1}. \end{equation*}

This corollary determines the threshold $\tilde{q}(H)$ – the largest number of colours for which $H$ is $q$ -Ramsey simple – up to a constant factor, and shows that its small-scale behaviour is quite different from its large-scale behaviour. Indeed, while Theorem1.4 shows $\tilde{q}(H)$ decreases from infinity to $1$ as $p$ increases from $\frac{\log n}{n}$ to $\left ( \frac{\log n }{ n } \right )^{\frac 12}$ , Corollary 1.5 shows that $\tilde{q}(H)$ grows as $p$ goes from $n^{-\frac{k}{2k-1}}$ to $n^{-\frac{k+1}{2k+1}}$ , for each fixed $k \ge 2$ . Thus, the overall decrease of $\tilde{q}(H)$ cannot be monotone in $p$ , as illustrated in Figure 1. Note that a more precise version of the above statement can be found in Corollary 5.2.

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

Our proofs shed some light on why this phenomenon occurs. We show in Section 3 that if we write $F$ for the subgraph of $H$ induced by the neighbourhood of its minimum degree vertex, then $H$ being $q$ -Ramsey simple is essentially equivalent to being able to pack $q$ edge-disjoint copies of $F$ on a set of $q(\delta (H) - 1) + 1$ vertices. For fixed $k$ , as $p$ increases from $n^{-\frac{k}{2k-1}}$ to $n^{-\frac{k+1}{2k+1}}$ , the minimum degree of $H$ grows, and so the order of $F$ increases. However, the complexity of $F$ does not – the order of its largest component remains $k$ . Thus, we have more space to work with, while the packing does not become much harder, which affords us the flexibility to pack more copies of $F$ .

1.4. Organisation and notation

In Section 2, we discuss the monotonicity of Ramsey simplicity and shall in particular justify the existence of the Ramsey simplicity threshold $\tilde{q}(H)$ . We then discuss general necessary and sufficient conditions for Ramsey simplicity in Section 3, relating the Ramsey simplicity problem for a particular class of graphs to a packing problem. Next, we turn to random graphs, collecting some useful properties in Section 4. In Section 5 we prove Theorem1.4. The constructions of Ramsey graphs that establish $q$ -Ramsey simplicity of $H$ are provided in Section 5.1, while the results on non- $q$ -Ramsey simplicity are proven in Section 5.2. The final section, Section 6, is devoted to concluding remarks and open problems.

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. A $q$ -edge-coloured graph $\Gamma$ is simply a graph $\Gamma$ equipped with an edge-colouring $f\,:\, E(\Gamma ) \rightarrow [q]$ . Given a graph $\Gamma$ with a $q$ -colouring $f$ 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$ .

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 [20], whereas the clique $K_t$ is not [9]. Similarly, there exist graphs that are $q$ -Ramsey simple but contain subgraphs that are not. For instance, Theorem 2.1.3 in [17] 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) \gt 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 \lt 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) \lt 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. Conditions for Ramsey simplicity

The goal of this section is to establish necessary and sufficient conditions for Ramsey simplicity, which we will later apply to the random graph to prove several parts of Theorem1.4 (and Theorem5.1). More specifically, we will relate the problem of determining whether a graph is $q$ -Ramsey simple to a certain packing problem.

Throughout this section we will assume that $H$ is a connected graph with a unique vertex of minimum degree, denoted by $u$ . Further, we will write $F$ for the subgraph induced by the neighbourhood of $u$ in $H$ , that is, $F = H[N(u)]$ . As suggested by the statement of Theorem5.1, the structure of this graph $F$ will play a key role in determining whether $H$ is $q$ -Ramsey simple.

We begin with the necessary condition.

Proposition 3.1. Let $q \ge 2$ , let $H$ be a connected graph containing a unique vertex $u$ of minimum degree, and let $F = H[N(u)]$ . Suppose $H$ is $q$ -Ramsey simple. Then there exists a $q$ -edge-coloured graph $\Gamma$ on $q(\delta (H) - 1) + 1$ vertices such that 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$ .

Proof. 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]$ .

As it turns out, under some additional constraints, the above necessary condition becomes sufficient. Since our aim will be to apply these conditions to a random graph, we describe several pseudorandom properties concerning the degrees, connectivity, and expansion of the target graph $H$ that will help us in the construction of minimal Ramsey graphs with vertices of low degree. These properties are collected in the definition below. As might be expected, for a large range of values of $p$ , the random graph $G(n,p)$ is very likely to satisfy these properties.

Definition 3.2 (Well-behaved). We say an $n$ -vertex graph $H$ is well-behaved if it satisfies the following properties:

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

2. (W2) every pair of vertices in $H$ has codegree at most $\tfrac 12 \delta (H)$ ,

3. (W3) $H$ is $3$ -connected, and

4. (W4) removing at most $\delta (H)$ vertices from $H$ cannot create a component of size $k \in \left[{\tfrac 12 \delta (H), \tfrac 12 n}\right]$ .

We now show that a well-behaved graph $H$ is guaranteed to be $q$ -Ramsey simple if it admits the existence of a colour pattern as in Proposition 3.1 in which the maximum degree of each $\Gamma _i$ is not too large.

Proposition 3.3. Let $q \ge 2$ , let $H$ be an $n$ -vertex 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.

Propositions 3.1 and 3.3 imply that, when establishing the $q$ -Ramsey simplicity of a well-behaved graph $H$ , we can focus our attention on the neighbourhood of the minimum degree vertex. We remark that the extra conditions required in Proposition 3.3, the well-behavedness of $H$ and property (ii), may not be necessary but they enable us to more easily 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 3.4 (Signal senders). Given a graph $H$ , a number of colours $q \ge 2$ , a distance $d \ge 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 of $S$ .

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 [9] and Burr, Nešetřil, and Rödl [27].

Theorem 3.5 ([26]). If $H$ is $3$ -connected, then for any $q \ge 2$ and $d \ge 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$ of $S$ with the edges $h_1$ and $h_2$ of $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 3.6. Let $q\geq 2$ , let $H$ be any 3-connected graph, and let $d \ge v(H)$ . Let $S = S^+(H,q,d,e,f)$ or $S = S^-(H,q,d,e,f)$ be a signal sender, let $G$ be any graph on a disjoint set of vertices, and let $g,h \in E(G)$ induce a matching in $G$ . If the graph $G^{\prime}$ is formed by attaching $S$ to $g$ and $h$ , then, for any copy $H_0$ of $H$ in $G^{\prime}$ , we have either $H_0 \subseteq G$ or $H_0 \subseteq S$ .

Proof. Let $H_0$ be a copy of $H$ in $G'$ and suppose for the sake of contradiction that $H_0$ is neither fully contained in $G$ nor in $S$ . We can then find edges $h_1 \in E(H_0) \cap \left ( E(S) \setminus E(G) \right )$ and $h_2 \in E(H_0) \cap \left ( E(G) \setminus E(S) \right )$ . Since the only edges of $S$ spanned by $V(G)$ are $e$ and $f$ , which are identified with $g,h \in E(G)$ , it follows that $h_1$ must contain a vertex $x \in V(S) \setminus V(G)$ . Similarly, since $g$ and $h$ induce a matching in $G$ , they are the only edges of $G$ spanned by $V(S)$ , and hence $h_2$ must contain a vertex $y \in V(G) \setminus V(S)$ .

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 \ge v(H)$ .

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

Proof of Proposition 3.3. 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:

1. (a) $G \rightarrow _q H$ ,

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

3. (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}) \le d_{G^{\prime}}(w) \le 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$ .

Figure 2. Construction of $G$ .

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 (W3) ensures $H$ is $3$ -connected, and hence by Theorem3.5 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 \lt 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 2.

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 3.7. 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 3.4(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 \lt 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 3.3, we find a colour- $i$ copy $F_{U,i}$ of $F$ in $\Gamma [U]$ , which we can complete to a monochromatic copy of $H$ by attaching $w$ and $R_{U,i}$ , contradicting our supposition.

Claim 3.8. 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 3.4, 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 3.6 that $H_0$ is fully contained either in a signal sender or 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,j}$ , for some subset $U$ and colour $j$ . First, note that since all edges incident to the vertices in $R_{U,j}$ are of colour $j$ , and $H_0$ is of colour $i$ , we must have $j = i$ . Now, 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})}| \le \tfrac 12 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}| \le |{V(H_0) \cap V(R_{U,i})}| \le \tfrac 12 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 (W2) implies $x$ has at most $\tfrac 12 \delta (H)$ neighbours in $U$ . As $d_{H_0}(x) \ge \delta (H)$ , this means $x$ must have at least $\tfrac 12 \delta (H)$ neighbours in $H_0 - U$ . Hence, we also have $|{K}| \ge \tfrac 12 \delta (H)$ . However, this contradicts condition (W4), as the removal of the vertices in $U\cap V(H_0)$ cannot create a component in $H_0$ of size between $\tfrac 12 \delta (H)$ and $\tfrac 12 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, proving the claim.

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

4. 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 Theorem1.4 (and Theorem5.1) and the deduction of Corollary 1.5 (and Corollary 5.2).

4.1. Facts about $G(n,p)$

We start by describing some properties of $G(n,p)$ for different values of $p$ . As most of the results presented in this section are well known, we will be very brief in the proofs. 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 [28, Theorem 2.3] and [29, Theorem 23.6]).

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

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

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

The following two lemmas collect some folklore bounds on the degrees and number of edges in $G(n,p)$ . We start by controlling the degrees.

Lemma 4.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 \ge 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 $H$ a.a.s. contains a star with $k-1$ edges, and hence $\Delta (H) \ge k-1$ ; see Theorem5.3 in [29] for more details. If $p = \frac{1}{nf}$ , a straightforward calculation shows that the expected number of vertices of degree at least $\frac{\log n}{\log\!(f \log n)}$ tends to infinity, which combined with an application of the second moment method (or of Theorem 3.1(ii) in [30]) establishes the desired result. Part (c) follows by applying Lemma 4.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. Both parts follow from simple applications of Lemma 4.1(a), in the second case in combination with a union bound, so we omit the proof.

Lemma 4.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^2p}{2}$ , and

2. (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 \ge \frac{20 \log n}{p}$ satisfies $e_H(S)\geq \frac{1}{4}s^2p$ .

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 4.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) \le \log n$ ,

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

3. (c) if $p = \frac{1}{nf}$ for some $f = f(n)$ satisfying $1 \ll f = n^{o(1)}$ , then $\lambda (H) \le (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 [29] for the details. Now suppose $H$ were to contain a tree on $t$ vertices. There are $\binom{n}{t}$ choices for the vertex set of the tree and $t^{t-2}$ possible labelled trees on that set, each of which appears with probability $p^{t-1}$ . Thus, the probability that $H$ contains any $t$ -vertex tree is at most $\binom{n}{t}t^{t-2}p^{t-1}$ . It is then straightforward to verify that, in each of the above cases, plugging in the claimed bound on $\lambda (H)$ for $t$ makes the corresponding probability $o(1)$ .

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. The proof is an easy application of the union bound and is thus omitted.

Lemma 4.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.

Finally, as might be expected, random graphs are highly likely to be well-behaved (recall Definition 3.2). This intuition is confirmed by the following lemma; we include a brief sketch of the proof.

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

Proof. Properties (W1) and (W3) are established in Theorem 3.9(i) of [30] and Theorem 4.3 in [29], respectively. Moreover, by Lemma 4.2(c) we may condition on $\delta (H)=(1\pm o(1))np$ . For property 2, observe that the distribution of the codegree of a given pair of vertices is $\mathrm{Bin}(n-2,p^2)$ . Now, considering the two cases $p^2 \geq \frac{10 \log n}{n}$ and $p^2 \leq \frac{10 \log n}{n}$ separately and applying parts (a) and (b) of Lemma 4.1 respectively yields the required result. Finally, for property (W4), note that for any fixed integers $1\leq s\leq \delta (H)$ and $k \in \left[{\tfrac 12 \delta (H), \tfrac 12 n}\right]$ and sets $U\in \binom{V(H)}{s}$ and $K\in \binom{V(H)-U}{k}$ , the probability that removing $U$ from $H$ leaves $K$ isolated is precisely $(1-p)^{k(n-k-s)}$ . Now taking a union bound over all choices of $s,k,U,$ and $K$ shows that the probability that property (W4) fails is $o(1)$ .

4.2. Transference lemma

As we will we see in the statement of Theorem5.1, our bounds on the simplicity threshold of $H \sim G(n,p)$ depend on the subgraph induced by the neighbourhood of the minimum degree vertex (which, by virtue of Lemma 4.6 and property (W1), we may assume to be unique for $p \gg \frac{\log n}{n}$ ). Our next lemma allows us to transfer what we know about the random graph $G(\delta (H), p)$ to this subgraph.

Lemma 4.7. Let $p=p(n)\in (0,1)$ be such that $\frac{\log n}{n} \ll p \ll 1$ . 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

\begin{equation*} {\mathbb {P}}\left ( G_s \in \mathcal {P}_s \right ) = 1 - o(1). \end{equation*}

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

Proof. We will follow an approach similar to that used in the proof of Corollary 2.1.4 in [17]. Before we proceed with the proof, we introduce some notation and facts that we will need later on. Let us first fix some $\beta _n=o(1)$ such that

(4.1) \begin{align} {\mathbb{P}}\left ( G_s \notin \mathcal{P}_s \right ) = o(\beta _n) \end{align}

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 4.6, specifically property (W1), and Lemma 4.2 we know that $X_\delta$ holds with high probability. In particular, we can find $\delta _n=o(1)$ such that

\begin{equation*} {\mathbb {P}}(0.5np\leq \delta (H) \leq 2np) \geq {\mathbb {P}}(X_{\delta })=1-\delta _n .\end{equation*}

We will also use the following two facts:

1. (1) There exists $\gamma _n= o(1)$ such that, 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]$ .

Part (1) follows from the proof of Theorem 3.9(i) in [30]. Part (2) follows from the fact that removing a vertex from a graph can reduce the minimum degree by at most one and that we can sample a graph $H\sim G(n,p)$ by first sampling $H^{\prime}\sim G(n-1,p)$ and then adding each potential edge containing the last vertex with probability $p$ , independently of all previous choices.

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) \lt 1-\varepsilon _n$ . Using (1) for $d = t_n$ , we conclude

(4.2) \begin{align} 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. \end{align}

Moreover, since $\varepsilon _n\gt \gamma _n + \delta _n$ , we obtain ${\mathbb{P}} (\delta (H) \leq t_n) \lt 1-\delta _n \lt{\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\left(n-1,p\right)$ . 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$ and write $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) \ge d+1$ for all $v \in V(H^{\prime}) \setminus S$ , and $d_{H^{\prime}}(v) \ge 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

(4.3) \begin{align} {\mathbb{P}}_{G(n,p)} (H[S] \in \mathcal{P}_d | X_{\delta } \land \{N(u) = S\}) ={\mathbb{P}}_{G(n-1,p)} (H^{\prime}[S] \in \mathcal{P}_d |C_S). \end{align}

Now, by the Law of Total Probability,

(4.4) \begin{align} &{\mathbb{P}}_{G(n,p)}(H[N(u)]\in \mathcal{P}_{d_H(u)} |X_{\delta }) \nonumber \\ &= \sum _{0 \le d \le n-1} \sum _{S \in \left({V\left(H^{\prime}\right) \atop d}\right)} {\mathbb{P}}_{G(n,p)} ({H[S] \in \mathcal{P}_d | X_{\delta } \land \{N(u) = S\} }) \cdot{\mathbb{P}}_{G(n,p)} ({N(u) = S | X_{\delta } }) \nonumber \\ & \geq \sum _{0.5np \le d \le t_n} \sum _{S \in \left({V\left(H^{\prime}\right) \atop d}\right)}{\mathbb{P}}_{G(n-1,p)}(H^{\prime}[S]\in \mathcal{P}_d| C_S) \cdot{\mathbb{P}}_{G(n,p)}(N(u) = S | X_{\delta }). \end{align}

Now let $d\in [0.5np, t_n]$ and $S\in \binom{V(H^{\prime})}{d}$ be fixed. To estimate the first factor, we observe that

(4.5) \begin{align} {\mathbb{P}}_{G(n-1,p)}(C_S) &\geq{\mathbb{P}}(\delta (H^{\prime})\geq d+1) \geq{\mathbb{P}}(\delta (H)\geq d+2) \notag \\ &\geq{\mathbb{P}}(\delta (H)\geq t_n+2) \geq{\mathbb{P}}(\delta (H)\geq t_n+1) - \gamma _n \geq \varepsilon _n/2, \end{align}

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 (4.2) and since $\varepsilon _n=\omega (\gamma _n)$ . Hence we have

\begin{align*}{\mathbb{P}}_{G(n-1,p)}({ H^{\prime}[S] \in \mathcal{P}_d | C_S }) & = 1 -{\mathbb{P}}_{G(n-1,p)}\left (H^{\prime}[S]\notin \mathcal{P}_d|C_S \right ) \\ &= 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)} \\ & \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)} \\ & \geq 1 - \frac{{\mathbb{P}}_{G(d,p)} \left (G_d\notin \mathcal{P}_d\right )}{\varepsilon _n/2} = 1 - o(1), \end{align*}

where for the second inequality we use (4.5) and that $H^{\prime}[S]\sim G(d,p)$ and the final estimate uses (4.1) and $\beta _n=o(\varepsilon _n)$ . Putting this into (4.4), we conclude that

\begin{align*}{\mathbb{P}}_{G(n,p)}(H[N(u)]\in \mathcal{P}_{d_H(u)} |X_{\delta }) & \geq \sum _{0.5np \le d \le t_n} \sum _{S \in \left({V(H^{\prime}) \atop d}\right)} (1-o(1)){\mathbb{P}}_{G(n,p)}(N(u) = S | X_{\delta }) \\ & = (1-o(1)){\mathbb{P}}_{G(n,p)}\left (0.5np\leq \delta (H) \leq t_n | X_{\delta } \right ) \\ & = (1-o(1)) \frac{{\mathbb{P}}_{G(n,p)}(\{\delta (H) \leq t_n\} \land X_{\delta })}{{\mathbb{P}}(X_\delta )} \\ & \geq (1-o(1)) \frac{1 -{\mathbb{P}}_{G(n,p)}(\delta (H) \gt t_n) -{\mathbb{P}}_{G(n,p)}(\overline{X_{\delta }})}{{\mathbb{P}}(X_\delta )} \\ & \geq (1-o(1)) \frac{1-\varepsilon _n-\delta _n}{1-\delta _n} = 1-o(1). \end{align*}

This proves the lemma.

4.3. The smallest neighbourhood

We can now combine the results from Section 4.1 with Lemma 4.7 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 Theorem1.4 (and Theorem5.1). As the proofs of the results in this section follow from simple applications of Lemma 4.7 combined with the corresponding results from Section 4.1, we choose to omit them.

To start with, for the proof of the Ramsey simplicity of $H$ in case (a) of Theorem1.4, when $\frac{\log n}{n} \ll p\ll n^{-\frac{2}{3}}$ , it will be important that $F$ is an empty graph. This is guaranteed by the following corollary.

Corollary 4.8. 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(u))=0$ .

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 4.9. 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^2p^3 \leq e(F)\leq 4n^2p^3$ .

Finally, in the range $n^{-\frac 23} \ll p \ll n^{-\frac 12}$ , 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 4.10. 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) \le \frac 12 \log n$ ,

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

3. (c) if $p = n^{-\frac 12}f^{-1}$ for some $f = f(n)$ satisfying $1 \ll f = n^{o(1)}$ , then $\lambda (F) \le \left (\frac 14 + 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 \ge 2$ , then $\Delta (F) \ge 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) \ge \left({\frac 12 - o(1)}\right) \frac{\log n}{\log\!( f^2 \log n )}$ .

5. Proof of Theorem1.4 and Corollary 1.5

In this section we prove Theorem1.4 and Corollary 1.5 by showing the following more precise result.

Theorem 5.1. Let $p = p(n) \in (0,1)$ and $H\sim G(n,p)$ . If $\frac{\log n}{n} \ll p \ll 1$ , then $H$ almost surely contains a unique vertex $u$ of minimum degree; in this case, we define $F = H[N(u)]$ to be the subgraph of $H$ induced by the neighbourhood of $u$ , and 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\lt 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) \ge (1 + o(1)) \max \left \{ \frac{\delta (H)}{\lambda (F)^2}, \frac{\delta (H)}{80 \log n} \right \}$ if $n^{-\frac 23} \ll p \ll n^{-\frac 12}$ .

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

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

Note that parts (a) and (b) of this theorem yield Theorem1.4(a), and together with part (c) they are proven in Section 5.1. Part (e) of this theorem is the same as Theorem1.4(c), and together with part 4 it is proven in Section 5.2. Lastly, Theorem1.4(b) follows from Lemma 2.1 and the bounds in parts (c) and (d) of the above theorem.

Additionally, by taking parts (c) and (d) of Theorem5.1 and plugging in the bounds on $\delta (H)$ , $e(F)$ , $\lambda (F)$ and $\Delta (F)$ obtained in Lemma 4.2 and Section 4.3, we can easily deduce the following quantitative result, which includes the statement of Corollary 1.5. We omit the details of these calculations.

Corollary 5.2. Let $k \ge 2$ be a fixed integer and let $f = f(n)$ satisfy $1 \ll f = n^{o(1)}$ . Let $p = p(n)$ satisfy $n^{-\frac 23} \ll p \ll \left ( \frac{\log n}{n} \right )^{\frac 12}$ 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} \le \tilde{q}(H) \le (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} \le \tilde{q}(H) \le (1 + o(1))\frac{np}{k-1}.$

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

4. (d) if $n^{-\frac 12} \ll p \ll \left ( \frac{\log n}{n} \right )^{\frac 12}$ , then $1 \le \tilde{q}(H) \le \frac{8}{p}$ .

5.1. Simplicity for $G(n,p)$

In this section we prove the lower bounds on $\tilde{q}(G(n,p))$ from Theorem5.1. 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 4.4 we know $H$ is a forest with high probability when $p \ll n^{-1}$ . Szabó, Zumstein, and Zürcher [20] proved that all forests are $2$ -Ramsey simple, and their proof extends directly to show $q$ -Ramsey simplicity for all $q \ge 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. By Lemma 4.6, 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 a position to apply Proposition 3.3. Thus, to prove the required results it is sufficient to show that a coloured graph $\Gamma$ satisfying conditions (i) and (ii) almost surely exists. We shall therefore use the results of Section 4 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 23}$ .

Proof of Theorem 5.1(b). Let $q \ge 2$ , let $p$ satisfy $\frac{\log n}{n} \ll p \ll n^{-\frac 23}$ , and let $H \sim G(n,p)$ . By Lemma 4.6 and Corollary 4.8, 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 3.3 are then trivially satisfied, and so it follows that $H$ is $q$ -Ramsey simple.

When $p \gg n^{-\frac 23}$ , we will begin to see edges in the neighbourhood of the minimum degree vertex. Provided $p \ll n^{-\frac 12}$ , 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 5.1(c), first bound. Let $n^{-2/3}\ll p\ll n^{-1/2}$ and $H \sim G(n,p)$ . By Lemma 4.6, we know that with high probability $H$ is well-behaved. Given any $\varepsilon \gt 0$ , we shall show that, as $n$ tends to infinity, $H$ is with high probability $q$ -Ramsey simple for every $q \le ({1 - 5 \varepsilon }) \frac{\delta (H)}{\lambda (F)^2}$ .

Corollaries 4.9 and 4.10 show that $F = H[N(u)]$ , the subgraph induced by the neighbourhood of the minimum degree vertex $u$ , 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) \le \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 $({1 - \varepsilon }) \frac{\delta (H)}{\lambda (F)}$ . By the upper bound of Baker, Harman, and Pintz [31] on prime gaps, we have $s \ge ({1 - 2 \varepsilon }) \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 \le s^2$ and $q \leq s \le \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 3.3, 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) \le s-1 \le \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 \ge 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}}| \ge ({1 - \varepsilon }) \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 12 - o(1)}$ and $\lambda (F)$ gets larger, a probabilistic construction yields a better bound.

Proof of Theorem 5.1(c), second bound. Let $p \ll n^{-\frac 12}$ , and let $H \sim G(n,p)$ . Our goal is to show that if $q \le \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 3.3.

By Lemma 4.2(c) and Lemma 4.6, we may assume that $H$ is well-behaved with $\delta (H) = (1\pm o(1)) np$ . Furthermore, applying Corollaries 4.9 and 4.10, 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({\delta (H)})$ edges, and whose largest tree has at most $\log n$ vertices. We label the nontrivial 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\left(N,\tfrac{1}{2}\right)$ 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\left(N,\tfrac{1}{2q}\right)$ . Hence, it follows from Lemma 4.2(c), combined with a union bound over the number of colours $q$ , that with high probability $\Delta (\Gamma _i) \le ({1 + o(1)}) \tfrac{N}{2q} \lt \delta (H)$ for every $i\in [q]$ . This establishes property (ii) of Proposition 3.3.

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 \ge 0$ , for any set $U^{\prime}$ of $(1- \varepsilon ) \delta (H) \ge \tfrac 12 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 4.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 12 np \gt \frac{20 \log N}{1/(2q)}$ vertices is at least $\tfrac 14 \left({\tfrac 12 np}\right)^2 \tfrac{1}{2q} \gt 2 np \log n$ .

Since the set $U^{\prime}$ spans at least $2 np \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 3.3 it follows that $H$ is $q$ -Ramsey simple.

5.2. Non-simplicity for $G(n,p)$

In this section we prove the upper bounds on $\tilde{q}(H)$ from Theorem5.1. 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$ .

We begin with the upper bounds for case (d) of our theorem. For this, we shall make use of the necessary condition provided by Proposition 3.1. 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 [32].

Theorem 5.3 ([32]). 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]) \le k$ .

Proof of Theorem 5.1(d). Let $n^{-2/3}\ll p\ll 1$ and $H\sim G(n,p)$ . By Lemma 4.6, we know that $H$ has a unique vertex $u$ of minimum degree. As before, we set $F = H[N(u)]$ . Suppose that $H$ is $q$ -Ramsey simple; it follows from Proposition 3.1 that there is an edge-coloured graph $\Gamma$ on $N = q(\delta - 1)+1$ vertices such that the induced graph on every $\delta (H)$ -subset of the vertices of $\Gamma$ contains, in each colour, a copy of $F$ .

We are now ready to prove that $\tilde{q}(H) \le \frac{\delta (H)}{\Delta (F)} + 1$ . 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 \left({N \atop 2}\right)}{qN}=\frac{N-1}{q} = \delta - 1$ . Thus, by Theorem5.3, $\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

\begin{equation*} \frac {\Delta (F)N}{\delta (H)+\Delta (F)-1} \le \delta (H) - 1, \end{equation*}

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

We turn our attention to the second bound, namely $\tilde{q}(H) \le \frac{\delta (H)^2}{2 e(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 end this section with a proof of Theorem5.1(e).

Proof of Theorem 5.1(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 4.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 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 [17] 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) \ge 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 12 - o(1)}$ , logarithmic factor. We note further that in the range $\frac{\log n}{n}\ll p\ll n^{-1/2}$ , we can actually show that the following stronger statement is true almost surely for the same values of $q$ as in Theorem5.1: not only does there exist a minimal $q$ -Ramsey graph for $H\sim G(n,p)$ that contains a vertex of degree $q(\delta (H)-1)+1$ , but we can actually show that there exist minimal $q$ -Ramsey graphs with arbitrarily many vertices of this degree; we provide the details in the arXiv version of this paper.

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 $p = \Omega \left ( \frac{1}{n} \right )$ and $ 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 [20], 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 between $p= \Omega \left({ n^{-\frac{1}{2}} }\right)$ and $ 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 12 - o(1)}$ , as demonstrated in Corollary 5.2. 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 $p= \Omega \left({ n^{-\frac{1}{2}} }\right)$ and $ 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 Proposition 3.1. 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 Corollary 5.2 (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 3, 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 5.1 are obtained by finding such $\Gamma$ (with additional properties as given in Proposition 3.3) 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$ vertices 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 Theorem5.1 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\lt p\lt 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 \ge 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 [16].

Question 6.5. How large is $s_2(H)$ for $H\sim G\left(n,\frac{1}{2}\right)$ 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 [20] 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 5.1 can be used to resolve a special case of a conjecture due to Grinshpun [17], stating that all triangle-free graphs are $2$ -Ramsey simple. In [16], 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.