# A Jump of the Saturation Number
in Random Graphs?

Sahar Diskin111School of Mathematical Sciences, Tel Aviv University, Tel Aviv
6997801, Israel. Ilay Hoshen222School of Mathematical Sciences, Tel Aviv
University, Tel Aviv 6997801, Israel. Maksim Zhukovskii333Department of
Computer Science, The University of Sheffield, Sheffield S1 4DP, United
Kingdom.

###### Abstract

For graphs $G$ and $F$, the saturation number $\textit{sat}(G,F)$ is the
minimum number of edges in an inclusion-maximal $F$-free subgraph of $G$. In
2017, Korándi and Sudakov initiated the study of saturation in random graphs.
They showed that for constant $p\in(0,1)$, whp
$\textit{sat}\left(G(n,p),K_{s}\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$.

We show that for every graph $F$ and every constant $p\in(0,1)$, whp
$\textit{sat}\left(G(n,p),F\right)=O(n\ln n)$. Furthermore, if every edge of
$F$ belongs to a triangle, then the above is the right asymptotic order of
magnitude, that is, whp $\textit{sat}\left(G(n,p),F\right)=\Theta(n\ln n)$. We
further show that for a large family of graphs $\mathcal{F}$ with an edge that
does not belong to a triangle, which includes all the bipartite graphs, for
every $F\in\mathcal{F}$ and constant $p\in(0,1)$, whp
$\textit{sat}\left(G(n,p),F\right)=O(n)$. We conjecture that this sharp
transition from $O(n)$ to $\Theta(n\ln n)$ depends only on this property, that
is, that for any graph $F$ with at least one edge that does not belong to a
triangle, whp $\textit{sat}\left(G(n,p),F\right)=O(n)$.

We further generalise the result of Korándi and Sudakov, and show that for a
more general family of graphs $\mathcal{F}^{\prime}$, including all complete
graphs $K_{s}$ and all complete multipartite graphs of the form
$K_{1,1,s_{3},\ldots,s_{\ell}}$, for every $F\in\mathcal{F}^{\prime}$ and
every constant $p\in(0,1)$, whp
$\textit{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$.
Finally, we show that for every complete multipartite graph
$K_{s_{1},s_{2},\ldots,s_{\ell}}$ and every $p\in\left[\frac{1}{2},1\right)$,
$\textit{sat}\left(G(n,p),K_{s_{1},s_{2},\ldots,s_{\ell}}\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$.

##  1 Introduction

###  1.1 Background and main results

For two graphs $G$ and $F$, a subgraph $H\subseteq G$ is said to be
$F$-saturated in $G$ if it is a maximal $F$-free subgraph of $G$, that is, $H$
does not contain any copy of $F$ as a subgraph, but adding any missing edge
$e\in E(G)\setminus E(H)$ creates a copy of $F$ (throughout the paper, we
assume for convenience that $F$ does not contain isolated vertices and note
that it does not cause any loss of generality). The minimum number of edges in
an $F$-saturated subgraph in $G$ is called the saturation number, which we
denote by $\textit{sat}(G,F)$. Zykov [12], and independently Erdős, Hajnal,
and Moon [5] initiated the study of the saturation number of graphs,
specifically of $\textit{sat}(K_{n},K_{s})$. Since then, there has been an
extensive study of $\textit{sat}(K_{n},F)$ for different graphs $F$. Note that
the maximum number of edges in an $F$-saturated graph is $ex(n,F)$, and hence
the saturation problem of finding $\textit{sat}(K_{n},F)$ is, in some sense,
the opposite of Turán problem. Of particular relevance is the following result
due to Kászonyi and Tuza [9], which shows that for every graph $F$, there
exists some constant $c=c(F)$ such that $\textit{sat}(K_{n},F)\leq cn$. We
refer the reader to [6] for a comprehensive survey on results on saturation
numbers of graphs.

In 2017, Korándi and Sudakov initiated the study of the saturation problem for
random graphs, that is, when the host graph $G$ is the binomial random graph
$G(n,p)$ for constant $p$. Considering the saturation number for cliques in
the binomial random graph, $\textit{sat}(G(n,p),K_{s})$, they showed the
following:

######  Theorem 1.1 (Theorem 1.1 in [10]).

Let $0<p<1$ be a constant and let $s\geq 3$ be an integer. Then whp444With
high probability, that is, with probability tending to $1$ as $n$ tends to
infinity.

$\displaystyle\textit{sat}\left(G(n,p),K_{s}\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n.$

If $F$ is a graph such that every $e\in E(F)$ belongs to a triangle, it is not
hard to see that $\textit{sat}\left(G(n,p),F\right)=\Omega(n\ln n)$. Indeed,
the neighbourhood $N_{H}(v)$ of every vertex $v$ in the saturated subgraph $H$
should dominate its neighbourhood in $G(n,p)$, and thus whp $|N_{H}(v)|$
should be at least of logarithmic order in $n$. More precisely, the lower
bound in [10] comes from the following:

######  Theorem 1.2 (Theorem 2.2 in [10]).

Let $0<p<1$ be a constant. Let $F$ be a graph such that every $e\in E(F)$
belongs to a triangle in $F$. Then whp

$\displaystyle\textit{sat}\left(G(n,p),F\right)\geq\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n.$

Following [10], there has been subsequent work on the saturation number
$\textit{sat}\left(G(n,p),F\right)$ for other concrete graphs $F$. Mohammadian
and Tayfeh-Rezaie [11] and Demyanov and Zhukovskii [3] proved tight
asymptotics for $F=K_{1,s}$. Demidovich, Skorkin and Zhukovskii [2] proved
that whp $\textit{sat}\left(G(n,p),C_{m}\right)=n+\Theta\left(\frac{n}{\ln
n}\right)$ when $m\geq 5$, and showed that whp
$\textit{sat}(G(n,p),C_{4})=\Theta(n)$.

In this paper, we revisit the problem of saturation number in $G(n,p)$. Our
first main result gives a general upper bound, holding for all graphs $F$.

######  Theorem 1.

Let $0<p<1$ be a constant. Let $F$ be an arbitrary graph. Then whp

$\textit{sat}\left(G(n,p),F\right)=O(n\ln n).$

Comparing with the result of [9], Theorem 1 shows that the saturation number
in random graphs can be larger than the saturation number in $K_{n}$ by at
most a factor of $O(\ln n)$, whereas Theorem 1.2 shows that this is
asymptotically tight.

We note that the hidden constant in $O(n\ln n)$ which we obtain in the proof
may depend on the probability $p$ and the graph $F$. Note that if every edge
of $F$ belongs to a triangle in $F$, then Theorems 1 and 1.2 imply that whp
$\textit{sat}\left(G(n,p),F\right)=\Theta(n\ln n)$. In fact, we conjecture
that the asymptotics of the saturation number are dictated by the limitations
of Theorem 1.2. That is:

######  Conjecture 1.3.

Let $0<p<1$ be a constant. If $F$ is a graph such that every $e\in E(F)$
belongs to a triangle in $F$, then whp

$\displaystyle\textit{sat}\left(G(n,p),F\right)=\Theta(n\ln n).$

On the other hand, if $F$ is a graph such that there exists $e\in E(F)$ which
does not belong to a triangle in $F$, then whp

$\displaystyle\textit{sat}\left(G(n,p),F\right)=O(n).$

Our second main result further advances us towards settling this conjecture.
We define a family of graphs for which the saturation number in $G(n,p)$ is
typically linear in $n$. Given a graph $F$, let $I_{\mathrm{max}}(F)$ be a
largest colour class of $F$ among all proper colourings of $F$ with $\chi(F)$
colours, where $\chi(F)$ is the chromatic number of $F$. We say that a graph
$F$ has the property $(\ntriangleright)$ if there exists an
$I_{\mathrm{max}}(F)$ and a vertex $v\in V(F)\setminus I_{\mathrm{max}}(F)$
such that $N_{F}(v)\subseteq I_{\mathrm{max}}(F)$ (see Figure 1). Note that
every bipartite graph satisfies property $(\ntriangleright)$.

######  Theorem 2.

Let $0<p<1$ be a constant. Let $F$ be a graph with property
$(\ntriangleright)$. Then whp

$\textit{sat}\left(G(n,p),F\right)=O(n).$

Once again, the hidden constant in $O(n)$ which we obtain in the proof may
depend on the probability $p$ and the graph $F$. Furthermore, observe that the
vertex $v$ in Theorem 2 does not belong to a triangle in $G$. In particular,
since we assume $F$ has no isolated vertices and thus $v$ is not an isolated
vertex, there exists at least one edge which does not lie in a triangle in
$F$, supporting the second part of Conjecture 1.3, although not resolving it
completely. Furthermore, Theorem 2 extends the asymptotic results of [3], as
every $F=C_{m}$ also satisfies property $(\ntriangleright)$.

Figure 1: An illustration of graphs satisfying property $(\ntriangleright)$.

The second part of the paper aims for tight asymptotic bounds. Indeed, more
ambitiously, one could try and aim for tight asymptotics in the case where
every edge of $F$ belongs to a triangle (as in Theorems 1.1 and 1.2). Our next
two results aim at extending the tight asymptotics of Theorem 1.1 to a wider
family of graphs. The first one extends Theorem 1.1 to complete multipartite
graphs for $p\geq\frac{1}{2}$.

######  Theorem 3.

Let $\ell\geq 3$ and $s_{1}\leq s_{2}\leq\ldots\leq s_{\ell}$. If
$p\geq\frac{1}{2}$, then whp

$\textit{sat}\left(G(n,p),K_{s_{1},\ldots,s_{\ell}}\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n.$

The second one defines a family of graphs for which the above is an asymptotic
upper bound for all values of $p$. For two graphs $A$ and $B$, we say that a
graph $B$ is $A$-degenerate, if every two-vertex-connected subgraph of it is a
subgraph of $A$. Furthermore, we say that a graph $F=(V,E)$ has the property
$(\star)$ if there is an edge $\\{u,v\\}=e\in E$ such that for every
independent set $I\subseteq V$, we have that $F[V\setminus I]$ is
non-$F[V\setminus\\{u,v\\}]$-degenerate, that is, there exists a two-vertex-
connected subgraph of $F[V\setminus I]$ which is not a subgraph of
$F[V\setminus\\{u,v\\}]$.

######  Theorem 4.

Let $F$ be a graph with property $(\star)$. Then whp

$\textit{sat}\left(G(n,p),F\right)\leq\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n.$

Let us mention a family of graphs satisfying property $(\star)$, which could
be of particular interest. Let $F$ be a graph with an edge $\\{u,v\\}$ such
that there exists a proper colouring of $F$ with $\chi(F)$ colours, where
$\\{u\\}$ and $\\{v\\}$ are distinct colour classes (see Figure 2), and let us
further suppose that for every independent set $I\subseteq V(F)$,
$F[V(F)\setminus I]$ is two-vertex-connected. Then $F\setminus\\{u,v\\}$ is
$\chi(F)-2$ colourable, whereas for any independent set $I$, $F[V\setminus I]$
requires at least $\chi(F)-1$ colours, and therefore $F$ satisfies property
$(\star)$.

Figure 2: An illustration of the edge $\\{u,v\\}$ and the remaining graph
$F\setminus\\{u,v\\}$.

Note that if, in addition, every edge of $F$ lies in a triangle, then by
Theorem 1.2, we obtain sharp asymptotics. That is, whp
$\textit{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$.
In particular, we obtain the following corollary.

######  Corollary 1.4.

Let $0<p<1$ be a constant. Let $\ell\geq 3$ and $s_{3},\ldots,s_{\ell}\geq 1$
be integers. Let $F=K_{1,1,s_{3},\ldots,s_{\ell}}$. Then whp

$\displaystyle\textit{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n.$

Theorem 1.2 together with Theorems 3 and 4 suggest that one may make a more
ambitious claim in Conjecture 1.3, stating that if every edge of $F$ lies in a
triangle, then whp
$\textit{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$
(see more on that in Section 5).

###  1.2 Main methods and organisation

The structure of the paper is as follows. In Section 2 we present and
establish several lemmas that will be useful for us throughout the paper.

In Section 3 we prove Theorems 1 and 2. Both proofs rely on Lemma 3.1, where
we use the notion of an $\mathcal{F}$-saturated graph for a family of graphs
$\mathcal{F}$. We say that a graph $H$ is $\mathcal{F}$-saturated if $H$ does
not contain a copy of any $F\in\mathcal{F}$, yet adding an edge closes a copy
of at least one $F\in\mathcal{F}$. The proof of Theorem 2 follows rather
immediately from the same construction given in Lemma 3.1, whereas the proof
of Theorem 1 utilises an inductive argument based on this construction.

In Section 4 we prove Theorems 3 and 4. The proof of Theorem 4 utilises the
construction of [10], refined with the following lemma. For every two graphs
$G$ and $A$, and $\varepsilon>0$, we say that a graph $G$ is
$\varepsilon$-dense with respect to $A$ if every induced subgraph of $G$ on at
least $\varepsilon|V(G)|$ vertices contains a copy of $A$. Finally, given a
family of graphs $\mathcal{F}$, we say that $G$ is $\mathcal{F}$-free if it
does not contain a subgraph isomorphic to $F$ for every $F\in\mathcal{F}$. We
will make use of the following result (see Remark 2 in [4]):

######  Lemma 1.5.

Let $p\in(0,1)$. Let $A$ be a graph and let $\mathcal{F}$ be a family of
graphs such that every $F\in\mathcal{F}$ is non-$A$-degenerate. Then for every
sufficiently small $\delta>0$, whp there is a spanning subgraph in $G(n,p)$
which is $\mathcal{F}$-free and $n^{-\delta}$-dense with respect to $A$.

We note that in [4] it was shown that the condition on $\mathcal{F}$ in the
above lemma is not only sufficient, but also necessary. In particular, this
implies some limitations in the results that can be obtained using the
construction of [10] (see Section 5 for more details on the matter).

The proof of Theorem 3 is more delicate, and is the most involved in this
paper. Let us briefly outline the key ideas in the construction, while
comparing them with the construction of [10] for cliques.

Very roughly, in [10], one takes a set $A$ on $\Theta(\log n)$ vertices, and
let $B\coloneqq[n]\setminus A$. One can then find in $A$ a spanning subgraph
that is $K_{s-1}$-free, but $(1/\ln^{3}|A|)$-dense with respect to $K_{s-2}$,
denote this subgraph by $A^{\prime}$. Let $H$ be the subgraph of $G(n,p)$ with
all the edges between $A$ and $B$, all the edges of the subgraph $A^{\prime}$,
and no edges inside $B$. Then, typically almost any pair of vertices $u,v$ in
$B$ is likely to have many common neighbours in $A$ and one can find a copy of
$K_{s-2}$ in $A^{\prime}$ induced by this common neighbourhood, such that
together with the edge $\\{u,v\\}$ they close a copy of $K_{s}$, while on the
other hand the graph is $K_{s}$-free since $A^{\prime}$ is $K_{s-1}$-free and
$B$ is empty.

Thus, in the case of a complete graph, one is mainly concerned with the
property that the endpoints of every edge in $G(n,p)[B]$ have a large common
neighbourhood in $A$. However, in the case of a complete $r$-partite graph $F$
with all parts being non-trivial, one cannot assume that in every large
induced subgraph of $A^{\prime}$ there is a copy of $F$ minus an edge, as
otherwise it is easy to see that our graph is not $F$-free. In particular, one
cannot consider an empty graph in $B$. Moreover, a suitable subgraph that we
take in $B$ should satisfy the property that every vertex and its
$B$-neighbours have a large common neighbourhood in $A$. In order to show the
likely existence of such a subgraph in $B$, we use a coupling with an
auxiliary random graph in a Hamming space and prove a tight bound for its
independence number using a covering-balls argument.

Finally, in Section 5 we discuss the obtained results and some of their
limitations, and mention some questions as well as open problems.

##  2 Preliminary lemmas

Given a graph $H$ and a vertex $v\in V(H)$, we denote by $N_{H}(v)$ the
neighbourhood of $v$ in $H$ and by $d_{H}(v)=|N_{H}(v)|$. Given a subset
$S\subseteq V(H)$, we denote by $N_{H}(S)$ the common neighbourhood of all
$v\in S$ in $H$ and by $d_{H}(S)=|N_{H}(S)|$. That is,
$N_{H}(S)\coloneqq\bigcap_{v\in S}N_{H}(v)$. Finally, given subsets
$S_{1},S_{2}\subseteq V(H)$, we denote by $N_{H}(S_{1}|S_{2})$ the common
neighbourhood of $S_{1}$ in $S_{2}$ in the graph $H$ and by
$d_{H}(S_{1}|S_{2})=|N_{H}(S_{1}|S_{2})|$. That is,
$N_{H}(S_{1}|S_{2})\coloneqq N_{H}(S_{1})\cap S_{2}$. When the graph $H$ is
clear from context, we may omit the subscript. We denote by $K_{s}^{\ell}$ the
complete-$\ell$-partite graph where each part is of size $s$. We omit rounding
signs for the sake of clarity of presentation.

We will make use of the following bounds on the tail of binomial distribution
(see, for example, Appendix A in [1] and [10, Claim 2.1]).

######  Lemma 2.1.

Let $N\in\mathbb{N}$, $p\in[0,1]$, and $X\sim Bin(N,p)$. Then, for any $t>0$,

$\displaystyle\mathbb{P}\left(|X-Np|\geq t\right)\leq
2\exp\left(-\frac{t^{2}}{3Np}\right),$ (1)
$\displaystyle\mathbb{P}(X>tNp)\leq\left(\frac{e}{t}\right)^{tNp},$ (2)
$\displaystyle\mathbb{P}\left(X\leq\frac{N}{\ln^{2}N}\right)\leq(1-p)^{N-\frac{N}{\ln
N}}.$ (3)

We will require the following probabilistic lemma which shows that large
enough sets are very likely to have a vertex whose number of neighbours in
this set deviates largely from the expectation.

For every $p\in(0,1)$, we set

$\displaystyle\rho(p)\coloneqq\frac{1}{1-p}.$ (4)

When the choice of $p$ is clear, we may abbreviate $\rho\coloneqq\rho(p)$.

######  Lemma 2.2.

Let $p\in\left[\frac{1}{2},1\right)$. For every $\gamma\geq 0$, there exist
sufficiently small $\epsilon>0$ such that the following holds. Let $X$ and $Y$
be disjoint sets of vertices of sizes $(1+\epsilon)\log_{\rho}n$ and at least
$\frac{n}{\ln^{3}n}$, respectively. Then,

$\displaystyle\mathbb{P}\left(\forall y\in Y\
d(y|X)<\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n\right)\leq\exp\left(-n^{\epsilon}\right).$

###### Proof.

Note that for every vertex $y\in Y$, the number of neighbours of $y$ in $X$ in
the graph $G(n,p)$ is distributed according to $Bin(|X|,p)$. Hence, for a
fixed $y\in Y$,

$\displaystyle\mathbb{P}\Big{(}d(y|X)\geq$
$\displaystyle\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n\Big{)}\geq\mathbb{P}\left(d(y|X)=\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n\right)$
$\displaystyle=\binom{|X|}{\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n}p^{\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n}(1-p)^{\gamma\epsilon\log_{\rho}n}$
$\displaystyle\geq\left(\frac{(1+\epsilon)(1-p)}{\gamma\epsilon}\right)^{\gamma\epsilon\log_{\rho}n}p^{\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n}$
$\displaystyle\geq(1-p)^{\gamma\epsilon\log_{1-p}\left(\frac{1+\epsilon}{\gamma\epsilon}\right)\log_{\rho}n+\gamma\epsilon\log_{\rho}n}(1-p)^{(\log_{1-p}p)\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n}$
$\displaystyle=n^{-\gamma\epsilon\log_{1-p}\left(\frac{1+\epsilon}{\gamma\epsilon}\right)-(\log_{1-p}p)\left(1+(1-\gamma)\epsilon\right)-\gamma\epsilon}.$

Since $p\geq\frac{1}{2}$, we have that $\log_{1-p}p\leq 1$ and thus

$\displaystyle\mathbb{P}\Big{(}d(y|X)\geq\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n\Big{)}$
$\displaystyle\geq
n^{-\gamma\epsilon\log_{1-p}\left(\frac{1+\epsilon}{\gamma\epsilon}\right)-1-\epsilon}$
$\displaystyle\geq n^{-1+2\epsilon},$

where the last inequality is true since for sufficiently small $\epsilon$ we
have
$-\gamma\epsilon\log_{1-p}\left(\frac{1+\epsilon}{\gamma\epsilon}\right)\geq
3\epsilon$.

Therefore, since $d(y|X)$ are independent for $y\in Y$, we obtain that

$\displaystyle\mathbb{P}\left(\forall y\in Y\
d_{G(n,p)}(y|X)\leq\left(1+(1-\gamma)\epsilon\right)\log_{\rho}n\right)$
$\displaystyle\leq\left(1-n^{-1+2\epsilon}\right)^{|Y|}$
$\displaystyle\leq\exp\left(-n^{\epsilon}\right),$

where in the last inequality we used our assumption that
$|Y|\geq\frac{n}{\ln^{3}n}$. ∎

We will also utilise the fact that random graphs typically have relatively
small chromatic number (see, for example, Chapter 7 in [7]):

######  Lemma 2.3.

Let $0<p<1$ be a constant. Then whp $\chi(G(n,p))=O\left(\frac{n}{\ln
n}\right)$.

##  3 Global bounds

We begin by giving a construction showing that, for any family of graphs which
contains at least one bipartite graph, whp the saturation number in $G(n,p)$
is linear in $n$. This construction will be key for both the proofs of
Theorems 1 and 2.

######  Lemma 3.1.

Let $p\in(0,1)$. Let $\mathcal{F}$ be a family of graphs which contains at
least one bipartite graph. Then whp

$\displaystyle\textit{sat}\left(G(n,p),\mathcal{F}\right)=O(n).$

###### Proof.

Set

$\displaystyle\ell\coloneqq\min\left\\{|V_{1}|\colon
F\in\mathcal{F},\chi(F)=2,V_{1}\text{ and }V_{2}\text{ are colour classes of
}F\text{ and }V(F)=V_{1}\sqcup V_{2}\right\\}.$

We may assume that $\ell\geq 2$, as the case of star is immediate — an
$\mathcal{F}$-saturated graph then has bounded maximum degree. Let us further
denote by $F_{0}$ a bipartite graph from $\mathcal{F}$ which achieves the
above $\ell$.

Let $\tau$ be the smallest integer satisfying

$(1-p^{\ell-1})^{\tau}n\leq n^{2/5}.$

We construct a subgraph $H\subseteq G(n,p)$ which is $\mathcal{F}$-saturated
such that whp $|E(H)|=O(n)$ in two stages. Let us fix $\tau$ vertex disjoint
sets of size $\ell-1$, denote them by $A_{1},\ldots,A_{\tau}$ and set
$A=\bigcup_{i}A_{i}$. We then proceed iteratively. At the first step, we set
$B_{1}$ to be the set of all common neighbours of $A_{1}$ in $G(n,p)$ among
the vertices outside $A$. At the $i$-th step, where $1<i\leq\tau$, we set
$B_{i}$ to be the set of all common neighbours of $A_{i}$ in $G(n,p)$ among
the vertices outside $A\cup\bigcup_{j<i}B_{j}$. The subgraph $H$ contains all
the edges between $A_{i}$ and $B_{i}$ in $G(n,p)$ for every $1\leq i\leq\tau$.

Observe that $H$ is $\mathcal{F}$-free since it contains only bipartite graphs
admitting a $2$-colouring with one colour class of size at most $\ell-1$.
Moreover, every edge in $H$ is incident to $B_{i}$, for some $1\leq
i\leq\tau$. Hence, the number of edges in $H$ thus far is at most

$\sum_{i}|B_{i}|(\ell-1)\leq(\ell-1)n.$

We now turn to add edges to $H$ such that it becomes $\mathcal{F}$-saturated.
First, we consider edges whose both endpoints are in $B_{i}$, for some $1\leq
i\leq\tau$. For every $1\leq i\leq\tau$, as long as there is an edge in
$G(n,p)[B_{i}]$ which does not close a copy of $F\in\mathcal{F}$, we add it to
$H$. Note that the degree of every vertex increased by at most
$|F_{0}|-\ell-1$. Indeed, if for some $1\leq i\leq\tau$ there is a vertex
$v\in B_{i}$ with degree $|F_{0}|-\ell$ in $H[B_{i}]$, then we can form a copy
of $K_{\ell,|F_{0}|-\ell}$ with $v,N_{H[B_{i}]}(v)$, and $A_{i}$. However,
$F_{0}\subseteq K_{\ell,|F_{0}|-\ell}$, a contradiction. Hence, the number of
edges that are added to $H$ is at most

$\sum_{i}|B_{i}|(\ell-1+|F_{0}|-\ell)\leq(|F_{0}|-1)n.$

Now, for every $1\leq i\leq\tau$, as long as there is an edge between
$[n]\setminus\cup_{j\leq i}B_{j}$ and $B_{i}$ which does not close a copy of
$F\in\mathcal{F}$, we add it to $H$. For every vertex $v\notin A$, the
probability that $v\notin\cup_{j=1}^{i}B_{j}$ is $(1-p^{\ell-1})^{i}$. By
Lemma 2.1(1), the probability that there are at least $2(1-p^{\ell-1})^{i}n$
such vertices is at most $\exp\left(-n^{1/4}\right)$. Thus, by the union bound
over all less than $n$ choices of $i\leq\tau$, whp

$\displaystyle n-\sum_{j=1}^{i}|B_{j}|\leq 2(1-p^{\ell-1})^{i}n,\quad\forall
1\leq i\leq\tau.$ (5)

Hence, by (5), the number of edges we add to $H$ in this step is whp at most

$\displaystyle\sum_{i\leq\tau}\left(n-\sum_{j=1}^{i}|B_{j}|\right)(|F_{0}|-\ell-1)\leq\sum_{i}2(1-p^{\ell-1})^{i}n(|F_{0}|-\ell-1)=O(n).$

Furthermore, as long as there is an edge in $G(n,p)$ outside $A$ which closes
a copy of some $F\in\mathcal{F}$, we add it to $H$. Note that, at this step,
we only add edges induced by $[n]\setminus\left(A\cup\bigcup_{i}B_{i}\right)$.
By (5) (for $i=\tau$) and our choice of $\tau$, we have that whp
$\left|[n]\setminus\left(A\cup\bigcup_{j=1}^{\tau}B_{i}\right)\right|\leq
2(1-p^{\ell-1})^{\tau}n=o(\sqrt{n})$. Therefore, we only add $o(n)$ many edges
in this step.

Finally, we are left with considering edges induced by $A$ and between $A$ and
$[n]\setminus\left(A\cup\bigcup_{i}B_{i}\right)$. We have whp at most
$O\left(\ln^{2}n\right)$ edges induced by $A$, and by the same reasoning as
above whp at most $o(\ln n\sqrt{n})$ edges between $A$ and
$[n]\setminus\left(A\cup\bigcup_{i}B_{i}\right)$. Hence, we can add to $H$
these edges one by one, until the resulting graph will be
$\mathcal{F}$-saturated. We thus obtain the required subgraph $H$ where whp
$|E(H)|=O(n)$. ∎

The proof of Theorem 2 follows a similar construction to the one in Lemma 3.1.

###### Proof of Theorem 2.

Let $F$ be a graph and let $I_{\mathrm{max}}(F)\subseteq V(F)$ be a colour
class of maximum size among all proper colourings of $F$ with $\chi(F)$
colours. We further assume that there is a vertex $v\in V(F)\setminus
I_{\mathrm{max}}(F)$ such that $N_{F}(v)\subseteq I_{\mathrm{max}}(F)$. We
repeat the construction of Lemma 3.1 with the following difference: we let the
$A_{i}$-s be isomorphic to $F\setminus(I_{\mathrm{max}}(F)\cup\\{v\\})$. Note
that this is indeed possible as we may first take a subset $U\subset[n]$ of
$n^{\epsilon}$ vertices, for some small $\epsilon>0$, and whp we can find a
$K_{|V(F)|}$-factor (see, for example, [8]), and then we can take a copy of
$F\setminus(I_{\mathrm{max}}(F)\cup\\{v\\})$ from the first $\tau$ cliques.
Then $B_{i}$ should be selected from $[n]\setminus U$.

Note that $A_{1}$ and its common neighbourhood $B_{1}$ do not contain a copy
of $F$. Indeed, if we had a copy of $F$, denote it by $\tilde{F}$, then
$\chi(\tilde{F}[A_{1}\cap V(\tilde{F})])<\chi(F)$, and thus we could colour
$V(\tilde{F}[B_{1}\cap V(\tilde{F})])$ with one colour and
$V(\tilde{F}[A_{1}\cap V(\tilde{F})])$ with $\chi(F)-1$ colours, thus
obtaining a colour class of size $|V(\tilde{F}[B_{1}\cap
V(\tilde{F})])|\geq|I_{\mathrm{max}}(F)|+1$ — a contradiction to the
assumption that $I_{\mathrm{max}}(F)$ is a colour class of $F$ of maximum
size.

Thus, by the same arguments as in Lemma 3.1, the obtained graph $H$ is
$F$-saturated, and has whp $O(n)$ edges. ∎

Utilising Lemma 3.1, we can now prove Theorem 1.

###### Proof of Theorem 1.

Set $\chi_{0}\coloneqq\chi(\mathcal{F})=\min_{F\in\mathcal{F}}\chi(F)$. We
prove by induction on $\chi_{0}$. If $\chi_{0}=2$, we are done by Lemma 3.1.
We may assume now that $\chi_{0}\geq 3$, and that the statement holds for any
family $\mathcal{F}^{\prime}$ with $\chi(\mathcal{F}^{\prime})<\chi_{0}$.

We now construct $H\subseteq G(n,p)$ such that whp $H$ is
$\mathcal{F}$-saturated, and $e(H)=O(n\ln n)$. We begin by letting $H$ be the
empty graph. Let $A$ be a set of $C\ln n$ vertices for some large enough
constant $C\coloneqq C(\mathcal{F},p)>0$. Set

$\displaystyle\hat{\mathcal{F}}\coloneqq\left\\{F\setminus I\colon
F\in\mathcal{F}\text{ and }I\text{ is an independent set of }F\right\\}.$

We thus have that for some $F^{\prime}\in\hat{\mathcal{F}}$,
$\chi(F^{\prime})=\chi_{0}-1$. By induction, whp there exists
$H^{\prime}\subseteq[n]\setminus A$ which is $\hat{\mathcal{F}}$-saturated in
$G(n,p)[[n]\setminus A]$ with $O(n\ln n)$ edges. Furthermore, for a fixed set
$X$ of order $\max_{F\in\mathcal{F}}|V(F)|$ in $[n]\setminus A$,
$d_{G(n,p)}(X|A)$ is distributed according to $Bin\left(|A|,p^{|X|}\right)$.
Thus, by Lemma 2.1(1),

$\displaystyle\mathbb{P}\left(d_{G(n,p)}(X|A)\leq\max_{F\in\mathcal{F}}|V(F)|\right)\leq\exp\left(-\frac{C(\ln
n)p^{|X|}}{4}\right)\leq n^{-2\max_{F\in\mathcal{F}}|V(F)|},$

for $C$ large enough. Thus, by the union bound, whp for every set of order
$\max_{F\in\mathcal{F}}|V(F)|$ in $[n]\setminus A$, we can find a set of
$\max_{F\in\mathcal{F}}|V(F)|$ common neighbours in $A$. Therefore, when we
add a missing edge from $G(n,p)[V\setminus A]$, we close a copy of some
$F^{\prime}\in\hat{\mathcal{F}}$. This copy of $F^{\prime}$ together with its
common neighbours in $A$ form a copy of some $F\in\mathcal{F}$ (see Figure 3).

Let $E^{\prime}$ be the set of edges of $G(n,p)$ between $[n]\setminus A$ and
$A$. Let $H$ be $H^{\prime}$ together with $E^{\prime}$.

First, note that $H$ is $\mathcal{F}$-free. Indeed, since $H[A]$ is an empty
graph, if there is a copy of $F$ in $H$, $F[A]$ must be an independent set.
However, by definition of $H^{\prime}$, $F[[n]\setminus A]$ is free of any
$F\setminus I$ for any independent set $I$ of $F$ — a contradiction.

Furthermore, by construction, every edge of $G(n,p)\setminus E(H)$ in
$[n]\setminus A$ closes a copy of $F\in\mathcal{F}$. Since whp
$|E^{\prime}|=O(n\ln n)$ and $|E(H^{\prime})|=O(n\ln n)$, we have that whp
$|E(H)|=O(n\ln n)$. In order to ensure that $H$ is $\mathcal{F}$-saturated,
the only edges to consider are those where both endpoints are in $A$, and
there are at most $O(\ln^{2}n)$ such edges. Hence, whp there exists $H$ which
is $\mathcal{F}$-saturated with $O(n\ln n)$ edges. ∎

Figure 3: In dashed red line there is a missing edge $\\{u,v\\}$ which closes
a copy of $F^{\prime}\in\hat{\mathcal{F}}$. Together with its common
neighbourhood in $A$ (coloured light green and blue), this closes a copy of
$F\in\mathcal{F}$.

##  4 Sharp bounds

In this section we prove Theorems 3 and 4. We begin with the proof of Theorem
3.

Let us begin with an outline of the proof. We show that whp there exists a
subgraph $H\subseteq G(n,p)$ which is $K_{s_{1},\dots,s_{\ell}}$-saturated and
$e(H)\leq(1+o(1))n\log_{\frac{1}{1-p}}n$. Note that if we find a subgraph
$H\subseteq G(n,p)$, with $e(H)\leq(1+o(1))n\log_{\frac{1}{1-p}}n$, which
completes all but at most $o(n\ln n)$ edges, then we can add edges one by one
if necessary, and obtain a subgraph which is
$K_{s_{1},\dots,s_{\ell}}$-saturated and has at most
$(1+o(1))n\log_{\frac{1}{1-p}}n$ many edges.

Very roughly, we take a subset $A$ of order $\Theta(\ln n)$ and $B$ from
$[n]\setminus A$. In the case of $s_{\ell}=1$, as in [10], it suffices to set
$B$ as the empty graph and draw all the edges between $A$ and $B$, and then to
show that all but at most $o(n\ln n)$ edges are completed (as in [10], it is
not evident that all edges in $B$ can be recovered in this case, thus some
additional technical work is required). The case of $s_{\ell}\geq 2$ is
naturally more delicate, as $B$ cannot be taken to be an empty graph, but
instead requires some special properties. Using a novel construction, we find
a subgraph in $G(n,p)[B]$ which is $(s_{2}-1)$-regular and
$K_{s_{1},s_{2}-s_{1}+1}$-free in $G(n,p)[B]$. This subgraph will have another
crucial property – the vertices of any copy of $K_{1,s_{2}-1}$ have a large
common neighbourhood in $A$, which we show through coupling and covering-balls
arguments (the construction of this graph is the most involved part of the
proof and includes key new ideas, and appears in Lemma 4.1).

We then find a subgraph in $G(n,p)[A]$ which is
$\left\\{K_{\ell},K_{s_{1}}^{(\ell-1)}\right\\}$-free and such that there is a
copy of $K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ in every large enough subset of $A$
(where if $s_{1}=1$,
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}=K_{s_{3},\dots,s_{\ell}}$). In this way,
when one adds an edge in $B$, it closes a copy of $K_{1,s_{2}}$ such that this
copy has a large common neighbourhood in $A$, in which we can find a copy of
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}$. These two copies form a copy of
$K_{s_{1},\dots,s_{\ell}}$ as needed.

Note that the requirement that the subgraph in $G(n,p)[B]$ is
$K_{s_{1},s_{2}-s_{1}+1}$-free is necessary, as otherwise a copy of
$K_{s_{1},\ldots,s_{\ell}}$ could be formed when drawing the edges between $B$
and $A$.

###  4.1 Proof of Theorem 3

We may assume that $s_{\ell}\geq 2$, as the case of cliques has been dealt
with in [10].

Let $\gamma,\epsilon>0$ be sufficiently small constants. Let $G=G(n,p)$. Let
$L\coloneqq L\left(s_{1},\ldots,s_{\ell}\right)$ be a constant large enough
with respect to $s_{1},\ldots,s_{\ell}$. Let $\rho=\rho(p)$ and set

$\displaystyle
a_{1}=\frac{1}{p}\left(1+(1+\gamma)\epsilon\right)\log_{\rho}n,\quad
a_{2}=L\log_{\rho}n,\quad a_{3}=\frac{a_{2}}{\sqrt{\ln a_{2}}}.$

Let $A_{1}$, $A_{2}$, and $A_{3}$, be disjoint sets of vertices of sizes
$a_{1}$, $a_{2}$, and $a_{3}$, respectively. Set $B\coloneqq
V\setminus(A_{1}\cup A_{2}\cup A_{3})$. Set

$I\coloneqq\Big{[}\left(1+\epsilon\right)\log_{\rho}n,\
\left(1+(1+2\gamma)\epsilon\right)\log_{\rho}n\Big{]}.$

We say that a vertex $v\in B$ is $A_{1}$-_good_ if $d_{G}(v|A_{1})\in I$.
Otherwise, we say that $v$ is $A_{1}$-_bad_. Let $B_{1}\subseteq B$ be the set
of $A_{1}$-good vertices, and set $B_{2}=B\setminus B_{1}$. Note that
$|B_{2}|=O\left(\frac{n}{\ln n}\right)$. Indeed, for every vertex $v\in B$, we
have $d_{G}(v|A_{1})\sim\mathrm{Bin}(a_{1},p)$. By Lemma 2.1(1), for every
vertex $v\in B$,

$\mathbb{P}(v\ \text{is $A_{1}$-bad})\leq\exp\left(-c\ln n\right),$

for some constant $c>0$. Thus, $\mathbb{E}[|B_{2}|]=O\left(n^{1-c}\right)$. By
Markov’s inequality, whp $|B_{2}|=O\left(\frac{n}{\log_{\rho}n}\right)$.

As mentioned prior to the proof, a key element in the proof is finding in
$B_{1}$ a subgraph $H_{B_{1}}$ of $G$ which is $K_{s_{1},s_{2}-s_{1}+1}$-free
and $(s_{2}-1)$-regular in the edges in $G[B_{1}]$. Moreover, we want
$H_{B_{1}}$ to satisfy the following property. Every vertex $v\in B_{1}$ and
its neighbours in $H_{B_{1}}$ have a large common neighbourhood in $A_{1}$ in
$G$. The proof of this key lemma is deferred to the end of this proof.

######  Lemma 4.1.

Whp there exists $H_{B_{1}}\subseteq G$ such that $|B_{1}\setminus
V(H_{B_{1}})|=O\left(\frac{n}{\log n}\right)$, which is
$K_{s_{1},s_{2}-s_{1}+1}$-free and $(s_{2}-1)$-regular in $G[V(H_{B_{1}})]$,
and for every $u,v\in V(H_{B_{1}})$ such that $\\{u,v\\}\in E(H_{B_{1}})$,
$d_{G}(u,v|A_{1})\geq(1+(1-6\gamma)\epsilon)\log_{\rho}n$.

Since $K_{\ell}$ and $K_{s_{1}}^{(\ell-1)}$ are two-vertex-connected graphs
(as $\ell\geq 3$ by assumption), and $K_{\ell}$ and $K_{s_{1}}^{(\ell-1)}$ are
non-$K_{s_{1}-1,s_{3},\ldots,s_{\ell}}$-degenarate, by Lemma 1.5, we can take
a spanning subgraph $H_{A_{1}}\subseteq G[A_{1}]$ which is
$(1/\ln^{3}|A_{1}|)$-dense with respect to $K_{s_{1}-1,s_{3},\dots,s_{\ell}}$
and $\\{K_{\ell},K_{s_{1}}^{(\ell-1)}\\}$-free. Moreover, let us move the set
of $O\left(\frac{n}{\log n}\right)$ vertices that is excluded by Lemma 4.1
from $B_{1}$ to $B_{2}$, and let $H_{B_{1}}\subseteq G[B_{1}]$ be
$K_{s_{1},s_{2}-s_{1}+1}$-free and $(s_{2}-1)$-regular in $G[B_{1}]$.

Let $H_{1}$ be the graph on $A_{1}\cup B$ with the edges $H_{A_{1}}$,
$H_{B_{1}}$, and all the edges between $A_{1}$ and $B$ in $G$. We now continue
with a series of self-contained claims.

######  Claim 4.2.

Whp, $H_{1}$ completes all but $o(n\ln n)$ of the vertex pairs in $B$ not
induced by $B_{2}$.

###### Proof.

Fix $S\subset A_{1}$, $u\in B$. We say that $u$ avoids $S$ if
$|N_{G}(u,S)|<\frac{|S|}{\ln^{2}|S|}$. The number of neighbours of $u$ in $S$
in $G$ is distributed according to $\text{Bin}(|S|,p)$. Thus, by Lemma 2.1(3),
the probability that $u$ avoids $S$ is at most $(1-p)^{|S|-|S|/\ln|S|}$. In
particular, if $|S|=\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n$, then the
probability that $u$ avoids $S$ is at most

$\displaystyle(1-p)^{|S|-|S|/\ln|S|}\leq(1-p)^{\left(1+\frac{1}{3}\epsilon\right)\log_{\rho}n}=n^{-1-\frac{1}{3}\epsilon}.$

Fix a vertex $v\in B$ and expose the edges in $G$ from $v$ to $A_{1}$. Assume
that $v$ is $A_{1}$-good. Fix $S\subset N_{G}(v,A_{1})$ of size
$\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n$. Let $X_{S}$ be the random
variable counting the number of vertices $u\in B\setminus\\{v\\}$ that avoid
$S$. Then $X_{S}$ is stochastically dominated by
$\text{Bin}\left(|B|-1,n^{-1-\frac{1}{3}\epsilon}\right)$. Since $|B|-1<n$, by
Lemma 2.1(2),

$\displaystyle\mathbb{P}\left(X_{S}\geq\sqrt{\ln
n}\right)\leq\left(\frac{e}{\sqrt{\ln n}\cdot
n^{\frac{1}{3}\epsilon}}\right)^{\sqrt{\ln
n}}\leq\exp\left(-\frac{1}{3}\epsilon\ln^{\frac{3}{2}}n\right).$

Note that since $v$ is $A_{1}$-good, then
$|N_{G}(v,A_{1})|\leq(1+(1+2\gamma)\epsilon)\log_{\rho}n$. Hence, by the union
bound, the probability that there exists $S\subset N_{G}(v,A_{1})$ of size
$\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n$ such that $X_{S}>\sqrt{\ln
n}$ is at most

$\displaystyle\binom{(1+(1+2\gamma)\epsilon)\log_{\rho}n}{\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n}\exp\left(-\frac{1}{3}\epsilon\ln^{\frac{3}{2}}n\right)$
$\displaystyle\leq\exp\left(\frac{3}{2}\epsilon\ln\left(\frac{e(1+2\epsilon)}{\frac{3}{2}\epsilon}\right)\log_{\rho}n\right)\exp\left(-\frac{1}{3}\epsilon\ln^{\frac{3}{2}}n\right)=o\left(\frac{1}{n}\right).$

Thus, by the union bound whp there are no vertices $v\in B_{1}$ such that
$X_{S}>\sqrt{\ln n}$ for some $S\subset N_{G}(v,A_{1})$ of size
$\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n$.

Now, fix an edge $\\{u,v\\}\subset B$ in $G$ but not in $H_{1}$, such that
$v\in B_{1}$. Since $H_{B_{1}}$ is $(s_{2}-1)$-regular, this edge closes a
copy of $K_{1,s_{2}}$ with the neighbours of $v$ in $H_{1}$, denote them by
$v_{1},\dots,v_{s_{2}-1}$. Let $S\coloneqq S(v,v_{1},\ldots,v_{s_{2}-1})$ be
the set of common neighbours of $v,v_{1},\ldots,v_{s_{2}-1}$ in $A_{1}$ in the
graph $G$. We note that the size of $S$ must be at least
$\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n$. Indeed, we have

$\displaystyle|S|$
$\displaystyle\geq|N_{G}(v,A)|-\sum_{i=1}^{s_{2}-1}|N_{G}(v,A)\setminus
N_{G}(v_{i},A)|$
$\displaystyle\geq|N_{G}(v,A)|-(s_{2}-1)(8\gamma\epsilon)\log_{\rho}n$
$\displaystyle\geq(1+\epsilon-8s_{2}\gamma\epsilon)\log_{\rho}n$
$\displaystyle\geq\left(1+\frac{1}{2}\epsilon\right)\log_{\rho}n,$

where the last inequality is true if $\gamma\leq\frac{1}{16s_{2}}$. Note that
if $u$ has more than $\frac{|S|}{\ln^{2}|S|}$ neighbours in $S$, then since
$H_{A_{1}}$ is $(1/\ln^{3}|A_{1}|)$-dense with respect to
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}$, we can find a copy of
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ in $S$ such that the edge $\\{v,u\\}$,
joined with the neighbours of $v$ in $B_{1}$, completes a copy of
$K_{s_{1},\dots,s_{\ell}}$. Thus, by this and the above, whp there are at most
$n\sqrt{\ln n}=o(n\ln n)$ non-completed edges from $B$ not induced by $B_{2}$.
∎

We now turn our attention to the edges induced by $B_{2}$. By Lemma 1.5, we
can take a spanning subgraph $H_{A_{2}}\subseteq G[A_{2}]$ which is
$(1/\ln|A_{2}|)$-dense with respect to $K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ and
$\\{K_{\ell},K_{s_{1}}^{(\ell-1)}\\}$-free. Furthermore, let $H_{B_{2}}\subset
G[B_{2}]$ be $K_{s_{2}}$-factor (that is, a spanning subgraph composed of
vertex disjoint $K_{s_{2}}$ — see [8]) of $G[B_{2}]$, which is in particular
$K_{1,s_{2}}$-saturated and $K_{s_{1},s_{2}-s_{1}+1}$-free. Let $H_{2}$ be the
graph on $A_{2}\cup B_{2}$ with the edges of $H_{A_{2}}$, $H_{B_{2}}$, and all
the edges between $A_{2}$ and $B_{2}$ in $G$.

Note that we can choose $L$ large enough such that every $s_{2}+1$ vertices
from $B_{2}$ have at least $\frac{a_{2}}{10}$ neighbours in $A_{2}$ in $G$.
Thus, when we add an edge induced by $B_{2}$, we close a copy of $K_{1,s_{2}}$
which has a large neighbourhood in $A_{2}$, in which we can find a copy of
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ and form a copy of
$K_{s_{1},s_{2},\ldots,s_{\ell}}$.

Observe that whp we have $\Theta(n\log n)$ edges between $A_{2}$ and $B_{1}$
in $G$. We now utilise the set $A_{3}$ in order to complete them. Indeed, by
Lemma 2.3 whp
$k\coloneqq\chi(G[A_{2}])=O\left(\frac{a_{2}}{\ln{a_{2}}}\right)$. We can then
split $A_{2}$ to $k$ colour classes $A_{2}^{1},\dots,A_{2}^{k}$. Thus, there
are no edges of $G$ (and thus of $H_{A_{2}}$) inside $A_{2}^{i}$, for every
$i\in[k]$. We further partition the vertices of $A_{3}$ to $2k$ (almost) equal
parts $A_{3}^{1},\dots,A_{3}^{2k}$ of size
$a_{4}\coloneqq\frac{a_{3}}{2k}=\Theta(\sqrt{\ln a_{2}})$. For every
$i\in[2k]$, by Lemma 1.5, the probability that there exists a subgraph
$H_{A_{3}^{i}}\subset G[A_{3}^{i}]$ which is $(1/\ln\ln\ln n)$-dense with
respect to $K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ and
$\\{K_{\ell},K_{s_{1}}^{(\ell-1)}\\}$-free is $1-o(1)$. Hence, by standard
binomial tail bounds, whp there exist distinct $i_{1},\dots,i_{k}$ such that
there exists such a subgraph in each $A_{3}^{i_{j}}$, for every $j\in[k]$.
Therefore, for every $j\in[k]$, there is $H_{A_{3}^{i_{j}}}\subseteq
G[A_{3}^{i_{j}}]$ which is $(1/\ln\ln\ln n)$-dense with respect to
$K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ and
$\\{K_{\ell},K_{s_{1}}^{(\ell-1)}\\}$-free. We let $A_{3}^{j}=A_{3}^{i_{j}}$
and $H_{A_{3}^{j}}=H_{A_{3}^{i_{j}}}$ for simplifying notations and without
loss of generality.

Let $H_{3}$ be the graph with edges of $H_{A_{2}}$,
$H_{A_{3}^{1}},\dots,H_{A_{3}^{k}}$, together with the edges between $A_{3}$
and $B_{1}$ in $G$, and together with the edges between $A_{3}^{i}$ to
$A_{2}^{i}$, for every $i\in[k]$, in $G(n,p)$. Set $H\coloneqq H_{1}\cup
H_{2}\cup H_{3}$.

######  Claim 4.3.

Whp, $H$ completes all but at most $o(n\log n)$ edges from $B_{1}$ to $A_{2}$.

###### Proof.

Fix two vertices $v\in B_{1}$ and $u\in A_{2}^{i}$, for some $i\in[k]$.

Recall that $v$ has $s_{2}-1$ neighbours in $B_{1}$. Thus, together with $u$,
we close a copy of $K_{1,s_{2}}$. If this copy has more than
$\frac{a_{4}}{\log^{3}a_{4}}$ common neighbours in $A_{3}^{i}$, then we can
find among these neighbours a copy of $K_{s_{1}-1,s_{3},\dots,s_{\ell}}$ which
closes a copy of $K_{s_{1},\dots,s_{\ell}}$. The probability that this copy of
$K_{1,s_{2}}$ has less than $\frac{a_{4}}{\log^{3}a_{4}}$ common neighbours is
at most

$\displaystyle(1-p^{s_{2}+1})^{a_{4}-a_{4}/\ln
a_{4}}\leq(1-p^{s_{2}+1})^{\Omega(\sqrt{\ln a_{2}})}.$

Hence, the expected number of uncompleted pairs $v\in B_{1}$ and $u\in A_{2}$
is at most

$\displaystyle(1-p^{s_{1}+1})^{\Omega(\sqrt{\ln
a_{2}})}\cdot|B_{1}|\cdot|A_{2}|=(1-p^{s_{1}+1})^{\Omega(\sqrt{\ln
a_{2}})}\cdot O(n\log_{\rho}n).$

Therefore, by Markov’s inequality, whp the number of uncompleted such pairs is
$o(n\log_{\rho}n)$. ∎

######  Claim 4.4.

Whp, $e(H)=(1+\Theta(\epsilon))n\log_{\rho}n$.

###### Proof.

Indeed, whp

$\displaystyle e(H)$ $\displaystyle\leq e(H_{1})+e(H_{2})+e(H_{3})$
$\displaystyle\leq(1+o(1))a_{1}np+e(H_{B_{1}})+e(H_{A_{1}})+a_{2}|B_{2}|p+e(H_{A_{2}})+e(H_{A_{3}})+a_{3}np$
$\displaystyle\leq(1+o(1))(1+(s_{1}+1)\epsilon)n\log_{\rho}n=(1+\Theta(\epsilon))n\log_{\rho}n.$

∎

######  Claim 4.5.

$H$ is $K_{s_{1},\dots,s_{\ell}}$-free.

###### Proof.

Suppose towards contradiction that there exists a copy of
$K_{s_{1},\dots,s_{\ell}}$ in $H$, denote this copy by $F$.

Assume first that $V(F)\cap A_{3}\neq\varnothing$. Set $\tilde{F}\coloneqq
V(F)\cap A_{3}$. Since $H[A_{3}]$ is $K_{\ell}$-free, then at least one full
part of $K_{s_{1},\dots,s_{\ell}}$ must come from $B_{1}\cup A_{2}$, as all
its vertices must be adjacent to every vertex of $\tilde{F}$. If only one full
part comes from $B_{1}\cup A_{2}$, then $H[A_{3}]$ must contain a copy of
$K_{s_{1}}^{(\ell-1)}$ — a contradiction, as by construction $H[A_{3}]$ is
composed of vertex disjoint subsets, each of which is $K_{s_{1}}^{(\ell-1)}$
free. Thus, $B_{1}\cup A_{2}$ contains at least one full part as well as an
additional vertex from another part of $K_{s_{1},\dots,s_{\ell}}$. As this
additional vertex is adjacent to the full part lying in $B_{1}\cup A_{2}$ and
there are no edges between $B_{1}$ and $A_{2}$, all these vertices must belong
exclusively to $B_{1}$ or exclusively to $A_{2}$. Now, if they belong to
$B_{1}$, since $H_{B_{1}}$ is $K_{s_{1},s_{2}-s_{1}+1}$-free, $H[A_{3}]$ must
contain $K_{s_{1}}^{(\ell-1)}$ in order to complete
$K_{s_{1},\dots,s_{\ell}}$, as there are $\ell-1$ parts missing at least
$s_{1}$ vertices, once again leading to contradiction. Finally, if they belong
to $A_{2}$, then they should be splitted between different independent sets
$A_{2}^{i}$ and $A_{2}^{j}$, but there are no vertices in $A_{3}$ which are
adjacent to both $A_{2}^{i}$ and $A_{2}^{j}$ in $H$ — a contradiction.

Let us now assume that $V(F)\cap A_{3}=\varnothing$ and $V(F)\cap
A_{2}\neq\varnothing$. Set $\tilde{F}\coloneqq V(F)\cap A_{2}$. Since
$H[A_{2}]$ is $K_{\ell}$-free, then a full part of $K_{s_{1},\dots,s_{\ell}}$
must come from $B_{2}$ and, as before, at least one additional vertex. This
vertex has neighbours in the full part, and thus, since $H[B_{2}]$ is a
$K_{s_{2}}$-factor, the full part must be of size $s_{1}$. Moreover, there are
at most $s_{2}-s_{1}$ vertices of $F$ in $B_{2}$ that do not belong to this
part of size $s_{1}$. Therefore, each part of $\tilde{F}$ must contain at
least $s_{1}$ vertices, creating a copy of $K_{s_{1}}^{(\ell-1)}$ — a
contradiction to the fact that $H[A_{2}]$ is $K_{s_{1}}^{(\ell-1)}$-free.
Similarly, if $V(F)\cap A_{3}=V(F)\cap A_{2}=\varnothing$ and $V(F)\cap
A_{1}\neq\varnothing$, since $H[A_{1}]$ is $K_{\ell}$-free, we once again
obtain a contradiction. Thus, we may assume that $V(F)\subseteq B$. However,
since there are no edges between $B_{1}$ and $B_{2}$ in $H$, we must either
$V(F)\subseteq B_{1}$ or $V(F)\subseteq B_{2}$, contradicting the fact that
$H[B_{1}]$ and $H[B_{2}]$ are $K_{s_{1},\ldots,s_{\ell}}$-free. ∎

In conclusion, whp by Claim 4.5 $H$ is $K_{s_{1},\ldots,s_{\ell}}$-free; by
Claims 4.2 and 4.3 whp $H$ completes all but at most $o(n\ln n)$ of the edges,
and adding each of these edges that does not close a copy of $F$ until none
remains results in a $K_{s_{1},\ldots,s_{\ell}}$-saturated graph; finally, by
Claim 4.4 and by the additional edges mentioned before, whp
$e(H)=\left(1+\Theta(\epsilon)\right)n\log_{\rho}n+o(n\ln
n)=\left(1+\Theta(\epsilon)\right)n\log_{\rho}n$. As we may choose $\epsilon$
arbitrarily small, this completes the proof of Theorem 3.

###  4.2 Proof of Lemma 4.1

We build such a subgraph iteratively. In each iteration, we find a large
matching in $G[B_{1}]$, which we add to the subgraph, such that the matching
satisfies the following:

  1. 1.

The union of the previous matching together with this matching does not induce
a copy of $K_{s_{1},s_{2}-s_{1}+1}$; and,

  2. 2.

the endpoints of every edge in the matching have a large common neighbourhood
in $A_{1}$ in $G$.

Denote by $\Gamma$ the auxiliary graph with vertex set $B_{1}$ and the set of
edges defined as follows. For every two vertices $v\neq u$ in $B_{1}$,

$\displaystyle\\{u,v\\}\in E(\Gamma)\Longleftrightarrow
d_{G}(u,v|A_{1})\geq(1+(1-6\gamma)\epsilon)\log_{\rho}n.$

Set $p^{\prime}=1-(1-p)^{1/(s_{2}-1)}$. For every $i\in[s_{2}-1]$, denote by
$\Gamma_{i}$ the subgraph of $\Gamma$ obtained by retaining every edge
independently with probability $p^{\prime}$. We have
$\Gamma_{p}\coloneqq\Gamma\cap G(n,p)$. Note that $\Gamma_{p}$ has the same
distribution as $\bigcup_{i=1}^{s_{2}-1}\Gamma_{i}$.

We will in fact prove the following equivalent Lemma:

######  Lemma 4.6.

Whp there exists $H_{B_{1}}\subseteq\Gamma_{p}$ which is
$K_{s_{1},s_{2}-s_{1}+1}$-free and $(s_{2}-1)$-regular in $G[B_{1}]$.

We consider two cases separately. In the first case, we assume that
$p=\frac{1}{2}$. While some details will be different when $p>\frac{1}{2}$, we
believe the key ideas, in particular the ball-covering technique (see Claim
4.9) are clearer in this case. Afterwards, we mention how to complete the
proof for the range of $p>\frac{1}{2}$, where, in particular, Claim 4.7 no
longer necessarily holds.

####  4.2.1 Proof of Lemma 4.1, $p=0.5$

Note that if $s_{1}=s_{2}$, then $K_{s_{1},s_{2}-s_{1}+1}=K_{1,s_{1}}$, and
thus it suffices to find $H_{B_{1}}\subseteq\Gamma_{p}$ which is
$K_{1,s_{2}}$-saturated in the edges in $G[B_{1}]$ (since by definition it is
$K_{1,s_{1}}$-free). Also, if $s_{1}=1$, then
$K_{s_{1},s_{2}-s_{1}+1}=K_{1,s_{2}}$ and again, it suffices to find
$H_{B_{1}}\subseteq\Gamma_{p}$ which is $K_{1,s_{2}}$-saturated in the edges
in $G(n,p)[B_{1}]$. Hence, in general, it suffices to find
$H_{B_{1}}\subseteq\Gamma_{p}$ which is $C_{4}$-free and
$K_{1,s_{2}}$-saturated in the edges in $G[B_{1}]$.

We will find a sufficiently large matching $M_{i}$ in $\Gamma_{i}$, for every
$i\in[s_{2}-1]$, such that there are no copies of $C_{4}$ in
$M:=\bigcup_{i=1}^{s_{2}-1}M_{i}$. Clearly, the subgraph of $M$ induced on the
maximum set of vertices which is matched by every $M_{i}$ (that is, every
$M_{i}$ restricted to this set is a perfect matching) would be the desired
subgraph of $\Gamma_{p}$.

Fix $i\in\left\\{2,\ldots s_{2}-1\right\\}$. Assume that there exist edge-
disjoint matchings
$M_{1}\subseteq\Gamma_{1},\dots,M_{i-1}\subseteq\Gamma_{i-1}$ such that
$\bigcup_{j=1}^{i-1}M_{j}$ is $C_{4}$-free. We will find a matching
$M_{i}\subseteq\Gamma_{i}$ such that $\bigcup_{j=1}^{i}M_{j}$ is $C_{4}$-free.

Recall that $I=\Big{[}\left(1+\epsilon\right)\log_{\rho}n,\
\left(1+(1+2\gamma)\epsilon\right)\log_{\rho}n\Big{]}$. Set

$W=\\{x\subseteq A_{1}\colon|x|\in I\\}.$

Denote by $G_{W}$ the graph with vertex set $W$ and the set of edges defined
as follows. For every $x\neq y\in W$,

$\displaystyle\\{x,y\\}\in E(G_{W})\Longleftrightarrow|x\cap
y|\geq(1+(1-6\gamma)\epsilon)\log_{\rho}n.$ (6)

Define $\phi:V(\Gamma)\to V(G_{W})$ such that $\phi(v)=N_{G}(v|A_{1})$ for
every $v\in V(\Gamma)$. Note that this definition is valid since if $v\in
V(\Gamma)$, then $v$ is $A_{1}$-good and thus $N_{G}(v|A_{1})\in W$.

######  Claim 4.7.

Whp $\phi$ is injective.

###### Proof.

Fix $u\in B$. If $u\in V(\Gamma)$, then for every vertex $v\in V(\Gamma)$, we
have $\phi(u)=\phi(v)$ if and only if $N_{G}(v|A_{1})=N_{G}(u|A_{1})$. For
every vertex $v\in B$,

$\displaystyle\mathbb{P}\left(N_{G}(v|A_{1})=N_{G}(u|A_{1})\right)$
$\displaystyle=p^{d_{G}(u|A_{1})}(1-p)^{a_{1}-d_{G}(u|A_{1})}=\left(\frac{1}{2}\right)^{a_{1}}$
$\displaystyle=\left(\frac{1}{2}\right)^{\frac{1}{p}\left(1+(1+\gamma)\epsilon\right)\log_{2}n}=o(1/n^{2}).$

Hence, by the union bound, whp there are no two vertices $u\neq v\in
V(\Gamma)$ such that $\phi(u)=\phi(v)$. ∎

Set $\widetilde{G}_{W}=G_{W}\left[\phi\left(V(\Gamma)\right)\right]$. Denote
by $\widetilde{G}_{W}(p^{\prime})$ the random subgraph of $\widetilde{G}_{W}$
obtained by retaining every edge of $\widetilde{G}_{W}$ independently with
probability $p^{\prime}$. By Claim 4.7, whp $\phi$ is injective. Therefore,
$\widetilde{G}_{W}\cong\Gamma$. Recall that we want to find a matching in
$\Gamma_{i}$. We will show that whp
$\alpha(\Gamma_{i})\leq\frac{n}{\log_{\rho}n}$ and later we will construct the
desire matching. Since $\widetilde{G}_{W}\cong\Gamma$, it suffices to prove
the following lemma.

######  Lemma 4.8.

Whp

$\alpha(\widetilde{G}_{W}(p^{\prime}))\leq\frac{n}{\log_{\rho}n}.$

###### Proof.

For every $x\in W$, denote by $B(x)$ the following Hamming ball around $x$:

$B(x)\coloneqq\\{y\in W\colon|x\cap
y|\geq(1+(1-\gamma)\epsilon)\log_{\rho}n\\}.$

Set $m\coloneqq\frac{n}{\log(n)}$ and
$m^{\prime}\coloneqq\frac{n}{\log^{3}n}$. Let
$B^{\prime}=\\{y_{1},\dots,y_{m^{\prime}}\\}\subseteq V(\Gamma)$ be an
arbitrary subset of size $m^{\prime}$.

######  Claim 4.9.

Whp, for every $x\in W$, there exists a vertex $v\in B^{\prime}$ such that

$d_{G}(v|x)\geq(1+(1-\gamma)\epsilon)\log_{\rho}n.$

###### Proof.

For every $x\in W$, set

$B^{\prime}(x)=\\{v\in B^{\prime}\colon
d_{G}(v|x)\geq(1+(1-\gamma)\epsilon)\log_{\rho}n\\}.$

Fix $x\in W$. Since $|B^{\prime}|\geq\frac{n}{\log^{3}n}$, by Lemma 2.2 the
probability that $B^{\prime}(x)=\varnothing$ is at most
$\exp\left(-n^{0.5\epsilon}\right)$. Note that $|W|=n^{O(1)}$. Thus, by the
union bound over $W$, the probability that there exists a vertex $x\in W$ such
that $B^{\prime}(x)=\varnothing$ is at most

$n^{O(1)}\cdot\exp\left(-n^{0.5\epsilon}\right)=o(1).\qed$

######  Claim 4.10.

For every $J=\\{x_{1},\dots,x_{m}\\}\subset V(\widetilde{G}_{W})$,

$\mathbb{P}\left(|E(\widetilde{G}_{W}(p^{\prime})[J])|=0\right)\leq(1-p^{\prime})^{0.25n\log_{\rho}n}.$

###### Proof.

For every $i\in[m^{\prime}]$, set

$Y_{i}\coloneqq\\{x\in J\colon N_{G}(y_{i}|A_{1})\in B(x)\\}.$

By Claim 4.9, whp $\bigcup_{i=1}^{m^{\prime}}Y_{i}=J$. Indeed, by Claim 4.9,
whp for every $x\in J$, there exists a vertex $y\in B^{\prime}$ such that
$N_{G}(y|A_{1})\in B(x)$ and thus there exists $i\in[m^{\prime}]$ such that
$x\in Y_{i}$.

We now show that $\widetilde{G}_{W}[Y_{i}]$ is a clique for every
$i\in[m^{\prime}]$. Fix $i\in[m^{\prime}]$ and two different vertices
$x,x^{\prime}\in Y_{i}$. By the definition of $Y_{i}$,

$|x\cap
N_{G}(y_{i}|A_{1})|=|N_{G}(y_{i}|x)|\geq(1+(1-\gamma)\epsilon)\log_{\rho}n$

and

$|x^{\prime}\cap
N_{G}(y_{i}|A_{1})|=|N_{G}(y_{i}|x^{\prime})|\geq(1+(1-\gamma)\epsilon)\log_{\rho}n.$

Recall that $y_{i}\in B_{1}$, so $y_{i}$ is $A_{1}$-good and thus
$d_{G}(y_{i}|A_{1})\leq(1+(1+2\gamma)\epsilon)\log_{\rho}n$. Then,

$|N_{G}(y_{i}|A_{1})\setminus
x|\leq(3\gamma\epsilon)\log_{\rho}n\quad\text{and}\quad|N_{G}(y_{i}|A_{1})\setminus
x^{\prime}|\leq(3\gamma\epsilon)\log_{\rho}n.$

Hence,

$\displaystyle|x\cap x^{\prime}|$ $\displaystyle\geq|x\cap x^{\prime}\cap
N_{G}(y_{i}|A_{1})|$
$\displaystyle\geq|N_{G}(y_{i}|A_{1})|-|N_{G}(y_{i}|A_{1})\setminus
x|-|N_{G}(y_{i}|A_{1})\setminus x^{\prime}|$
$\displaystyle\geq(1+\epsilon-6\gamma\epsilon)\log_{\rho}n,$

where the last inequality is true since
$d_{G}(y_{i}|A_{1})\geq(1+\epsilon)\log_{\rho}n$ because $y_{i}$ is
$A_{1}$-good. Therefore, by (6), $\\{x,x^{\prime}\\}\in E(\widetilde{G}_{W})$
implying that $\widetilde{G}_{W}[Y_{i}]$ is indeed a clique.

For every $i\in[m^{\prime}]$, set

$\displaystyle Y_{i}^{\prime}$ $\displaystyle\coloneqq
Y_{i}\setminus\left(\bigcup_{j=1}^{i-1}Y_{j}\right).$

We have $|J|=\sum_{i=1}^{m^{\prime}}|Y_{i}^{\prime}|$. Since, for every
$i\in[m^{\prime}]$, $\widetilde{G}_{W}[Y_{i}]$ is a clique,
$\widetilde{G}_{W}[Y_{i}^{\prime}]\subseteq\widetilde{G}_{W}[Y_{i}]$ is also a
clique. Thus,

$\displaystyle|E(\widetilde{G}_{W}[J])|$
$\displaystyle\geq\sum_{i=1}^{m^{\prime}}\binom{|Y_{i}^{\prime}|}{2}\geq
m^{\prime}\cdot\binom{\frac{m}{m^{\prime}}}{2}\geq
m^{\prime}\cdot\left(\frac{m}{2m^{\prime}}\right)^{2}$
$\displaystyle=\frac{m^{2}}{4m^{\prime}}=\frac{1}{4}n\log_{\rho}n,$

where the second inequality is true by Jensen’s inequality and the fact that
$m=|J|=\sum_{i=1}^{m^{\prime}}|Y_{i}^{\prime}|$. Therefore,

$\mathbb{P}(|E(\widetilde{G}_{W}(p^{\prime})[J])|=0)=(1-p^{\prime})^{|E(\widetilde{G}_{W}[J])|}\leq(1-p^{\prime})^{0.25n\log_{\rho}n}.\qed$

We have

$\displaystyle\binom{|W|}{m}\leq|W|^{m}=\exp\left(\Theta(m\log
n)\right)=\exp\left(\Theta(n)\right).$

Therefore, by the union bound, the probability that there is an independent
set in $\widetilde{G}_{W}(p^{\prime})$ of size $m$ is at most

$\binom{|W|}{m}(1-p^{\prime})^{0.25n\log_{\rho}n}=o(1).\qed$

Recall that our goal is to find a matching
$M_{i}\subseteq\Gamma_{i}\setminus(\cup_{j=1}^{i-1}M_{j})$ such that
$\cup_{j=1}^{i}M_{j}$ is $C_{4}$-free. By Claim 4.8 and the fact that
$\widetilde{G}_{W}\cong\Gamma$, whp

$\alpha(\Gamma_{i})\leq\frac{n}{\log_{\rho}n}.$

Let $M_{i}\subseteq\Gamma_{i}\setminus(\cup_{j=1}^{i-1}M_{j})$ be a matching
of the maximum size such that $\bigcup_{j=1}^{i}M_{j}$ is $C_{4}$-free.

Let $U\subseteq V(\Gamma_{i})$ be the set of unmatched vertices. The next
claim bounds the maximum degree $\Delta(\Gamma_{i}[U])$.

######  Claim 4.11.

$\Delta(\Gamma_{i}[U])\leq{s_{2}}^{3}$.

###### Proof.

Suppose towards contradiction that $\Delta(\Gamma_{i}[U])>{s_{2}}^{3}$ and
take a vertex $v\in U$ such that $d_{\Gamma_{i}[U]}(v)>{s_{2}}^{3}$.

Note that there are at most ${s_{2}}^{3}$ many paths with three edges in
$\bigcup_{j=1}^{i}M_{j}$ which start with the vertex $v$. Thus, there exists a
vertex $u\in N_{\Gamma_{i}[U]}(v)$ such that $u$ is not adjacent to another
endpoint of the above paths and thus $\\{u,v\\}$ does not close a copy of
$C_{4}$ in $\bigcup_{j=1}^{i}M_{j}$. Hence, we can add $\\{u,v\\}$ to the
matching $M_{i}$, a contradiction to the maximality of $M_{i}$. ∎

We finish with the following claim.

######  Claim 4.12.

Whp $|U|\leq(s_{2}^{3}+1)\frac{n}{\log_{\rho}n}$.

###### Proof.

Suppose towards contradiction that $|U|>(s_{2}^{3}+1)\frac{n}{\log_{\rho}n}$.
By Claim 4.11, $\Delta(\Gamma_{i}[U])\leq{s_{2}}^{3}$. Hence,

$\alpha\left(\Gamma_{i}[U]\right)\geq\frac{|U|}{\Delta(\Gamma_{i}[U])+1}>\frac{n}{\log_{\rho}n},$

a contradiction to Lemma 4.8. ∎

The desired subgraph in Lemma 4.1 is the subgraph $H_{B_{1}}$ of
$\cup_{i=1}^{s_{2}-1}M_{i}$ induced on the maximum set of vertices, such that
every $M_{i}$ restricted to this set is a perfect matching, finishing the
proof.

####  4.2.2 Proof of Lemma 4.1, $p>0.5$

Let us now explain how to complete the proof for $p>0.5$. Indeed, note that
Claim 4.7 is not necessarily true, and hence we require a more delicate
treatment to overcome the lack of isomorphism. Recall that our main goal is to
show that $\alpha(\Gamma_{i})\leq\frac{n}{\log_{\rho}n}$. We prove this with
the following series of relatively short claims and lemmas, where the key idea
is that one can consider equivalence classes under $\phi$, and show that whp
either all such classes are of bounded order, or of polynomial order (Claim
4.13).

For every $v,u\in V(\Gamma)$, we say that $v\sim u$ if and only if
$\phi(v)=\phi(u)$. Let $C_{1},\dots,C_{\ell}$ be the equivalence classes under
this relation. With a slight abuse of notation, given
$C_{j}=\\{v_{1},\ldots,v_{k}\\}$ we write $\phi(C_{j})\coloneqq\phi(v_{1})$.

######  Claim 4.13.

Whp one of the following holds.

  1. 1.

There exists a constant $C$ such that

$|C_{j}|\leq C,\quad\forall j\in[\ell].$

  2. 2.

There exists $\beta>0$ such that

$|C_{j}|\geq n^{\beta},\quad\forall j\in[\ell].$

###### Proof.

For every $v\in[n]\setminus A_{1}$, set $X_{v}=0$ if $v$ is $A_{1}$-bad and
$X_{v}$ to be the number of vertices $u\sim v$ otherwise. Fix
$v\in[n]\setminus A_{1}$ and consider the random variable
$\epsilon^{\prime}=\epsilon^{\prime}(v)$ such that $|N_{G(n,p)}(v)\cap
A_{1}|=(1+\epsilon^{\prime})\log_{\rho}n$. Note that if $v$ is $A_{1}$-good,
then $\epsilon^{\prime}\in[\epsilon,(1+2\gamma)\epsilon]$. We have

$\displaystyle\mathbb{E}[X_{v}|N_{G(n,p)}(v)\cap$ $\displaystyle A_{1}\
\text{and $v$ is $A_{1}$-good}]=(1+o(1))np^{|N_{G(n,p)}(v)\cap
A_{1}|}(1-p)^{|A_{1}|-|N_{G(n,p)}(v)\cap A_{1}|}$
$\displaystyle=(1+o(1))np^{(1+\epsilon^{\prime})\log_{\rho}n}(1-p)^{\frac{1+(1+\gamma)\epsilon}{p}\log_{\rho}n-(1+\epsilon^{\prime})\log_{\rho}n}$
$\displaystyle=(1+o(1))n(1-p)^{(\log_{1-p}p)(1+\epsilon^{\prime})\log_{\rho}n}(1-p)^{\frac{1+(1+\gamma)\epsilon}{p}\log_{\rho}n-(1+\epsilon^{\prime})\log_{\rho}n}$
$\displaystyle=(1+o(1))n^{1-(1+\epsilon^{\prime})(\log_{1-p}p)-\frac{1+(1+\gamma)\epsilon}{p}+1+\epsilon^{\prime}}$
$\displaystyle=(1+o(1))n^{2-\log_{1-p}p-\frac{1}{p}+\epsilon^{\prime}-\epsilon^{\prime}\log_{1-p}p-\frac{(1+\gamma)\epsilon}{p}}.$

Set $f(x)\coloneqq 2-\log_{1-x}(x)-\frac{1}{x}$. Let $x^{\prime}$ be in
$(0,1)$ such that $f(x^{\prime})=0$, noting that $f(x)$ is increasing in
$x\in(0,1)$ and $f(x)=0$ around $x\approx 0.64$. We then have that for
$\epsilon$ small enough and for some constant $c>0$,
$\epsilon^{\prime}-\epsilon^{\prime}\log_{1-x^{\prime}}x^{\prime}-\frac{(1+\gamma)\epsilon}{x^{\prime}}<-c\epsilon$.
Thus, if $p\leq x^{\prime}$, we have that $\mathbb{E}[X_{v}\,|\,\text{$v$ is
$A_{1}$-good}]\leq n^{-c\epsilon}$ for every $v\in[n]\setminus A_{1}$. By
Lemma 2.1(2),

$\mathbb{P}(X_{v}>C\,|\,\text{$v$ is
$A_{1}$-good})\leq\left(\frac{e}{\frac{C}{\mathbb{E}[X_{v}]}}\right)^{C}\leq
n^{-C\cdot c\epsilon}=o(1/n).$

Hence, by the union bound over all $v\in[n]\setminus A_{1}$, whp $X_{v}\leq C$
for every $v\in V(\Gamma)$, and thus the first item of the claim holds.

If $p>x^{\prime}$, then we may choose $\epsilon$ small enough such that
$\mathbb{E}[X_{v}\mid\text{$v$ is $A_{1}$-good}]\geq n^{\beta}$, for some
$\beta>0$, for every $v\in[n]\setminus A_{1}$. By Lemma 2.1(1),

$\mathbb{P}(X_{v}\leq 0.5\mathbb{E}\left[X_{v}\mid\text{$v$ is
$A_{1}$-good}\right]\mid\text{$v$ is
$A_{1}$-good})\leq\exp\left(-\Theta(n^{\beta})\right).$

Hence, by the union bound over all $v\in V(\Gamma)$, whp $X_{v}\geq
0.5n^{\beta}$ for every $v\in[n]\setminus A_{1}$ which is $A_{1}$-good, and
thus the second item of the claim holds as well. ∎

We complete the proof with the two following lemmas.

######  Lemma 4.14.

If there exists a constant $C$ such that

$|C_{j}|\leq C,\quad\forall j\in[\ell],$

then whp $\alpha(\Gamma_{i})\leq\frac{n}{\log_{\rho}n}$.

###### Proof.

Set $\widetilde{G}_{W}$. Consider the following coupling
$(\widetilde{G}_{W}(p^{\prime}),\Gamma_{p^{\prime}})$. $\Gamma_{p^{\prime}}$
is obtained by retaining each edge independently in $\Gamma$ with probability
$p^{\prime}$. For every $v,u\in V(\widetilde{G}_{W})$, there is an edge
$\\{u,v\\}$ in $\widetilde{G}_{W}(p^{\prime})$ if and only if in
$\Gamma_{p^{\prime}}$ there are all the edges between $\phi^{-1}(v)$ and
$\phi^{-1}(u)$. Note that

$\frac{\alpha(\Gamma_{p^{\prime}})}{C}\leq\alpha(\widetilde{G}_{W}(p^{\prime})).$

Indeed, let $I$ be a maximum independent set in $\Gamma_{p^{\prime}}$. Assume
that $I$ has vertices from $m$ different equivalence classes. Observe that
$m\geq\frac{|I|}{C}$ as otherwise, by the pigeonhole principle, we have an
equivalence class larger than $C$. Notice that $\phi(I)$ is also an
independent set in $\widetilde{G}_{W}(p^{\prime})$ since, for every $v,u\in
I$, there is at least one edge missing in $\Gamma_{p^{\prime}}$ between the
equivalence classes of $v$ and $u$, and thus there is no edge between
$\phi(v)$ and $\phi(u)$ in $\widetilde{G}_{W}(p^{\prime})$. Hence,
$\phi(I)\leq\alpha(\widetilde{G}_{W}(p^{\prime}))$ and thus,

$\frac{\alpha(\Gamma_{p^{\prime}})}{C}\leq
m=|\phi(I)|\leq\alpha(\widetilde{G}_{W}(p^{\prime})).$

By the coupling above, every edge in $\widetilde{G}_{W}(p^{\prime})$ appears
with probability at least $(p^{\prime})^{C^{2}}$. Thus, it suffices to show
that whp the independence number of the binomial random subgraph of
$\widetilde{G}_{W}$ obtained by retaining every edge with probability
$(p^{\prime})^{C^{2}}$ is at most $\frac{n}{\log_{\rho}n}$. The rest of the
proof is identical to the proof of Claim 4.8. ∎

######  Lemma 4.15.

If there exists $\beta>0$ such that

$|C_{j}|\geq n^{\beta},\quad\forall j\in[\ell],$

then whp $\alpha(\Gamma_{i})\leq\frac{n}{\log_{\rho}n}$.

###### Proof.

Let $I$ be a maximum independent set in $\Gamma_{i}$. For every $j\in[\ell]$,
set $I_{j}\coloneqq I\cap C_{j}$.

Notice that, for every $j\in[\ell]$, $C_{j}$ is a clique in $\Gamma$. The
probability that there is an independent set in $G(n,p)$ of size
$n/\log_{\rho}n$ is at most

$\binom{n}{\frac{n}{\log_{\rho}n}}(1-p)^{\binom{n/\log_{\rho}n}{2}}\leq\exp\left(n-\frac{pn^{2}}{2\ln^{2}n}\right).$

There are at most $n^{1-\beta}$ many $C_{j}$s, and thus, by the union bound,
whp $I_{j}\leq\frac{n^{\beta}}{\log_{\rho}n}$, for every $j\in[\ell]$. Hence,

$|I|\leq
n^{1-\beta}\cdot\frac{n^{\beta}}{\log_{\rho}n}=\frac{n}{\log_{\rho}n}.$

∎

###  4.3 Theorem 4

The proof of Theorem 4 follows immediately from Lemma 1.5 together with the
construction given in the proof of Theorem 3 (with $A_{1},A_{2},A_{3}$ and $B$
defined in the same manner), where we instead let $B$ be the empty graph,
similarly to [10] ($B_{2}$ is defined as the set of vertices which are not
$A_{1}$-good in $B$, and Lemma 4.1 is not relevant any more).

##  5 Discussion and open problems

In this paper, we present Conjecture 1.3 and make progress towards resolving
it, in particular obtaining a universal bound of $O(n\ln n)$ for the
saturation number $\textit{sat}(G(n,p),F)$ for all $F$ (Theorem 1), and
characterising a family of graphs for which the bound is linear in $n$
(Theorem 2). On the same matter, let us also iterate the question raised in
the introduction:

######  Question 5.1.

Is it true that, for all constant $0<p<1$ and all graphs $F$ where every edge
of $F$ is in a triangle, whp
$\textit{sat}\left(G(n,p),F\right)=\left(1+o(1)\right)n\log_{\frac{1}{1-p}}n$?

For specific graph families we answer positively. In particular, we extended
the sharp asymptotics results of [10], both to a wide family of graphs
(Theorem 4), and to complete multipartite graphs when $p\geq\frac{1}{2}$
(Theorem 3). However, our proof of Theorem 3 requires our graph to be dense
enough, so that we may find a subgraph $A$ of an appropriate size and such
that the neighborhoods of the vertices outside this subgraph form a dense
enough subset in a Hamming space with the domain $A$. Unfortunately, this no
longer holds when $p$ is a small constant (with the technicalities explicit in
Lemma 2.2). It would be interesting to know whether a similar construction,
with different probabilistic or combinatorial tools, could extend the result
for $p<\frac{1}{2}$.

Finally, let us reiterate that it was shown in [4] that Lemma 1.5 is in fact
tight, in the sense that the conditions for it are both sufficient and
necessary. This implies that the results that can be obtained by the
construction given in [10], where $B$ is taken as an empty graph, are limited
to those of Theorem 4. Indeed, already trying to extend this result to
complete multipartite graphs, which may not adhere to the conditions of Lemma
1.5, required a delicate (and at times technical) treatment, utilising a
coupling with an auxiliary random graph in a Hamming space and proving a tight
bound for its independence number using a covering-balls argument.

##### Acknowledgements

The authors wish to thank Michael Krivelevich for helpful comments and
suggestions, and Dor Elboim for fruitful discussions.

## References

  * [1] N. Alon and J. H. Spencer.  The probabilistic method.  Hoboken, NJ: John Wiley & Sons, fourth edition, 2016.
  * [2] Y. Demidovich, A. Skorkin, and M. Zhukovskii.  Cycle saturation in random graphs.  arXiv preprint, arXiv:2109.05758, 2021.
  * [3] S. Demyanov and M. Zhukovskii.  Tight concentration of star saturation number in random graphs.  arXiv preprint, arXiv:2212.06101, 2022.
  * [4] S. Diskin, I. Hoshen, M. Krivelevich, and M. Zhukovskii.  On vertex Ramsey graphs with forbidden subgraphs.  arXiv preprint, arXiv:2211.13966, 2022.
  * [5] P. Erdős, A. Hajnal, and J. W. Moon.  A problem in graph theory.  Amer. Math. Monthly, 71:1107–1110, 1964.
  * [6] J. R. Faudree, R. J. Faudree, and J. R. Schmitt.  A survey of minimum saturated graphs.  Electron. J. Combin., DS19(Dynamic Surveys):36, 2011.
  * [7] A. Frieze and M. Karoński.  Introduction to random graphs.  Cambridge University Press, Cambridge, 2016.
  * [8] A. Johansson, J. Kahn, and V. Vu.  Factors in random graphs.  Random Structures Algorithms, 33(1):1–28, 2008.
  * [9] L. Kászonyi and Z. Tuza.  Saturated graphs with minimal number of edges.  J. Graph Theory, 10(2):203–210, 1986.
  * [10] D. Korándi and B. Sudakov.  Saturation in random graphs.  Random Structures Algorithms, 51(1):169–181, 2017.
  * [11] A. Mohammadian and B. Tayfeh-Rezaie.  Star saturation number of random graphs.  Discrete Math., 341(4):1166–1170, 2018.
  * [12] A. A. Zykov.  On some properties of linear complexes.  Mat. Sbornik N.S., 24(66):163–188, 1949.