# Percolation on Irregular High-dimensional Product Graphs

Sahar Diskin 111School of Mathematical Sciences, Tel Aviv University, Tel Aviv
6997801, Israel. Email<EMAIL_ADDRESS>Joshua Erde 222Institute
of Discrete Mathematics, Graz University of Technology, Steyergasse 30, 8010
Graz, Austria. Email<EMAIL_ADDRESS>Research supported in part by FWF
P36131. Mihyun Kang 333Institute of Discrete Mathematics, Graz University of
Technology, Steyergasse 30, 8010 Graz, Austria. Email<EMAIL_ADDRESS>Research supported in part by FWF W1230. Part of this work was done while the
author was visiting the Simons Institute for the Theory of Computing. Michael
Krivelevich 444School of Mathematical Sciences, Tel Aviv University, Tel Aviv
6997801, Israel. Email<EMAIL_ADDRESS>Research supported in part
by USA–Israel BSF grant 2018267.

###### Abstract

We consider bond percolation on high-dimensional product graphs
$G=\square_{i=1}^{t}G^{(i)}$, where $\square$ denotes the Cartesian product.
We call the $G^{(i)}$ the base graphs and the product graph $G$ the host
graph. Very recently, Lichev [19] showed that, under a mild requirement on the
isoperimetric properties of the base graphs, the component structure of the
percolated graph $G_{p}$ undergoes a phase transition when $p$ is around
$\frac{1}{d}$, where $d$ is the average degree of the host graph.

In the supercritical regime, we strengthen Lichev’s result by showing that the
giant component is in fact unique, with all other components of order
$o(|G|)$, and determining the sharp asymptotic order of the giant.
Furthermore, we answer two questions posed by Lichev [19]: firstly, we provide
a construction showing that the requirement of bounded-degree is necessary for
the likely emergence of a linear order component; secondly, we show that the
isoperimetric requirement on the base graphs can be, in fact, super-
exponentially small in the dimension. Finally, in the subcritical regime, we
give an example showing that in the case of irregular high-dimensional product
graphs, there can be a polynomially large component with high probability,
very much unlike the quantitative behaviour seen in the Erdős-Rényi random
graph and in the percolated hypercube, and in fact in any regular high-
dimensional product graphs, as shown by the authors in a companion paper [9].

##  1 Introduction and main results

In 1957, Broadbent and Hammersley [6] initiated the study of percolation
theory in order to model the flow of fluid through a medium with randomly
blocked channels. In _(bond) percolation_ , given a graph $G$, the percolated
random subgraph $G_{p}$ is obtained by retaining every edge of the _host
graph_ $G$ independently and with probability $p$. If we take the host graph
$G$ to be the complete graph $K_{d+1}$ then $G_{p}$ coincides with the well-
known _binomial random graph model_ $G(d+1,p)$. In their seminal paper from
1960, Erdős and Rényi [12] showed that $G(d+1,p)$555In fact, Erdős and Rényi
worked in the closely related _uniform_ random graph model $G(d+1,m)$. As we
mainly consider graphs with average degree $d$, we use the slightly unusual
notation of $G(d+1,p)$ instead of $G(n,p)$, to make the comparison of the
results simpler. undergoes a dramatic phase transition, with respect to its
component structure, when $p$ is around $\frac{1}{d}$. More precisely, given a
constant $\epsilon>0$ let us define $y=y(\epsilon)$ to be the unique solution
in $(0,1)$ of the equation

$\displaystyle y=1-\exp\left(-(1+\epsilon)y\right),$ (1)

where we note that $y$ is an increasing continuous function on $(0,\infty)$
with $y(\epsilon)=2\epsilon-O(\epsilon^{2})$.

######  Theorem 1.1 ([12]).

Let $\epsilon>0$ be a small enough constant. Then, with probability tending to
one as $d\to\infty$,

  * (a)

if $p=\frac{1-\epsilon}{d}$, then all the components of $G(d+1,p)$ are of
order $O_{\epsilon}\left(\log d\right)$; and,

  * (b)

if $p=\frac{1+\epsilon}{d}$, then there exists a unique _giant_ component in
$G(d+1,p)$ of order $(1+o(1))y(\epsilon)d$. Furthermore, all the other
components of $G(d+1,p)$ are of order $O_{\epsilon}\left(\log d\right)$.

We refer the reader to [3, 14, 17] for a systematic coverage of random graphs,
and to the monographs [5, 15, 18] on percolation theory.

This phenomenon of such a sharp change in the order of the largest component
has been subsequently studied in many other percolation models. Some well-
studied examples come from percolation on lattice-like structures with fixed
dimension (see [16] for a survey on many results in this subject). Another
extensively studied model is the percolated hypercube, where the host graph is
the _$d$ -dimensional hypercube_ $Q^{d}$. Indeed, answering a question of
Erdős and Spencer [13], Ajtai, Komlós, and Szemerédi [1] proved that
$Q^{d}_{p}$ undergoes a phase transition quantitatively similar to the one
which occurs in $G(d+1,p)$, and their work was later extended by Bollobás,
Kohayakawa, and Łuczak [4].

######  Theorem 1.2 ([1, 4]).

Let $\epsilon>0$ be a small enough constant. Then, with probability tending to
one as $d\to\infty$,

  * (a)

if $p=\frac{1-\epsilon}{d}$, then all the components of $Q^{d}_{p}$ are of
order $O_{\epsilon}(d)$; and,

  * (b)

if $p=\frac{1+\epsilon}{d}$, then there exists a unique giant component of
order $(1+o(1))y(\epsilon)2^{d}$. Furthermore, all the other components of
$Q^{d}_{p}$ are of order $O_{\epsilon}(d)$.

Note that, since $|V(Q^{d})|=2^{d}$, in both Theorems 1.1 and 1.2 the likely
order of the largest component changes from logarithmic in the order of the
host graph in the subcritical regime, to linear in the order of the host graph
in the supercritical regime, whilst the second-largest component in the
supercritical regime remains of logarithmic order. Furthermore, in both models
this giant component is the unique component of linear order, and covers the
same asymptotic fraction of the vertices in each case. We informally refer to
this quantitative behaviour as the _Erdős-Rényi component phenomenon_.

Recently, Lichev [19] initiated the study of percolation on some families of
high-dimensional graphs, those arising from the product of many bounded-degree
graphs. Given a sequence of graphs $G^{(1)},\ldots,G^{(t)}$, the Cartesian
product of $G^{(1)},\ldots,G^{(t)}$, denoted by $G=G^{(1)}\square\cdots\square
G^{(t)}$ or $G=\square_{i=1}^{t}G^{(i)}$, is the graph with the vertex set

$\displaystyle V(G)=\left\\{v=(v_{1},v_{2},\ldots,v_{t})\colon v_{i}\in
V(G^{(i)})\text{ for all }i\in[t]\right\\},$

and the edge set

$\displaystyle E(G)=\left\\{uv\colon\begin{array}[]{l}\text{there is some
}i\in[t]\text{ such that }u_{i}v_{i}\in E\left(G^{(i)}\right)\\\ \text{ and
}u_{j}=v_{j}\text{ for all }i\neq j\end{array}\right\\}.$

We call $G^{(i)}$ the base graphs of $G$. Throughout the rest of the paper, we
denote by $|G|$ for the number of vertices of the graph $G$, and use $t$ for
the number of base graphs in the product. We denote by $d\coloneqq d(G)$ the
average degree of a given graph $G$.

Considering percolation in these high-dimensional product graphs, Lichev [19]
showed the existence of a threshold for the appearance of a component of
linear order in these models, under some mild assumptions on the
_isoperimetric constants_ of the base graphs. The isoperimetric constant
$i(H)$ of a graph $H$ is a measure of the edge-expansion of $H$ and is given
by

$i(H)=\min_{\begin{subarray}{c}S\subseteq V(H),\\\
|S|\leq|V(H)|/2\end{subarray}}\frac{e(S,S^{C})}{|S|}.$

Throughout the paper, all asymptotics are with respect to $t$, and we use the
standard Landau notations (see e.g., [17]). We often state results for
properties that hold whp, (short for “with high probability”), that is, with
probability tending to $1$ as $t$ tends to infinity.

######  Theorem 1.3 ([19]).

Let $C,\gamma>0$ be constants and let $\epsilon>0$ be a small enough constant.
Let $G^{(1)},\ldots,G^{(t)}$ be graphs such that
$1\leq\Delta\left(G^{(j)}\right)\leq C$ and $i\left(G^{(j)}\right)\geq
t^{-\gamma}$ for all $j\in[t]$. Let $G=\square_{j=1}^{t}G^{(j)}$. Then, whp

  1. 1.

if $p=\frac{1-\epsilon}{d}$, then all the components of $G_{p}$ are of order
at most $\exp\left(-\frac{\epsilon^{2}t}{9C^{2}}\right)|G|$;

  2. 2.

if $p=\frac{1+\epsilon}{d}$, then there exists a positive constant
$c_{1}=c_{1}(\epsilon,C,\gamma)$ such that the largest component of $G_{p}$ is
of order at least $c_{1}|G|$.

Lichev asked if the conditions in Theorem 1.3 could be weakened.

######  Question 1.4 ([19, Question 5.1]).

Does Theorem 1.3 still hold without the assumption on the maximum degrees of
the $G^{(j)}\mathord{?}$

######  Question 1.5 ([19, Question 5.2]).

Does Theorem 1.3 still hold if the isoperimetric constant
$i\left(G^{(j)}\right)$ decreases faster than a polynomial function of
$t\mathord{?}$

Furthermore, in comparison to Theorems 1.1 and 1.2, we note that Theorem 1.3
only gives a rough, qualitative description of the phase transition, and it is
natural to ask if a more precise, quantitative description of the component
structure of these percolated product graphs in the sub- and super-critical
regimes can be given, in the vein of the Erdős-Rényi component phenomenon, and
if not in general, then under which additional assumptions?

In a recent paper [9], the authors gave a partial answer to this final
question, showing that it is sufficient to assume that the base graphs are all
_regular_ and of bounded order.

######  Theorem 1.6 (Informal [9]).

Let $C>1$ be a constant and let $G=\square_{j=1}^{t}G^{(j)}$ be a product
graph where $G^{(j)}$ is connected and regular and
$1<\left|V\left(G^{(j)}\right)\right|\leq C$ for each $j\in[t]$. Then the
phase transition that $G_{p}$ undergoes around $p=\frac{1}{d}$ exhibits the
Erdős-Rényi component phenomenon.

In this paper, we will investigate further the properties of the phase
transition in _irregular_ high-dimensional product graphs. Firstly, we will
give a negative answer to Question 1.4, showing that if the maximum degree of
the base graphs is allowed to grow (as a function in $t$), then the largest
component may have sublinear order for any $p=\Theta\left(\frac{1}{d}\right)$.
Let us write $S(r,s)$ for the graph formed by taking the complete graph
$K_{r}$ on $r$ vertices and adding $s$ leaves to each vertex of $K_{r}$.

######  Theorem 1.

Let $r=r(t)$ and $s=s(t)$ be integers, which may tend to infinity as $t$ tends
to infinity, such that $r=\omega(st)$. Let $G^{(j)}=K_{2}$ for $1\leq j<t$,
let $G^{(t)}=S(r,s)$ and let $G=\square_{i=1}^{t}G^{(i)}$, where we note that
$d=(1+o(1))\frac{r}{s}$. Let $p\leq\frac{1}{4st}$. Then, whp the largest
component of $G_{p}$ has order at most $\frac{2|G|}{s}$.

Note that for the base graphs defined in Theorem 1, we have
$i\left(G^{(j)}\right)=1$ for $1\leq j\leq t-1$, and
$i\left(G^{(t)}\right)=\Omega\left(\frac{1}{s}\right)$, and so, as long as $s$
is not too large, this graph will satisfy the requirements of Theorem 1.3
regarding the isoperimetric constant. However, by choosing $s=\omega(1)$ and
${r=\omega(s^{2}t)}$, so that the upper bound on the edge probability $p$ in
Theorem 1 is such that
${\frac{1}{4st}=\omega\left(\frac{s}{r}\right)=\omega\left(\frac{1}{d}\right)}$,
we see that even significantly above the point $p_{*}=\frac{1}{d}$, the
largest component in the percolated product graph will typically have size
$o(|G|)$.

However, we are able to give a positive answer to Question 1.5, showing that
in fact a threshold for the existence of a linear sized component in a
percolated product graph exists even when the isoperimetric constants of the
base graphs are _super-exponentially_ small in $t$. Furthermore, we strengthen
Lichev’s [19] result by determining the asymptotic order of the giant, and
showing that it is in fact unique.

######  Theorem 2.

Let $C>0$ be a constant, and let $\epsilon>0$ be a small enough constant. Let
$G^{(1)},\ldots,G^{(t)}$ be graphs such that for all $j\in[t]$,
$1\leq\Delta\left(G^{(j)}\right)\leq C$ and $i\left(G^{(j)}\right)\geq
t^{-t^{\frac{1}{4}}}$. Let $G=\square_{j=1}^{t}G^{(j)}$, let $d$ be the
average degree of $G$ and let $p=\frac{1+\epsilon}{d}$. Then, whp

  1. 1.

$G_{p}$ contains a unique giant component of order $(1+o(1))y(\epsilon)|G|$,
where $y(\epsilon)$ is defined according to (1);

  2. 2.

all other components of $G_{p}$ are of order $o(|G|)$.

Note that, this is the same asymptotic fraction of the vertices as in Theorems
1.1 and 1.2.

Whilst Theorem 2 concerns the size of the largest component in the
supercritical regime, which follows the Erdős-Rényi component phenomenon, we
are also able to give an example that demonstrates that, if the base graphs
are allowed to be irregular, the percolated product graph can also deviate in
behaviour significantly from the Erdős-Rényi component phenomenon in the
subcritical regime.

######  Theorem 3.

Let $s$ be a large enough integer. Let $G^{(i)}=S(1,s)$, that is, a star with
$s$ leaves, for every $1\leq i\leq t$, and let $G=\square_{i=1}^{t}G^{(i)}$,
noting that $d=\frac{2st}{s+1}$. Let $p=\frac{c}{t}$ for $c>\frac{1}{3}$.
Then, whp the largest component of $G_{p}$ is of order at least
$|G|^{1-s^{-\frac{1}{6}}}$.

Note that Theorem 3 demonstrates the necessity of the assumption that the base
graphs are regular in Theorem 1.6, as well as the near optimality of the bound
in Theorem 1.3 1, in terms of the size of the largest component in the
subcritical regime. Indeed, since $t=\Theta(\log|G|)$ and
$\Delta\left(G^{(i)}\right)=s=\Theta(1)$ for all $i$, here we have that the
largest component has order at least $\exp\left(-\Theta(t)\right)|G|$, which
matches the bound in Theorem 1.3 1, up to the dependence on $p$ and
$\max_{i}\\{\Delta\left(G^{(i)}\right)\\}$ in the leading constant.
Furthermore, note that as $s$ grows, the bound on the largest component grows
close to linear in $|G|$.

The structure of the paper is as follows. In Section 2 we introduce some
preliminary tools and lemmas we will use in the paper. In Section 3 we prove
Theorem 1. In Section 4 we provide a general framework for showing the
existence of a large component, in particular in high-dimensional product
graphs. We then use this framework to prove Theorem 2 and, with an additional
analysis of the structure of the $t$-fold product of stars, to prove Theorem
3. Finally, in Section 5 we make some brief comments on our results and
indicate directions for further research.

##  2 Preliminaries

With respect to high-dimensional product graphs, our notation follows that of
[9]. Given a vertex $u=(u_{1},u_{2},\ldots,u_{t})$ in $V(G)$ and $i\in[t]$ we
call the vertex $u_{i}\in V\left(G^{(i)}\right)$ the $i$-th coordinate of $u$.
We note that, as is standard, we may still enumerate the vertices of a given
set $M$, such as $M=\left\\{v_{1},\ldots,v_{m}\right\\}$ with $v_{i}\in V(G)$.
Whenever confusion may arise, we will clarify whether the subscript stands for
enumeration of the vertices of the set, or for their coordinates.

When $G^{(i)}$ is a graph on a single vertex, that is,
$G^{(i)}=\left(\\{u\\},\varnothing\right)$, we call it trivial (and non-
trivial, otherwise). We define the dimension of $G=\square_{i=1}^{t}G^{(i)}$
to be the number of base graphs $G^{(i)}$ of $G$ which are non-trivial.

Given $H\subseteq G=\square_{i=1}^{t}G^{(i)}$, we call $H$ a projection of $G$
if $H$ can be written as $H=\square_{i=1}^{t}H^{(i)}$ where for every $1\leq
i\leq t$, $H^{(i)}=G^{(i)}$ or $H^{(i)}=\\{v_{i}\\}\subseteq
V\left(G^{(i)}\right)$; that is, $H$ is a projection of $G$ if it is the
Cartesian product graph of base graphs $G^{(i)}$ and their trivial subgraphs.
In that case, we further say that $H$ is the projection of $G$ onto the
coordinates corresponding to the trivial subgraphs. For example, let $u_{i}\in
V\left(G^{(i)}\right)$ for $1\leq i\leq k$, and let
$H=\\{u_{1}\\}\square\cdots\square\\{u_{k}\\}\square
G^{(k+1)}\square\cdots\square G^{(t)}$. In this case we say that $H$ is a
projection of $G$ onto the first $k$ coordinates.

Given a graph $H$ and a vertex $v\in V(H)$, we denote by $C_{v}(H)$ the
component of $v$ in $H$. We denote by $N_{H}(S)$ the external neighbourhood of
a set $S$ in the graph $H$, by $E_{H}(A,B)$ the set of edges between $A$ and
$B$ in $H$, and by $e_{H}(A,B)\coloneqq|E_{H}(A,B)|$. When the graph we refer
to is obvious, we may omit the subscript. We omit rounding signs for the sake
of clarity of presentation.

###  2.1 The BFS algorithm

For the proofs of our main results, we will use the Breadth First Search (BFS)
algorithm. This algorithm explores the components of a graph $G$ by building a
maximal spanning forest.

The algorithm maintains three sets of vertices:

  * •

$S$, the set of vertices whose exploration is complete;

  * •

$Q$, the set of vertices currently being explored, kept in a queue; and

  * •

$T$, the set of vertices that have not been explored yet.

The algorithm starts with $S=Q=\emptyset$ and $T=V(G)$, and ends when $Q\cup
T=\emptyset$. At each step, if $Q$ is non-empty, then the algorithm queries
$T$ for neighbours in $G$ of the first vertex $v$ in $Q$, according to some
order $\sigma$ on $V$. Each neighbour which is discovered is added to the back
of the queue $Q$. Once all neighbours of $v$ have been discovered, we move $v$
from $Q$ to $S$. If $Q=\emptyset$, then we move the next vertex from $T$
(according to $\sigma$) into $Q$. Note that the set of edges queried during
the algorithm forms a maximal spanning forest of $G$.

In order to analyse the BFS algorithm on a random subgraph $G_{p}$ of a graph
$G$ with $m$ edges, we will utilise the _principle of deferred decisions_.
That is, we will take a sequence $(X_{i}\colon 1\leq i\leq m)$ of i.i.d.
Bernoulli$(p)$ random variables, which we will think of as representing a
positive or negative answer to a query in the algorithm. When the $i$-th edge
of $G$ is queried during the BFS algorithm, we will include it in $G_{p}$ if
and only if $X_{i}=1$. It is clear that the forest obtained in this way has
the same distribution as a forest obtained by running the BFS algorithm on
$G_{p}$.

###  2.2 Preliminary Lemmas

We will make use of two standard probabilistic bounds. The first is a typical
Chernoff type tail bound on the binomial distribution (see, for example,
Appendix A in [2]).

######  Lemma 2.1.

Let $n\in\mathbb{N}$, let $p\in[0,1]$, and let $X\sim Bin(n,p)$. Then for any
positive $m$ with $m\leq\frac{np}{2}$,

$\displaystyle\mathbb{P}\left[|X-np|\geq m\right]\leq
2\exp\left(-\frac{m^{2}}{3np}\right).$

The second is the well-known Azuma-Hoeffding concentration inequality (see,
for example, Chapter 7 in [2])

######  Lemma 2.2.

Let $X=(X_{1},X_{2},\ldots,X_{m})$ be a random vector with independent entries
and with range $\Lambda=\prod_{i\in[m]}\Lambda_{i}$, and let
$f:\Lambda\to\mathbb{R}$ be such that there exists
$C=(C_{1},\ldots,C_{m})\in\mathbb{R}^{m}$ such that for every
$x,x^{\prime}\in\Lambda$ which differ only in the $j$-th coordinate,

$\displaystyle|f(x)-f(x^{\prime})|\leq C_{j}.$

Then, for every $m\geq 0$,

$\displaystyle\mathbb{P}\left[\big{|}f(X)-\mathbb{E}\left[f(X)\right]\big{|}\geq
m\right]\leq 2\exp\left(-\frac{m^{2}}{2\sum_{i=1}^{m}C_{i}^{2}}\right).$

We will use the following result of Chung and Tetali [8, Theorem 2], which
bounds the isoperimetric constant of product graphs.

######  Theorem 2.3 ([8]).

Let $G^{(1)},\ldots,G^{(t)}$ be non-trivial graphs and let
$G=\square_{i=1}^{t}G^{(i)}$. Then

$\min_{j}\left\\{i\left(G^{(j)}\right)\right\\}\geq
i(G)\geq\frac{1}{2}\min_{j}\left\\{i\left(G^{(j)}\right)\right\\}.$

The following projection lemma, which is a key tool in [9, Lemma 4.1], allows
us to cover a small set of points in a product graph with a disjoint set of
high-dimensional projections. This allows us to explore the neighbourhoods of
these points in the percolated subgraph in an independent fashion.

######  Lemma 2.4 (Projection Lemma).

Let $G=\square_{i=1}^{t}G^{(i)}$ be a product graph with dimension $t$. Let
$M\subseteq V(G)$ be such that $|M|=m\leq t$. Then, there exist pairwise
disjoint projections $H_{1},\ldots,H_{m}$ of $G$, each having dimension at
least $t-m+1$, such that every $v\in M$ is in exactly one of these
projections.

We will make repeated use of the following simple, but powerful, observation
of Lichev [19] about the degree distribution in a product graph. If $G$ is a
product graph in which all base graphs have maximum degree bounded by $C$,
then for any $v,w\in V(G)$ we have

$\displaystyle|d_{G}(v)-d_{G}(w)|\leq(C-1)\cdot dist_{G}(v,w).$ (2)

In particular, if $v$ is a vertex with degree significantly above or below
$d$, then, despite the fact that $G$ may be quite irregular, vertices close to
$v$ will still have degree significantly above or below $d$, and the
percolated subgraph close to $v$ will look either super- or sub-critical,
respectively.

Finally, for the proof of Theorem 3, we will utilise the structure, and in
particular the isoperimetric inequalities, of both the Hamming graph and the
Johnson graph.

Given positive integers $t$ and $s$, the Hamming graph $H(t,s)$ is the graph
with vertex set $[s]^{t}$ in which two vertices are adjacent if they differ in
a single coordinate. Alternatively, $H(t,s)$ can be defined as the $t$-fold
Cartesian product of the complete graphs $K_{s}$. In particular, it follows
from Theorem 2.3 that for any non-negative integers $z\leq t$,

$i(H(t-z,s))\geq\frac{1}{2}i(K_{s})=\frac{s}{2}.$ (3)

Given positive integers $t$ and $z$, the Johnson graph $J(t,z)$ is the graph
with vertex set $\binom{[t]}{z}$ in which two $z$-sets $I$ and $K$ are
adjacent if $|I\triangle K|=2$. We note that $J(t,z)$ is the induced subgraph
of the square of $Q^{t}$ on the vertex set of the $z$-th _layer_ ,
$\binom{[t]}{z}$. We will make use of the next vertex-isoperimetric inequality
for Johnson graphs, which follows from the work of Christofides, Ellis and
Keevash [7].

######  Theorem 2.5 ([7]).

Let $t$ and $z$ be positive integers with $z<t$ and let $\alpha\in(0,1)$. Then
there exists a constant $c>0$ such that for any subset $A\subseteq V(J(t,z))$
of size $|A|=\alpha\binom{t}{z}$

$\left|N_{J(t,z)}(A)\right|\geq c\sqrt{\frac{t}{z(t-z)}}(1-\alpha)|A|.$

##  3 Unbounded degree

Given $r=r(t)$ and $s=s(t)$, recall that $S(r,s)$ is the graph formed by
taking a complete graph $K_{r}$ on $r$ vertices and adding $s$ leaves to each
vertex of $K_{r}$. Note that $i(S(r,s))=\Omega\left(\frac{1}{s}\right)$.

Let $G^{(j)}=K_{2}$ for $1\leq j<t$, let $G^{(t)}=S(r,s)$ and let
$G=\square_{i=1}^{t}G^{(i)}$. Observe that

$|V(G)|=2^{t-1}|S(r,s)|=2^{t-1}r(s+1),$

and, as long as $r=\omega(st)$,

$|E(G)|=\frac{1}{2}2^{t-1}\bigg{(}r(r+s+t-2)+rs\left(1+(t-1)\right)\bigg{)}=(1+o(1))2^{t-2}r^{2},$

and so, if $s=\omega(1)$, we have that
$d=(1+o(1))\frac{r^{2}}{r(s+1)}=(1+o(1))\frac{r}{s}$.

In order to prove Theorem 1, we will show that typically, when
$p\leq\frac{1}{4st}$, almost all the vertices of $G_{p}$ are isolated
vertices.

######  Lemma 3.1.

If $p\leq\frac{1}{4st}$, then whp at least
$2^{t-1}rs\left(1-\frac{1}{2s}\right)$ vertices of $G_{p}$ are isolated
vertices.

###### Proof.

Let $\\{z_{i}\colon i\in[r]\\}\subseteq V(S(r,s))$ be the vertex set of the
complete graph $K_{r}$ and let $\\{\ell_{i,j}\colon j\in[s]\\}$ be the set of
leaves adjacent to the vertex $z_{i}$ for each $i\in[r]$. Let

$L=\\{x\in V(G)\colon x_{t}=\ell_{i,j}\text{ for some }i\in[r],j\in[s]\\}.$

Note that $d_{G}(x)=t$ for every $v\in L$ and that $|L|=2^{t-1}rs$.

Let $X_{L}$ be the number of edges in $G_{p}$ which intersects with $L$.
Clearly $X_{L}$ is stochastically dominated by $Bin(|L|t,p)$ and hence, by
Chebyshev’s inequality, whp

$X_{L}\leq 2|L|tp\leq\frac{|L|}{2s}.$

Therefore, whp, the number of isolated vertices in $L$ is at least

$|L|\left(1-\frac{1}{2s}\right)\geq 2^{t-1}rs\left(1-\frac{1}{2s}\right).$

∎

The proof of Theorem 1 will now be a fairly straightforward corollary of Lemma
3.1.

###### Proof of Theorem 1.

Since $|G|=2^{t-1}r(s+1)$ and by Lemma 3.1 whp there are at least
$2^{t-1}rs\left(1-\frac{1}{2s}\right)$ isolated vertices in $G_{p}$, it
follows that whp the number of vertices in any non-trivial component is at
most

$\displaystyle 2^{t-1}r(s+1)-2^{t-1}rs\left(1-\frac{1}{2s}\right)$
$\displaystyle=|G|\left(1-\left(1-\frac{1}{s+1}\right)\left(1-\frac{1}{2s}\right)\right)=\frac{3|G|}{2s+2}\leq\frac{2|G|}{s}.$

∎

##  4 Irregular graphs of bounded degree

In many standard proofs of the existence of a phase transition in percolation
models, for example in [1, 4, 9, 11, 19] and many more, in order to show the
existence of a linear sized component in the supercritical regime, one first
shows that whp a positive proportion of the vertices in the host graph $G$ are
contained in _big_ components, that is, components of size at least $k$ for
some appropriately chosen threshold $k$. One then completes the proof by using
a sprinkling argument to show that whp almost all of these big components
merge into a single, giant component.

More concretely, the first part of the argument is normally shown by bounding
from below the probability that a fixed vertex is contained in a big
component, together with some concentration result. In most cases, at least on
a heuristic level, this is done by comparing a component exploration process
near to a vertex $v$ to some supercritical branching process.

In some ways, (2) allows us to say that, in product graphs, the vertex degree
is almost constant locally. Hence, the threshold probability above which it is
likely that $v$ will lie in a big component will depend not on the global
parameters of the graph, but rather just locally on the degree of the vertex
$v$.

We will use this observation in two ways. Firstly, when the base graphs have
bounded maximal degree, typical concentration bounds will imply that almost
all the vertices have degree very close to the average degree of the graph,
and so these methods will allow us to estimate the proportion of vertices
which are typically contained in big components, and hence eventually the
giant component, in the proof of Theorem 2. The second way, which is perhaps
more unusual, will be to apply this reasoning to the vertices in the host
graph whose degrees are significantly higher than the average degree, to see
that whp many of these vertices are contained in big components even in the
subcritical regime, which we will use in the proof of Theorem 3.

We thus begin with the following lemma, utilising the tools developed in [9,
Lemma 4.2], which provides a lower bound on the probability that a vertex $v$
belongs to a big component, provided that the percolation probability is
significantly larger than $\frac{1}{d_{G}(v)}$. However, since it will be
essential for us to be able to grow components of order super-polynomially
large in $t$ in order to prove Theorem 2, unlike in the proof of [9, Lemma
4.2], we will need to run our inductive argument for $\omega(1)$ steps, which
will necessitate a more careful and explicit handling of the error terms and
probability bounds in the proof.

######  Lemma 4.1.

Let $C>1$ be a constant and let $\epsilon>0$ be sufficiently small. Let
$G^{(1)},\ldots,G^{(t)}$ be graphs such that
$1\leq\Delta\left(G^{(i)}\right)\leq C$ for all $i\in[t]$. Let
$G=\square_{i=1}^{t}G^{(i)}$. Let $v\in V(G)$ be such that $d\coloneqq
d_{G}(v)=\omega(1)$. Let $k=k(t)=o\left(d^{1/3}\right)$ be an integer and let
$m_{k}=d^{\frac{k}{6}}$. Then, for any $p\geq\frac{1+\epsilon}{d}$ there
exists $c=c(\epsilon,d,k)\geq\left(\frac{\epsilon}{5}\right)^{k}$ such that

$\displaystyle\mathbb{P}\left[|C_{v}(G_{p})|\geq cm_{k}\right]\geq y-o(1),$

where $y\coloneqq y(\epsilon)$ is as defined in (1).

###### Proof.

We argue by induction on $k$, over all possible values of $C,\epsilon,d$ and
all possible choices of $G^{(1)},\ldots,G^{(t)}$.

For $k=1$, we run the BFS algorithm (as described in Section 2.1) on $G_{p}$
starting from $v$ with a slight alteration: we terminate the algorithm once
$\min\left(|C_{v}(G_{p})|,d^{\frac{1}{2}}\right)$ vertices are in $S\cup Q$.
Note that at every point in the algorithm we have $|S\cup Q|\leq
d^{\frac{1}{2}}$. Therefore, since at each point in the modified algorithm
$S\cup Q$ spans a connected set, by (2), at each point in the algorithm the
first vertex $u$ in the queue has degree at least $d-Cd^{\frac{1}{2}}$ in $G$,
and thus has at least $d-(C+1)d^{\frac{1}{2}}$ neighbours (in $G$) in $T$.

Hence, we can couple the tree $B_{1}$ built by this truncated BFS algorithm
with a Galton-Watson tree $B_{2}$ rooted at $v$ with offspring distribution
$Bin\left(d-(C+1)d^{\frac{1}{2}},p\right)$ such that $B_{1}\subseteq B_{2}$ as
long as $|B_{1}|\leq d^{\frac{1}{2}}$. Therefore, since

$\displaystyle\left(d-(C+1)d^{\frac{1}{2}}\right)\cdot p$
$\displaystyle\geq\frac{(1+\epsilon)\left(d-(C+1)d^{\frac{1}{2}}\right)}{d}$
$\displaystyle\geq(1+\epsilon)\left(1-(C+1)d^{-\frac{1}{2}}\right)$
$\displaystyle\geq 1+\epsilon-2Cd^{-\frac{1}{2}},$

standard results imply that $B_{2}$ grows infinitely large with probability at
least $y\left(\epsilon-2Cd^{-\frac{1}{2}}\right)-o(1)$ (see, for example, [10,
Theorem 4.3.12]). Thus, by the above and by (1), with probability at least
$y-o(1)$ we have that $|C_{v}(G_{p})|\geq d^{\frac{1}{2}}$. Since
$c(\epsilon,d,1)\leq 1$, it follows that the statement holds for $k=1$, for
all $C,\epsilon,d$ and all possible choices of $G^{(1)},\ldots,G^{(t)}$.

Let $k\geq 2$ and assume the statement holds with
$c(\epsilon^{\prime},d,k-1)=\left(\frac{\epsilon^{\prime}}{5}\right)^{k-1}$
for all $C,\epsilon^{\prime},d$ and $G^{(1)},\ldots,G^{(t)}$. We argue via a
two-round exposure. Set $p_{2}=d^{-\frac{4}{3}}$ and
$p_{1}=\frac{p-p_{2}}{1-p_{2}}$ so that $(1-p_{1})(1-p_{2})=1-p$. Note that
$G_{p}$ has the same distribution as $G_{p_{1}}\cup G_{p_{2}}$, and that
$p_{1}=\frac{1+\epsilon^{\prime}}{d}$ with
$\epsilon^{\prime}\geq\epsilon-d^{-\frac{1}{3}}$. In fact, we will not expose
either $G_{p_{1}}$ or $G_{p_{2}}$ all at once, but in several stages, each
time considering only some subset of the edges.

We begin in a manner similar to $k=1$. We run the BFS algorithm on
$G_{p_{1}}$, starting from $v$, and we terminate the exploration once
$\min\left(|C_{v}(G_{p_{1}})|,d^{\frac{1}{2}}\right)$ vertices are in $S\cup
Q$. Once again, by standard arguments, we have that $|C_{v}(G_{p_{1}})|\geq
d^{\frac{1}{2}}$ with probability at least
$y(\epsilon^{\prime}-2Cd^{-\frac{1}{2}})-o(1)=y-o(1)$ (where the last equality
is by (1)).

Let $W_{0}\subseteq C_{v}(G_{p_{1}})$ be the set of vertices explored in this
process, and let $\mathcal{A}_{1}$ be the event that
$|W_{0}|=d^{\frac{1}{2}}$, whereby the above

$\mathbb{P}[\mathcal{A}_{1}]\geq y-o(1).$ (4)

We assume in what follows that $\mathcal{A}_{1}$ holds. Let us write
$W_{0}=\\{v_{1},\ldots,v_{d^{\frac{1}{2}}}\\}$, and note that $v\in W_{0}$ is
one of the $v_{i}$. Using Lemma 2.4, we can find pairwise disjoint projections
$H_{1},\ldots,H_{d^{\frac{1}{2}}}$ of $G$, each having dimension at least
$t-d^{\frac{1}{2}}$, such that each $v_{i}\in W_{0}$ is in exactly one of the
$H_{i}$. Note that $d\leq\Delta(G)\leq Ct$, and so $d^{\frac{1}{2}}\leq t$,
and so we can apply Lemma 2.4.

Thus, it follows from observation (2) that, for all
$i\in\left[d^{\frac{1}{2}}\right]$, we have

$\displaystyle|d_{G}(v)-d_{G}(v_{i})|\leq(C-1)\cdot dist_{G}(v,v_{i})\leq
Cd^{\frac{1}{2}},$

and therefore

$\displaystyle d_{H_{i}}(v_{i})\geq d_{G}(v_{i})-Cd^{\frac{1}{2}}\geq
d_{G}(v)-2Cd^{\frac{1}{2}}.$

Let $W=\bigcup_{i\in\left[d^{\frac{1}{2}}\right]}N_{H_{i}}(v_{i})$. Then,
$W\subseteq N_{G}(W_{0})$ and, since the $H_{i}$ are pairwise disjoint, by the
above $|W|\geq d^{\frac{3}{2}}-2Cd$.

We now expose the edges between $W_{0}$ and $W$ in $G_{p_{2}}$. Let us denote
the vertices in $W$ that are connected with $W_{0}$ in $G_{p_{2}}$ by
$W^{\prime}$. Then, $|W^{\prime}|$ stochastically dominates

$\displaystyle Bin\left(d^{\frac{3}{2}}-2Cd,p_{2}\right).$

Thus, if we let $\mathcal{A}_{2}$ be the event that
$|W^{\prime}|\geq\frac{d^{\frac{1}{6}}}{3}$ and $|W^{\prime}|\leq
d^{\frac{1}{2}}$, then by Lemma 2.1 we have that

$\mathbb{P}[\mathcal{A}_{2}|\mathcal{A}_{1}]\geq
1-\exp\left(-\frac{d^{\frac{1}{6}}}{15}\right).$ (5)

We assume in what follows that $\mathcal{A}_{2}$ also holds.

Let $W_{i}^{\prime}=W^{\prime}\cap V(H_{i})$. Now, for each $i$, we apply once
again Lemma 2.4 to find a family of $|W^{\prime}_{i}|\coloneqq\ell_{i}\leq
d^{\frac{1}{2}}$ pairwise disjoint projections of $H_{i}$, which we denote by
$H_{i,1},\ldots,H_{i,\ell_{i}}$, such that every vertex of $W^{\prime}_{i}$ is
in exactly one of the $H_{i,j}$, and each of the $H_{i,j}$ is of dimension at
least $t-2d^{\frac{1}{2}}$. Furthermore, we denote by $v_{i,j}$ the unique
vertex of $W_{i}^{\prime}$ that is in $H_{i,j}$. Again, by (2), for all $i,j$

$\displaystyle d_{H_{i,j}}(v_{i,j})\geq d_{G}(v_{i,j})-2Cd^{\frac{1}{2}}\geq
d_{G}(v_{i})-2Cd^{\frac{1}{2}}-C\geq d_{G}(v)-4Cd^{\frac{1}{2}},$

where we used that, by (2), $d_{G}(v_{i})-d_{G}(v_{i,j})\leq C\cdot
dist_{G}(v_{i},v_{i,j})=C$.

Crucially, note that when we ran the BFS algorithm on $G_{p_{1}}$, we did not
query any of the edges in any of the $H_{i,j}$. Indeed, we only queried edges
in $W_{0}$ and between $W_{0}$ and its neighbourhood, and by construction
$E(H_{i,j})\cap E\left(W_{0}\cup N_{G}(W_{0})\right)=\varnothing$. Noting that

$p_{1}\cdot
d_{H_{i,j}}(v_{i,j})\geq\frac{1+\epsilon-d^{-\frac{1}{3}}}{d}\left(d-4Cd^{\frac{1}{2}}\right)\geq
1+\epsilon-2d^{-\frac{1}{3}},$

we may thus apply the induction hypothesis to $v_{i,j}$ in $G_{p_{1}}\cap
H_{i,j}$ and conclude that

$\displaystyle\mathbb{P}\left[|C_{v_{i,j}}\left(G_{p_{1}}\cap
H_{i,j}\right)|\geq
c\left(\epsilon-2d^{-\frac{1}{3}},d_{H_{i,j}}(v_{i,j}),k-1\right)m_{k-1}\right]$
$\displaystyle\geq y\left(\epsilon-2d^{-\frac{1}{3}}\right)-o(1)$
$\displaystyle\geq y-o(1),$

where the first inequality follows from the induction hypothesis, and the
second inequality follows from (1). Furthermore, these events are independent
for each $H_{i,j}$.

Let us define the following indicator random variables

$\displaystyle\mathbb{I}(v_{i,j})\coloneqq\begin{cases}1&\quad\text{if
}|C_{v_{i,j}}(G_{p_{1}}\cap H_{i,j})|\geq
c\left(\epsilon-2d^{-\frac{1}{3}},d_{H_{i,j}}(v_{i,j}),k-1\right)m_{k-1};\\\
0&\quad\text{otherwise,}\end{cases}$

and let $\mathcal{A}_{3}$ be the event that

$\displaystyle\sum_{v_{i,j}\in
W^{\prime}}\mathbb{I}(v_{i,j})\geq\frac{yd^{\frac{1}{6}}}{4}.$

Then, by Lemma 2.1 and by (1),

$\mathbb{P}\left[\mathcal{A}_{3}|\mathcal{A}_{2},\mathcal{A}_{1}\right]\geq
1-\exp\left(-\frac{yd^{\frac{1}{6}}}{20}\right)\geq
1-\exp\left(-\frac{\epsilon d^{\frac{1}{6}}}{20}\right).$ (6)

In particular, by (4), (5) and (6),

$\mathbb{P}[\mathcal{A}_{1}\cup\mathcal{A}_{2}\cup\mathcal{A}_{3}]\geq
y-o(1)-\exp\left(-\frac{\epsilon
d^{\frac{1}{6}}}{20}\right)-\exp\left(-\frac{d^{\frac{1}{6}}}{15}\right)=y-o(1).$
(7)

However, we note that

$\displaystyle
c\left(\epsilon-2d^{-\frac{1}{3}},d_{H_{i,j}}(v_{i,j}),k-1\right)m_{k-1}$
$\displaystyle\geq\left(1-\frac{1}{2\epsilon
d^{\frac{1}{3}}}\right)^{k-1}\left(\frac{\epsilon}{5}\right)^{k-1}m_{k-1}$
$\displaystyle\geq(1-o(1))\left(\frac{\epsilon}{5}\right)^{k-1}m_{k-1},$

where the last inequality follows since $k=o\left(d^{1/3}\right)$. Hence, if
$\mathcal{A}_{3}$ holds, then by (1)

$\displaystyle|C_{v}(G_{p})|$ $\displaystyle\geq\left(\sum_{v_{i,j}\in
W^{\prime}}\mathbb{I}(v_{i,j})\right)\cdot
c\left(\epsilon-2d^{-\frac{1}{3}},d_{H_{i,j}}(v_{i,j}),k-1\right)m_{k-1}$
$\displaystyle\geq\left(\frac{y}{4}d^{\frac{1}{6}}\right)\cdot(1-o(1))\left(\frac{\epsilon}{5}\right)^{k-1}m_{k-1}$
$\displaystyle\geq\left(\frac{\epsilon}{5}\right)^{k}m_{k},$

and so the induction step holds by (7). ∎

Figure 1 illustrates the induction step in the above Lemma.

Figure 1: The induction step in Lemma 4.1

We note that the choice of $p_{2}=d^{-\frac{4}{3}}$ in the proof of Lemma 4.1
was relatively arbitrary, and we could take $p_{2}=d^{-\gamma}$ for any
$1<\gamma<\frac{3}{2}$, which would lead to a similar statement for all
$k=o\left(d^{\gamma-1}\right)$, with

$c=\left(\frac{\epsilon}{5}\right)^{k}\qquad\text{ and }\qquad
m_{k}=d^{\left(\frac{3}{2}-\gamma\right)k}.$

In particular, this lemma can be utilised similarly for components almost as
large as $d^{d^{\frac{1}{2}}}$, by taking $\gamma$ arbitrarily close to
$\frac{3}{2}$ and choosing $k$ appropriately.

In $G(d+1,p)$, isoperimetric considerations alone are enough to guarantee that
typically all the big components merge after a sprinkling step. In many other
cases, for example in the percolated hypercube $Q^{d}_{p}$, isoperimetric
considerations alone will not suffice, and a key step to proving that the big
components likely merge into a giant component is to show that the vertices in
the big components are in some way ’densely’ spread throughout the host graph
$G$. In an irregular product graph this might not be true, but the following
lemma, which is a generalised version of [9, Lemma 4.5], shows that at the
very least the big components are typically well-distributed around the
vertices of large degree.

######  Lemma 4.2.

Let $C>1$ be a constant and let $\epsilon>0$ be small enough constant. Let
$G^{(1)},\ldots,G^{(t)}$ be graphs such that for all $i\in[t]$,
$1\leq\Delta\left(G^{(i)}\right)\leq C$. Let $d=d(t)=\omega(1)$ and let
$p\geq\frac{1+\epsilon}{d}$. Then, whp, there are at most
$\exp(-d^{\frac{3}{2}})|G|$ vertices $v\in V(G)$ such that $d_{G}(v)\geq d$
and $v$ is at distance (in $G$) greater than $2$ from a component of order at
least $d^{d^{\frac{1}{3}}}$ in $G_{p}$.

###### Proof.

Fix $v\in V(G)$ with $d_{G}(v)\geq d$, and let us write
$v=(v_{1},\ldots,v_{t})$ such that $\forall i\in[t],v_{i}\in
V\left(G^{(i)}\right)$. Denote by $w_{i}$ an arbitrarily chosen neighbour of
$v_{i}$ in $G^{(i)}$. Furthermore, for any $\ell,m$ such that $1\leq\ell\neq
m\leq\epsilon^{2}d$ we define

$\displaystyle\begin{cases}H^{(i)}_{\ell,m}=\\{v_{i}\\}&\text{when }1\leq
i\leq\epsilon^{2}d,i\notin\left\\{\ell,m\right\\};\\\
H^{(i)}_{\ell,m}=\\{w_{i}\\}&\text{when }i\in\left\\{\ell,m\right\\};\text{
and,}\\\ H^{(i)}_{\ell,m}=G^{(i)}&\text{when }i>\epsilon^{2}d.\end{cases}$

Note that, since $d\leq\Delta(G)\leq Ct$, and $\epsilon>0$ is sufficiently
small, these projections are well-defined. Let
$H_{\ell,m}=\square_{i=1}^{t}H^{(i)}_{\ell,m}$.

We defined in this manner
$\binom{\epsilon^{2}d}{2}\geq\frac{\epsilon^{4}d^{2}}{3}$ pairwise disjoint
projections $H_{\ell,m}$, each of dimension $t-\epsilon^{2}d$, such that each
$H_{\ell,m}$ has a vertex at distance $2$ (in $G$) from $v$, which we denote
by $w_{\ell,m}$. Observe that by (2), for $\epsilon>0$ sufficiently small,

$\displaystyle d_{H_{\ell,m}}(w_{\ell,m})\geq
d_{G}(v)-C\epsilon^{2}d\geq(1-C\epsilon^{2})d\geq\left(1-\frac{\epsilon}{2}\right)d.$

Thus, by Lemma 4.1, with an appropriate choice of $k$, we have that
$w_{\ell,m}$ belongs to a component of $H_{{\ell,m}_{p}}$ of order
$d^{d^{\frac{1}{3}}}$ with probability at least
$y\left(\frac{\epsilon}{3}\right)-o(1)>\frac{\epsilon}{3}$. Since the
$H_{\ell,m}$ are pairwise disjoint, these events are independent for different
$w_{\ell,m}$. Thus, by Lemma 2.1, there is some $c^{\prime}(\epsilon)>0$ such
that at least one of the $w_{\ell,m}$ belongs to a component whose order is at
least $d^{d^{\frac{1}{3}}}$ with probability at least
$1-\exp(-c^{\prime}d^{2})$. Hence, the expected number of vertices $v\in V(G)$
such that $d_{G}(v)\geq d$ and $v$ is not distance at most $2$ from a
component of order $d^{d^{\frac{1}{3}}}$ is at most
$\exp(-c^{\prime}d^{2})|G|$. Therefore, by Markov’s inequality, whp there are
at most $\exp(-d^{\frac{3}{2}})|G|$ such vertices. ∎

Note, in particular, that since $d=\Theta(t)$, if the orders of the base
graphs $G^{(i)}$, $|G^{(i)}|$, are growing sufficiently slowly, then
$\exp(-d^{\frac{3}{2}})|G|=o(1)$, and so whp _all_ the vertices of $G$ of
large order will be close to a big component.

Such a ‘density lemma’ can then be used in graphs with sufficiently good
isoperimetric inequalities to show that the big components in the percolated
subgraph are typically well enough connected that after a sprinkling step they
will likely all merge. More concretely, one often shows that between any
suitable partition of the big components, the host graph will typically
contain a large family of short edge-disjoint paths between the two sides of
this partition. If the number and length of these paths is sufficiently
large/small, respectively, compared to the size of the big components, we can
conclude that after sprinkling whp a large proportion of these components
merge. Since we will use a variant of this argument in the proof of both
Theorems 2 and 3, let us state a very general version of it.

Given graphs $H\subseteq G$ and a subset $X\subseteq V(G)$, we say a partition
$X=A\cup B$ is _( $H$-)component respecting_ if for every component $K$ of
$H$, $K\cap X$ is fully contained in either $A$ or $B$.

######  Lemma 4.3.

Let $p\in(0,1)$, let $c\in\left(0,\frac{1}{2}\right)$ and let
$m\in\mathbb{N}$. Assume $k=\omega\left(rp^{-m}\right)$. Let $H\subseteq G$ be
graphs and let $X\subseteq V(G)$ be a subset such that

  1. (C1)

for every component $K$ of $H$ which meets $X$, we have that $|X\cap K|\geq
k$;

  2. (C2)

for any partition $X=A\cup B$ with $|A|,|B|\geq c|X|$ that is $H$-component
respecting there is a family of at least $\frac{|X|}{r}$ edge-disjoint $A-B$
paths of length at most $m$ in $G$.

Then whp $H\cup G_{p}$ contains a component with at least $(1-c)|X|$ vertices
of $X$.

###### Proof.

If there is no component in $H\cup G_{p}$ which contains at least $(1-c)|X|$
vertices of $X$, then there is some $H$-component respecting partition
$X=A\cup B$ with $|A|,|B|\geq c|X|$ such that there is no path between $A$ and
$B$ in $G_{p}$.

By (C2), for each such $H$-component respecting partition $X=A\cup B$ there is
a family of at least $\frac{|X|}{r}$ many edge-disjoint $A-B$ paths of length
at most $m$ in $G$. The probability that none of these paths are in $G_{p}$ is
at most

$(1-p^{m})^{\frac{|X|}{r}}\leq\exp\left(-\frac{|X|p^{m}}{r}\right).$

On the other hand, by (C1), for every component $K$ of $H$ which meets $X$, we
have that $|X\cap K|\geq k$. Hence, the total number of $H$-component
respecting partitions $X=A\cup B$ with $|A|,|B|\geq c|X|$ is at most
$2^{\frac{|X|}{k}}$.

Therefore, by the union bound, the probability that $H\cup G_{p}$ does not
contain a component of order at least $(1-c)|X|$ is at most

$2^{\frac{|X|}{k}}\exp\left(-\frac{|X|p^{m}}{r}\right)=\exp\left(-\Omega\left(-\frac{k}{rp^{-m}}\right)\right)=o(1),$

where the first equality is because $|X|\geq|X\cap K|\geq k$ by (C1), and the
second inequality follows from our assumption that
$k=\omega\left(rp^{-m}\right)$. ∎

In the remainder of this section, we prove Theorems 2 and 3.

###  4.1 Proof of Theorem 2

###### Proof of Theorem 2.

Note that, since all of the $G^{(i)}$ are non-trivial, we have $t\leq d\leq
Ct$ and $|G|\geq 2^{t}$, and therefore,

$t^{t^{\frac{1}{4}}}=o\left(d^{d^{\frac{3}{10}}}\right)=o(|G|).$

We argue via a two-round exposure. Set $p_{2}=\frac{1}{d\log d}$ and
$p_{1}=\frac{p-p_{2}}{1-p_{2}}$, so that $(1-p_{1})(1-p_{2})=1-p$. Note that
$G_{p}$ has the same distribution as $G_{p_{1}}\cup G_{p_{2}}$ and that
$p_{1}=\frac{1+\epsilon-o(1)}{d}$.

Set $I\coloneqq\left[\left(1-\frac{1}{\log d}\right)d,\left(1+\frac{1}{\log
d}\right)d\right]$, and denote the set of vertices whose degree in $G$ lies in
the interval $I$ by $V_{1}\subseteq V(G)$. Note that the degree of a uniformly
chosen vertex in $G$ is distributed as the sum of $t$ random variables, each
of which is bounded by $C$. Since the expected degree of a uniformly chosen
vertex is the average degree $d$, we have by Lemma 2.2 that $|V\setminus
V_{1}|\leq 4\exp\left(-\frac{d}{\log^{2}d}\right)|G|.$

Let $W$ be the set of vertices belonging to components of order at least
$d^{d^{\frac{3}{10}}}$ in $G_{p_{1}}$. Since for every $v\in V_{1}$ we have
that $d_{G}(v)\cdot p_{1}=1+\epsilon-o(1)$, we have by Lemma 4.1 that

$\displaystyle\text{every }v\in V_{1}\text{ belongs to }W\text{ with
probability at least }y(\epsilon)-o(1).$ (8)

We assume henceforth that the above stated whp statements of $G_{p_{1}}$ hold.
Note furthermore that by adding or a deleting an edge from $G_{p_{1}}$ we can
change the number of vertices in $W$ by at most
$2d^{d^{\frac{3}{10}}}=o\left(\frac{|G|}{d}\right)$. Hence, by Lemma 2.2
applied to the edge-exposure martingale on $G_{p_{1}}$ of length
$\frac{|G|d}{2}$, we see that whp $|W|=\left(y(\epsilon)+o(1)\right)|G|$. Note
that, by Lemma 4.2, whp there are at most
$\exp\left(-d^{\frac{3}{2}}\right)|G|$ vertices at distance (in $G$) greater
than $2$ from $W$.

Let $A\cup B$ be a partition of $W$ into two parts, $A$ and $B$, with
$|A|\leq|B|$ and $|A|\geq\frac{|W|}{t}$. Let $A^{\prime}$ be the set of
vertices in $A$ together with all vertices in $V(G)\setminus B$ at distance at
most $2$ from $A$, and let $B^{\prime}$ be the set of vertices in $B$ together
with all vertices in $V(G)\setminus A^{\prime}$ at distance at most $2$ from
$A$. By Lemma 2, we have

$i(G)\geq\frac{1}{2}\min_{j\in[t]}i\left(G^{(j)}\right)\geq\frac{1}{2}t^{-t^{\frac{1}{4}}}.$

Let $E^{\prime}\coloneqq E(A^{\prime},(A^{\prime})^{C}).$ We thus have that

$\displaystyle|E^{\prime}|=e(A^{\prime},(A^{\prime})^{C})\geq\frac{|W|}{t}\cdot\frac{1}{2}t^{-t^{\frac{1}{4}}}=\frac{|W|}{2}t^{-t^{\frac{1}{4}}-1}=\Omega\left(\exp\left(-t^{\frac{1}{4}}\log
t\right)|G|\right).$ (9)

Recall that whp $|V(G)\setminus V_{1}|\leq
4\exp\left(-\frac{d}{\log^{2}d}\right)|G|$ and $|V(G)\setminus(A^{\prime}\cup
B^{\prime})|\leq\exp\left(-d^{\frac{3}{2}}\right)|G|$, and so whp

$|V(G)\setminus\left(V_{1}\cap\left(A^{\prime}\cup
B^{\prime}\right)\right)|\leq 5\exp\left(-\frac{d}{\log^{2}d}\right)|G|.$

Therefore, whp the number of edges in $E^{\prime}$ which do not meet
$B^{\prime}$ is at most

$\displaystyle 2\Delta(G)\cdot 5\exp\left(-\frac{d}{\log^{2}d}\right)|G|\leq
10Ct\exp\left(-\frac{d}{\log^{2}d}\right)|G|=o(|E^{\prime}|).$

Hence, whp at least $\frac{|E^{\prime}|}{2}$ of the edges in $E^{\prime}$ have
their end-vertices in $B^{\prime}$.

Since each vertex in $A^{\prime}$ is at distance at most $2$ from $A$, and
similarly every vertex in $B^{\prime}$ is at distance at most $2$ from $B$, we
can extend these edges to a family of $\frac{|E^{\prime}|}{2}$ paths of length
at most $5$ between $A$ and $B$. Since every edge participates in at most
$5\Delta(G)^{4}$ paths of length $5$, we can greedily thin this family to a
set of

$\frac{|E^{\prime}|}{50\Delta(G)^{4}}\geq{|W|}{t^{-t^{\frac{1}{4}}-6}}$

edge-disjoint paths of length at most $5$, where the inequality follows from
(9) and the fact that $\Delta(G)\leq Ct$.

We can thus apply Lemma 4.3, with
$H=G_{p_{1}},c=\frac{1}{t},X=W,p=p_{2},k=d^{d^{\frac{3}{10}}},r=t^{t^{\frac{1}{4}}+6}$,
and $m=5$. Indeed, by our assumptions on $G_{p_{1}}$, we have that whp both
conditions in Lemma 4.3 hold, and

$\displaystyle rp^{-m}$ $\displaystyle=t^{t^{\frac{1}{4}}+6}p_{2}^{-5}\leq
t^{t^{\frac{1}{4}}+6}\left(d\log
d\right)^{5}=o\left(d^{d^{\frac{3}{10}}}\right)=o(k).$

Hence, whp $G_{p}$ contains a component $L_{1}$ with at least
$\left(1-\frac{1}{t}\right)|W|=(y(\epsilon)-o(1))|G|$ vertices from $W$.

As for the remaining components, observe that by (2) we can couple the first
$\sqrt{d}$ steps of a BFS exploration process in $G_{p}$ starting from $v\in
V_{1}$ from above by a Galton-Watson branching process with offspring
distribution $Bin\left(\left(1+\frac{1}{\log d}\right)d+C\sqrt{d},p\right)$.
Then, by standard results on Galton-Watson trees (see, for example, [10,
Theorem 4.3.12]), we have that

$\displaystyle\forall v\in
V_{1}\colon\mathbb{P}\left[|C_{v}(G_{p})|\geq\sqrt{d}\right]\leq
y(\epsilon)+o(1).$ (10)

Let $W^{\prime}$ be the set of vertices of $V_{1}$ which lie in components of
order larger than $\sqrt{d}$ in $G_{p}$, noting that $W\subseteq W^{\prime}$.

Then, by (10),
$\mathbb{E}|W^{\prime}|\leq\left(y(\epsilon)+o(1)\right)|V_{1}|$. Furthermore,
by (8),
$\mathbb{E}(|W^{\prime}|)\geq\mathbb{E}(|W|)\geq\left(y(\epsilon)-o(1)\right)|V_{1}|$,
and so $\mathbb{E}|W^{\prime}|=\left(y(\epsilon)+o(1)\right)|V_{1}|$. Hence,
by a similar argument as before, by Lemma 2.2 we have that whp
$|W^{\prime}|=(y(\epsilon)+o(1))|V_{1}|$.

In particular, every component of $G_{p}$ apart from $L_{1}$ either meets
$V_{1}\setminus W^{\prime}$, and so has order at most $\sqrt{d}=o(|G|)$, or is
contained in $(V(G)\setminus V_{1})\cup(W^{\prime}\setminus L_{1})$, and so
has order at most

$|V(G)\setminus V_{1}|+|W^{\prime}\setminus L_{1}|=o(|G|),$

as required. ∎

###  4.2 Proof of Theorem 3

Throughout the section, we let $G$ be the $t$-fold Cartesian product of the
star $S(1,s)$ with $s$ leaves. Observe that the vertex degrees in $G$ are not
very well-distributed, in the following sense: whilst it is easy to see that
the average degree $d\coloneqq d(G)=\frac{2st}{s+1}\approx 2t$ for large
enough $s$, the number of vertices $v$ such that
$d_{G}(v)\geq\frac{1+\epsilon}{p}$ is polynomially large in $|G|$ for any
choice of $\frac{1}{3t}<p\leq\frac{1-\epsilon}{d}$, and is in fact of order
$|G|^{1-o_{s}(1)}$. In particular, for such values of $p$, even though we are
in the subcritical regime, for many of the vertices the percolated graph
$G_{p}$ looks locally supercritical. We note that in order to make the
calculations and explanations cleaner and more transparent, we will in fact
restrict our attention to a smaller set of vertices, whose degree in $G$ is
much larger than $(1+\epsilon)3t$. To give some intuition to our statements
and proof, observe that as with the hypercube $Q^{t}$, we can think of
$G=\left(S(1,s)\right)^{t}$ as consisting of a number of _layers_ ,
$M_{0},M_{1},\ldots,M_{t}$, where the $z$-th layer, $M_{z}$, consists of the
set of vertices in $G$ such that exactly $z$ of their coordinates are centres
of stars, and so their other $t-z$ coordinates are leaves (indeed, comparing
to the $t$-dimensional hypercube, one can have the $z$-th layer there as the
layer with $z$ coordinates being one and the other $t-z$ coordinates being
zero). It is easy to see then that the degrees of the vertices in each fixed
layer are the same; explicitly,

$d_{G}(v)=zs+(t-z)\qquad\text{ for all }v\in M_{z},$

and that the edges of $G$ are only between ‘adjacent’ layers, that is, between
$M_{z}$ and $M_{z-1}$, and between $M_{z}$ and $M_{z+1}$. Let $\Gamma_{z}$ be
the induced subgraph of $G$ between the layers $M_{z}$ and $M_{z-1}$. Observe
that this graph is bipartite and biregular, such that any vertex in the $z$-th
layer, $u\in M_{z}$, has degree $d_{\Gamma_{z}}(u)=zs$, and any vertex in the
$(z-1)$-th layer, $v\in M_{z-1}$ has degree $d_{\Gamma_{z}}(v)=t-z+1$.

Whilst these graphs $\Gamma_{z}$ are not product graphs, they are subgraphs of
the product graph $G$, and so many of the tools we developed earlier in the
paper can be adjusted and applied here. In particular, for a fixed subcritical
$p>\frac{1}{3t}$, for large enough $r$, the percolation process around the
vertices in $M_{z}$ looks locally supercritical. In fact, this phenomenon is
so pronounced, that even if we restrict ourselves to the subgraph $\Gamma_{z}$
in which the degrees of the vertices in $M_{z-1}$ are _much_ smaller than in
$G$, we still expect the percolation clusters around the vertices in $M_{z}$
to grow quite large, and in particular to contain _many_ vertices in $M_{z}$.

Explicitly, taking $z$ to be, say, $z=\frac{t}{\sqrt{s}}$, we can see that the
number of vertices in $M_{z}$ that are at distance two in $\Gamma_{z}$ from a
fixed vertex $v\in M_{z}$ is at least

$\frac{st}{\sqrt{s}}\left(1-\frac{1}{\sqrt{s}}\right)t=\left(1-o_{s}(1)\right)\sqrt{s}t^{2},$

and so, naively, if we look in the second neighbourhood of $v$ in
$(\Gamma_{z})_{p}$, we expect to find
$\Theta\left(p^{2}\sqrt{s}t^{2}\right)=\Omega(\sqrt{s})>1$ vertices in
$M_{z}$, for large enough $s$. Hence, we expect the early stages of a ‘two-
step’ exploration process in $(\Gamma_{z})_{p}$, to stochastically dominate a
supercritical branching process, and so to grow to a large size, say
$\sqrt{t}$, with probability bounded away from zero.

Then, using the fact that $\Gamma_{z}$ is contained in a product graph $G$, we
can refine the proof of Lemma 4.1 and use projections in order to apply this
argument inductively to build a large connected set, of polynomial size in
$t$, which contains many vertices in $M_{z}$.

Let us now formalise the above heuristics.

######  Lemma 4.4.

Let $s$ be a large enough integer, let $\epsilon,\delta>0$ be sufficiently
small constants, and let $k$ be an integer. Let $\frac{1-\epsilon}{3t}\leq
p\leq\frac{1}{t}$. Let $z$ be such that $\frac{1+\delta}{10\sqrt{s}p}\leq
z\leq\frac{t}{\sqrt{s}}$. Let $M_{z}$ be the set of vertices with $z$ centre
coordinates in $G$, and let $v\in M_{z}$. Then, there exist positive constants
$c_{1}=c(z,k,\epsilon,\delta)$ and $c_{2}=(z,k,\epsilon,\delta)$ such that
with probability at least $c_{1}$, there is a set of vertices $W$ such that
$v\in W$, $W$ is connected in $G_{p}$ and $|W\cap M_{z}|\geq
c_{2}t^{\frac{k}{6}}$.

Before proving the lemma, let us note that $p=\frac{1}{3t}$ and
$z=\frac{t}{\sqrt{s}}$, for $s$ large enough, satisfy the requirements of the
lemma.

###### Proof of Lemma 4.4.

Throughout the proof, we will use ideas similar to those of Lemma 4.1, while
refining them to our particular setting. Let $M_{z-1}$ be the set of vertices
with $z-1$ centre coordinates in $G$. Let $\Gamma\coloneqq\Gamma_{z}$ be the
bipartite biregular induced subgraph of $G$ between the layers $M_{z}$ and
$M_{z-1}$. Throughout the proof, we will in fact consider the percolated graph
$\Gamma_{p}\subseteq G_{p}$.

We prove by induction on $k$, over all relevant values of $z$, $\epsilon$ and
$\delta$.

For $k=1$, let us first describe the following variant of the BFS algorithm.
Here, we maintain the following sets of vertices:

  * •

$Q$, the vertices are currently exploring, kept in a queue;

  * •

$S_{1}\cup S_{2}$, the vertices already processed in the exploration process;

  * •

$T_{1}\cup T_{2}$, the unvisited vertices.

We begin with $Q=\\{v\\}$, $S_{1},S_{2}=\emptyset$ and
$T_{1}=M_{z}\setminus\\{v\\}$, $T_{2}=M_{z-1}$. At each iteration, we proceed
as follows. We consider the first vertex $u\in Q$, and explore its
neighbourhood in $T_{2}$ in $G_{p}$, that is, $N_{G_{p}}(u,T_{2})$. For each
vertex $x\in N_{G_{p}}(u,T_{2})$ in turn, we do the following:

  * -

We move $x$ to $S_{2}$;

  * -

We expose the neighbours of $x$ in $T_{1}$ in $G_{p}$, that is,
$N_{G_{p}}(x,T_{1})$;

  * -

We move the vertices $y\in N_{G_{p}}(x,T_{1})$ from $T_{1}$ to $Q$ one by one.

Finally, after exploring all relevant vertices $x\in N_{G_{p}}(u,T_{2})$, we
move $u$ from $Q$ to $S_{1}$. See Figure 2 for an illustration. Note that, by
taking an edge from the vertex $u$ to each vertex $x\in N_{G_{p}}(u,T_{2})$
and an edge from each vertex $x\in N_{G_{p}}(u,T_{2})$ to each vertex $y\in
N_{G_{p}}(x,T_{1})$ discovered in this way, we can think of this process as
building a tree $B_{1}\subseteq G_{p}$ which spans $S_{1}\cup S_{2}\cup Q$ at
each stage of the process.

Figure 2: The vertex $u\in Q$ and its exposed neighbourhood in $T_{2}$, and a
vertex $x\in T_{2}$ and its exposed neighbourhood in $T_{1}$. Note that in the
course of the exploration process, all the vertices in $N_{G_{p}}(x,T_{2})$
move from $T_{1}$ to $Q$, the vertex $x$ (and, subsequently, all the vertices
from $N_{G_{p}}(u,T_{2})$) move to $S_{2}$, and, finally, the vertex $u$ moves
to $S_{1}$.

We run the algorithm until either $Q$ is empty, or $|S_{1}\cup S_{2}\cup
Q|=\sqrt{t}$. Let us first note that at all times, $Q\cup S_{1}\cup
T_{1}\subseteq M_{z}$, and $S_{2}\cup T_{2}\subseteq M_{z-1}$.

Observe that, since at all times $|S_{1}\cup S_{2}\cup Q|\leq\sqrt{t}$, we
have that for every $u\in Q$, $d(u,T_{2})\geq zs-\sqrt{t}\geq\frac{zs}{2}$
(since $z\geq\frac{1+\delta}{10\sqrt{s}p}\geq\frac{(1+\delta)t}{10\sqrt{s}}$),
and for every $w\in T_{2}$, $d(w,T_{1})\geq t-z+1-\sqrt{t}\geq\frac{2t}{3}$
(since $z\leq\frac{t}{\sqrt{s}}$ and $s$ is large enough). We can thus couple
the tree $B_{1}$ constructed in our truncated algorithm with a Galton-Watson
tree $B_{2}$ rooted at $v$, such that for all $i$, the offspring distribution
at the $2i$-th generation (where we start at generation $0$, with $v$) is
$Bin\left(\frac{zs}{2},p\right)$, and at the $(2i+1)$-th generation is
$Bin\left(\frac{2t}{3},p\right)$, such that $B_{2}$ is isomorphic to a
subgraph of $B_{1}$ as long as $|B_{1}|\leq\sqrt{t}$.

Let us denote by $Z_{i}$ be the number of vertices at depth $i$ in $B_{2}$
(where $Z_{0}=1$, and the vertex in the $0$-th depth is $v$). We then have by
the above and by Lemma 2.1 that, for large enough $s$,

$\displaystyle\mathbb{P}\left[Z_{2(i+1)}\leq\frac{zs^{\frac{2}{3}}x}{10t}\mid
Z_{2i}=x\right]$
$\displaystyle\leq\mathbb{P}\left[Z_{2i+1}\leq\frac{zs^{\frac{2}{3}}x}{t}\mid
Z_{2i}=x\right]+\mathbb{P}\left[Z_{2(i+1)}\leq\frac{zs^{\frac{2}{3}}x}{10t}\mid
Z_{2i+1}\geq\frac{zs^{\frac{2}{3}}x}{t}\right]$
$\displaystyle\leq\mathbb{P}\left[Bin\left(\frac{zsx}{2},p\right)\leq\frac{zs^{\frac{2}{3}}x}{t}\right]+\mathbb{P}\left[Bin\left(\frac{2zs^{\frac{2}{3}}x}{3},p\right)\leq\frac{zs^{\frac{2}{3}}x}{10t}\right]$
$\displaystyle\leq\exp\left(-2x\right)+\exp\left(-\frac{3x}{16}\right)\leq\exp\left(-\frac{x}{100}\right),$

where the penultimate inequality follows since $p\geq\frac{1-\epsilon}{3t}$
and $zsp\geq\frac{(1+\delta)\sqrt{s}}{10}$. Hence, we obtain:

$\displaystyle\mathbb{P}\left[\exists i\text{ such that
}Z_{2i}\leq\left(\frac{zs^{\frac{2}{3}}}{10t}\right)^{i}\right]$
$\displaystyle\leq\sum_{i=1}^{\infty}\mathbb{P}\left[Z_{2i}\leq\left(\frac{zs^{\frac{2}{3}}}{10t}\right)^{i}\mid
Z_{2(2i-1)}\geq\left(\frac{zs^{\frac{2}{3}}}{10t}\right)^{i-1}\right]$
$\displaystyle\leq\sum_{i=1}^{\infty}\exp\left(-\frac{1}{100}\cdot\left(\frac{zs^{\frac{2}{3}}}{10t}\right)^{i}\right)\leq\exp\left(-\frac{1}{200}\right),$

where the last inequality follows since $p\leq\frac{1}{t}$, and
$z\geq\frac{(1+\delta)}{10\sqrt{s}p}\geq\frac{(1+\delta)t}{10\sqrt{s}}$, and
we take $s$ to be large enough. In particular,
$\frac{zs^{\frac{2}{3}}}{10t}>1$, and hence the Galton-Watson tree grows to
infinity with probability at least $\exp\left(-\frac{1}{200}\right)$, and
therefore with probability at least $\exp\left(-\frac{1}{200}\right)$ we have
that $|B_{2}|=\sqrt{t}$ and hence $|S_{1}\cup S_{2}\cup Q|=\sqrt{t}$ at some
point. We thus have that with the same probability, we have a connected set
$W$ such that $v\in W$, $W$ is connected in $G_{p}$, and $|W|=\sqrt{t}$. Let
us argue further that, in fact, $|W\cap\left(S_{1}\cup
Q\right)|\geq\frac{\sqrt{t}}{22}$. Consider any vertex $w\in S_{2}$.
Crucially, observe that by the construction of the exploration process, unless
$w$ is the last vertex we have moved such that now $|B_{1}|=\sqrt{t}$, after
we move $w$ from $T_{2}$ to $S_{2}$ we expose the neighbourhood of $w$ in
$T_{1}$ (see Figure 2). If $|N_{G_{p}}(w,T_{1})|\geq 1$, then we added at
least one child of $w$ to $B_{1}$. The probability that
$|N_{G_{p}}(w,T_{1})|=0$ is at most

$\displaystyle(1-p)^{\frac{2t}{3}-\sqrt{t}}\leq\left(1-\frac{1-\epsilon}{3t}\right)^{\frac{t}{2}}\leq\exp\left(-\frac{1-\epsilon}{6}\right)\leq\frac{9}{10}.$

Hence the number of $w\in S_{2}$ which does not have at least one child,
stochastically dominates $1+Bin\left(\sqrt{t},\frac{9}{10}\right)$ (where we
use the fact that $|B_{1}|\leq\sqrt{t}$ and our stochastic domination on the
number of neighbours). Hence, by Lemma 2.2, the number of vertices $w\in
T_{2}$ which do not have at least one child in $T_{1}$ in $B_{1}$ (that
afterwards moves to $Q_{1}$ and perhaps subsequently to $S_{1}$) is whp at
most $\frac{10\sqrt{t}}{11}$. Therefore, there are at most
$\frac{10\sqrt{t}}{11}$ vertices in $S_{2}$ which do not have a child in
$B_{1}$. Since $B_{1}$ is a tree, these children are distinct for distinct
$w$, and they all lie in $S_{1}$ or $Q$. It follows that whp $|S_{1}\cup
Q|\geq|S_{2}|-\frac{10\sqrt{t}}{11}$, and hence with probability at least
$c>0$, we have that $|S_{1}\cup Q|\geq\frac{\sqrt{t}}{22}$, and hence $|W\cap
M_{z}|\geq\frac{\sqrt{t}}{22}$, completing the case of $k=1$.

We proceed in a manner somewhat similar to the proof of Lemma 4.1. Let $k\geq
2$ and assume the statement holds with
$c_{1}(z^{\prime},k-1,\epsilon^{\prime},\delta^{\prime})$ and
$c_{2}(z^{\prime},k-1,\epsilon^{\prime},\delta^{\prime})$ for all relevant
values of $z^{\prime}$, $\epsilon^{\prime}$ and $\delta^{\prime}$. We argue
via a two-stage exposure, with $p_{2}=\frac{1}{t\log t}$ and
$p_{1}=\frac{p-p_{2}}{1-p_{2}}$ so that $(1-p_{1})(1-p_{2})=1-p$. Note that
$G_{p}$ has the same distribution as $G_{p_{1}}\cup G_{p_{2}}$, and that
$p_{1}\geq(1-o_{t}(1))p\geq\frac{1-\epsilon_{1}}{3t}$ for some
$\epsilon_{1}>0$ constant. Similarly,
$z\geq\frac{1+\delta}{10\sqrt{s}p}\geq\frac{1+\delta_{1}}{10\sqrt{s}p_{1}}$,
and we can thus begin in the same manner as $k=1$, and find with probability
at least $c>0$, a set $W_{0}$ such that $v\in W_{0}$, $W_{0}$ is connected in
$G_{p}$, $|W_{0}|=\sqrt{t}$ and $|W_{0}\cap M_{z}|\geq\frac{\sqrt{t}}{22}$. We
further note that $W_{0}\subseteq V(\Gamma)$. We proceed under the assumption
that indeed $|W_{0}|=\sqrt{t}$. Let us enumerate the vertices in $W_{0}\cap
M_{z}$ as $\left\\{v_{1},\ldots,v_{\ell}\right\\}$, where
$\ell\geq\frac{\sqrt{t}}{22}$ and $\ell\leq\sqrt{t}$ (since
$|W_{0}|=\sqrt{t}$).

Using Lemma 2.4, we can find pairwise disjoint projections
$H_{1},\ldots,H_{\ell}$ of $G$, each having dimension at least $t-\sqrt{t}$,
such that each $v_{i}\in W_{0}$ is in exactly one of $H_{i}$’s.

We now intend to find pairwise disjoint projection of $G$, each with a vertex
in $M_{z}$, to which we can apply our induction hypothesis. Note that, in an
arbitrary projection $H^{\prime}$ of $G$ with dimension $t^{\prime}$, the set
$M_{z}\cap V(H^{\prime})$ will still be a layer of $H^{\prime}$. However, for
the vertices in this layer, the number of ‘active’ coordinates in $H^{\prime}$
which are centres of stars will be some number between $z$ and
$z-(t-t^{\prime})$. Our approach here is then almost identical to that of the
proof of Lemma 4.1, with the slight difference that we want our vertices to be
in $M_{z}$, and have $z^{\prime}$ centre coordinates inside the projected
subgraph, for some $z^{\prime}$ such that
$z^{\prime}\geq\frac{1+\delta^{\prime}}{10\sqrt{s}p_{1}}$ for some
$\delta^{\prime}>0$.

In order to obtain that, we begin by exposing some carefully chosen sets of
edges with probability $p_{2}$. Observe that for each $v_{i}\in W_{0}\cap
M_{z}$, we have that

$|N_{H_{i}\cap\Gamma}(v_{i})|\geq|N_{\Gamma}(v_{i})|-s\cdot\sqrt{t}\geq\frac{zs}{3},$

where the first inequality follows since the dimension of $H_{i}$ is at least
$t-\sqrt{t}$ and the maximum degree of the base graphs is $s$. We further note
that $N_{H_{i}\cap\Gamma}(v_{i})\subseteq M_{z-1}$. Let

$W_{1}=\bigcup_{i\in\left[\sqrt{\ell}\right]}N_{H_{i}\cap\Gamma}(v_{i})\subseteq
M_{z-1}.$

Then, recalling that the $H_{i}$’s are pairwise disjoint, we have that

$\displaystyle|W_{1}|\geq\frac{\sqrt{t}}{25}\cdot\frac{zs}{3}\geq\frac{\sqrt{t}(1+\delta)\sqrt{s}}{750p}\geq
t^{\frac{3}{2}},$

where we used our assumption that $z\geq\frac{1+\delta}{10\sqrt{s}p}$ and that
$s$ is large enough.

We now expose the edges between $W_{0}$ and $W_{1}$ in $G_{p_{2}}$. Let us
denote the set of vertices in $W_{1}$ that are connected with $W_{0}$ in
$G_{p_{2}}$ by $W_{1}^{\prime}$. Then, $|W_{1}^{\prime}|$ stochastically
dominates $Bin\left(t^{\frac{3}{2}},p_{2}\right)$. Thus, by Lemma 2.1, we have
that whp $|W_{1}^{\prime}|\geq\frac{\sqrt{t}}{10\log t}$. We assume in what
follows that this property holds.

We now expose the edges in $G_{p_{2}}$ between $W_{1}^{\prime}$ and
$M_{z}\setminus W_{0}$, recalling that by our assumption $|W_{0}|=\sqrt{t}$.
Note that for every $w_{i}\in W_{1}^{\prime}$, we have that

$|N_{H_{i}\cap\Gamma}(w_{i})\cap(M_{z}\setminus
W_{0})|\geq|N_{\Gamma}(w_{1})|-2s\cdot\sqrt{t}\geq\frac{t}{3},$

and $N_{H_{i}\cap\Gamma}(w_{i})\cap(M_{z}\setminus W_{0})\subseteq M_{z}$. Let

$W_{2}=\bigcup_{i\in\left[\ell\right]}N_{H_{i}\cap\Gamma}(w_{i})\cap(M_{z}\setminus
W_{0})\subseteq M_{z},$

where we note that by the projection Lemma (lemma 2.4) and our construction,
these neighbourhoods are disjoint. Then whp
$|W_{2}|\geq\frac{t}{3}\cdot\frac{\sqrt{t}}{10\log t}.$

Let $W_{2}^{\prime}\subseteq M_{z}$ be the set of vertices in $W_{2}$ that are
connected with $W_{1}^{\prime}$ in $G_{p_{2}}$. Then, $|W_{2}^{\prime}|$
stochastically dominates $Bin\left(\frac{t^{\frac{3}{2}}}{10\log
t},p_{2}\right).$ Thus, by Lemma 2.1, we have that whp
$|W_{2}^{\prime}|\geq\frac{\sqrt{t}}{20\log^{2}t}$ and
$|W_{2}^{\prime}|\leq\sqrt{t}$. We assume henceforth that these two properties
hold.

The subsequent part of the proof is almost identical to that of the proof of
Lemma 4.1, where here we only need to run the inductive step constantly many
times (as opposed to $\omega(1)$ times), allowing us to analyse it in a more
straightforward manner.

Indeed, let $W_{2,i}^{\prime}=W_{2}^{\prime}\cap V(H_{i})\subseteq M_{z}$. We
thus have now our set of vertices in $M_{z}$. Now, for each $i$, we apply once
again Lemma 2.4 to find a family of
$|W_{2,i}^{\prime}|\coloneqq\ell_{i}\leq\sqrt{t}$ pairwise disjoint
projections of $H_{i}$, which we denote by $H_{i,1},\ldots,H_{i,\ell_{i}}$,
such that every vertex of $W_{2,i}^{\prime}\subseteq M_{z}$ is in exactly one
of the $H_{i,j}$, and each of the $H_{i,j}$ is of dimension at least
$t-2\sqrt{t}$. We have that for all $i,j$, the number of centre coordinates of
$v_{i,j}$ in $H_{i,j}$, denote it by $z_{i,j}$, is at least $z-2s\sqrt{t}$.
Recall that $p_{1}\geq\frac{1-\epsilon_{1}}{3t}$, and note that

$\displaystyle z_{i,j}\geq
z-2s\sqrt{t}\geq\frac{1+\delta}{10\sqrt{s}p}-2s\sqrt{t}\geq\frac{1+\delta_{2}}{10\sqrt{s}p}\geq\frac{1+\delta_{3}}{10\sqrt{s}p_{1}}$

for some $\delta_{2},\delta_{3}>0$, where we used $p\leq\frac{1}{t}$ and
$p_{1}=(1-o(1))p$. Altogether, the $v_{i,j}$ (that is, their corresponding
$z_{i,j}$) together with $p_{1}$ satisfy the conditions of the induction
hypothesis for some $\epsilon_{i,j},\delta_{i,j}>0$.

As in the proof of Lemma 4.1, note that when we ran the algorithm on
$G_{p_{1}}$, we did not query any of the edges inside any of the $H_{i,j}$. By
the above inequality we can apply the induction hypothesis to $v_{i,j}$ in
$G_{p_{1}}\cap H_{i,j}$ and conclude that with probability at least
$c_{1}(z_{i,j},k-1,\epsilon_{i,j},\delta_{i,j})$, there exists a connected set
$W_{i,j}$ such that $v_{i,j}$ is $W_{i,j}$, $|W_{i,j}\cap M_{z}|\geq
c_{2}(z_{i,j},k-1,\epsilon_{i,j},\delta_{i,j})t^{\frac{k-1}{6}}$. Let
$c^{\prime}_{1}=\min_{i,j}c_{1}(z_{i,j},k-1,\epsilon_{i,j},\delta_{i,j})$ and
$c^{\prime}_{2}=\min_{i,j}c_{2}(z_{i,j},k-1,\epsilon_{i,j},\delta_{i,j})$.
Noting that the above described events are independent for every $H_{i,j}$, we
obtain by Lemma 2.1 that whp, at least
$\frac{c^{\prime}_{1}\sqrt{t}}{40\log^{2}t}$ of the $H_{i,j}$ have that
$|W_{i,j}\cap M_{z}|\geq c^{\prime}_{2}t^{\frac{k-1}{6}}$. Thus, with
probability at least $c^{\prime}_{1}+o(1)\coloneqq c_{1}$, we have found a
connected set $W$ such that $v$ is in $W$, and there is some $c_{2}>0$ such
that

$\displaystyle|W\cap M_{z}|\geq\frac{c_{1}^{\prime}\sqrt{t}}{40\log^{2}t}\cdot
c^{\prime}_{2}t^{\frac{k-1}{6}}>c_{2}t^{\frac{k}{6}},$

completing the induction step. ∎

We now turn to show that whp many of the vertices with
$z\coloneqq\frac{t}{\sqrt{s}}$ centre coordinates are contained in big
connected sets in $G_{p}$.

######  Lemma 4.5.

Let $s$ be a large enough integer. Let $p\geq\frac{1}{3t}$ and let $k>0$ be an
integer. Let $z\coloneqq\frac{t}{\sqrt{s}}$. Let $M_{z}$ be the set of
vertices with $z$ centre coordinates in $G$ and let $W\subseteq M_{z}$ be the
set of vertices in $M_{z}$ that belong to components with at least $t^{k}$
vertices in $M_{z}$ in $G_{p}$. Then, there exists a constant $\rho>0$ such
that whp,

$\displaystyle|W|\geq\rho|M_{z}|\geq|G|^{1-s^{-\frac{1}{5}}}.$

###### Proof.

Observe that in order to choose a vertex in $M_{z}$ we have $\binom{t}{z}$
choices for the $z$-set of coordinates which are the centre of a star, and
then we have $s^{t-z}$ choices for the leaf coordinates. It follows that

$\displaystyle|M_{z}|=\binom{t}{z}s^{t-z}\geq\left(\sqrt{s}\right)^{\frac{t}{\sqrt{s}}}s^{\left(1-\frac{1}{\sqrt{s}}\right)t}\geq(s+1)^{\left(1-s^{-\frac{1}{3}}\right)t}=|G|^{1-s^{-\frac{1}{3}}},$

where the penultimate inequality holds for any $s$ large enough.

By Lemma 4.4, there is some constant $c^{\prime}>0$ such that every $v\in
M_{z}$ belongs to a connected set of order $t^{k}$ with probability at least
$c^{\prime}>0$. We thus have that

$\mathbb{E}[|W|]\geq c^{\prime}|M_{z}|\geq
c^{\prime}|G|^{1-s^{-\frac{1}{3}}}.$

Consider the edge-exposure martingale on $G_{p}$. It has length
$|E(G)|=\frac{st}{s+1}|G|\leq 2t|G|$, and the addition or deletion of an edge
can change the value of $|W|$ by at most $2t^{k}$. Therefore, by Lemma 2.2, we
have for sufficiently $\rho=\frac{c^{\prime}}{2}>0$ that

$\displaystyle\mathbb{P}\left[|W|\leq\rho|M_{z}|\right]$
$\displaystyle\leq\mathbb{P}\left[|W|\leq\frac{\mathbb{E}|W|}{2}\right]\leq
2\exp\left(-\frac{|G|^{2-2s^{-\frac{1}{3}}}}{16|G|t^{2k+1}}\right)\leq
2\exp\left(-|G|^{1-s^{-\frac{1}{4}}}\right)=o(1),$

as long as $s$ is large enough. It follows that whp

$|W|\geq\rho|M_{z}|\geq\frac{c^{\prime}}{2}|G|^{1-s^{-\frac{1}{4}}}\geq|G|^{1-s^{-\frac{1}{5}}}.$

∎

We note that while $M_{z}$, where $z=\frac{t}{\sqrt{s}}$, takes a polynomial
fraction of the vertices, this set of vertices still only amounts to $o(|G|)$.
Thus, we cannot use global isoperimetric properties of $G$ to find typically
sufficiently many short paths between relevant (respecting) partitions of
$M_{z}$, as we do in the proof of Theorem 2. Instead, we need to look at local
isoperimetric properties of $M_{z}$, such as the isoperimetric property of its
two-neighbourhood in $G$, in order to show that whp many of the large
connected sets in $G_{p}\cap M_{z}$ in fact belong to the same connected
component in $G_{p}$.

###### Proof of Theorem 3.

Assume that all the conditions in Theorem 3 hold.

Once again, we argue via a two-round exposure. Let $\epsilon$ be a small
enough constant, such that $p_{2}=\frac{\epsilon}{3t}$, $p_{1}=\frac{1}{3t}$
and $(1-p_{1})(1-p_{2})=1-p$, noting that $G_{p_{1}}\cup G_{p_{2}}$ has the
same distribution as $G_{p}$.

Let $z\coloneqq\frac{t}{\sqrt{s}}$. Let $M_{z}$ be the set of vertices with
$z$ centre coordinates in $G$, and let $W\subseteq M_{z}$ be the set of
vertices in $M_{z}$ belonging to a component with at least $t^{15}$ vertices
in $M_{z}$ in $G_{p_{1}}$. Then, by Lemma 4.5 with $k=15$, we have that there
exists a constant $\rho>0$ such that whp,

$\displaystyle|W|\geq\rho|M_{z}|\geq|G|^{1-s^{-\frac{1}{5}}}.$ (11)

We note further that, since the average degree $t=\Theta(\log|G|)$, by a
similar argument as in Lemma 4.2 applied to the vertices with $z$ centre
coordinates in $G$, we claim that whp

every vertex in $M_{z}$ is at distance at most 2 from $W$. (12)

To see why, observe that given a vertex $v\in M_{z}$, we can form
$t^{\frac{4}{3}}$ pairwise disjoint projections of $G$, each isomorphic to the
product of $(1-o(1))t$ copies of $S(1,s)$ and each containing a vertex with
$z$ centre coordinates at distance $2$ from $v$. Indeed, since the number $z$
of coordinates of $v$ which are the centre of star satisfies
$t^{\frac{2}{3}}\leq z\leq t-t^{\frac{2}{3}}$, we can assume without loss of
generality that the first $t^{\frac{2}{3}}$ coordinates of $v$ are the centres
of stars, and the second $t^{\frac{2}{3}}$ coordinates are leaves.

Given a pair of coordinates $1\leq i\leq t^{\frac{2}{3}}<j\leq
2t^{\frac{2}{3}}$, let $H_{i,j}$ be the projection of $G$ to the first
$2t^{\frac{2}{3}}$ coordinates where the first $2t^{\frac{2}{3}}$ coordinates
agree with $v$, except that the $i$-th coordinate is some arbitrary leaf and
the $j$-th coordinate is the centre of the star.

Then, the graphs $H_{i,j}$ form a collection of $t^{\frac{4}{3}}$ pairwise
disjoint projections of $G$, each isomorphic to the product of $(1-o(1))t$
copies of $S(1,s)$ and each containing a vertex with $z$ centre coordinates in
$G$ at distance $2$ from $v$.

Since $p$ will still be ‘supercritical’ at these vertices in each $H_{i,j}$,
an argument as in Lemma 4.2 will imply that the expected number of vertices in
$M_{z}$ which are not at distance at most 2 from a vertex in $W$ is at most
$\exp\left(-\Omega\left(t^{\frac{4}{3}}\right)\right)|G|=o(1)$, and so the
claim follows by Markov’s inequality. We assume in the following that claim
(12) holds.

Let $A\cup B$ be a $G_{p_{1}}$-respecting partition of $W$ into two parts, $A$
and $B$, such that $|A|\leq|B|$ and $|A|\geq\frac{|W|}{3}$. Let $A^{\prime}$
be the set of vertices in $A$ together with all vertices in $M_{z}\setminus B$
that are within distance $2$ to $A$, and let $B^{\prime}$ be the set of
vertices in $B$ together with all vertices in $M_{z}\setminus A^{\prime}$ that
are within distance $2$ to $B$, so that $M_{z}=A^{\prime}\cup B^{\prime}$. We
require the following claim, whose proof we defer to the end of this proof:

######  Claim 4.6.

Whp, there are at least $\frac{|W|}{t^{2}}$ paths of length $2$ in $G$ between
$A^{\prime}$ and $B^{\prime}$.

We can extend these paths to a family of $A-B$ paths of length at most $6$
(see Figure 3) and then, very crudely, since $\Delta(G)=st$, we can greedily
thin this family to a set of $\frac{|W|}{36s^{6}t^{8}}$ edge-disjoint $A-B$
paths of length at most $6$.

We can now apply Lemma 4.3 with $H=G_{p_{1}}$, $c=\frac{1}{3}$, $X=W$,
$p=p_{2}=\frac{\epsilon}{3t}=O(t^{-1})$, $k=t^{15}$, $r=36s^{6}t^{8}$ and
$m=6$. Indeed, by our assumptions on $G_{p_{1}}$ and by Lemma 4.4, we have
that whp both conditions in Lemma 4.3 hold, and

$\displaystyle rp^{-m}$
$\displaystyle=36s^{6}t^{8}p_{2}^{-6}=O\left(t^{14}\right)=o\left(t^{15}\right)=o(k).$

As a consequence of Lemma 4.3, we have that whp $G_{p}=G_{p_{1}}\cup
G_{p_{2}}$ contains a component which contains at least $\frac{2}{3}|W|$
vertices of $W$. Combining this with the bound
$|W|\geq|G|^{1-s^{-\frac{1}{5}}}$ from (11), we have that whp the largest
component of $G_{p}$ is of order at least
$\frac{2}{3}|G|^{1-s^{-\frac{1}{5}}}\geq|G|^{1-s^{-\frac{1}{6}}}$. ∎

Figure 3: An extension of a partition $A\cup B$ of $W$ to a partition
$A^{\prime}\cup B^{\prime}$ of $M_{z}$. Each $A^{\prime}-B^{\prime}$ two-path
(solid) can be extended into an $A-B$ six-path (solid and dashed). Note that
some vertices in these paths may lie outside of $M_{z}$.

We finish this section with the proof of the above claim.

###### Proof of Claim 4.6.

Let $z=\frac{t}{\sqrt{s}}$ be the number of coordinates of $v$ which
correspond to a centre of a star. Recall that, by Lemma 4.5, there is a
constant $\rho>0$ such that whp $|W|\geq\rho|M_{z}|$. The following two
constants will be useful throughout the proof:

$\displaystyle\alpha\coloneqq\frac{\rho}{4},\quad\beta\coloneqq\frac{\rho}{3(4-\rho)}.$

Note that
$\beta+(1-\beta)\alpha=\frac{\rho}{3(4-\rho)}+\frac{\rho}{4}\left(1-\frac{\rho}{3(4-\rho)}\right)=\frac{\rho}{3}$.

We are interested in the structure of the graph $G^{2}[M_{z}]$. Suppose that
$v,w\in M_{z}$, and denote by $I,K\in[t]^{z}$ (respectively) the set of
coordinates corresponding to centres of stars. Then $v$ and $w$ are at
distance $2$ in $G$ if either

  1. (T1)

$I=K$ and they disagree on a single coordinate of a leaf outside $I$; or

  2. (T2)

$|I\triangle K|=2$ and they agree on all the (leaf) coordinates outside $I\cup
K$.

Hence, we can see that $G^{2}[M_{z}]$ can be built in the following manner
(see also Figure 4) — we start with the Johnson graph $J\coloneqq J(t,{z})$,
which represents the ${z}$-set of coordinates which are centres of stars, and
we replace each vertex with a copy of $H\coloneqq H(t-{z},s)$, which
represents the set of leaf coordinates. There is a natural map $f:M_{z}\to
V(J)\times V(H)$ which maps a vertex $v\in M_{z}$ to the pair $(I,x)$ where
$I$ is the ${z}$-set of coordinates of $v$ which are centres of stars and $x$
is the restriction of $v$ to the coordinates which are leaves.

The edges of $G^{2}[M_{z}]$ then come in two types. Those of type (T1) give
rise to a copy of $H$ on $I\times V(H)$ for each $I\in V(J)$, whereas those of
type (T2) give rise to a matching between $I\times V(H)$ and $K\times V(H)$
for each $(I,K)\in E(J)$, where a vertex $(I,x)$ is matched to a vertex
$(K,y)$ if and only if $f^{-1}(I,x)$ and $f^{-1}(K,y)$ agree on all
coordinates outside $I\cup J$. Note that this is similar to, but not quite the
same as, the Cartesian product of $J$ and $H$.

We use the partition $M_{z}=A^{\prime}\cup B^{\prime}$ to define a colouring
$\chi:V(J)\to[3]$ in the following manner. We say that a copy of $H$ given by
$I\times V(H)$ is evenly-split if

$\alpha|H|\leq|f^{-1}(I\times V(H))\cap
A^{\prime}|\leq\left(1-\alpha\right)|H|.$

Note that, since $M_{z}=A^{\prime}\cup B^{\prime}$ is a partition, if $I\times
V(H)$ is evenly-split then it also satisfies

$\alpha|H|\leq|f^{-1}\left(I\times V(H)\right)\cap
B^{\prime}|\leq\left(1-\alpha\right)|H|.$

If $I\times V(H)$ is not evenly-split then we say it is either _$A^{\prime}$
-dominated_ or _$B^{\prime}$ -dominated_ if

$|f^{-1}(I\times V(H))\cap A^{\prime}|\geq\left(1-\alpha\right)|H|\qquad\text{
or }\qquad|f^{-1}(I\times V(H))\cap B^{\prime}|\geq\left(1-\alpha\right)|H|,$

respectively. We then let $\chi(I)=1$ if $I\times V(H)$ is
$A^{\prime}$-dominated, $\chi(I)=2$ if $I\times V(H)$ is
$B^{\prime}$-dominated, and $\chi(I)=3$ if $I\times V(H)$ is evenly-split (see
Figure 4).

Let us suppose first that $|\chi^{-1}(3)|\geq\frac{|J|}{\rho t^{2}}$. In this
case, at least $\frac{|J|}{\rho t^{2}}$ of the copies of $H$ are evenly-split.
As mentioned in Section 2.2, since $H(t-{z},s)$ is the product of $t-{z}$
copies of the complete graph $K_{s}$, using (3), we have that

$i(H(t-{z},s))\geq\frac{1}{2}i(K_{s})=\frac{s}{2}.$

In particular, each copy of $H$ which is evenly-split must contain at least
$\frac{\alpha s|H|}{2}$ many edges from $A^{\prime}$ to $B^{\prime}$, and so
it follows that there are at least

$\frac{|J|}{\rho t^{2}}\cdot\frac{\alpha
s|H|}{2}\geq\frac{\rho|M_{z}|}{t^{2}}\geq\frac{|W|}{t^{2}}$

paths of length 2 between $A^{\prime}$ and $B^{\prime}$.

So, let us assume that $|\chi^{-1}(3)|<\frac{|J|}{\rho t^{2}}$, and so the
vast majority of copies of $H$ are either $A^{\prime}$-dominated or
$B^{\prime}$-dominated. Furthermore, since

$|A|\geq\frac{|W|}{3}\geq\frac{\rho|M_{z}|}{3}=\frac{\rho}{3}|J|\cdot|H|,$

it follows that $|\chi^{-1}(1)|,|\chi^{-1}(2)|\leq\left(1-\beta\right)|J|$.
Indeed, if $|\chi^{-1}(1)|>(1-\beta)|J|$, then we would have that

$\displaystyle|B|$
$\displaystyle\leq|B^{\prime}|<\beta|J|\cdot|H|+\left(1-\beta\right)\alpha|J|\cdot|H|$
$\displaystyle=\frac{\rho}{3}|J|\cdot|H|=\frac{\rho|M_{z}|}{3}\leq|A|,$

that is, $|B|<|A|$, contradicting our assumption that $|B|\geq|A|$. Similarly,
if $|\chi^{-1}(2)|>(1-\beta)|J|$, we would have that $|A|<|A|$, a
contradiction.

Hence, we may restrict our attention to the case where
$|\chi^{-1}(1)|,|\chi^{-1}(2)|\leq(1-\beta)|J|$ and
$|\chi^{-1}(3)|<\frac{|J|}{\rho t^{2}}$. Since, by definition,
$|\chi^{-1}(1)|+|\chi^{-1}(2)|+|\chi^{-1}(3)|=|J|$, we have that

$\displaystyle|\chi^{-1}(1)|,|\chi^{-1}(2)|\geq|J|-(1-\beta)|J|-\frac{|J|}{\rho
t^{2}}\geq\frac{\beta}{2}|J|.$

Hence, by Theorem 2.5, there is a constant $c>0$ such that there are
$c\sqrt{\frac{t}{z(t-z)}}\left(1-\frac{\beta}{2}\right)\frac{\beta|J|}{2}\geq\frac{|J|}{t}$
edges of $J$ which go between a vertex with colour $1$ and a vertex with
colour $2$. Each of these edges represents an $A^{\prime}$-dominated copy of
$H$ (which we call the first copy of $H$) which is adjacent in $J$ to a
$B^{\prime}$-dominated copy of $H$ (which we call the second copy of $H$).
Since at most $\alpha|H|$ of the vertices in the first copy are in
$B^{\prime}$ and at most $\alpha|H|$ of the vertices in the second copy are in
$A^{\prime}$, it follows that the number of vertices in the first copy which
are in $A^{\prime}$ and are matched to vertices in $B^{\prime}$ in the second
copy is at least

$(1-2\alpha)|H|=\left(1-\frac{\rho}{2}\right)|H|\geq\frac{|H|}{2},$

since $\rho\leq 1$.

In particular, there are at least

$\displaystyle\frac{|J|}{t}\cdot\frac{|H|}{2}=\frac{|M_{z}|}{2t}\geq\frac{|W|}{2t}$

many edges in $G^{2}[M_{z}]$ between $A^{\prime}$ and $B^{\prime}$ and hence
$\frac{|W|}{2t}\geq\frac{|W|}{t^{2}}$ many paths of length 2 between
$A^{\prime}$ and $B^{\prime}$ in $G$. ∎

Figure 4: A visualisation of the graph $G^{2}[M_{z}]$ in the case $t=4,z=2$
and $s=2$. Here, each circle is a copy of $H(t-z,s)$ and the black tubes
represent the edges of $J(t,z)$. A pair of copies of $H(t-z,s)$ have been
displayed, where the vertices of $M_{z}$ inside each copy have been coloured
according to whether they lie in $A^{\prime}$ (blue) or $B^{\prime}$ (orange).
Inside the black tube corresponding to the edge of $J(t,z)$ between this pair
of vertices there is some matching, represented by the dashed (purple) edges.
Note that this matching may not respect the structure of the $H$ copies in
each circle. Each vertex $I$ of $J(t,z)$ is then coloured according to whether
it is $A^{\prime}$-dominated (blue), $B^{\prime}$-dominated (orange) or evenly
balanced (green), corresponding to $\chi(I)=1,2,$ and $3$, respectively.

We note that, in terms of showing that the Erdős-Rényi component phenomenon
does not hold in irregular product graphs, a simple application of Lemma 4.1
is sufficient. Indeed, if the $G^{(i)}$ are all irregular and of bounded
order, then it is not hard to show that there is some $\epsilon(C)>0$ such
that $G$ must contain a vertex of degree at least $(1+2\epsilon)d$, and hence
by Lemma 4.1 at a subcritical probability $p=\frac{1-\epsilon}{d}$, with
positive probability $G_{p}$ will contain a component of order $d^{k}$ for any
fixed integer $k>0$, and so not all components in $G_{p}$ have linear order
(in $d$) throughout the subcritical regime. However, Theorem 3 shows that in
the particular case of a product of many stars much more is true — in parts of
the subcritical regime whp $G_{p}$ will even contain a component of order
$|G|^{1-o_{s}(1)}$.

##  5 Discussion

In what follows we will use $G$ to refer to the product graph, $t$ for its
dimension, $d$ for its average degree, $\delta$ for its minimum degree and $C$
for the maximum degree of the base graphs. Let us briefly summarise the
results on the typical component structure of percolated product graphs with
probability close to $p=\frac{1}{d}$ which follow from Theorems 1.3 and 1.6,
and Theorems 1, 2 and 3. There are three main assumptions which we work with:

(BO)

The base graphs have bounded order;

(BD)

The base graphs have bounded maximum degree;

(R)

The base graphs are regular.

Note that clearly (BO) implies (BD).

Lichev [19] showed that (BD), together with some mild isoperimetric
assumptions, is sufficient to show the existence of a linear sized component
in the supercritical regime, and to bound the order of the largest component
in the subcritical regime. Whilst this bound on the order of the largest
component in the subcritical regime was only polynomial in the size of the
host graph, we note that Theorem 3 implies that this bound is in fact close to
optimal.

Indeed, whilst Theorem 1.3 implies that when $p=\frac{1-\epsilon}{d}$ whp the
largest component of $G_{p}$ has order at most
$\exp\left(-\frac{\epsilon^{2}t}{9C^{2}}\right)|G|$, by Theorem 3, there is a
choice of $G$ such that whp $G_{p}$ contains a component of order at least
$\exp\left(-\Theta(t)\right)|G|$. In particular, (BD) alone is not sufficient
to show that the percolated subgraph exhibits the Erdős-Rényi component
phenomenon in the subcritical regime (which requires that the largest
component in the subcritical regime is of logarithmic order in $|G|$).

Furthermore, Theorem 2 further strengthens Lichev’s results in [19] by greatly
weakening the isoperimetric assumptions and showing that at least in the
supercritical regime the order of the largest component does behave
quantitatively similar to the Erdős-Rényi random graph. As for the order of
the second-largest component, Theorem 2 implies it is $o(|G|)$.

######  Question 5.1.

Is there an example of a product graph $G$ which satisfies (BD), and some mild
isoperimetric assumptions, for which the second-largest component in the
supercritical regime has polynomial order in $|G|$?

As demonstrated by Theorem 1.6, (BO) and (R) are sufficient to guarantee that
the percolated subgraph exhibits the Erdős-Rényi component phenomenon, and our
work shows that (R) is necessary, in the stronger sense that (BO) together
with the assumption that none of the base graphs are regular imply that the
Erdős-Rényi component phenomenon does not hold. However, it remains an
interesting open question as to whether (BD) and (R), together with some mild
isoperimetric assumptions, are themselves sufficient. For example the
following question is still open.

######  Question 5.2.

Let $C>1$ be a constant, let $\alpha>0$ be a constant and let
$G=\square_{j=1}^{t}G^{(j)}$ be a product graph where $G^{(i)}$ is regular,
$1\leq\left|d\left(G^{(i)}\right)\right|\leq C$ for each $i\in[t]$ and
$i(G)\geq\alpha$. Does the phase transition that $G_{p}$ undergoes around
$p=\frac{1}{d}$ exhibit the Erdős-Rényi component phenomenon?

Note that Theorem 1 shows that at the very least (BD) is necessary to show the
existence of a linear sized component in the supercritical regime, even under
some quite strong isoperimetric constraints. It is perhaps interesting to ask
what the limit of this pathological behaviour is. Indeed, the problem here
seems to be an abundance of vertices of low degree (where the percolation is
locally subcritical), which would suggest that at the very least a probability
significantly larger than $p=\frac{1}{\delta}$ would be sufficient to show the
existence of a linear sized component.

######  Conjecture 5.3.

Let $G$ be a high-dimensional product graph whose isoperimetric constant is
not too small, let $\epsilon>0$ and let $p=\frac{1+\epsilon}{\delta}$. Then
whp $G_{p}$ contains a component of size at least $(y(\epsilon)-o(1))|G|$,
where $y(\epsilon)$ is defined according to (1).

Finally, in the case of $G(d+1,p)$, Theorem 1.1 can be sharpened to show that,
between the subcritical and the supercritical phases, there is a phase when
the largest two components are both of polynomial order $|G|^{\gamma}$ for
some $\gamma\leq\frac{2}{3}$, and then a phase when the largest component has
order $|G|^{\gamma}$ for some $\gamma>\frac{2}{3}$ and the second-largest
component has order at most $|G|^{\frac{2}{3}}$, although this whole
transition happens in a very small window around $\frac{1}{d}$ (see, for
example, [14]).

It would be interesting to know how the component structure of the graph in
Theorem 3 develops as $p$ increases, and in particular at what point typically
a unique giant component emerges, and when a linear sized component emerges.

######  Question 5.4.

Let $s$ be a sufficiently large integer and let $\epsilon>0$ be a sufficiently
small constant, let $G^{(i)}=S(1,s)$ for every $1\leq i\leq t$ and let
$G=\square_{i=1}^{t}G^{(i)}$. Let us write $L_{1}$ and $L_{2}$ for the largest
and second-largest component, respectively, of $G_{p}$.

  * •

For which $p$ is it true that whp $|L_{2}|=o(|L_{1}|)$?

  * •

For which $p$ is it true that whp $|L_{1}|=\Theta(|G|)$?

  * •

Does there exist a probability $p$ and a constant $\gamma>\frac{2}{3}$ such
that whp both $|L_{1}|$ and $|L_{2}|$ have order at least $|G|^{\gamma}$?

Furthermore, as mentioned after the proof of Theorem 3, for any family of
bounded-order irregular base graphs, the percolated product graph will not
exhibit the Erdős-Rényi phenomenon in the subcritical regime, containing a
component of order at least a superlinear polynomial (in $d$) for certain
subcritical values of $p$. However, in the particular case of Theorem 3, we in
fact show that the largest component throughout some part of the sparse
subcritical regime, where $p=\Theta(\frac{1}{d})$, is of polynomial order in
$|G|$. It would be interesting to know if this behaviour is universal in high-
dimensional products of bounded-order irregular graphs.

######  Question 5.5.

For all $i\in[t]$, let $G^{(i)}$ be an irregular connected graph of order at
most $C>0$. Let $G=\square_{i=1}^{t}G^{(i)}$. Let $\epsilon>0$ be a small
enough constant, and let $p=\frac{1-\epsilon}{d}$. Does there exist a
$c(\epsilon,C)$ such that whp the largest component in $G_{p}$ has order at
least $|G|^{c}$?

The table in Figure 5 summarises what is known about the order of the largest
and second-largest component in $G_{p}$ for various values of $p$ and under
various combinations of the assumption (BD), (BO) and (R), and indicates some
combinations of probabilities and assumptions where open questions remain.

| $p=\frac{1-\epsilon}{d}$ | $p=\frac{1+\epsilon}{d}$ | $p=\frac{1+\epsilon}{\delta}$
---|---|---|---
$\emptyset$ | - |  $\exists G$ with $|L_{1}|=o(|G|)$ (Theorem 1) | Conjecture 5.3
(BD) |  $|L_{1}|\leq\exp\left(-\frac{\epsilon^{2}t}{9C^{2}}\right)|G|$ (Theorem 1.3) |  $|L_{1}|=\left(y(\epsilon)+o(1)\right)|G|$ (Theorem 2) | -
|  $\exists G$ with $|L_{1}|\geq\exp\left(-\Theta(t)\right)|G|$ (Theorem 3) |  $|L_{2}|=o(|G|)$ (Theorem 2), Question 5.1 |
(BD) & (R) | Question 5.2 |  $|L_{1}|=\left(y(\epsilon)+o(1)\right)|G|$ (Theorem 2) | -
|  |  $|L_{2}|=o(|G|)$ (Theorem 2), Question 5.2 |
(BO) & (R) |  $|L_{1}|=O(d)$ (Theorem 1.6) |  $|L_{1}|=\left(y(\epsilon)+o(1)\right)|G|$ (Theorem 1.6) | -
|  |  $|L_{2}|=O(d)$ (Theorem 1.6) |
(BO) & $\neg$(R) | Question 5.5 | - | -

Figure 5: A summary of the typical component structure of percolated high-
dimensional product graphs

## References

  * [1] M. Ajtai, J. Komlós, and E. Szemerédi.  Largest random component of a $k$-cube.  Combinatorica, 2(1):1–7, 1982.
  * [2] N. Alon and J. H. Spencer.  The probabilistic method.  Hoboken, NJ: John Wiley & Sons, fourth edition, 2016.
  * [3] B. Bollobás.  Random graphs.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001.
  * [4] B. Bollobás, Y. Kohayakawa, and T. Łuczak.  The evolution of random subgraphs of the cube.  Random Structures Algorithms, 3(1):55–90, 1992.
  * [5] B. Bollobás and O. Riordan.  Percolation. Cambridge University Press, Cambridge, 2006.
  * [6] S. B. Broadbent and J. M. Hammersley.  Percolation processes. I: Crystals and mazes.  Proc. Camb. Philos. Soc., 53:629–641, 1957.
  * [7] D. Christofides, D. Ellis, and P. Keevash.  An approximate vertex-isoperimetric inequality for $r$-sets.  Electron. J. Comb., 20(4):research paper p15, 12, 2013.
  * [8] F. R. K. Chung and P. Tetali.  Isoperimetric inequalities for Cartesian products of graphs.  Combin. Probab. Comput., 7(2):141–148, 1998.
  * [9] S. Diskin, J. Erde, M. Kang, and M. Krivelevich.  Percolation on high-dimensional product graphs.  arXiv:2007.02891, 2022.
  * [10] R. Durrett.  Probability: theory and examples.  Cambridge University Press, Cambridge, 2019.
  * [11] P. Erdős and A.Rényi.  On random graphs. I.  Publ. Math., 6:290–297, 1959.
  * [12] P. Erdős and A. Rényi.  On the evolution of random graphs.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 5:17–61, 1960\.
  * [13] P. Erdős and J. Spencer.  Evolution of the $n$-cube.  Comput. Math. Appl., 5(1):33–39, 1979.
  * [14] A. Frieze and M. Karoński.  Introduction to random graphs.  Cambridge University Press, Cambridge, 2016.
  * [15] G. Grimmett.  Percolation. Berlin: Springer, 1999.
  * [16] M. Heydenreich and R. van der Hofstad.  Progress in high-dimensional percolation and random graphs.  CRM Short Courses. Springer, Cham; Centre de Recherches Mathématiques, Montreal, QC, 2017.
  * [17] S. Janson, T. Łuczak, and A. Ruciński.  Random graphs.  Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, 2000.
  * [18] H. Kesten.  Percolation theory for mathematicians.  Birkhäuser, Boston, MA, 1982.
  * [19] L. Lichev.  The giant component after percolation of product graphs.  J. Graph Theory, 99(4):651–670, 2022.