# Perfect Matching in Product Graphs
and in their Random Subgraphs

Sahar Diskin 111School of Mathematical Sciences, Tel Aviv University, Tel Aviv
6997801, Israel. Email<EMAIL_ADDRESS>Anna Geisler 222Institute
of Discrete Mathematics, Graz University of Technology, Steyrergasse 30, 8010
Graz, Austria. Email<EMAIL_ADDRESS>
###### Abstract

For $t\in\mathbb{N}$ and every $i\in[t]$, let $H_{i}$ be a $d_{i}$-regular
connected graph, with $1<|V(H_{i})|\leq C$ for some integer $C\geq 2$. Let
$G=\square_{i=1}^{t}H_{i}$ be the Cartesian product of $H_{1},\ldots,H_{t}$.
We show that if $t\geq 5C\log_{2}C$ then $G$ contains a (nearly-)perfect
matching.

Then, considering the random graph process on $G$, we generalise the result of
Bollobás on the binary hypercube $Q^{t}$, showing that with high probability,
the hitting times for minimum degree one, connectivity, and the existence of a
(nearly-)perfect matching in the $G$-random-process are the same. We develop
several tools which may be of independent interest in a more general setting
of the typical existence of a perfect matching under percolation.

##  1 Introduction

###  1.1 Background and main results

Given two graphs $H_{1}=(V_{1},E_{1})$ and $H_{2}=(V_{2},E_{2})$, the
Cartesian product $H=H_{1}\square H_{2}$ is the graph whose vertex set is
$V_{1}\times V_{2}$, and for $u_{1},v_{1}\in V_{1}$ and $u_{2},v_{2}\in
V_{2}$, we have that $\\{(u_{1},u_{2}),(v_{1},v_{2})\\}\in E(H)$ either if
$u_{1}=v_{1}$ and $\\{u_{2},v_{2}\\}\in E(H_{2})$ or if $u_{2}=v_{2}$ and
$\\{u_{1},v_{1}\\}\in E(H_{1})$. More generally, given $t$ graphs,
$H_{i},\ldots,H_{t}$, their Cartesian product $G=\square_{i=1}^{t}H_{i}$ is
the graph with the vertex set

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

and the edge set

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

We call $H_{1},H_{2},\ldots,H_{t}$ the base graphs of $G$. Cartesian product
graphs arise naturally in many contexts and have received much attention in
combinatorics, probability, and computer science. Many classical graphs, which
have been extensively studied, are in fact Cartesian product graphs: the
$t$-dimensional torus is the Cartesian product of $t$ copies of the cycle
$C_{k}$, the $t$-dimensional grid is the Cartesian product of $t$ copies of
the path $P_{k}$, and the binary $t$-dimensional hypercube $Q^{t}$ is the
Cartesian product of $t$ copies of a single edge $K_{2}$. We refer the reader
to [16] for a systematic coverage of Cartesian product graphs, and related
product structures on graphs. Throughout the paper, whenever we write product
graphs we consider the Cartesian product as defined above.

In this paper, we study perfect matchings in product graphs. One can convince
oneself that if one of the base graphs has a perfect matching, then the
product graph $G$ has a perfect matching as well. Indeed, Kotzig [19] showed
something even stronger: let $G=\square_{i=1}^{t}H_{i}$ be such that each
$H_{i}$ is regular, then if at least one of the base graphs has a
$1$-factorisation (recall that a $1$-factorisation is a decomposition of the
edges of the graph into disjoint perfect matchings), or at least two base
graphs have perfect matchings, then $G$ has a $1$-factorisation; and
furthermore these sufficient conditions are not necessary. However, when none
of the base graphs have a perfect matching, it is not clear whether their
product graph will have a perfect matching. Indeed, not every connected
regular graph has a perfect matching (or nearly-perfect matching, that is, a
matching covering all but one vertex when the order of the graph is odd).
However, note that given two graphs $H_{1}$ and $H_{2}$, the proportion of
vertices covered by a largest matching is at least as large as this proportion
in any of the base graphs. Thus, taking the product of many graphs, one can
hope to improve this proportion. Indeed, our first result gives a simple
sufficient condition for the existence of a perfect matching in product graphs
in this spirit.

######  Theorem 1.

Let $C>1$ be a constant, and let $t\geq 5C\log_{2}C$ be an integer. For every
$i\in[t]$, let $H_{i}$ be a $d_{i}$-regular connected graph with
$1<|V(H_{i})|\leq C$. Let $G=\square_{i=1}^{t}H_{i}$ and suppose that $|V(G)|$
is even. Then $G$ has a perfect matching.

Observe that since each $H_{i}$ is a $d_{i}$-regular connected graph,
$G=\square_{i=1}^{t}H_{i}$ is a connected $d$-regular graph with
$d=\sum_{i=1}^{t}d_{i}$, and in particular $d=\Theta_{C}(\log|V(G)|)$.
Furthermore, we note that we have not tried to optimise the constants in the
above. Theorem 1 shows that if the dimension of the product graph is
sufficiently large, with respect to the maximum size of the base graphs, then
the product graph has a perfect matching — regardless of whether the base
graphs themselves contain any perfect matchings. Furthermore, from the same
proof it follows that if $G$ has an odd number of vertices, then it has a
nearly-perfect matching.

As mentioned above, a well-studied product graph is the binary hypercube,
$Q^{t}$, in particular in terms of bond percolation on it. Given a graph $G$
and probability $p$, we form the percolated random subgraph $G_{p}\subseteq G$
by including every edge of $G$ independently with probability $p$ (note that
$G(n,p)$ is then $(K_{n})_{p}$). The study of $Q^{t}_{p}$ has been initiated
by Sapoženko [22] and by Burtin [8], who showed that the sharp threshold for
connectivity is $p^{*}=\frac{1}{2}$: when $p<\frac{1}{2}$, whp333With high
probability, that is, with probability tending to one as $t$ tends to
infinity. $Q^{t}_{p}$ is disconnected, whereas for $p>\frac{1}{2}$, whp
$Q^{t}_{p}$ is connected. Erdős and Spencer [14] conjectured that $Q^{t}_{p}$
undergoes a phase transition with respect to its component structure, that is,
the typical emergence of a giant component (a connected component containing a
linear fraction of the vertices) around $p=\frac{1}{t}$, similar to that of
$G(n,p)$ around $p=\frac{1}{n}$. This conjecture was confirmed by Ajtai,
Komlós, and Szemerédi [1], with subsequent work by Bollobás, Kohayakawa, and
Łuczak [6]. We refer the reader to [20] for a modern short proof of this
result.

In recent years, there has been an effort to generalise these results to a
wider family of product graphs. Lichev [21] gave sufficient conditions, in
terms of the base graphs, for the typical emergence of a giant component in
bond percolation on high-dimensional product graphs. Diskin, Erde, Kang, and
Krivelevich [11] improved upon this, giving sufficient and tight conditions
for the typical emergence of a giant component. Furthermore, they showed that
assuming the base graphs are regular, one can give a rather precise
description, similar to that in $G(n,p)$, both of the typical component
structure [10], and of the asymptotic combinatorial properties of the giant
component [12].

Returning to the dense regime, that is, when $p$ is constant, studying
connectivity and the existence of a perfect matching in $Q^{t}_{p}$, Bollobás
[4] obtained a hitting time result for the random graph process on $Q^{t}$.
Given a graph $\Gamma$, the random graph process on $\Gamma$ is defined as a
random sequence of nested graphs
$\Gamma(0)\subseteq\ldots\subseteq\Gamma(|E(\Gamma)|)$ together with an
ordering $\sigma$ on $E(\Gamma)$, chosen uniformly at random from among all
$|E(\Gamma)|!$ such orderings. We set $\Gamma(0)$ to be the empty graph on
$V(\Gamma)$. Given $\Gamma(i)$, with $0\leq i<|E(\Gamma)|$, we form
$\Gamma(i+1)$ by adding the $(i+1)$-th edge, according to the ordering
$\sigma$, to $\Gamma(i)$. The hitting time of a monotone increasing, non-empty
graph property $\mathcal{P}$, is a random variable equal to the index $\tau$
for which $\Gamma(\tau)\in\mathcal{P}$, but $\Gamma(\tau-1)\notin\mathcal{P}$.
Note that having minimum degree one, connectivity, and the existence of a
perfect matching are all monotone increasing properties. Furthermore, observe
that for a graph $\Gamma$ to be connected or contain a perfect matching, the
minimum degree of $\Gamma$ has to be at least one. A classical result of Erdős
and Rényi [13], and of Bollobás and Thomason [7], is that in the random
process on $K_{n}$, whp the hitting time for minimum degree one, connectivity,
and the existence of a perfect matching are the same. In 1990, Bollobás [4]
showed that the same phenomenon holds in the random graph process on $Q^{t}$.

######  Theorem 1.1.

Consider the random graph process on $Q^{t}$. Let $\tau_{1}$ be the hitting
time of minimum degree one, let $\tau_{2}$ be the hitting time for
connectivity, and let $\tau_{3}$ be the hitting time for the existence of a
perfect matching. Then, whp, $\tau_{1}=\tau_{2}=\tau_{3}$.

Subsequent work by Joos determined the threshold for connectivity for
Cartesian powers of graphs [17, 18], that is, $\prod_{i=1}^{t}H_{i}$ where all
the base graphs $H_{i}$ are the same.

Our main result generalises the result of Bollobás [4] to a wider family of
product graphs.

######  Theorem 2.

Let $C>1$ be an integer. For every $i\in[t]$, let $H_{i}$ be a $d_{i}$-regular
connected graph, with $1<|V(H_{i})|\leq C$. Let $G=\square_{i=1}^{t}H_{i}$,
and suppose that $|V(G)|$ is even. Consider the random graph process on $G$.
Let $\tau_{1}$ be the hitting time of minimum degree one, let $\tau_{2}$ be
the hitting time for connectivity, and let $\tau_{3}$ be the hitting time for
the existence of a perfect matching. Then, whp, $\tau_{1}=\tau_{2}=\tau_{3}$.

In fact, we prove the following description of $G_{p}$, from which standard
results (see, for example, [5] and [4, Lemma 2]), allow one to derive Theorem
2.

######  Theorem 3.

Let $C>1$ be an integer. For every $i\in[t]$, let $H_{i}$ be a $d_{i}$-regular
connected graph with $1<|V(H_{i})|\leq C$. Let $G=\square_{i=1}^{t}H_{i}$, and
suppose that $n\coloneqq|V(G)|$ is even. Let $d\coloneqq
d(G)=\sum_{i=1}^{t}d_{i}$. Let $\epsilon\geq 0$ be a sufficiently small
constant, and let $p$ be such that $(1-p)^{d}\leq n^{-(1-\epsilon)}$. Then,
whp, the following holds in $G_{p}$.

  1. (a)

There exists a unique giant component, spanning all but $o(n)$ of the
vertices. All the other components of $G_{p}$, if there are any, are isolated
vertices. Furthermore, every two isolated vertices in $G_{p}$ are at distance
at least two in $G$.

  2. (b)

The giant component of $G_{p}$ has a (nearly-)perfect matching.

A few comments are in place. Note that the threshold probability $p^{*}$, at
which the expected number of isolated vertices is zero, is
$p^{*}=1-\left(\frac{1}{n}\right)^{1/d}$. Since $2^{d}\leq n\leq C^{d}$, one
can observe that $p^{*}$ is bounded away from zero and one. Since
$d=\Theta_{C}(\log n)$, note that if $p$ is such that $(1-p)^{d}\leq
n^{-(1-\epsilon)}$ for small enough constant $\epsilon\geq 0$, then
$p=\Theta_{C}(1)$, and in particular is bounded away from zero and one as
well.

Furthermore, let us remark that Theorem 3a implies that whp adding any edge to
$G_{p}$, which is not contained in the giant component, must connect an
isolated vertex to the giant component, and indeed this suffices to show that
the hitting times of minimum degree one and connectivity are whp the same.
Theorem 3b then shows that whp the only obstacle to a perfect matching in
$G_{p}$ itself is the existence of isolated vertices. Moreover, the proof of
Theorem 3a does not rely on the product structure of the graph, and only uses
the assumptions that the graph is $d$-regular, has optimal edge-expansion for
sets of size polynomial in $d$, and has some mild edge-expansion for larger
sets.

Let us briefly remark that since the hypercube is bipartite, in order to find
a perfect matching it suffices to apply Hall’s theorem. In our setting,
however, the graph $G$ is not necessarily bipartite, which means that in order
to show the typical existence of a perfect matching, one needs to consider the
Tutte-Berge formula. This requires a much more delicate treatment, which is
detailed in the proof outline in the subsequent section, and also requires us
to develop tools which are valid for more general graphs (see Lemmas 3.2 and
3.7) and could be of independent interest when treating perfect matchings in
the setting of percolation.

The paper is structured as follows. In Section 1.2 we give an outline of the
proofs. In Section 2 we prove Theorem 3a, and in Section 3 we prove Theorem
3b. Finally, in Section 4 we conclude with a short discussion of the results
and possible avenues for future research.

###  1.2 Proofs outline

#### Notation and definitions.

Throughout the paper we let $C>1$ be an integer, $(H_{i})_{i=1}^{t}$ be a
sequence of $d_{i}$-regular and connected graphs with $1<|V(H_{i})|\leq C$,
and let $G=\square_{i=1}^{t}H_{i}$ be their product. We let $G=(V,E)$. We call
$t$ the dimension of $G$, and given $u=(u_{1},\ldots,u_{t})\in V$ we call
$u_{i}$ the $i$-th coordinate of $u$. Furthermore, we denote by $n:=|V|$ the
order of $G$, and by $d\coloneqq d(G)$ the degree of $G$, noting once again
that $d=\sum_{i=1}^{t}d_{i}=\Theta_{C}(\log n)$.

Given a graph $\Gamma$ and subsets $S_{1},S_{2}\subseteq V(\Gamma)$ with
$S_{1}\cap S_{2}=\varnothing$, we denote by $E_{\Gamma}(S_{1})$ the set of
edges in $\Gamma$ whose both endpoints are in $S_{1}$, and by
$E_{\Gamma}(S_{1},S_{2})$ the edges in $\Gamma$ with one endpoint in $S_{1}$
and the other endpoint in $S_{2}$. We set
$e_{\Gamma}(S_{1})\coloneqq|E_{\Gamma}(S_{1})|$ and
$e_{\Gamma}(S_{1},S_{2})\coloneqq|E_{\Gamma}(S_{1},S_{2})|$. If the choice of
$\Gamma$ is clear, we may omit the subscript. Moreover, given $S\subseteq
V(\Gamma)$, we define $S^{C}$ to be $V(\Gamma)\setminus S$.

Finally, throughout the paper, we let $\epsilon\geq 0$ be a sufficiently small
constant, and let $p$ be such that $(1-p)^{d}\leq n^{-(1-\epsilon)}$,
recalling that this implies that $p=\Theta_{C}(1)$.

#### External results.

We make extensive use of the following generalisations of Harper’s inequality
to regular high-dimensional product graphs.

######  Theorem 1.2 (Theorems 1 and 2 in [12]).

For every $S\subseteq V$ with $1\leq|S|\leq n$,

$\displaystyle e(S,S^{C})\geq\frac{|S|(d-\log_{C}|S|)}{C-1}\text{ and }$
$\displaystyle e(S,S^{C})\geq|S|(d-(C-1)\log_{2}|S|).$

We also utilise the following bound on the number of trees on $k$ vertices in
a $d$-regular graph, that are rooted at a fixed vertex.

######  Lemma 1.3 (Lemma 2 in [3]).

Let $\Gamma$ be a $d$-regular graph, let $k$ be a positive integer and let
$v\in V(\Gamma)$. Denote by $t_{k}(v)$ the number of trees on $k$ vertices
rooted at $v$ in $\Gamma$. Then $t_{k}(v)\leq(ed)^{k-1}$.

#### Proof outline of Theorem 3a.

The proof follows from a double-exposure argument, similar in spirit to the
classical argument of Ajtai, Komlós, and Szemerédi [1]. Let
$p_{2}\coloneqq\frac{1}{d^{2}}$ and let $p_{1}$ be such that
$(1-p_{1})(1-p_{2})=1-p$. Note that $G_{p_{1}}\cup G_{p_{2}}\sim G_{p}$, and
$p_{1}\approx p-\frac{1}{d^{2}}$. We first show, using a first-moment
calculation, that whp every two vertices $u,v$ which are isolated in
$G_{p_{1}}$ are at distance at least two in $G$ (Lemma 2.1). Then, utilising
Theorem 1.2 and Lemma 1.3, we show that whp there are no components in
$G_{p_{1}}$ whose order is in $\left[2,d^{20}\right]$ (Lemma 2.2). We then
turn to show that typically components whose order is at least $d^{20}$ merge
after sprinkling with $p_{2}$ — this is fairly standard, and follows the same
approach as in [1]. Noting that any vertex which was an isolated vertex in
$G_{p_{1}}$, is whp either an isolated vertex after sprinkling with $p_{2}$ or
merged into a component which was of size at least $d^{20}$ in $G_{p_{1}}$, we
obtain that whp $G_{p}$ has a unique large connected component, and all the
other vertices are isolated vertices. Finally, from Markov’s inequality it
follows that the total volume of isolated vertices in $G_{p}$ is at most
$n^{\epsilon/2}=o(n)$.

#### Proof outline of Theorem 3b.

Recall that we seek to show that the giant component of $G_{p}$ has a
(nearly-)perfect matching. We know from Theorem 3a that whp every vertex of
$G$ which is not in the giant component is an isolated vertex in $G_{p}$.
Thus, it suffices to show that whp $G_{p}$ has a perfect matching if there are
typically no isolated vertices in $G_{p}$. To that end, we will utilise the
Tutte-Berge formula [2], which implies that the number of unmatched vertices
in a maximum matching in $\Gamma$ is equal to

$\max_{U\subseteq V(\Gamma)}\left(\mathrm{odd}\left(\Gamma[V(\Gamma)\setminus
U]\right)-|U|\right),$

where $\mathrm{odd}\left(\Gamma[V(\Gamma)\setminus U]\right)$ is the number of
connected components with an odd number of vertices in
$\Gamma[V(\Gamma)\setminus U]$. In particular, a graph $\Gamma$ has a perfect
matching if and only if for every subset $U\subseteq V(\Gamma)$, the subgraph
$\Gamma[V(\Gamma)\setminus U]$ has at most $|U|$ connected components with an
odd number of vertices. Note here that if $\Gamma$ has isolated vertices, then
choosing $U=\varnothing$ witnesses that there is no perfect matching in
$\Gamma$.

We thus define Tutte-like obstructions — we say that $U\subseteq V$ is an
obstruction (for $G_{p}$) if $|U|\geq 1$, and the number of components of size
different than two in $G_{p}[V\setminus U]$ is at least $|U|+1$. We say that
the size of the obstruction is $|U|$. Note that if $G_{p}$ has no such
obstructions, then the only possible obstructions to a perfect matching are
isolated vertices, and whp the giant component has a perfect matching.
Furthermore, observe that this definition does not capture all the properties
coming from the Tutte-Berge formula – indeed, we treat components with an even
number of vertices, except two, the same as components with an odd number of
vertices – but this crude, yet much-simplified, outlook will suffice for our
needs.

We denote the components in $G_{p}[V\setminus U]$ of size different from two
by $K_{1},\ldots,K_{\ell}$, where $\ell\geq|U|+1$ if $U$ is an obstruction,
and let $K=\bigcup_{i=1}^{\ell}V(K_{i})$ and $k_{i}\coloneqq|K_{i}|$ for every
$i\in[\ell]$. We denote the components of size two in $G_{p}[V\setminus U]$ by
$W_{1},\ldots,W_{w/2}$, such that their total volume is $w$.

We say that $U$ is a minimal obstruction, if it is an obstruction with the
smallest size of $U$. Note that if a graph has an obstruction, then it must
also have a minimal obstruction. We will use the convention that
$u\coloneqq|U|$ and $k\coloneqq|K|$. Note that $u+k+w=n$.

We will require a finer description of the components in $K$. Let us partition
the vertices in $K$ into three sets, according to the size of the component in
$G_{p}[V\setminus U]$ they belong to. Let $\ell_{1}$ be the number of
components of size one in $G_{p}[V\setminus U]$, let $\ell_{2}$ be the number
of components whose size is in $[3,d^{2}]$ in $G_{p}[V\setminus U]$, and let
$\ell_{3}=\ell-\ell_{1}-\ell_{2}$ be the number of components in
$G_{p}[V\setminus U]$ that contain more than $d^{2}$ vertices. We further
denote the set of vertices in components of $G_{p}[V\setminus U]$ whose size
is one by $V_{1}$, those whose size is in $[3,d^{2}]$ by $S$, and those whose
size is larger than $d^{2}$ by $B$. We write $s:=|S|$ and $b:=|B|$, and note
that $\ell_{1}=|V_{1}|$.

Figure 1: Illustration of an obstruction, with the sets $U$, $V_{1}$, $W$, $S$
and $B$. Note that the only edges in $G_{p}$, which are not induced by $U$ or
by components $K_{i}$ in $K$ or $W_{i}$ in $W$, are in $E(U,V_{1}\cup W\cup
S\cup B)$.

Note that an obstruction is uniquely determined by the choice of $U$, and that
$U$ is not necessarily connected, and thus the number of choices could be
$\binom{n}{u}$. As is often the case, a key ingredient will be to efficiently
enumerate the number of possible obstructions, and $\binom{n}{u}$ will often
be an inefficient bound. We thus prove two claims, which could be of
independent interest in arguing about perfect matchings under percolation for
general graphs. First, in Lemma 3.2, we show that a minimal obstruction of
size $u$ is determined by the choice of $W\cup S\cup B$. We stress that this
result holds for any graph $G$, without requirements on its degree or
structure. As these sets contain connected components, by Lemma 1.3 there are
at most (roughly) $n^{w/2+\ell_{2}+\ell_{3}}(ed)^{s+w+b}$ choices for a
minimal obstruction of size $u$ (see Lemma 3.3 for a precise statement). Since
$d=\Theta_{C}(\log n)$, for ‘large’ $u$ this will be a much more efficient
bound than $\binom{n}{u}$. As it turns out, for certain types of obstructions,
neither of these bounds will be efficient enough, and we will require a
different approach. Utilising the isoperimetric properties of $G$ (Theorem
1.2), we show in Lemma 3.7 that whp if $U$ is an obstruction of order
polynomial in $n$ (that is, $n^{a}$ for some constant $0<a<1$), then there is
a set $M$ such that $U\subseteq M$, $|M|\leq 10u$, and there are relatively
few connected components in $M$ — that is, $U$ must reside in a relatively
well-connected set of order proportional to $|U|$. This allows us to more
efficiently bound the number of choices of such obstructions, using Lemma 1.3.

With these definitions and tools at hand, we can now describe how to proceed
in showing that typically obstructions do not exist. Using 1.2 one can deduce
a lower bound of the number of edges in $E(K_{i},K_{i}^{C})$. Note that for
$U$ to be an obstruction, $E_{G_{p}}(K_{i},K_{i}^{C})\subseteq E(K_{i},U)$ for
all $i\in[\ell]$. Since $G$ is $d$-regular, there are at most $du$ edges
touching $U$. So in order to have an obstruction in $G_{p}$, many of the edges
in $\bigcup_{i\in\ell}E(K_{i},K_{i}^{C})$ cannot be present in $G_{p}$.
Utilising the enumeration given by Lemma 3.7 and this probabilistic bound, we
show in Lemma 3.8 that whp there are no obstructions with $1\leq
u\leq\frac{n}{d^{C^{3}/p}}$. Then, using the enumeration given by Lemma 3.2
and the aforementioned probabilistic bound, we show that whp there are no
obstructions with $b$ not ‘too large’. For larger values of $b$, the
aforementioned probabilistic bound no longer suffices. Thus, the final
ingredient, similar in spirit to the approach of Bollobás in [4], will be
Lemma 3.5, which allows to efficiently bound the number of choices for sets
$B$ that have ‘bad expansion’, that is, the number of edges in $E(B,B^{C})$ is
small. We note that this is the only place where we use the structure of $G$
as a product graph. Indeed, sets $B$ with bad expansion leave a large
‘fingerprint’ on some coordinates of the product, in particular, if $B$
intersects non-trivially with a projection $G(I)$ of $G$ onto some coordinates
$I\subseteq[t]$, then $G(I)$ spans many edges of $E(B,B^{C})$.

Finally, let us briefly comment on the difference between the proof here and
the proof for the hypercube, given in [4]. Since the hypercube is a bipartite
graph, it suffices there to apply Hall’s theorem, and in particular, one does
not need to consider the entirety of the giant component, but only sets of
size at most $\frac{n}{2}$ which expand badly. Hence, Harper’s isoperimetric
inequality for the hypercube, together with a fingerprint argument given by
Bollobás [4], allows one to show that whp there are no obstructions (bar
isolated vertices) to a perfect matching. Here, since $G$ is not necessarily
bipartite, one needs to consider Tutte-type obstructions, and in particular
sets encompassing the entirety of the giant component. This, in turn, requires
a much more delicate treatment, and in particular, to consider the structure
of obstructions, and the more efficient enumerations given by Lemmas 3.2 and
3.7.

##  2 Connectivity

We begin by showing that isolated vertices in $G_{p}$ are typically at
distance at least two in $G$.

######  Lemma 2.1.

Whp, every two isolated vertices in $G_{p}$ are at distance at least two.

###### Proof.

Fix an edge $\\{u,v\\}\in E$. Since $G$ is $d$-regular, the total number of
edges meeting $u$ and $v$ is $2d-1$. Thus, the probability that $u$ and $v$
are isolated vertices in $G_{p}$ is at most

$(1-p)^{2d-1}\leq(1-p)^{-1}n^{-2(1-\epsilon)}\leq n^{-2(1-2\epsilon)},$

where we used that $(1-p)^{d}\leq n^{-(1-\epsilon)}$. There are $\frac{dn}{2}$
edges to consider. Thus, by the union bound, the probability that two isolated
vertices in $G_{p}$ are at distance one in $G$ is at most
$\frac{dn}{2}n^{-2(1-2\epsilon)}=o(1)$. ∎

Let us further show the following ‘gap’ statement, which is an almost-
immediate corollary of Theorem 1.2 and Lemma 1.3. We note that $d^{20}$ in the
following lemma is chosen rather arbitrarily, and a much tighter bound can be
obtained.

######  Lemma 2.2.

Whp, there are no connected components $K$ in $G_{p}$ with $|V(K)|\eqqcolon
k\in[2,d^{20}]$.

###### Proof.

Fix $k\in[2,d^{20}]$. Let us estimate the probability that there is a
connected component $K$ of order $k$ in $G_{p}$. By Theorem 1.2, we have that
$e(K,K^{C})\geq k(d-(C-1)\log_{2}k)\geq\frac{9kd}{10}$, where we used the fact
that $k\leq d^{20}$. Let $\mathcal{T}_{k}$ be the set of trees of order $k$,
and let $\mathcal{A}_{k}$ be the event that there exists a connected component
of order $k$ in $G_{p}$. Thus, by the union bound and by Lemma 1.3,

$\displaystyle\mathbb{P}\left[\mathcal{A}_{k}\right]$
$\displaystyle\leq\sum_{T\in\mathcal{T}_{k}}(1-p)^{e(T,T^{C})}\leq
n(ed)^{k-1}(1-p)^{\frac{9kd}{10}}\leq
n^{1-(1-\epsilon)\frac{9k}{10}}(ed)^{k-1}\leq
n^{1-(1-2\epsilon)\frac{9k}{10}}.$

By the union bound over the less than $d^{20}$ possible values of $k$, we have
that the probability of an event violating the statement of the lemma is at
most

$\displaystyle\sum_{k=2}^{d^{20}}n^{1-(1-2\epsilon)\frac{9k}{10}}\leq
2n^{1-(1-2\epsilon)\frac{18}{10}}\leq n^{-7/10}=o(1).$

∎

We are now ready to prove the key result of this section, that is, Theorem 3a,
whose proof will utilise the classical double-exposure argument of [1].

######  Proposition 2.3.

Whp there is a unique giant component in $G_{p}$ whose order is $n-o(n)$, and
all the other components in $G_{p}$ are isolated vertices. Furthermore, every
two isolated vertices are at distance at least two from each other.

###### Proof.

Let $p_{2}=\frac{1}{d^{2}}$, and let $p_{1}$ be such that
$(1-p_{1})(1-p_{2})=1-p$. Note there exists $\epsilon^{\prime}>0$ such that
$(1-p_{1})^{d}=n^{-(1-\epsilon^{\prime})}$, and thus we may apply Lemmas 2.1
and 2.2 on $G_{p_{1}}$. Furthermore, observe that $G_{p}$ has the same
distribution as $G_{p_{1}}\cup G_{p_{2}}$.

We begin by percolating with probability $p_{1}$. Note that by Lemma 2.2, whp
in $G_{p_{1}}$ there are only isolated vertices and components of order at
least $d^{20}$. We begin by showing that after sprinkling with $p_{2}$,
typically all the components of order at least $d^{20}$ merge. Let $W$ be the
set of vertices in components of order at least $d^{20}$ in $G_{p_{1}}$. Let
$A\sqcup B=W$ be a partition of $W$ which respects the components of
$G_{p_{1}}$. We may assume that $|A|\leq|B|$ and let $a\coloneqq|A|$.

Let $A^{\prime}\coloneqq\left(A\cup N_{G}(A)\right)\setminus B$, where
$N_{G}(X)$ is the external neighbourhood of $X$ in $G$, and let
$B^{\prime}\coloneqq\left(B\cup N_{G}(B)\right)\setminus A^{\prime}$. By Lemma
2.1, whp every two isolated vertices in $G_{p_{1}}$ are at distance at least
two from each other in $G$. We continue assuming this holds deterministically.
Thus, every isolated vertex in $G_{p}$ is in the neighbourhood of $A$ or $B$,
and we have that $V=A^{\prime}\sqcup B^{\prime}$, that is,
$B^{\prime}=V\setminus A^{\prime}$. By Theorem 1.2, we have that
$e(A^{\prime},B^{\prime})\geq\frac{a(d-\log_{C}a)}{C-1}\geq\frac{a}{C-1}$,
since $a\leq\frac{n}{2}$. We can thus extend these edges to $\frac{a}{C-1}$
paths of length at most $3$ between $A$ and $B$. Very naively, we can trim
these to a set of $\frac{a}{Cd^{2}}$ edge-disjoint paths of length at most $3$
between $A$ and $B$.

We now sprinkle with probability $p_{2}$. The probability none of these paths
are in $G_{p_{2}}$ is thus at most
$(1-p_{2}^{3})^{\frac{a}{Cd^{2}}}\leq\exp\left\\{-\frac{a}{d^{9}}\right\\}$.
Thus, by the union bound, the probability that there is a component of order
at least $d^{20}$ in $G_{p_{1}}$ which does not merge in $G_{p_{1}}\cup
G_{p_{2}}$ is at most

$\displaystyle\sum_{a=d^{20}}^{\frac{n}{2d^{20}}}\binom{n/d^{20}}{a/d^{20}}\exp\left\\{-\frac{a}{d^{9}}\right\\}$
$\displaystyle\leq\sum_{a=d^{20}}^{n}(en)^{a/d^{20}}\exp\left\\{-\frac{a}{d^{9}}\right\\}=o(1),$

where we used the fact that $\ln n\leq\ln(C^{d})\leq d^{2}$, and that $a\geq
d^{20}$. Thus, all the components of order at least $d^{20}$ in $G_{p_{1}}$
merge after sprinkling with probability $p_{2}$.

Note that by Lemma 2.1, whp every two isolated vertices in $G_{p_{1}}$ are not
connected by an edge of $G$. Hence, adding any edge touching an isolated
vertex connects it to a component whose order is at least $d^{20}$ in
$G_{p_{1}}$, and these components all merge whp. Hence, whp, there exists a
unique connected component in $G_{p_{1}}$ whose order is at least $d^{20}$,
and all the other components are isolated vertices, whose distance in $G$ is
at least two. Finally, let $Y$ be the random variable counting the number of
isolated vertices in $G_{p}$. Then, $\mathbb{E}[Y]=n(1-p)^{d}\leq
n^{\epsilon}$. Thus, by Markov’s inequality, whp $Y\leq n^{\epsilon/2}=o(n)$,
completing the proof. ∎

##  3 Perfect matching

We begin with the proof of Theorem 1. Throughout the section, we assume
divisibility by two whenever is necessary, noting that minor modifications
will allow us to argue for the existence of nearly-perfect matching otherwise.
Let us first show that, by Theorem 1.2, for ‘high enough’ dimension of $G$
every edge-cut of $G$ has at least $d$ edges.

######  Lemma 3.1.

Suppose that $t\geq 5C\log_{2}C$. Then, we have that $G$ is $d$-edge-
connected.

###### Proof.

It suffices to show that $e(S,S^{C})\geq d$ for all $S\subseteq V$ with
$1\leq|S|\leq n-1$, and in fact by symmetry, for $S$ of size at most
$\frac{n}{2}$. By 1.2,

$\displaystyle e(S,S^{C})\geq|S|(d-(C-1)\log_{2}|S|).$ (1)

For all $|S|$ such that $d\geq C\log_{2}|S|+C/\ln 2$, (1) is increasing with
$|S|$. Since $d\geq t\geq 5C\log_{2}C$, we have that

$\displaystyle d-C\log_{2}d\geq\frac{1.1C\log_{2}C}{\ln 2}>\frac{C}{\ln 2}\,,$

where we further used the fact that $C\geq 2$. Hence,
$|S|(d-(C-1)\log_{2}|S|)$ is increasing with $|S|$ for $|S|\leq d$, and for
all $S$ with $|S|\leq d$ we have that $e(S,S^{C})\geq d$, as required. For
$d\leq|S|\leq 2^{\frac{d-1}{C-1}}$ we have $d-(C-1)\log_{2}|S|\geq 1$, and
thus $e(S,S^{C})$ is at least $d$, as required. Thus, suppose that
$2^{\frac{d-1}{C-1}}\leq|S|\leq\frac{n}{2}$. Note that $|S|\leq n/2\leq
C^{t}/2\leq C^{d}/2$, which implies that $d-\log_{C}|S|\geq\log_{C}2$. Hence,
by 1.2,

$\displaystyle e(S,S^{C})$
$\displaystyle\geq\frac{|S|(d-\log_{C}|S|)}{C-1}\geq\frac{|S|\log_{C}2}{C-1}\geq\frac{2^{\frac{d-1}{C-1}}\log_{C}2}{C-1}\geq\frac{2^{\frac{d-1}{C-1}}}{2C\ln
C}\,.$ (2)

We claim that for our choice of $t$, (2) is at least $d$. Note that the
$\frac{2^{\frac{d-1}{C-1}}}{2C\ln C}-d$ is increasing as $d$ is increasing,
and indeed

$\displaystyle\frac{2^{\frac{5C\log_{2}C-1}{C-1}}}{2C\ln
C}-5C\log_{2}C>\frac{C^{3}}{2\ln C}-5C\log_{2}C\geq 0,$

for $C\geq 2$. ∎

The proof of Theorem 1 then follows immediately from Lemma 3.1, since every
$d$-regular, $(d-1)$-edge-connected graph has a perfect matching (see [2,
Theorem 7, Chapter 18]).

###  3.1 Threshold for a perfect matching

Recall the definitions of an obstruction and the sets $U,V_{1},W,S$ and $B$
given in Section 1.2, and that $p$ satisfies $(1-p)^{d}\leq n^{-(1-\epsilon)}$
for a sufficiently small constant $\epsilon\geq 0$. We begin by collecting
several lemmas which we will utilise to show that whp there are no
obstructions with $u\geq 1$.

###  3.2 Typical properties of obstructions

We begin with the following Lemma, which will allow us to bound the number of
possible obstructions more efficiently.

######  Lemma 3.2.

There are at most two minimal obstructions, $U$ and $U^{\prime}$, with
$|U|=|U^{\prime}|=u\geq 2$ and the same choice of $W\cup S\cup B$.

###### Proof.

Fix a minimal obstruction $U$ with $u=|U|\geq 2$. We have that
$V\setminus(U\cup W\cup S\cup B)=V_{1}$.

Suppose first that there are two sets, $\varnothing\neq A_{1}\subsetneq U$ and
$\varnothing\neq A_{2}\subseteq V_{1}$, such that $X\coloneqq(U\setminus
A_{1})\cup A_{2}$ is a minimal obstruction as well. By minimality, we have
that $|A_{1}|=|A_{2}|$. Since $X$ is also an obstruction and has the same set
of components of size strictly larger than one, every $v\in V_{1}\setminus
A_{2}$ has that $N(v)\subseteq U\setminus A_{1}$. But then, we have that
$U\setminus A_{1}$ is also an obstruction, where $1\leq|U\setminus A_{1}|<u$ —
contradicting the minimality of $U$. Indeed, there are $\ell_{1}-|A_{2}|$
components of size $1$ in $G_{p}[V\setminus(U\setminus A_{1})]$, and
$\ell_{2}+\ell_{3}$ components of size at least three in $G_{p}[S\cup B]$,
thus at least $\ell_{1}+\ell_{2}+\ell_{3}-|A_{2}|=\ell-|A_{2}|\geq
u+1-|A_{2}|=|X|+1$ components in total.

Now, suppose towards contradiction that there are three minimal obstructions
$U,U^{\prime},U^{\prime\prime}$ with the same choice of $W\cup S\cup B$. Then,
by the above, we have $\varnothing\neq U^{\prime},U^{\prime\prime}\subseteq
V_{1}$ with $U^{\prime}\neq U^{\prime\prime}$, such that
$u=|U^{\prime}|=|U^{\prime\prime}|$. But then, note that there must be some
$v\in U^{\prime\prime}\subseteq V_{1}$, with $v\notin U^{\prime}$. Since
$N(v)\subseteq U$, $N(v)\subseteq U^{\prime}$, and $U^{\prime}\cap
U=\varnothing$, we have that $v$ is an isolated vertex. But then
$U^{\prime\prime}\setminus\\{v\\}$ is also an obstruction of size $u-1\geq 1$
— contradiction. ∎

We will often seek to enumerate the number of minimal obstructions, having
fixed $w,\ell_{2},s,\ell_{3},$ and $b$.

######  Lemma 3.3.

Given $u,w,\ell_{2},s,\ell_{3},$ and $b$, the number of minimal obstructions
is at most

$2n^{w/2+\ell_{2}+2\ell_{3}}(ed)^{w/2+2s+b}.$

###### Proof.

Recall that $W$ is a set of $w/2$ edges. We thus have at most
$\binom{nd/2}{w/2}\leq(nd)^{w/2}$ ways to choose $W$. As for $S$, it has
$\ell_{2}$ components. Let us denote the sizes of these components by
$s_{1},\ldots,s_{\ell_{2}}$, where we have that $3\leq s_{i}\leq d^{2}$ for
every $i\in[\ell_{2}]$. Thus there are at most $d^{2\ell_{2}}$ ways to choose
$s_{1},\ldots,s_{\ell_{2}}$. We then have at most $\binom{n}{\ell_{2}}\leq
n^{\ell_{2}}$ ways to choose roots for some spanning trees of these
components. Thus by Lemma 1.3, the number of ways to choose $S$ is at most
$d^{2\ell_{2}}n^{\ell_{2}}\prod_{i=1}^{\ell_{2}}(ed)^{s_{i}-1}\leq
n^{\ell_{2}}(ed)^{2s}$. Finally, $B$ has $\ell_{3}$ components, and here we
use the crude bound of at most $n^{\ell_{3}}$ ways to choose their sizes.
Then, similarly to the above, by Lemma 1.3 there are at most
$n^{2\ell_{3}}(ed)^{b}$ ways to choose $B$.

By Lemma 3.2, given $W\cup S\cup B$ and $u$ there are at most $2$ minimal
obstructions. Thus, given $u,w,\ell_{2},s,\ell_{3},$ and $b$, the number of
minimal obstructions is at most $2n^{w/2+\ell_{2}+2\ell_{e}}(ed)^{w/2+2s+b}$.
∎

Noting that there are at most $du$ edges touching $U$ in $G$, let us bound
from below the number of edges leaving the components $K_{i}$ for
$i\in[\ell]$. To that end, for $m\in[n/2]$, let

$\displaystyle
f(m)=\max\left\\{m(d-(C-1)\log_{2}m),\frac{m(d-\log_{C}m)}{C-1}\right\\},$ (3)

where for $m\in[n/2+1,n]$ we set $f(m)=f(n-m)$.

######  Lemma 3.4.

Suppose $U\subseteq V$ is an obstruction. Then

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})\geq d(\ell-1)+f(k-\ell+1),$

where $f$ is defined according to (3).

###### Proof.

By Theorem 1.2, we have that
$\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})\geq\sum_{i=1}^{\ell}f(k_{i})$. We have
that

$\displaystyle\sum_{i=1}^{\ell}f(k_{i})=\sum_{i=1}^{\ell}\max\left\\{k_{i}(d-(C-1)\log_{2}k_{i}),\frac{k_{i}(d-\log_{C}k_{i})}{C-1}\right\\}.$

We claim that the function $f$ is concave, and thus the minimum of the above
sum is obtained with $k_{i}=1$ for all $i\in[\ell-1]$, and
$k_{\ell}=k-(\ell-1)$. Indeed, note that $g_{1}(x)=x(d-(C-1)\log_{2}x)$ and
$g_{2}(x)=\frac{x(d-\log_{C}x)}{C-1}$ are concave. While the maximum of two
concave functions is not necessarily concave, observe that there is some
minimal integer $m_{0}$ such that for all $m\geq m_{0}$, $g_{2}(m)\geq
g_{1}(m)$, and for all $m^{\prime}<m_{0}$, $g_{2}(m^{\prime})\leq g_{1}(m)$.
It thus suffices to verify that that the discrete second derivative at $m_{0}$
is decreasing. Indeed, the function $g(x)=g_{2}(x)-g_{1}(x-1)$ is decreasing
at $x=m_{0}$, and thus $f(x)$ is concave. ∎

We will further make use of the following estimate on the number of sets whose
size is not too small, yet having a small edge-boundary.

######  Lemma 3.5.

Let $a\geq\frac{n}{d^{\ln^{2}d}}$. Then, the number of sets $A\subseteq V$ of
size $a$ with $e(A,A^{C})<a\ln^{2}d$ is at most $\exp\left\\{\frac{2a}{\ln
d}\right\\}$.

###### Proof.

Let $\mathcal{F}$ be the family of $A\subseteq V$ satisfying the conditions of
the lemma.

For $i\in[t]$ and any $A\subseteq V$, let $E_{i}(A,A^{C})\subseteq E(A,A^{C})$
be the set of edges in $E(A,A^{C})$ corresponding to a change in the $i$-th
coordinate, and let $e_{i,A}\coloneqq|E_{i}(A,A^{C})|$. Moreover, given
$I\subseteq[t]$, let $e_{I,A}=\sum_{i\in I}e_{i,A}$. We say that $A$ is bad
with respect to a set of coordinates $I$, if
$e_{I,A}<a\ln^{2}d\cdot\frac{|I|}{t}$. Let $\mathcal{A}_{I}$ be the family of
sets $A$ which are bad with respect to some $I\subseteq[t]$. Note that for
every fixed $m\in\mathbb{N}$, if $A\in\mathcal{F}$, then there is some $I$
with $|I|=m$ such that $e_{I,A}<a\ln^{2}d\cdot\frac{|I|}{t}$. Thus,

$|\mathcal{F}|\leq\sum_{\begin{subarray}{c}I\subseteq[t]\\\
|I|=m\end{subarray}}|\mathcal{A}_{I}|\leq\binom{t}{m}\max_{\begin{subarray}{c}I\subseteq[t]\\\
|I|=m\end{subarray}}|\mathcal{A}_{I}|.$

We now set $m=\log_{C}\left(\ln^{5}d\right)$, and turn to estimate
$|\mathcal{A}_{I}|$ for any $I\subseteq[t]$ with $|I|=m$.

For such an $I$ and $v\in V$, let $G(I,v)\coloneqq\square_{i\in[t]\setminus
I}\\{v_{i}\\}\square_{i\in I}H_{i}\subseteq G$. Observe that
$2^{|I|}\leq|V(G(I,v))|\leq C^{|I|}$, and that for every $v\neq u\in V$,
$V(G(I,v))$ and $V(G(I,u))$ are either disjoint or identical. Thus, fixing $I$
with $|I|=m$, there are at most $\frac{n}{2^{m}}$ different subgraphs
$G(I,v)$, and their union is $V$. We say that $A$ intersects non-trivially
with $G(I,v)$ if $V(G(I,v))\cap A\neq\varnothing$ and $V(G(I,v))\setminus
A\neq\varnothing$. By Theorem 1.2 and Lemma 3.1, we have that if $A$
intersects non-trivially with $G(I,v)$, then $G(I,v)$ spans at least $|I|=m$
edges of $E(A,A^{C})$. Thus, if $A\in\mathcal{A}_{I}$, we have that $A$
intersects non-trivially at most $\frac{a\ln^{2}d}{t}$ such subgraphs. Indeed,
otherwise, there would be no $I$ with $|I|=m$ and
$e_{I,A}<a\ln^{2}d\cdot\frac{m}{t}$. Therefore, a set $A\in\mathcal{A}_{I}$
contains at least

$\frac{a-C^{m}\frac{a\ln^{2}d}{t}}{C^{m}}$

such subgraphs, and at most $C^{m}\frac{a\ln^{2}d}{t}$ other vertices.
Recalling $a\geq\frac{n}{d^{\ln^{2}d}}$ we thus obtain that

$\displaystyle|\mathcal{A}_{I}|$
$\displaystyle\leq\binom{\frac{n}{2^{m}}}{\frac{a}{C^{m}}}\binom{n}{C^{m}\frac{a\ln^{2}d}{t}}\leq\left(\frac{enC^{m}}{a}\right)^{\frac{a}{C^{m}}}\left(\frac{ent}{C^{m}a\ln^{2}d}\right)^{C^{m}\frac{a\ln^{2}d}{t}}$
$\displaystyle\leq\left(ed^{\ln^{2}d}C^{m}\right)^{\frac{a}{C^{m}}}\left(\frac{etd^{\ln^{2}d}}{C^{m}\ln^{2}d}\right)^{C^{m}\frac{a\ln^{2}d}{t}}\leq\left(ed^{\ln^{2}d}\ln^{5}d\right)^{\frac{a}{\ln^{5}d}}\left(\frac{ed^{\ln^{2}d+1}}{\ln^{7}d}\right)^{\frac{a\ln^{7}d}{t}}$
$\displaystyle\leq\exp\left\\{\frac{a}{\ln d}\right\\}.$

Altogether, we obtain that
$|\mathcal{F}|\leq\binom{t}{\log_{C}(\ln^{5}d)}\exp\left\\{\frac{a}{\ln
d}\right\\}\leq\exp\left\\{\frac{2a}{\ln d}\right\\}$, as required. ∎

We finish this section by showing that given an obstruction with $u\geq
2^{\frac{d}{10C}}$, whp $U$ lies in a set which is not ‘too disconnected’, and
whose size is proportional to that of $U$. First, we require the following
fairly simple claim.

######  Claim 3.6.

Whp there are no obstructions such that one (or more) of the following holds,

  1. (a)

$\ell_{1}\geq 5u$,

  2. (b)

$s\geq 6u$,

  3. (c)

$\ell_{3}\geq\frac{6u}{d^{2}}$ and $u\geq d^{2}$.

###### Proof.

We first claim that in any of the above cases, we would have that

$\displaystyle\sum_{i\in[\ell]}e(K_{i},K_{i}^{C})\geq 5du.$

Indeed, if $\ell_{1}=|V_{1}|\geq 5u$, since the graph $G$ is $d$-regular,
$\sum_{i\in[\ell]}e(K_{i},K_{i}^{C})\geq d\ell_{1}\geq 5du$. Similarly, since
by Theorem 1.2, every component $K_{i}$ in $G_{p}[S]$ satisfies
$e(K_{i},K_{i}^{C})\geq|K_{i}|(d-2(C-1)\log_{2}d)$, if $s\geq 6u$ then
$\sum_{i\in[\ell]}e(K_{i},K_{i}^{C})\geq(1-o(1))ds\geq 5du$. Finally, if
$\ell_{3}\geq\frac{6u}{d^{2}}$, then, by Theorem 1.2 and by convexity
arguments similar to Lemma 3.4, we have that

$\displaystyle\sum_{i\in[\ell]}e(K_{i},K_{i}^{C})$
$\displaystyle>(\ell_{3}-1)d^{2}(d-2(C-1)\log_{2}d)$ $\displaystyle\geq
6du-d^{3}+2(C-1)\log_{2}d\geq 5du,$

where we used the assumption that $u\geq d^{2}$.

Fix $u$ and recall that $U$ has at most $du$ edges touching it. Note that any
edge between two components $K_{i},K_{j}$ for $i,j\in[\ell]$ would contradict
the fact that we consider an obstruction. Hence, the probability of an
obstruction with $\sum_{i\in[\ell]}e(K_{i},K_{i}^{C})\geq 5du$ is at most

$\displaystyle\binom{n}{u}(1-p)^{5du-du}\leq n^{u}n^{-(1-\epsilon)4u}\leq
n^{-\frac{5u}{2}},$

where we used $(1-p)^{d}\leq n^{-(1-\epsilon)}$, and recalling that choosing
$U$ determines the obstruction. A union bound over all possible values of $u$,
and the at most $n^{2}$ choices for $s$ and $\ell_{3}$ yields that the
probability of an event violating the statement of the claim is at most

$\displaystyle 3n^{2}\sum_{u=1}^{n}n^{-\frac{5u}{2}}\leq 3n^{2}\cdot
2n^{-\frac{5}{2}}=o(1).$

∎

We are now ready to describe for some range of $u$ a set $M$ containing $U$
with relatively few components.

######  Lemma 3.7.

Whp for every obstruction with $u\geq 2^{\frac{d}{10C}}$, there is a
$M\subseteq V$ satisfying the following,

  1. 1.

$U\subseteq M$; and,

  2. 2.

$|M|\leq 10u$; and,

  3. 3.

$G[M]$ contains at most $u/2^{\frac{d}{(100C)^{3}}}$ components.

###### Proof.

Suppose that $U$ is an obstruction with $u=|U|$, $|V_{1}|=\ell_{1}$ and
$s=|S|$. By Claim 3.6, we have that whp there is no obstruction with
$\ell_{1}\geq 4u$, as well as no obstruction with $s\geq 5u$, and no
obstruction with $\ell_{3}\geq 10u/d^{2}$. We may thus assume that
$\ell_{1}<4u,s<5u$ and $\ell_{3}<10u/d^{2}$. In particular,
$\ell_{1}+\ell_{2}\geq u+1-10u/d^{2}$.

For every component $K_{i}$ in $G_{p}[S\cup V_{1}]$, we have that
$E_{G_{p}}(K_{i},K_{i}^{C})\subseteq E(K_{i},U)$. Now, by Theorem 1.2,

$\displaystyle\sum_{K_{i}\in G_{p}[S\cup V_{i}]}e(K_{i},K_{i}^{C})\geq
d\ell_{1}+(1+o(1))ds\geq d(\ell_{1}+\ell_{2})\geq d(u+1-10u/d^{2}),$

where in the second inequality we used that $s\geq 3\ell_{2}$. Thus, the
probability that there is such an obstruction with $e(U,V_{1}\cup
S)\leq\frac{du}{100C^{2}}$ is at most

$\displaystyle\binom{n}{u}(1-p)^{d(u+1-10u/d^{2}-\frac{u}{100C^{2}})}$
$\displaystyle\leq\left(\frac{en}{u}\right)^{u}n^{-\left(1-\frac{1}{95C^{2}}\right)u}\leq\exp\left\\{\frac{u}{95C^{2}}\ln
n+u-u\ln u\right\\}$ $\displaystyle\leq\exp\left\\{u\left(\frac{\ln
n}{95C^{2}}-\frac{\ln 2\cdot d}{10C}\right)\right\\}=o\left(n^{-3}\right),$

where we used $n\leq C^{d}$, $C\geq 2$ and $u\geq 2^{\frac{d}{10C}}$. Hence,
by the union bound over the at most $n^{3}$ possible choices for $u$, $s$ and
$\ell_{3}$, we have that whp any obstruction $U$ with $u\geq
2^{\frac{d}{10C}}$ has $\ell_{1}<4u$, $s<5u$ and there are at least
$\frac{du}{100C^{2}}$ edges in $G[U\cup V_{1}\cup S]$.

Let $M=U\cup V_{1}\cup S$. We have that $U\subseteq M$ and
$|M|=u+\ell_{1}+s\leq 10u$, by our assumptions $\ell_{1}<4u$ and $s<5u$. 1.2
implies that for any set $M\subseteq V(G)$

$e_{G}(M)\leq|M|d-|M|(d-(C-1)\log_{2}|M|)=|M|(C-1)\log_{2}|M|.$

If $G[M]$ had at least $u/2^{\frac{d}{(100C)^{3}}}$ components, then by
standard convexity arguments, we would have that

$\displaystyle e_{G}(M)$
$\displaystyle\leq|M|(C-1)\log_{2}\left(\frac{|M|}{u/2^{\frac{d}{(100C)^{3}}}}\right)$
$\displaystyle\leq 10u(C-1)\log_{2}\left(10\cdot
2^{\frac{d}{(100C)^{3}}}\right)\leq\frac{du}{(100C)^{2}}<\frac{du}{100C^{2}},$

a contradiction. ∎

###  3.3 Typically no obstructions

We are now ready to show that whp there are no obstructions with $u\geq 1$ in
$G_{p}$. We consider several cases separately: when $|U|$ is small; when
$s=b=0$; when $s\neq 0$ and $b=0$; when $0\neq b\leq\frac{n}{2}$; and, when
$b>\frac{n}{2}$. We show that for each of these cases, whp there are no
obstructions, thus completing the proof of Theorem 3b.

#### Obstructions with small $U$.

We denote by $\mathcal{B}_{u}$ the event there exists an obstruction in
$G_{p}$ with $|U|=u$.

######  Lemma 3.8.

We have that

$\displaystyle\bigcup_{1\leq
u\leq\frac{n}{d^{C^{3}/p}}}\mathbb{P}\left(\mathcal{B}_{u}\right)=o(1).$

###### Proof.

Suppose there exists a construction with $|U|=u$ and
$u\in\left[\frac{n}{d^{C^{3}/p}}\right]$. By Lemma 3.4, we have that

$\displaystyle\sum_{j=1}^{j=w/2}e(W_{j},W_{j}^{C})+\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})$
$\displaystyle\geq w(d-1)+d(\ell-1)+f(k-\ell+1)$ $\displaystyle\geq
w(d-1)+du+f(n-2u-w)\geq du+f(2u),$

where we used that $\ell\geq u+1,k=n-u-w$ and the definition of $f(x)$.

We continue by considering two ranges separately. First, suppose that $u\leq
2^{\frac{d}{10C}}$. We then have that
$(C-1)\log_{2}u\leq(C-1)\frac{d}{10C}<\frac{d}{10}$ and thus $f(2u)\geq
2u(d-(C-1)\log_{2}u)>\frac{3du}{2}$. As there are at most $du$ edges touching
$U$, and noting that any edge between any two different components in
$G_{p}[V\setminus U]$ would rule out the existence of such an obstruction, we
have that

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u}\right)\leq\binom{n}{u}(1-p)^{3du/2}\leq
n^{-(1-\epsilon)\frac{3u}{2}+u}<n^{-u/3}.$

Therefore, by the union bound,

$\displaystyle\bigcup_{1\leq u\leq
2^{\frac{d}{10C}}}\mathbb{P}\left(\mathcal{B}_{u}\right)\leq\sum_{u=1}^{2^{\frac{d}{10C}}}\frac{1}{n^{u/3}}=o(1).$

We now turn to $2^{\frac{d}{10C}}\leq u\leq\frac{n}{d^{C^{3}/p}}$. By Lemma
3.7, we may assume that there exists $M$ such that $|M|\leq 10u$, $U\subseteq
M$ and there are at most $u/2^{\frac{d}{(100C)^{3}}}\eqqcolon r$ components in
$G[M]$. We have at most $n^{r}$ ways to choose the sizes of these components.
Thus, by Lemma 1.3, there are at most $\binom{10u}{u}n^{2r}(ed)^{10u}$ ways to
choose $U$. Since $u\leq\frac{n}{d^{C^{3}/p}}$, we have that

$\displaystyle
f(2u)\geq\frac{2u(d-\log_{C}u)}{C}\geq\frac{2uC^{2}\log_{C}d}{p}.$

Thus, the probability of such an obstruction is at most

$\displaystyle\binom{10u}{u}n^{2r}(ed)^{10u}(1-p)^{\frac{2uC^{2}\log_{C}d}{p}}$
$\displaystyle\leq\left(10e\right)^{u}n^{2r}(ed)^{10u}\exp\left\\{-2uC^{2}\log_{C}d\right\\}$
$\displaystyle\leq\exp\left\\{u\left(11+\ln 10+\frac{2\ln
n}{2^{d/(100C)^{3}}}+10\ln d-2C^{2}\log_{C}d\right)\right\\}$
$\displaystyle\leq\exp\left\\{u\left(15+\frac{2\ln
n}{2^{d/(100C)^{3}}}-\left(10-\frac{2C^{2}}{\ln C}\right)\ln
d\right)\right\\}$ $\displaystyle=\exp\left\\{-\frac{u\ln d}{2}\right\\}\leq
d^{-u/2},$

using $\frac{2C^{2}}{\ln C}\geq 11$ for $C\geq 2$ and $\frac{2\ln
n}{2^{d/(100C)^{3}}}=o(\ln d)$. A union bound over the less than $n$ possible
values of $u$ completes the proof. ∎

We now turn to consider obstructions with large $U$. We consider several cases
separately. The proofs in Lemmas 3.9-3.14 follow quite similar calculations,
however, each such calculation requires a slightly different approach. As
these differences are telling of the different challenges in showing that such
typical obstructions do not appear, we left the calculations explicit.

#### Obstructions with $s=b=0$.

######  Lemma 3.9.

Whp, there are no obstructions with $s=b=0$.

###### Proof.

Fix $u$ and $w$, and let $\mathcal{B}_{u,w}$ be the event that there is a
minimal obstruction with $u=|U|,w=|W|$ and $s=b=0$. By Lemma 3.3, there are at
most $2n^{w/2}(ed)^{w/2}$ such minimal obstructions. In particular,
$\ell=|V_{1}|=n-u-w$.

We have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq
d\ell+w(d-1).$

As there are at most $du$ edges touching $U$ in $G$, we have by the union
bound

$\displaystyle\mathbb{P}\left(\bigcup_{\begin{subarray}{c}u\in[1,n/2-1]\\\
w\in[0,n-2u-1]\end{subarray}}\mathcal{B}_{u,w}\right)$
$\displaystyle\leq\sum_{u=1}^{n/2-1}\sum_{w=0}^{n-2u-1}2n^{w/2}(ed)^{w/2}(1-p)^{d(\ell+w-u)-Cw}$
$\displaystyle\leq\sum_{u=1}^{n/2-1}\sum_{w=0}^{n-3}2n^{-(1-\epsilon)(\ell-u)-w/3}.$

Recall that since $u$ and $w$ are fixed, $\ell-u$ is fixed as well and ranges
from $2$ to $n-2$. Furthermore, note that the sum over $w$ is a geometric sum
and is at most twice its value when $w=0$. Thus, we have that

$\displaystyle\mathbb{P}\left(\bigcup_{\begin{subarray}{c}u\in[1,n/2-1]\\\
w\in[0,n-2u-1]\end{subarray}}\mathcal{B}_{u,w}\right)$ $\displaystyle\leq
4\sum_{j=2}^{n-2}n^{-(1-\epsilon)j}=o(1),$

as required. ∎

#### Obstructions with $s\neq 0,b=0$.

######  Lemma 3.10.

Whp, there are no obstructions with $s\neq 0$ and $b=0$.

###### Proof.

Fix $u,w$ and $s$, and let $\mathcal{B}_{u,w,s}$ be the event that there is a
minimal obstruction with $u=|U|$, $w=|W|$, $0\neq s=|S|$ and $b=0$. We then
have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{j=w/2}e(W_{j},W_{j}^{C})\geq
d\ell_{1}+ds-2Cs\log_{2}d+w(d-1),$

since the components in $S$ are of size at most $d^{2}$, and thus by Theorem
1.2, any $K_{i}$ of size at most $d^{2}$ has that
$e(K_{i},K_{i}^{C})\geq|K_{i}|(d-2C\log_{2}d)$.

By Lemma 3.3 there are at most $2n^{w/2+\ell_{2}}(ed)^{w/2+2s}$ choices for
such a minimal obstruction with $u=|U|$, $w=|W|$, $s=|S|$ and $b=0$. As
before, we obtain that

$\displaystyle\mathbb{P}\left(\bigcup_{w\in[0,n-u-s-\ell_{1}]}\mathcal{B}_{u,w,s}\right)$
$\displaystyle\leq\sum_{w=0}^{n-u-s-\ell_{1}}2n^{w/2+\ell_{2}}(ed)^{w/2+2s}(1-p)^{d(\ell_{1}+s+w-u)-2Cs\log_{2}d-w}$
$\displaystyle\leq
4n^{\ell_{2}}(ed)^{2s}(1-p)^{d(\ell_{1}+s-u)-2Cs\log_{2}d}.$

Now, $\ell_{1}+\ell_{2}\geq u+1$, and thus $\ell_{1}-u\geq 1-\ell_{2}$. Hence,

$\displaystyle n^{\ell_{2}}(ed)^{2s}(1-p$
$\displaystyle)^{d(\ell_{1}+s-u)-2C\log_{2}ds}\leq
n^{\ell_{2}}(ed)^{2s}(1-p)^{d(s-\ell_{2}+1)-2Cs\log_{2}d}$ $\displaystyle\leq
n^{-(1-\epsilon)(s-2\ell_{2}+1)}(ed)^{2s}(1-p)^{-2Cs\log_{2}d}$
$\displaystyle\leq\exp\left\\{-(1-\epsilon)(s-2\ell_{2}+1)\ln
n+5C\left(1+\ln\left(\frac{1}{1-p}\right)\right)s\ln d\right\\}.$

Note that the above decreases as $s$ increases, and therefore, using $s\geq
3\ell_{2}$ and $\ell_{2}\geq\frac{s}{d^{2}}$, we have that

$\displaystyle\mathbb{P}\left(\bigcup_{\begin{subarray}{c}s\in[3,n-u-\ell_{1}]\\\
w\in[0,n-u-s-\ell_{1}]\end{subarray}}\mathcal{B}_{u,w,s}\right)$
$\displaystyle\leq
4\sum_{s=3}^{n-u-\ell_{1}}\exp\left\\{-(1-\epsilon)(\ell_{2}+1)\ln
n+15C\left(1+\ln\left(\frac{1}{1-p}\right)\right)\ell_{2}\ln d\right\\}$
$\displaystyle\leq
4d^{2}\sum_{\ell_{2}=1}^{n}\exp\left\\{-(1-2\epsilon)(\ell_{2}+1)\ln
n\right\\}$ $\displaystyle\leq 5d^{2}\exp\left\\{-(1-2\epsilon)2\ln
n\right\\}=o(1/n),$

where we used the fact that $p$ is bounded away from one. Therefore, by the
union bound over the at most $n$ values of $u$, we have that whp there is no
obstruction violating the statement of the Lemma. ∎

#### Obstructions with $0\neq b\leq\frac{n}{2}$.

We first treat this case under the assumption that the edge boundary of $B$ in
$G$ is not too small.

######  Lemma 3.11.

Whp there are no obstructions with $0\neq b$ and $e(B,B^{C})\geq b\ln^{2}d$.

###### Proof.

Fix $u,w,s,\ell_{2},b$, and $\ell_{3}$, and let $\mathcal{B}_{u,w,s,b}$ be the
event that there is a minimal obstruction with $u=|U|$, $w=|W|$, $s=|S|$ and
$0\neq b=|B|$. Similarly to before, we then have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+e(B,B^{C})+wd-w.$

Since we assume that $e(B,B^{C})\geq b\ln^{2}d$, we obtain that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+b\ln^{2}d+wd-w.$

Now, by Lemma 3.3, there are at most
$2n^{w/2+\ell_{2}+2\ell_{3}}(ed)^{w/2+2s+b}=2n^{\ell-\ell_{1}+\ell_{3}+w/2}(ed)^{2s+b+w/2}$
such minimal obstructions with $u=|U|,w=|W|,s=|S|$ and $b=|B|$. As before, we
obtain that

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2n^{\ell-\ell_{1}+\ell_{3}}(ed)^{2s+b}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+b\ln^{2}d}\cdot
n^{w/2}(ed)^{w/2}(1-p)^{dw-w}$ $\displaystyle\leq
2n^{\ell-\ell_{1}+\ell_{3}}(ed)^{2s+b}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+b\ln^{2}d}\cdot
n^{-w/3}$ $\displaystyle\leq
2n^{\ell-\ell_{1}+\ell_{3}}(ed)^{2s+b}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+b\ln^{2}d}$
$\displaystyle\leq 2\exp\left\\{(\ell-\ell_{1}+\ell_{3})\ln
n+(2s+b)\ln(ed)-pb\ln^{2}d\right\\}n^{-(1-\epsilon)(\ell_{1}+(1+o(1))s-u)}$
$\displaystyle\leq 2\exp\left\\{(\ell-\ell_{1})\ln n+2s(\ln
d+1)-\frac{p}{2}b\ln^{2}d-(1-\epsilon)(\ell_{1}+(1+o(1))s-u)\ln n\right\\}$
$\displaystyle\leq
2\exp\left\\{(\ell+\ell_{3}-(2-\epsilon)\ell_{1}+(1-\epsilon)u)\ln
n-s(1-2\epsilon)\ln n-\frac{p}{2}b\ln^{2}d\right\\}.$

Recall that $\ell=\ell_{1}+\ell_{2}+\ell_{3}$ and $\ell_{2}\leq\frac{s}{3}$
and $\ell_{3}\leq\frac{b}{d^{2}}$. Thus,

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2\exp\left\\{(\ell+\ell_{3}-(2-\epsilon)(\ell-\ell_{2}-\ell_{3})+(1-\epsilon)u)\ln
n-s(1-2\epsilon)\ln n-\frac{p}{2}b\ln^{2}d\right\\}$ $\displaystyle\leq$
$\displaystyle
2\exp\left\\{\left((1-\epsilon)\left(u-\ell\right)+\frac{2s}{3}+\frac{3b}{d^{2}}\right)\ln
n-s(1-2\epsilon)\ln n-\frac{p}{2}b\ln^{2}d\right\\}$ $\displaystyle\leq$
$\displaystyle 2\exp\left\\{(1-\epsilon)(u-\ell)\ln
n+O\left(\frac{b}{d}\right)-s\left(1-2\epsilon-\frac{2}{3}\right)\ln
n-\frac{p}{2}b\ln^{2}d\right\\}$ $\displaystyle\leq$ $\displaystyle
2\exp\left\\{O\left(\frac{b}{d}\right)-\frac{p}{2}b\ln^{2}d\right\\},$

where in the last step we used that $u<\ell$. Since $b\geq d^{2}$, by the
union bound over the at most $n^{6}$ values for $u,w,s,\ell_{2},b$ and
$\ell_{3}$, we have that the probability of an obstruction violating the
statement of the claim is at most

$n^{6}\exp\left\\{-\Omega\left(d^{2}\ln^{2}d\right)\right\\}=o(1).$

∎

We now turn to obstructions where $B$ has a small edge-boundary.

######  Lemma 3.12.

Whp there are no obstructions with $0\neq b\leq\frac{n}{2}$ and
$e(B,B^{C})\leq b\ln^{2}d$.

###### Proof.

Note that every set $B\subseteq V$ with $e(B,B^{C})\leq b\ln^{2}d$ is of size
at least $\frac{n}{d^{\ln^{2}d}}$ since by 1.2, for
$b<\frac{n}{d^{\ln^{2}d}}$,

$e(B,B^{C})\geq\frac{b(d-\log_{C}b)}{C}\geq\frac{b\ln^{2}d\log_{C}d}{C}>b\ln^{2}d$

Fix $u,w,s,\ell_{2},b$, and $\ell_{3}$, and let $\mathcal{B}_{u,w,s,b}$ be the
event that there is a minimal obstruction with $u=|U|$, $w=|W|$, $s=|S|$ and
$0\neq b=|B|\leq\frac{n}{2}$. Similarly to before, we then have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+f(b)+wd-w.$

By the proof of Lemma 3.3, there are at most $n^{\ell_{2}+w/2}(ed)^{2s+w/2}$
ways to choose $W\cup S$. Furthermore, since we assume $e(B,B^{C})\leq
b\ln^{2}d$ and $b\geq\frac{n}{d^{\ln^{2}d}}$, by Lemma 3.5 there are at most
$\exp\left\\{\frac{2b}{\ln d}\right\\}$ choices for $B$. Therefore, by Lemma
3.2, there are at most
$2n^{\ell_{2}+w/2}(ed)^{2s+w/2}\exp\left\\{\frac{2b}{\ln d}\right\\}$ such
minimal obstructions. We obtain that

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2n^{\ell_{2}}(ed)^{2s}\exp\left\\{\frac{2b}{\ln
d}\right\\}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+f(b)}\cdot
n^{w/2}(ed)^{w/2}(1-p)^{dw-w}$ $\displaystyle\leq
2n^{\ell_{2}}(ed)^{2s}\exp\left\\{\frac{2b}{\ln
d}\right\\}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+f(b)}$ $\displaystyle\leq
2\exp\left\\{\ell_{2}\ln n+2s\ln(ed)+\frac{2b}{\ln
d}-pf(b)\right\\}n^{-(1-\epsilon)(\ell_{1}+(1+o(1))s-u)}$ $\displaystyle\leq
2\exp\left\\{\ell_{2}\ln n+2s(\ln d+1)+\frac{2b}{\ln
d}-pf(b)-(1-\epsilon)(\ell_{1}+(1+o(1))s-u)\ln n\right\\}$ $\displaystyle\leq
2\exp\left\\{(\ell_{2}-(1-\epsilon)(\ell_{1}-u))\ln n-s(1-2\epsilon)\ln
n+\frac{2b}{\ln d}-pf(b)\right\\}.$

Recall that $\ell=\ell_{1}+\ell_{2}+\ell_{3}$ and $\ell_{2}\leq\frac{s}{3}$
and $\ell_{3}\leq\frac{b}{d^{2}}$. Thus,

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2\exp\left\\{(\ell_{2}-(1-\epsilon)(\ell-\ell_{2}-\ell_{3}-u))\ln
n-s(1-2\epsilon)\ln n+\frac{2b}{\ln d}-pf(b)\right\\}$ $\displaystyle\leq
2\exp\left\\{\left(\epsilon\frac{s}{3}+(1-\epsilon)\frac{b}{d^{2}}-(1-\epsilon)(\ell-u)\right)\ln
n-s(1-2\epsilon)\ln n+\frac{2b}{\ln d}-pf(b)\right\\}$ $\displaystyle\leq
2\exp\left\\{\frac{3b}{\ln d}-pf(b)\right\\},$

where in the last step we used that $u<\ell$. Since we assume that
$b\leq\frac{n}{2}$ and $n\leq C^{d}$, we have that
$\log_{C}b\leq\log_{C}(C^{d}/2)\leq d-\frac{1}{C}$. Hence,
$f(b)\geq\frac{b}{C^{2}}$. Therefore,

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2\exp\left\\{b\left(\frac{3}{\ln
d}-\frac{p}{C^{2}}\right)\right\\}\leq\exp\left\\{-\frac{d^{2}}{2C^{2}}\right\\}.$

union bound over the at most $n^{6}$ values for $u,w,s,\ell_{2},n$ and
$\ell_{3}$ completes the proof. ∎

#### Obstructions with $b>\frac{n}{2}$.

Note that here, by Lemma 3.8, we may assume that $u\geq\frac{n}{d^{C^{3}/p}}$,
and thus $|B^{C}|\geq\frac{n}{d^{C^{3}/p}}$. We begin by assuming that $B^{C}$
has a large edge-boundary.

######  Lemma 3.13.

Whp there are no obstructions with $b>\frac{n}{2}$ and
$e(B^{C},B)\geq|B^{C}|\ln^{2}d$.

###### Proof.

Fix $u,\ell_{1},w,s$ and $b$. We then have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+e(B,B^{C})+wd-w.$

By Claim 3.6, we may assume that $\ell_{3}<\frac{6u}{d^{2}}$, and since
$u+1\leq\ell_{1}+\ell_{2}+\ell_{3}$, we have that

$\displaystyle\ell_{1}d+(1+o(1))sd+e(B,B^{C})+wd-w\geq
du-\frac{6u}{d}+|B^{C}|\ln^{2}d\geq du+\frac{u\ln^{2}d}{2}.$

We have at most $\binom{n}{u}$ ways to choose the obstruction. Thus, the
probability of having an obstruction with such $u,\ell_{1},w,s,b$ is at most

$\displaystyle\binom{n}{u}(1-p)^{u\ln^{2}d/2}$
$\displaystyle\leq\left(\frac{en}{u}\right)^{u}\exp\left\\{-\frac{pu\ln^{2}d}{2}\right\\}$
$\displaystyle\leq\exp\left\\{u\left(1+\ln n-\ln
u-\frac{p\ln^{2}d}{2}\right)\right\\}$
$\displaystyle\leq\exp\left\\{u\left(1+\frac{C^{3}}{p}\ln
d-\frac{p\ln^{2}d}{2}\right)\right\\}\leq\exp\left\\{-\frac{pu\ln^{2}d}{3}\right\\},$

where in the penultimate inequality we used $u\geq\frac{n}{d^{C^{3}/p}}$.
Union bound over the at most $n^{5}$ choices of $u,\ell_{1},w,s$ and $b$
completes the proof. ∎

We now turn the case where $B^{C}$ has a small edge-boundary.

######  Lemma 3.14.

Whp there are no obstructions with $b>\frac{n}{2}$ and
$e(B^{C},B)\leq|B^{C}|\ln^{2}d$.

###### Proof.

We follow a similar argument to that in Lemma 3.12. Fix $u,w,s$, and $b$, and
let $\mathcal{B}_{u,w,s,b}$ be the event that there is a minimal obstruction
with $u=|U|$, $w=|W|$, $s=|S|$ and $\frac{n}{2}\neq b=|B|$. Similarly to
before, we then have that

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+e(B,B^{C})+wd-w.$

By 1.2 $e(B,B^{C})\geq f(b)=f(n-b)$ and we obtain

$\displaystyle\sum_{i=1}^{\ell}e(K_{i},K_{i}^{C})+\sum_{j=1}^{w/2}e(W_{j},W_{j}^{C})\geq\ell_{1}d+(1+o(1))sd+f(n-b)+wd-w.$

By the proof of Lemma 3.3, there are at most $n^{\ell_{2}+w/2}(ed)^{2s+w/2}$
ways to choose $W\cup S$. Furthermore, since we assume
$e(B,B^{C})\leq|B^{C}|\ln^{2}d$ and $|B^{C}|\geq u\geq\frac{n}{d^{\ln^{2}d}}$,
by Lemma 3.5 there are at most $\exp\left\\{\frac{2|B^{C}|}{\ln
d}\right\\}=\exp\left\\{\frac{2(n-b)}{\ln d}\right\\}$ choices for $B^{C}$,
and hence for $B$. Therefore, by Lemma 3.2, there are at most
$2n^{\ell_{2}+w/2}(ed)^{2s+w/2}\exp\left\\{\frac{2(n-b)}{\ln d}\right\\}$ such
minimal obstructions. We thus obtain that

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2n^{\ell_{2}}(ed)^{2s}\exp\left\\{\frac{2(n-b)}{\ln
d}\right\\}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+f(n-b)}\cdot
n^{w/2}(ed)^{w/2}(1-p)^{dw-w}$ $\displaystyle\leq
2n^{\ell_{2}}(ed)^{2s}\exp\left\\{\frac{2(n-b)}{\ln
d}\right\\}(1-p)^{d(\ell_{1}+(1+o(1))s-u)+f(n-b)}$ $\displaystyle\leq
2\exp\left\\{(\ell_{2}-(1-\epsilon)(\ell_{1}-u))\ln n-s(1-2\epsilon)\ln
n+\frac{2(n-b)}{\ln d}-pf(n-b)\right\\}.$

Recall that $\ell=\ell_{1}+\ell_{2}+\ell_{3}$ and $\ell_{2}\leq\frac{s}{3}$
and by Claim 3.6 $\ell_{3}\leq\frac{6u}{d^{2}}$. Thus,

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2\exp\left\\{(\ell_{2}-(1-\epsilon)(\ell-\ell_{2}-\ell_{3}-u))\ln
n-s(1-2\epsilon)\ln n+\frac{2(n-b)}{\ln d}-pf(n-b)\right\\}$
$\displaystyle\leq
2\exp\left\\{\left(\frac{6u}{d^{2}}+\epsilon\frac{s}{3}-s(1-2\epsilon)-(1-\epsilon)(\ell-u)\right)\ln
n+\frac{2(n-b)}{\ln d}-pf(n-b)\right\\}$ $\displaystyle\leq
2\exp\left\\{\frac{3(n-b)}{\ln d}-pf(n-b)\right\\},$

where in the last step we used that $u<\ell$. Since $b\geq\frac{n}{2}$, we
have that $\log_{C}(n-b)\leq\log_{C}(C^{d}/2)\leq d-\frac{1}{C}$. Hence,
$f(n-b)\geq\frac{n-b}{C^{2}}$. Moreover, $n-b\geq u$. Therefore,

$\displaystyle\mathbb{P}\left(\mathcal{B}_{u,w,s,b}\right)$ $\displaystyle\leq
2\exp\left\\{u\left(\frac{3}{\ln
d}-\frac{1}{C^{2}}\right)\right\\}\leq\exp\left\\{-\frac{u}{2C^{2}}\right\\}.$

A union bound over the at most $n^{6}$ values for $u,w,s,\ell_{2},b$ and
$\ell_{3}$ completes the proof. ∎

##  4 Discussion

We have extended the classical result concerning hitting times of minimum
degree one, connectivity, and the existence of a perfect matching to random
subgraphs of regular Cartesian product graphs. In particular, this includes a
simplified self-contained version of the connectivity result for bond
percolation on the hypercube. Let us mention that, independently, Collares,
Doolittle, and Erde use a similar approach – that is, sprinkling with
probabilities $p_{1}$ and $p_{2}$ – to show a connectivity result for bond
percolation on the permutahedron [9]. There, however, similarly to the
approach of [1, 6, 20], one utilises that in $G_{p_{1}}$, large components are
relatively well-spread, that is, typically every vertex in $G$ is quite close
(in $G$) to a large component of $G_{p_{1}}$. In this paper, we neither
require nor utilise such a ‘density’ statement, and instead use the fact that
the isolated vertices are ‘sparsely spread’.

We note that Lemma 3.2 does not require anything from the host graph $G$, and
Lemma 3.7 only utilises some of the isoperimetric profile of $G$, yet does not
utilise the product structure of $G$. Hence, these two results could be of
independent interest, in particular in questions concerning the typical
existence of a perfect matching under percolation in a more general setting.
Still, in this proof, the bound on the number of sets with ‘bad expansion’
from Lemma 3.5 exploits the coordinate structure present in product graphs.

Many other random graph models are known to have typically the same hitting
times for minimum degree one, connectivity, and the existence of a perfect
matching (see, for example, [15] and the references therein). It is thus
natural to ask what are the minimal requirements on $G$ for this phenomenon to
hold. As a step towards this, we propose the following question, considering
regular graphs with high-degree.

######  Question 4.1.

Let $G$ be a $d$-regular graph on $n$ vertices, with $d=\omega(1)$ and $n$
divisible by two. What minimal requirements are needed on $G$, such that in
the graph process on $G$, the hitting times for minimum degree one,
connectivity, and the existence of a perfect matching are the same?

Utilising the Tutte-Berge formula we aimed for a (nearly-)perfect matching,
that is, a matching missing none or only one vertex (in the case when $n$ is
odd) of the graph. A natural extension is to look for the threshold to have a
matching that covers all but a small fraction of the vertices.

######  Question 4.2.

Let $G=\square_{i=1}^{t}H_{i}$ for $H_{i}$ connected, regular and of bounded
size. What is the threshold $p^{*}$ such that for all $p\geq p^{*}$, whp, the
giant component of $G_{p}$ contains a (nearly-)perfect matching?

### Acknowledgements

The authors would like to thank Joshua Erde, Mihyun Kang and Michael
Krivelevich for their guidance, advice, and fruitful discussions. The second
author was supported in part by the Austrian Science Fund (FWF)
[10.55776/W1230].

## 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] C. Berge.  The theory of graphs and its applications.  London: Methuen & Co. Ldt.; New York: John Wiley & Sons. Inc. X, 247 p. (1962)., 1962.
  * [3] A. Beveridge, A. Frieze, and C. McDiarmid.  Random minimum length spanning trees in regular graphs.  Combinatorica, 18(3):311–333, 1998.
  * [4] B. Bollobás.  Complete matchings in random subgraphs of the cube.  Random Structures Algorithms, 1(1):95–104, 1990.
  * [5] B. Bollobás.  Random graphs.  Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2001.
  * [6] B. Bollobás, Y. Kohayakawa, and T. Łuczak.  The evolution of random subgraphs of the cube.  Random Structures Algorithms, 3(1):55–90, 1992.
  * [7] B. Bollobás and A. Thomason.  Random graphs of small order.  In Random graphs ’83 (Poznań, 1983), volume 118 of North-Holland Math. Stud., pages 47–97. North-Holland, Amsterdam, 1985.
  * [8] J. D. Burtin.  The probability of connectedness of a random subgraph of an $n$-dimensional cube.  Problemy Peredači Informacii, 13(2):90–95, 1977.
  * [9] M. Collares, J. Doolittle, and J. Erde.  The evolution of the permutahedron.  In preperation.
  * [10] S. Diskin, J. Erde, M. Kang, and M. Krivelevich.  Percolation on high-dimensional product graphs.  arXiv:2209.03722, 2022.
  * [11] S. Diskin, J. Erde, M. Kang, and M. Krivelevich.  Percolation on irregular high-dimensional product graphs.  Combin. Probab. Comput., 33(3):377–403, 2024.
  * [12] S. Diskin, J. Erde, M. Kang, and M. Krivelevich.  Isoperimetric inequalities and supercritical percolation on high-dimensional graphs.  Combinatorica, to appear.
  * [13] P. Erdős and A. Rényi.  On the existence of a factor of degree one of a connected random graph.  Acta Math. Acad. Sci. Hungar., 17:359–368, 1966.
  * [14] P. Erdős and J. Spencer.  Evolution of the $n$-cube.  Comput. Math. Appl., 5(1):33–39, 1979.
  * [15] A. Frieze and B. Pittel.  Perfect matchings in random graphs with prescribed minimal degree.  In Mathematics and computer science. III, Trends Math., pages 95–132. Birkhäuser, Basel, 2004.
  * [16] R. Hammack, W. Imrich, and S. Klavžar.  Handbook of product graphs.  Discrete Mathematics and its Applications (Boca Raton). CRC Press, Boca Raton, FL, second edition, 2011.  With a foreword by Peter Winkler.
  * [17] F. Joos.  Random subgraphs in Cartesian powers of regular graphs.  Electron. J. Combin., 19(1):Paper 47, 12, 2012.
  * [18] F. Joos.  Random subgraphs in sparse graphs.  SIAM J. Discrete Math., 29(4):2350–2360, 2015.
  * [19] A. Kotzig.  $1$-factorizations of Cartesian products of regular graphs.  J. Graph Theory, 3(1):23–34, 1979.
  * [20] M. Krivelevich.  Component sizes in the supercritical percolation on the binary cube.  arXiv preprint arXiv:2311.07210, 2023.
  * [21] L. Lichev.  The giant component after percolation of product graphs.  J. Graph Theory, 99(4):651–670, 2022.
  * [22] A. A. Sapoženko.  Metric properties of almost all functions of the algebra of logic.  Diskret. Analiz, 10:91–119, 1967.


[a]Eleftheria Malami

# CP Violation and Mixing in Beauty Sector:
A Theoretical Overview

###### Abstract

We provide an overview of the latest progress in the study of CP violation and
mixing in the $B$ meson decays. Studying the $B^{0}_{d}\to J/\psi K^{0}_{S}$
and $B^{0}_{s}\to J/\psi\phi$ decays, we focus on the determination of the
mixing phases $\phi_{d}$ and $\phi_{s}$, including hadronic uncertainties with
the help of the data. CP violation in the non-leptonic decays $B\to\pi K$ and
$B^{0}_{s}\to D_{s}^{\mp}K^{\pm}$ indicate puzzling patterns. Could these
puzzles indicate New Physics?

##  1 Introduction

CP Violation and Mixing in the beauty sector are important for testing the
Standard Model (SM) and a good probe for physics beyond the SM. The neutral
$B$ mixing efffects in the SM are described by loop diagrams, called boxes.
The CP-violating phases $\phi_{d}$ and $\phi_{s}$, which are associated with
$B^{0}_{q}-\bar{B}^{0}_{q}$, mixing $(q=d,s)$ are important for searching for
hints of New Physics (NP). The SM predictions of the mixing phases strongly
depend on the input parameters and especially the apex of the Unitarity
Triangle (UT). As tensions arise between measurements of the elements of the
Cabibbo–Kobayashi–Maskawa (CKM) matrix [1, 2], leading to different pictures
for the allowed NP parameter space in the $B_{q}$-meson mixing [3], it becomes
essential to investigate their origin and eventually resolve them. Here, we
focus on $B$ meson decays to determine the CP-violating phases and explore
phenomena that comes from mixing-induced CP violation, which involve
interference effects caused by $B^{0}_{q}-\bar{B}^{0}_{q}$ mixing.
Interestingly, we also encounter puzzling patterns which follow from current
data.

##  2 Mixing in $B^{0}_{d}\to J/\psi K^{0}_{S}$ and $B^{0}_{s}\to J/\psi\phi$
decays

The $B^{0}_{d}\to J/\psi K^{0}_{S}$ and $B^{0}_{s}\to J/\psi\phi$ modes, which
are considered “golden modes”, are characterised by tree topologies as well as
penguin topologies, which are doubly Cabibbo suppressed. These penguin
contributions are related to non-perturbative effects, therefore it is
difficult to calculate them reliably. In order to handle them, one has to use
control channels as well as experimental data. The key feature in these
control channels is that the penguin effects are not anymore doubly Cabibbo
suppressed.

The decay amplitude of the $B^{0}_{d}\to J/\psi K^{0}_{s}$ channel can be
written in the form [4]

$A(B_{d}^{0}\to J/\psi
K^{0})=\left(1-\frac{1}{2}\lambda^{2}\right)\mathcal{A}^{\prime}\left[1+\epsilon
a^{\prime}e^{i\theta^{\prime}}e^{i\gamma}\right]\>,\qquad\epsilon\equiv\frac{\lambda^{2}}{1-\lambda^{2}}\approx
0.052\>,$ (1)

where $\lambda=|V_{us}|$, $\mathcal{A}^{\prime}$ is the hadronic amplitude and
the term $a^{\prime}e^{i\theta^{\prime}}$ denotes the penguin parameters. The
effective mixing phase is determined as [6, 5]:

$\sin\left(\phi_{q}^{\text{eff}}\right)=\sin\left(\phi_{q}^{\text{SM}}+\phi_{q}^{\text{NP}}+\Delta\phi_{q}\right)={\eta_{f}\mathcal{A}_{\text{CP}}^{\text{mix}}(B_{q}\to
f)}/{\sqrt{1-\left(\mathcal{A}_{\text{CP}}^{\text{dir}}(B_{q}\to
f)\right)^{2}}}\>,$ (2)

where $\eta_{f}$ is the CP eigenvalue of the final state $f$ and the
$\Delta\phi_{q}$ is a hadronic phase shift associated with penguin topologies.

A state-of-the-art analysis has been presented in [7] and the SU(3) flavour
symmetry of strong interaction has been applied, which allows us to relate the
parameters of $\bar{b}\to\bar{s}c\bar{c}$ to those of
$\bar{b}\to\bar{d}c\bar{c}$ transitions (thus the hadronic parameters of the
control channels):

$a^{\prime}e^{i\theta^{\prime}}=ae^{i\theta}\>.$ (3)

Utilising Eq. 3 the $B^{0}_{d}\to J/\psi K^{0}_{S}$ decay is related to its
partner control channels $B^{0}_{s}\to J/\psi K^{0}_{S}$ and $B^{0}_{d}\to
J/\psi\pi^{0}$ and similarly, the $B^{0}_{s}\to J/\psi\phi$ decay to
$B^{0}_{d}\to J/\psi\rho^{0}$ channel [6, 8, 9, 7]. The mixing-induced CP
asymmetries of all these five $B^{0}_{q}\to J/\psi X$ channels depend on the
$\phi_{q}$ phases. In order to properly take into account the dependencies
between $\phi_{d}$, $\Delta\phi_{d}$, $\phi_{s}$ and $\Delta\phi_{s}$, a
simultaneous analysis between these five decays has been proposed [7]. This
allows the extraction of the relevant hadronic parameters and the mixing
phases [10]:

$\phi_{d}=\left(44.4_{-1.5}^{+1.6}\right)^{\circ}\>,\qquad\phi_{s}=-0.074_{-0.024}^{+0.025}=\left(-4.2\pm
1.4\right)^{\circ}\>,$ (4)

taking the penguin effects directly into account. Future scenarios show that
New Physics (NP) contributions to $\phi_{s}$ could be established with more
than $5\sigma$ in the ultra high-precision era. Discovering NP in the $B_{s}$
system is possible but only if there are improvements in the measurements of
the CP asymmetries of all the five $B^{0}_{q}\to J/\psi X$ channels. Regarding
$\phi_{d}$, revealing NP effects is limited by the knowledge of the UT apex,
determined through the angle $\gamma$ and the side $R_{b}$, which strongly
depends on the choice of the CKM matrix elements $|V_{ub}|$ and $|V_{cb}|$. In
the future, it is necessary to improve the precision on $R_{b}$ and resolve
the tension between the inclusive and exclusive determination of these CKM
elements from semileptonic $B$ decays [7, 10, 3].

Another important topic is the determination of the effective colour-
suppression factor $a_{2}$ in the cleanest possible way from the data. For
this purpose, a new strategy has been proposed using semileptonic decays.
Hence, for the $B^{0}_{d}\to J/\psi\pi^{0}$ decay (and $B^{0}_{s}\to J/\psi
K^{0}_{S}$) one may use the semileptonic channel
$B^{0}_{d}\to\pi^{-}\ell^{+}\nu_{\ell}$ (and $B^{0}_{s}\to
K^{-}\ell^{+}\nu_{\ell}$, respectively) to create the ratio [7]:

$R_{d}^{\pi}={\mathcal{B}(B^{0}_{d}\to
J/\psi\pi^{0})}/{\left[d\mathcal{B}/dq^{2}|_{q^{2}=m_{J/\psi}^{2}}(B^{0}_{d}\to\pi^{-}\ell^{+}\nu_{\ell})\right]}\>,$
(5)

where the CP-averaged branching fraction of the $B^{0}_{d}\to J/\psi\pi^{0}$
decay is given by:

$\displaystyle 2\>\mathcal{B}(B_{d}^{0}\to J/\psi\pi^{0})=$
$\displaystyle\>\tau_{B_{d}}\>\frac{G_{\mathrm{F}}^{2}}{32\pi}|V_{cd}V_{cb}|^{2}\>m_{B_{d}}^{3}\left[f_{J/\psi}f_{B_{d}\to\pi}^{+}(m_{J/\psi}^{2})\right]^{2}\left[\Phi\left(\frac{m_{J/\psi}}{m_{B_{d}}},\frac{m_{\pi^{0}}}{m_{B_{d}}}\right)\right]^{3}$
$\displaystyle\times(1-2a\cos\theta\cos\gamma+a^{2})\times\left[a_{2}(B_{d}^{0}\to
J/\psi\pi^{0})\right]^{2}.$ (6)

The hadronic form factors drop out in Eq. 5, yielding
$a_{2}=0.363^{+0.066}_{-0.079}$, thus allowing a theoretically clean
extraction of the $a_{2}$ value. This result agrees with expectation from
naive factorisation, $a_{2}=0.21\pm 0.05$ [11]. This is a very interesting
finding suggesting that factorisation is working better than it was expected
in this category of decays.

##  3 CP Violation in $B\to\pi K$ and $B^{0}_{s}\to D_{s}^{\mp}K^{\pm}$ Decays

Over the years, the $B\to\pi K$ puzzle has received a lot of attention and
remains an intriguing problem [12, 13, 14, 15, 16]. These decays are dominated
by gluonic (QCD) loop diagrams (penguins) but electro-weak penguins (EWP) play
also an important role. One of the most important channels is the
$B^{0}_{d}\to\pi^{0}K_{S}$, which is the only mode which exhibits mixing-
induced CP violation.

A state-of-the-art analysis of the correlation between the mixing-induced and
the direct CP asymmetries has shown that the tension with the data has become
even stronger compared to the previous results. In order to resolve this
puzzle either the $B^{0}_{d}\to\pi^{0}K_{S}$ data should change or NP might be
present. In the first case, reducing the branching ratio by $2.5\sigma$ would
lead to a consistent picture with the SM. On the other hand, if NP effects are
present, then a modified EWP sector is a possible interesting candidate. A new
strategy has been proposed in order to determine the EWP parameters, using
both neutral and charged $B\to\pi K$ decays [16]. In the future, it will be
interesting to measure CP violation with much higher precision, in particular
the $B^{0}_{d}\to\pi^{0}K_{S}$ mixing-induced CP asymmetry and hopefully to
clarify the situation.

Another surprising situation arises in the $B^{0}_{s}\to D_{s}^{\mp}K^{\pm}$
system [17, 18]. These are pure tree decays and theoretically clean, making
them key players in the testing of the SM. The first puzzling pattern is
related to the value of the angle $\gamma$ of the UT [19]. Through
interference effects with the $B^{0}_{s}-\bar{B}^{0}_{s}$ mixing, the CP
asymmetry parameters allow the determination of the term $\phi_{s}+\gamma$,
thus $\gamma$. The result is in tension with the SM at the $3\sigma$ level.
Taking into account that the experimental $\phi_{s}$ value includes NP effects
in $B^{0}_{s}-\bar{B}^{0}_{s}$ mixing, possible new contributions should enter
at the decay amplitude level.

Such NP effects should also appear in the corresponding branching ratios.
Extracting individual branching ratios and comparing with the SM, a second
intriguing puzzle arises. The case gets even more exciting as similar patterns
are also observed in the branching ratios of other $B$ meson decays which have
similar dynamics. Utilising information from semileptonic decays, the
phenomenological colour factors $|a_{1}|$, characterising colour-allowed tree
decays, can be extracted in a way that minimises the dependence on CKM matrix
elements and hadronic form factors. The tensions between the theoretical
predictions and the experimental values are up to $4.8\sigma$ level.

In view of these intriguing puzzles, a new model independent description has
been suggested in order to include NP effects. Introducing the NP parameters
$\bar{\rho},\rho$, which denote the strength of NP contributions with respect
to the SM amplitudes, as well as $\bar{\delta},\delta$ and
$\bar{\varphi},\varphi$, which represent the strong and the weak CP-violating
phases, respectively, the amplitudes are parametrised. The expression of the
observables $\xi$ and $\bar{\xi}$ (which measure the strength of interference
effects) has been generalised as well as the assumption $C+\bar{C}=0$, which
was used by LHCb Collaboration. Therefore, the general expression takes the
form:

$\xi\times\bar{\xi}=\sqrt{1-2\left[\frac{C+\bar{C}}{\left(1+C\right)\left(1+\bar{C}\right)}\right]}e^{-i\left[2(\phi_{s}+\gamma)+\gamma_{\text{eff}}\right]}\qquad{\text{with}}\qquad\gamma_{\rm
eff}\equiv\gamma+\gamma_{\text{NP}},$ (7)

where $\gamma$ enters with a shift
$\gamma_{\text{NP}}=f(\bar{\rho},\rho,\bar{\varphi},\varphi)$, which is due to
CP-violating NP contributions, resulting in an effective angle $\gamma_{\rm
eff}$. Applying the strategy to the current data, correlations between the NP
parameters are determined. Interestingly, it is shown that NP contributions at
the $30\%$ level could accommodate the data.

##  4 Conclusions

The decays $B^{0}_{d}\to J/\psi K^{0}_{S}$ and $B^{0}_{s}\to J/\psi\phi$ are
the central modes for the determination of the CP violating phases $\phi_{d}$
and $\phi_{s}$, which are associated with the neutral $B$ mixing phenomena. We
are entering a phase where hadronic uncertainties have to be included to match
the experimental precision. A strategy has been developed of including these
corrections with the help of data. Other non-leptonic decays indicate puzzling
patterns. Regarding the $B\to\pi K$ system, key quantity is the mixing-induced
CP asymmetry of the $B^{0}_{d}\to\pi^{0}K_{S}$ channel. Another interesting
system, which has different dynamics though, is given by $B^{0}_{s}\to
D_{s}^{\mp}K^{\pm}$ decays, showing puzzles both in CP violation and in the
branching ratios. Consistent patterns arise in other $B_{(s)}$ modes with
similar dynamics, making the situation even more interesting. Could these
puzzles in the non-leptonic decays indicate NP? It will be exciting to see how
the data will evolve in the future high precision era.

## Acknowledgements

I would like to thank R. Fleischer, K. De Bruyn, K. K. Vos, P. van Vliet, R.
Jaarsma and M. Z. Barel for interesting collaborations and useful discussion.
I would also like to thank the organisers of the "LHCP2022 Conference" for the
invitation.

## References

  * [1] N. Cabibbo, Phys. Rev. Lett. 10, 531-533 (1963) doi:10.1103/PhysRevLett.10.531
  * [2] M. Kobayashi and T. Maskawa, Prog. Theor. Phys. 49, 652-657 (1973) doi:10.1143/PTP.49.652
  * [3] K. De Bruyn, R. Fleischer, E. Malami and P. van Vliet, [arXiv:2208.14910 [hep-ph]].
  * [4] R. Fleischer, Eur. Phys. J. C 10, 299-306 (1999) doi:10.1007/s100529900099 [arXiv:hep-ph/9903455 [hep-ph]].
  * [5] S. Faller, R. Fleischer and T. Mannel, Phys. Rev. D 79, 014005 (2009) doi:10.1103/PhysRevD.79.014005 [arXiv:0810.4248 [hep-ph]].
  * [6] S. Faller, M. Jung, R. Fleischer and T. Mannel, Phys. Rev. D 79, 014030 (2009) doi:10.1103/PhysRevD.79.014030 [arXiv:0809.0842 [hep-ph]].
  * [7] M. Z. Barel, K. De Bruyn, R. Fleischer and E. Malami, J. Phys. G 48, no.6, 065002 (2021) doi:10.1088/1361-6471/abf2a2 [arXiv:2010.14423 [hep-ph]].
  * [8] K. De Bruyn, R. Fleischer and P. Koppenburg, Eur. Phys. J. C 70, 1025-1035 (2010) doi:10.1140/epjc/s10052-010-1495-z [arXiv:1010.0089 [hep-ph]].
  * [9] K. De Bruyn and R. Fleischer, JHEP 03, 145 (2015) doi:10.1007/JHEP03(2015)145 [arXiv:1412.6834 [hep-ph]].
  * [10] M. Z. Barel, K. De Bruyn, R. Fleischer and E. Malami, [arXiv:2203.14652 [hep-ph]].
  * [11] A. J. Buras and L. Silvestrini, Nucl. Phys. B 548, 293-308 (1999) doi:10.1016/S0550-3213(99)00022-X [arXiv:hep-ph/9806278 [hep-ph]].
  * [12] R. Fleischer, Int. J. Mod. Phys. A 12, 2459-2522 (1997) doi:10.1142/S0217751X97001432 [arXiv:hep-ph/9612446 [hep-ph]].
  * [13] A. J. Buras, R. Fleischer, S. Recksiegel and F. Schwab, Phys. Rev. Lett. 92, 101804 (2004) doi:10.1103/PhysRevLett.92.101804 [arXiv:hep-ph/0312259 [hep-ph]].
  * [14] M. Gronau and J. L. Rosner, Phys. Lett. B 666, 467-471 (2008) doi:10.1016/j.physletb.2008.08.004 [arXiv:0807.3080 [hep-ph]].
  * [15] R. Fleischer, S. Jager, D. Pirjol and J. Zupan, Phys. Rev. D 78, 111501 (2008) doi:10.1103/PhysRevD.78.111501 [arXiv:0806.2900 [hep-ph]].
  * [16] R. Fleischer, R. Jaarsma, E. Malami and K. K. Vos, Eur. Phys. J. C 78, no.11, 943 (2018) doi:10.1140/epjc/s10052-018-6397-5 [arXiv:1806.08783 [hep-ph]].
  * [17] R. Fleischer and E. Malami, Phys. Rev. D 106, no.5, 056004 (2022) doi:10.1103/PhysRevD.106.056004 [arXiv:2109.04950 [hep-ph]].
  * [18] R. Fleischer and E. Malami, [arXiv:2110.04240 [hep-ph]].
  * [19] R. Aaij et al. [LHCb], JHEP 03, 059 (2018) doi:10.1007/JHEP03(2018)059 [arXiv:1712.07428 [hep-ex]].