11institutetext: J.W. van Holten 22institutetext: Nikhef, Science Park 105,
Amsterdam NL
and Lorentz Insitute, Leiden University, Leiden NL; 22email:
<EMAIL_ADDRESS>
# The gravity of light

Jan W. van Holten

###### Abstract

The gravitational field of an idealized plane-wave solution of the Maxwell
equations can be described in closed form. After discussing this particular
solution of the Einstein-Maxwell equations, the motion of neutral test
particles, which are sensitive only to the gravitational background field, is
analyzed. This is followed by a corresponding analysis of the dynamics of
neutral fields in the particular Einstein-Maxwell background, considering
scalars, Majorana spinors and abelian vector fields, respectively.

##  1 Light and gravity

Light and gravity provide the main tools for studying the universe at large;
gravity, as it determines the interactions and paths of celestial bodies, and
light as it makes them visible to us and enables us to unravel their
properties. The theoretical descriptions of light, as a form of
electromagnetism, and gravity have much in common. The classical theories of
electromagnetism and gravity are both local relativistic field theories; these
fields carry physical degrees of freedom propagating energy, momentum and
angular momentum at a finite speed $c$, commonly referred to as the speed of
light, even though gravity, and also the color charges of subatomic particles,
propagate their interactions at the same universal speed as well111For a
discussion of the role of the universal constant $c$ characterizing the
relations between inertial frames, see ref. jwvh:2021 .

Of course, at the microscopic level electromagnetism is more than a classical
field theory, as quantum effects become essential to its propagation and
interaction with matter in the form of electrons and other charged particles.
A similar change in the way gravity behaves in this domain is expected as
well, although experimental confirmation of these ideas has as yet remained
out of reach.

Even though the sources of gravity and electromagnetism are different, with
gravity coupling to the local density of energy and momentum, and
electromagnetism to the local density of electric charges and currents, the
corresponding physical degrees of freedom (classical fields in the macroscopic
world) do influence each other, but in an asymmetric way. The present chapter
is dedicated to a discussion of some aspects of this mutual interaction.
Unless specified otherwise (when numerical estimates are required) units are
used in which the speed of light is unity: $c=1$.

##  2 Einstein-Maxwell theory

General Relativity (GR), the classical theory of gravity, states that space-
time is endowed with a geometry, encoded in the metric $g_{\mu\nu}$,
determined by the distribution of all combined energy- and momentum-densities.
This geometry expresses itself in the motion of matter and light in the
universe. For the interaction between gravity and electromagnetic fields this
results in an Einstein equation specifying the Ricci curvature in terms of the
electro-magnetic energy-momentum tensor:

$R_{\mu\nu}-\frac{1}{2}\,g_{\mu\nu}R=-8\pi GT_{\mu\nu}[F],$ (1)

with the local energy-momentum density of electromagnetic fields given by

$T_{\mu\nu}[F]=F_{\mu\lambda}F_{\nu}^{\;\,\lambda}-\frac{1}{4}\,g_{\mu\nu}F_{\kappa\lambda}F^{\kappa\lambda}.$
(2)

At the same time the classical dynamics of the electromagnetic field is
specified by the generalized Maxwell equations in a space-time with given
dynamical metric:

$D_{\mu}F^{\mu\nu}=\partial_{\mu}F^{\mu\nu}+\Gamma_{\mu\lambda}^{\;\;\;\,\mu}F^{\lambda\nu}+\Gamma_{\mu\lambda}^{\;\;\;\,\nu}F^{\mu\lambda}=-j^{\nu},$
(3)

where $j^{\nu}$ is the electric charge-current density, and
$\Gamma_{\mu\lambda}^{\;\;\;\,\nu}$ the Riemann-Christoffel connection. In the
absence of charges and currents: $j^{\nu}=0$, equations (1)-(3) form a closed
system describing gravity interacting with dynamical electromagnetic fields in
otherwise empty space; this set-up applies in particular to the coupling of
gravity with electromagnetic radiation.

In places where the energy-momentum density of the electromagnetic field is
small compared to the Ricci-curvature determined by external sources, such as
the sun or compact bodies like neutron stars or black holes, one can to first
approximation neglect the contribution of the electromagnetic fields to the
curvature and describe the electromagnetic fields outside the external source
regions by Maxwell equations in the gravitational background of the external
sources. This approach is usually taken in studies of gravitational lensing,
which offered one of the first tests of GR: observing the bending of light by
the sun eddington:1919 ; and in a more extreme case the recent observations of
a black-hole shadow by the Event Horizon Telescope eht:2019 .

However, as equation (1) indicates, curvature can also be induced by
electromagnetic fields themselves, even though this requires rather extreme
electromagnetic energy densities. Indeed, according to this equation
(temporarily reinstating the speed of light $c$) the curvature $R$ measured in
$1/m^{2}$ corresponding to an energy flux $\Phi$ in $W/m^{2}$ is numerically
of the order

$\frac{R}{1/\mbox{m${}^{2}$}}\sim\,\frac{8\pi G}{c^{5}}\,\Phi\simeq 2\times
10^{-52}\,\frac{\Phi}{1\,\mbox{W/m${}^{2}$}}.$ (4)

Measuring the curvature due to even intense electromagnetic radiation will
therefore be an even more extreme challenge than the curvature due to the
collision of very distant black holes and neutron stars ligo:2016 . In the
following sections a more precise analysis is presented.

##  3 Plane waves

An complete radiative solution of the Einstein-Maxwell equations is that of a
plane electromagnetic wave of infinite width, which is accompanied by a
parallel plane gravitational wave of $pp$-type brinkmann:1923 -jwvh:2018 .
With the wave propagating in the $z$-direction, it is convenient to use light-
cone co-ordinates $u=t-z$ and $v=t+z$; the traveling plane-wave solution of
the electromagnetic field is then expressed in terms of a transverse vector
potential

$A_{i}(u)=\int_{\infty}^{\infty}\frac{dk}{2\pi}\left(a_{i}(k)\sin
ku+b_{i}(k)\cos ku\right),$ (5)

where $i=(1,2)$ labels the directions in the transverse $x$-$y$-plane; the
corresponding electric and magnetic field strengths are given by

$E_{i}(u)=-\varepsilon_{ij}B_{j}(u)=F_{ui}(u).$ (6)

Such solutions can take the form of wave packets of finite lengths carrying a
finite energy flux per unit area. Specifically in the absence of external
sources of curvature the energy density in the transverse plane is constant
and the transverse geometry can be taken to be flat; the energy flux is then
given in terms of the energy-momentum tensor by the only non-zero component

$T_{uu}(u)=F_{ui}F_{u}^{\;\,i}=\frac{1}{2}\left(\bf E^{2}+\bf
B^{2}\right)(u),$ (7)

provided the metric is of the Brinkmann type

$ds^{2}=-dudv-\Phi(u,x^{i})du^{2}+dx^{i\,2},$ (8)

which is flat in the $x$-$y$-plane as required. In this Brinkmann geometry the
only non-zero components of the Riemann curvature and Ricci tensor are

$R_{uiuj}=-\frac{1}{2}\,\partial_{i}\partial_{j}\Phi,\hskip
20.00003ptR_{uu}=-\frac{1}{2}\left(\partial_{x}^{2}+\partial_{y}^{2}\right)\Phi.$
(9)

The Einstein equation (1) then reduces to a single equation linking the
$uu$-components of the Ricci and energy-momentum tensor:

$\left(\partial_{x}^{2}+\partial_{y}^{2}\right)\Phi=8\pi G\left(\bf E^{2}+\bf
B^{2}\right).$ (10)

The general solution of this inhomogeneous linear equation for the
gravitational potential, the metric component $\Phi(u,x^{i})$, is

$\Phi=2\pi G\left(x^{2}+y^{2}\right)\left(\bf E^{2}+\bf
B^{2}\right)+\Phi_{0},$ (11)

where $\Phi_{0}(u,x^{i})$ is an arbitrary solution of the homogeneous equation

$\left(\partial_{x}^{2}+\partial_{y}^{2}\right)\Phi_{0}=0.$ (12)

These solutions of the homogeneous equation represent pure gravitational waves
of $pp$-type brinkmann:1923 :

$\Phi_{0}=\kappa_{+}(u)\left(x^{2}-y^{2}\right)+2\kappa_{\times}(u)xy.$ (13)

Equation (9) then implies that the co-efficients $\kappa_{+,\times}(u)$
represent the components of the corresponding Riemann tensor in the transverse
plane:

$R^{(0)}_{uiuj}=-\left(\begin{array}[]{cc}\kappa_{+}&\kappa_{\times}\\\
\kappa_{\times}&\kappa_{+}\end{array}\right).$ (14)

Under a rotation in the transverse plane over an angle $\varphi$ they
transform as quadrupole components:

$\left(\begin{array}[]{l}\kappa^{\prime}_{+}\\\
\kappa^{\prime}_{\times}\end{array}\right)=\left(\begin{array}[]{cc}\cos
2\varphi&-\sin 2\varphi\\\ \sin 2\varphi&\cos
2\varphi\end{array}\right)\left(\begin{array}[]{l}\kappa_{+}\\\
\kappa_{\times}\end{array}\right).$ (15)

In contrast, the special solution (11) of the inhomogenous equation
proportional to the energy density of the electromagnetic field:
$\Phi-\Phi_{0}\sim x^{2}+y^{2}$, is of monopole type, being invariant under
rotations in the transverse plane. Thus the plane electromagnetic wave is
accompanied by a scalar gravitational wave, on which a free gravitational wave
of quadrupole type can be superimposed.

##  4 Motion in the background of a plane wave

Classical motion of electrically neutral particles in the background of this
specific gravitational wave is described in terms of geodesics jwvh:2011 ;
jwvh:2018 . The worldline $X^{\mu}(\tau)$ of a massive particle parametrized
by the proper time $\tau$ is restricted by the constraint

$\dot{U}\dot{V}-\Phi(U,X^{i})\dot{U}^{2}+\dot{X}^{i\,2}=1,$ (16)

with the overdot denoting a proper-time derivative. This constraint is one of
the integrals of motion of the geodesic equation

$\ddot{X}^{\mu}+\Gamma_{\lambda\nu}^{\;\;\;\mu}(X)\dot{X}^{\lambda}\dot{X}^{\nu}=0,$
(17)

The existence of a Killing vector of the metric defined by $\partial_{v}$
implies another constant of motion

$\dot{U}=\gamma=\mbox{constant}.$ (18)

As by definition of the laboratory velocity $v^{a}=dX^{a}/dT$ we get

$\frac{dU}{dT}=1-v_{z},$ (19)

it follows from a rewriting of the constraint (16) that

$\frac{1-\bf{v}^{2}}{(1-v_{z})^{2}}+\Phi=\frac{1}{\gamma^{2}}.$ (20)

As $dU=\gamma d\tau$, the geodesic equations in the transverse plane can be
written alternatively as

$\frac{\partial{{}^{2}X^{i}}}{\partial{U^{2}}}+\frac{1}{2}\,\frac{\partial{\Phi}}{\partial{X^{i}}}=0.$
(21)

In particular for the electromagnetic wave (11) these equations simplify to
those of a 2-dimensional parametric oscillator:

$\frac{\partial{{}^{2}X^{i}}}{\partial{U^{2}}}+2\pi G\left(\bf E^{2}+\bf
B^{2}\right)X^{i}=0.$ (22)

In the special case $2\pi G(\bf E^{2}+\bf B^{2})=\mu^{2}=$ constant the
solutions take the form

$X^{i}(U)=X_{0}^{i}\cos\mu(U-U_{0}).$ (23)

In this case the non-zero components of the Riemann tensor are

$R_{uiuj}=-\mu^{2}\delta_{ij}.$ (24)

Therefore the remarkable consequence is, that the geodesics oscillate in the
transverse plane at a frequency proportional to the square root of the
curvature. Scattering of neutral test particles with a wavetrain of finite
length has been discussed in this formalism in refs. jwvh:2011 ; jwvh:2018
and references therein.

##  5 Scalar fields in a plane-wave background

The gravitational field of the light wave can be probed by neutral test
particles, as discussed in the previous section, or by electrically neutral
fields of scalar, vector or spinor type, which at the classical level are
sensitive only to the non-trivial gravitational background. At the quantum
level these fields can describe e.g. pions, photons or neutrinos. As a first
example we discuss a massive real scalar field $S$, with action

$\begin{array}[]{lll}I[S]&=&\displaystyle{-\frac{1}{2}\,\int
d^{4}x\,\sqrt{-g}\left(g^{\mu\nu}\partial_{\mu}S\partial_{\nu}S+m^{2}S^{2}\right)}\\\
&&\\\ &=&\displaystyle{\int
d^{4}x\left(2\partial_{u}S\partial_{v}S-2\Phi(\partial_{v}S)^{2}-\frac{1}{2}(\partial_{x}S)^{2}-\frac{1}{2}(\partial_{y}S)^{2}-\frac{m^{2}}{2}\,S^{2}\right),}\end{array}$
(25)

where $\nabla_{\perp}$ represents the gradient in the transverse plane. The
corresponding field equation is

$\left(4\partial_{u}\partial_{v}-4\Phi\partial_{v}^{2}-\partial_{x}^{2}-\partial_{y}^{2}+m^{2}\right)S=0.$
(26)

To solve this equation we introduce the expansion

$S(u,v,x_{i})=\int\frac{dqds}{2\pi}\,\kappa(q,s;x_{i})e^{i(qv+su)},$ (27)

with $\kappa^{*}(q,s;x_{i})=\kappa(-q,-s;x_{i})$. Note that in terms if
standard space-time co-ordinates we get

$qv+su=(q+s)t+(q-s)z\equiv Et+pz\hskip 10.00002pt\Leftrightarrow\hskip
10.00002ptq=\frac{1}{2}\left(E+p\right),\hskip
10.00002pts=\frac{1}{2}\left(E-p\right).$ (28)

The field equation then contstrains the amplitudes in the expansion to
solutions of

$\left(-\partial_{x}^{2}-\partial_{y}^{2}+4q^{2}\Phi-4sq+m^{2}\right)\kappa=0.$
(29)

For the special case (24) with constant energy density $T_{uu}$ this equation
becomes that of a 2-dimensional harmonic quantum oscillator:

$\left(-\partial_{x}^{2}-\partial_{y}^{2}+\omega_{q}^{2}(x^{2}+y^{2})-4sq+m^{2}\right)\kappa=0,$
(30)

where $\omega_{q}=2\mu|q|$. Introducing the notation
$\xi_{i}=\sqrt{\omega_{q}}\,x_{i}$ the solutions are of the form

$\kappa(q,s;x_{i})=\sum_{n_{1},n_{2}=0}^{\infty}c_{n_{1}n_{2}}(q,s)H_{n_{1}}(\xi_{1})H_{n_{2}}(\xi_{2})e^{-(\xi_{1}^{2}+\xi_{2}^{2})/2},$
(31)

where the $H_{n}(\xi)$ are standard Hermite polynomials. It follows that the
energy and momentum dispersion relation is quantized according to

$E^{2}=p^{2}+m^{2}+2(n_{1}+n_{2}+1)\omega_{q}.$ (32)

##  6 Spinor fields in a plane-wave background

Our second example is a Majorana spinor field $\Psi=\Psi^{c}\equiv
C\bar{\Psi}^{T}$, where $C$ is the charge conjugation operator and $T$ denotes
transposition in spinor space (for our conventions on the Dirac algebra
including charge conjugation, see the appendix); such a field can describe
e.g. neutrinos of Majorana type.

As spinor fields are primarily defined in Minkowski space, we need to
introduce the formalism of translating between the curved space-time manifold
and the flat local tangent space-time; this is achieved by the use of
vierbein-fields $e_{\;\mu}^{a}$ such that

$g_{\mu\nu}=\eta_{ab}e_{\;\mu}^{a}e_{\;\nu}^{b}.$ (33)

Here $a$ labels vector components in the local Minkowski space, and $\mu$ does
the same thing in the curved space-time manifold. Using the vierbein fields
one can define 1-forms $E^{a}=e^{a}_{\;\mu}dx^{\mu}$, which for the metric (8)
have the component form

$E^{a}=\left(\frac{1}{2}\left(dv+(\Phi+1)du\right),dx,dy,\frac{1}{2}\left(dv+(\Phi-1)du\right)\right).$
(34)

Defining the inverse vierbein $e^{\mu}_{\;a}$ by

$e^{\mu}_{\;a}e^{a}_{\;\nu}=\delta_{\nu}^{\mu},$ (35)

there is a corresponding gradient operator

$\nabla_{a}=e_{\;a}^{\mu}\partial_{\mu}=\left(\partial_{u}+(1-\Phi)\partial_{v},\partial_{x},\partial_{y},-\partial_{u}+(1+\Phi)\partial_{v}\right).$
(36)

In order for the metric to be covariantly constant, the vierbein must satisfy
the more general condition

$dE^{a}=\omega^{a}_{\;b}\wedge E^{b},$ (37)

where the antisymmetric-tensor valued 1-form
$\omega^{ab}=-\omega^{ba}=\omega_{\mu}^{\;ab}dx^{\mu}$ defines the spin
connection. For the special vierbein (34) it is reduced to the form

$\omega^{a}_{\;b}=\omega_{u\;b}^{\;a}\,du,\hskip
20.00003pt\omega_{u\;b}^{\;a}=-\frac{1}{2}\left(\begin{array}[]{cccc}0&\partial_{x}\Phi&\partial_{y}\Phi&0\\\
\partial_{x}\Phi&0&0&-\partial_{x}\Phi\\\
\partial_{y}\Phi&0&0&-\partial_{y}\Phi\\\
0&\partial_{x}\Phi&\partial_{y}\Phi&0\end{array}\right),$ (38)

modulo an arbitrary local Lorentz transformation in tangent space.

Defining $\omega_{a}^{\;bc}=\omega_{\mu}^{\;bc}e^{\mu}_{\;a}$, the curved-
space Dirac operator now is

$\gamma\cdot
D=\gamma^{a}\left(\nabla_{a}-\frac{1}{2}\,\omega_{a}^{\;bc}\sigma_{bc}\right).$
(39)

For our special metrics (8) or vierbeins (34) a great simplification is, that
the spin-connection term $\omega_{a}^{\;bc}\sigma_{bc}$ actually vanishes
after contraction with $\gamma^{a}$ jwvh:1999 ; therefore the Dirac operator
simplifies to

$\gamma\cdot
D=\gamma^{a}\nabla_{a}=-i\left(\begin{array}[]{cc}0&\sigma_{i}\nabla_{i}+\nabla_{0}\\\
-\sigma_{i}\nabla_{i}+\nabla_{0}&0\end{array}\right),$ (40)

and in the 2-component notation introduced in the appendix the Dirac equation
becomes:

$\begin{array}[]{l}2\partial_{v}\chi_{2}-\left(\partial_{x}+i\partial_{y}\right)\chi_{1}=im\chi^{*}_{1},\\\
\\\
\left(\partial_{x}-i\partial_{y}\right)\chi_{2}-2\left(\partial_{u}-\Phi\partial_{v}\right)\chi_{1}=im\chi^{*}_{2}.\end{array}$
(41)

The complex conjugate components $\chi^{*}$ can be eliminated by applying the
complex conjugate Dirac equation to get

$\begin{array}[]{l}\left(4\partial_{u}\partial_{v}-4\Phi\partial_{v}^{2}-\partial_{x}^{2}-\partial_{y}^{2}+m^{2}\right)\chi_{1}=0,\\\
\\\
\left(4\partial_{u}\partial_{v}-4\Phi\partial_{v}^{2}-\partial_{x}^{2}-\partial_{y}^{2}+m^{2}\right)\chi_{2}=2\left(\partial_{x}+i\partial_{y}\right)\Phi\,\partial_{v}\chi_{1}.\end{array}$
(42)

Therefore the general solution for $\chi_{1}$ is fully analoguous to that for
the scalar field $S$, with the same spectrum of energy and momentum states; in
contrast, the general solution for $\chi_{2}$ consists of a special solution,
defined in terms of the solution for $\chi_{1}$ by the right-hand side of the
second equation (42), plus an arbitrary solution of the homogeneous free
Klein-Gordon equation, as for $\chi_{1}$. Therefore all solutions are found to
have a structure similar to the scalar field, except that any non-trivial
solution $\chi_{1}$ is accompanied by a special dependend solution for
$\chi_{2}$ constructed from $\chi_{1}$ by

$\left[-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)+m^{2}\right]\chi_{2}=2(\partial_{x}+i\partial_{y})\left(\partial_{u}-\Phi\partial_{v}\right)\chi_{1}-2im\left(\partial_{u}-\Phi\partial_{v}\right)\chi_{1}^{*}.$
(43)

##  7 Massless abelian vector fields in a plane-wave background

Finally we describe the propagation of a massless abelian vector field in the
plane-wave gravitational background. The Maxwell-action takes the form

$\begin{array}[]{lll}\displaystyle{I[a]=\int
dudvdxdy}&&\left[(\partial_{u}a_{v}-\partial_{v}a_{u})^{2}+(\partial_{u}a_{i}-\partial_{i}a_{u})(\partial_{v}a_{i}-\partial_{i}a_{v})\right.\\\
&&\\\ &&\hskip
10.00002pt\left.-\,\Phi(\partial_{v}a_{i}-\partial_{i}a_{v})^{2}-\frac{1}{8}\left(\partial_{i}a_{j}-\partial_{j}a_{i}\right)^{2}\right].\end{array}$
(44)

The resulting field equations are

$\begin{array}[]{l}\displaystyle{4\partial_{u}\partial_{v}a_{v}-\Delta_{\perp}a_{v}-2\partial_{v}\left(\partial_{u}a_{v}+\partial_{v}a_{u}-\frac{1}{2}\,\partial_{i}a_{i}\right)=0,}\\\
\\\
\displaystyle{4\partial_{u}\partial_{v}a_{u}-\Delta_{\perp}a_{u}-2\partial_{u}\left(\partial_{u}a_{v}+\partial_{v}a_{u}-\frac{1}{2}\,\partial_{i}a_{i}\right)+2\partial_{i}\left[\Phi\left(\partial_{i}a_{v}-\partial_{v}a_{i}\right)\right]=0,}\\\
\\\
\displaystyle{-2\partial_{u}\partial_{v}a_{i}+\frac{1}{2}\,\Delta_{\perp}a_{i}+\partial_{i}\left(\partial_{u}a_{v}+\partial_{v}a_{u}-\frac{1}{2}\,\partial_{j}a_{j}\right)-2\partial_{v}\left[\Phi\left(\partial_{i}a_{v}-\partial_{v}a_{i}\right)\right]=0.}\end{array}$
(45)

Gauge transformations $a^{\prime}_{\mu}=a_{\mu}+\partial_{\mu}\Lambda$ can be
used to simplify these equations. First note that we can take

$\partial_{u}a^{\prime}_{v}+\partial_{v}a^{\prime}_{u}-\frac{1}{2}\,\partial_{i}a^{\prime}_{i}=0,$
(46)

by taking $\Lambda$ as the solution of

$\left(-4\partial_{u}\partial_{v}+\partial_{x}^{2}+\partial_{y}^{2}\right)\Lambda=2\left(\partial_{u}a_{v}+\partial_{v}a_{u}\right)-\partial_{i}a_{i}.$
(47)

The remaining field equations are

$\begin{array}[]{l}\displaystyle{4\partial_{u}\partial_{v}a^{\prime}_{v}-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a^{\prime}_{v}=0,}\\\
\\\
\displaystyle{4\partial_{u}\partial_{v}a^{\prime}_{u}-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a^{\prime}_{u}+2\partial_{i}\left[\Phi\left(\partial_{i}a^{\prime}_{v}-\partial_{v}a^{\prime}_{i}\right)\right]=0,}\\\
\\\
\displaystyle{4\partial_{u}\partial_{v}a^{\prime}_{i}-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a^{\prime}_{i}+4\partial_{v}\left[\Phi\left(\partial_{i}a^{\prime}_{v}-\partial_{v}a^{\prime}_{i}\right)\right]=0.}\end{array}$
(48)

Next we can still make a residual gauge transformation to eliminate
$a^{\prime}_{v}$ by taking $\Lambda^{\prime}$ restricted by

$\left(-4\partial_{u}\partial_{v}+\partial_{x}^{2}+\partial_{y}^{2}\right)\Lambda^{\prime}=0,\hskip
20.00003pta^{\prime\prime}_{v}=a^{\prime}_{v}+\partial_{v}\Lambda^{\prime}=0.$
(49)

Then the gauge contraint (46) reduces to

$\partial_{v}a_{u}^{\prime\prime}=\frac{1}{2}\,\partial_{i}a_{i}^{\prime\prime}.$
(50)

Therefore we are left with

$\begin{array}[]{l}\displaystyle{4\partial_{u}\partial_{v}a^{\prime\prime}_{u}-4\Phi\,\partial_{v}^{2}a_{u}^{\prime\prime}-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a^{\prime\prime}_{u}=2\partial_{i}\Phi\,\partial_{v}a^{\prime\prime}_{i},}\\\
\\\
\displaystyle{4\partial_{u}\partial_{v}a^{\prime\prime}_{i}-4\Phi\,\partial^{2}_{v}a^{\prime\prime}_{i}-\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a^{\prime\prime}_{i}=0,}\end{array}$
(51)

This set of equations looks similar to that of the Majorana-Dirac equations in
the previous section: the transverse components $a_{i}^{\prime\prime}$ are
solutions of the scalar Klein-Gordon equation, accompanied by a special fixed
solution $\bar{a}_{u}^{\prime\prime}$:

$-(\partial_{x}^{2}+\partial_{y}^{2})\,\bar{a}_{u}^{\prime\prime}=-2\partial_{i}\left[\left(\partial_{u}-\Phi\partial_{v}\right)a_{i}^{\prime\prime}\right].$
(52)

But in contrast to the Majorana-Dirac case there is no independent dynamical
solution for $a_{u}^{\prime\prime}$, as for vanishing $a_{i}^{\prime\prime}=0$
the homogeneous equation for $a_{u}^{\prime\prime}$ implies its vanishing as
well:

$\partial_{v}a_{u}^{\prime\prime}=0\hskip 10.00002pt\mbox{and}\hskip
10.00002pt\left(\partial_{x}^{2}+\partial_{y}^{2}\right)a_{u}^{\prime\prime}=0.$
(53)

These conditions do not allow normalizable solutions for
$a_{u}^{\prime\prime}$; in fact, for $a_{i}^{\prime\prime}=0$ the longitudinal
component $a_{u}^{\prime\prime}$ can be gauged away by a third residual gauge
transformation with a gauge function $\Lambda^{\prime\prime}$ satisfying the
constraints

$a_{u}^{\prime\prime\prime}=a_{u}^{\prime\prime}+\partial_{u}\Lambda^{\prime\prime}=0,\hskip
10.00002pt\partial_{v}\Lambda^{\prime\prime}=0,\hskip
10.00002pt(\partial_{x}^{2}+\partial_{y}^{2})\,\Lambda^{\prime\prime}=0.$ (54)

Therefore the transverse components are the only dynamical ones, taking the
same form as solutions of the massless scalar wave equation, with the same
spectrum of energy and momentum, whilst
$a_{u}^{\prime\prime}=\bar{a}_{u}^{\prime\prime}$ is a dependend field fixed
entirely in terms of the transverse components by equation (52).

##  8 Conclusions

In summary, in the above it has been shown that the equations of motion of
neutral test particles, and the field equations of neutral scalar fields,
Majorana-Dirac spinor fields and abelian vector fields can all be solved in
the background of gravitational $pp$-waves such as those accompanying infinite
plane electromagnetic waves. For energy-momentum density of the source field
constant in time, such as that of a circularly polarized plane light wave, a
distinct signature is, that test particles oscillate in the transverse plane
of the wave, whilst the spectrum of transverse momentum of the fields becomes
discrete. Because of the small curvature to be expected from such waves, these
effects will be difficult to observe; moreover, in realistic conditions beams
of electromagnetic wave will be of finite width, introducing modifications to
the above conclusions which still have to be considered. Nevertheless, as a
matter of principle the scattering of neutral particles by beams of
electromagnetic waves will be another test in establishing the universality
and dynamics of gravitational interactions.

## Appendix: Spinors and the Dirac algebra

Spinor fields in curved space-time are most easily described in the tangent
Minkowski space, using the vierbein formulation to translate the results to
the curved space-time manifold. We use the flat-space representation of the
Dirac algebra in which $\gamma_{5}$ is diagonal:

$\gamma_{0}=i\left(\begin{array}[]{cc}0&1\\\ 1&0\end{array}\right),\hskip
10.00002pt\gamma_{i}=\left(\begin{array}[]{cc}0&-i\sigma_{i}\\\
i\sigma_{i}&0\end{array}\right),\hskip
10.00002pt\gamma_{5}=\left(\begin{array}[]{cc}1&0\\\ 0&-1\end{array}\right),$
(55)

such that for $a=(0,1,2,3)$

$\left\\{\gamma_{a},\gamma_{b}\right\\}=2\eta_{ab}{\bf 1},\hskip
20.00003pt\gamma_{5}^{2}={\bf 1},\hskip
20.00003pt\left\\{\gamma_{5},\gamma_{a}\right\\}=0.$ (56)

The generators of the Lorentz transformations on spinors are defined by

$\sigma_{ab}=\frac{1}{4}\left[\gamma_{a},\gamma_{b}\right],$ (57)

with commutation relations

$\left[\sigma_{ab},\sigma_{cd}\right]=\eta_{ad}\sigma_{bc}-\eta_{ac}\sigma_{bd}-\eta_{bd}\sigma_{ac}+\eta_{bc}\sigma_{ad}.$
(58)

Hermitean conjugation is achieved by

$\gamma_{a}^{\dagger}=\gamma_{0}\gamma_{a}\gamma_{0}.$ (59)

The charge conjugation operator $C$ is defined by

$C=C^{\dagger}=C^{-1}=-C^{T}=\gamma_{2}\gamma_{0}=\left(\begin{array}[]{cc}\sigma_{2}&0\\\
0&-\sigma_{2}\end{array}\right),$ (60)

such that

$C^{-1}\gamma_{a}C=-\gamma_{a}^{T}.$ (61)

If the spinor $\Psi$ is a solution of the Dirac equation in Minkowski space

$\left(\gamma\cdot\partial+m\right)\Psi=0,$ (62)

then this is also true for the charge-conjugate:

$\Psi^{c}=C\bar{\Psi}^{T}=-\gamma_{2}\Psi^{*}\hskip
10.00002pt\Rightarrow\hskip
10.00002pt\left(\gamma\cdot\partial+m\right)\Psi^{c}=0.$ (63)

The Majorana constraint $\Psi^{c}=\Psi$ reduces the number of independent
spinor components from 4 to 2 complex ones. This makes it easy to work in
terms of 2-component spinors $(\chi,\eta)$ which are eigenspinors of
$\gamma_{5}$, by the decomposition

$\Psi=\Psi^{c}=\left[\begin{array}[]{c}\chi\\\ \eta\end{array}\right]\hskip
20.00003pt\eta=-i\sigma_{2}\chi^{*}.$ (64)

###### Acknowledgements.

Discussions with Ernst Traanberg of the Lorentz Institute in Leiden on solving
field equations in the plane-wave background are gratefully acknowledged.

## References

  * (1) G. Koekoek, J.W. van Holten and U. Wyder, The path to special relativity; preprint arXiv:2109.11925v2
  * (2) F. Dyson, A. Eddington and C. Davidson A determination of the deflection of light by the sun’s gravitational field, Phil. Trans. Royal Soc. A 220 (1920), 571
  * (3) K. Akiyama et al. (Event Horizon Telescope Collaboration), First M87 Event Horizon Telescope Results. I. The shadow of the supermassive black hole, ApJL 875 (2019), L1
  * (4) B. Abbott et al. (LIGO Scientific Collaboration and Virgo Collaboration), Observation of gravitational waves from a binary black-hole merger, Phys. Rev. Lett. 116 (2016), 061102
  * (5) H.W. Brinkmann, Proc. Natl. Ac. Sciences 9 (1923), 1
  * (6) O. Baldwin and G. Jeffery, The relativity theory of plane waves, Proc. Roy. Soc. A 111 (1926), 95
  * (7) W. Rindler, Essential Relativity (Springer, 1977)
  * (8) H. Stephani, D. Kramer, M. MacCallum, C. Hoenselaers and E. Herlt, Exact solutions of Einstein’s field equations, (Cambridge Univ. Press, 2003)
  * (9) J.W. van Holten, Gravitational waves and masless particle fields, Proc. XXXVth Karpacz Winterschool of Theor. Physics, ed. J. Kowalski-Glikman (Springer, 1999), 365
  * (10) J.W. van Holten, The gravitational field of a light wave, Fortschr. Phys. 59 (2011), 284
  * (11) J.W. van Holten, The gravity of light-waves, Universe 4 (2018), 110


# Blockchain Intelligence: When Blockchain Meets Artificial Intelligence

Zibin Zheng, , Hong-Ning Dai, , Jiajing Wu Z. Zheng, J. Wu are with School of
Data and Computer Science, Sun Yat-sen University, China (email:
<EMAIL_ADDRESS>wujiajing@mail.sysu.edu.cn).H.-N. Dai is with
Faculty of Information Technology, Macau University of Science and Technology,
Macau (email: hndai@ieee.org).

###### Abstract

Blockchain is gaining extensive attention due to its provision of secure and
decentralized resource sharing manner. However, the incumbent blockchain
systems also suffer from a number of challenges in operational maintenance,
quality assurance of smart contracts and malicious behaviour detection of
blockchain data. The recent advances in artificial intelligence bring the
opportunities in overcoming the above challenges. The integration of
blockchain with artificial intelligence can be beneficial to enhance current
blockchain systems. This article presents an introduction of the convergence
of blockchain and artificial intelligence (namely blockchain intelligence).
This paper also gives a case study to further demonstrate the feasibility of
blockchain intelligence and point out the future directions.

###### Index Terms:

Blockchain; Artificial Intelligence; Smart Contract; Machine Learning

##  I Introduction

Blockchain has received extensive attention recently due to its provision of
secure data sharing services with traceability, immutability and non-
repudiation. Despite the merits of blockchain, the development of blockchain
technologies has undergone a number of challenges including poor scalability,
difficulties in operational maintenance, detecting vulnerable codes in smart
contracts and identifying malicious behaviours in blockchain historical data.

The recent advances in artificial intelligence (AI) have greatly propelled the
evolution of diverse business applications. The integration of AI with
blockchain has the potentials to overcome the limitations of blockchain. We
name the intelligent capability bestowed by AI on the blockchain ecosystem as
_blockchain intelligence_. In particular, AI approaches such as machine
learning, data mining and data visualization may help to capture the abnormal
behaviours in blockchain, identify risks in transactions, detect possible
vulnerable program codes in smart contracts, and so on. Consequently,
proactive and autonomic actions can be made to prevent blockchain from
disruptive or illegal actions, and thus make the blockchain more intelligent.

Figure 1: Overview of blockchain

This article aims at reviewing blockchain technologies as well as AI
technologies, presenting an in-depth analysis on integrating blockchain with
AI, providing implications of enabling technologies of blockchain
intelligence. In contrast to most of recent studies on the integration of
blockchain and AI (which mainly focuses on applying blockchain to overcome
shortcomings of AI, such as security and privacy vulnerabilities [14]), this
article mainly concentrates on improving blockchain systems by applying AI
technologies. In summary, the main contributions of this article are
summarized as follows:

  * •

We first give an overview of blockchain technology and point out the
challenges in existing blockchain systems.

  * •

We then review the advances in AI and formally introduce the convergence of AI
and blockchain followed by a discussion on opportunities brought by blockchain
intelligence.

  * •

We next present a case study to demonstrate the feasibility of blockchain
intelligence.

##  II Overview of blockchain technologies

As a disruptive software technology, blockchain is reshaping diverse business
sectors. Blockchain is essentially a chain-like data structure storing
transactions verified by majority of nodes throughout the whole network as
shown in Fig. 1. Since the committed transactions in the blockchain have been
stored at every node, they are extremely difficult to be altered or falsified.
Integrating with digital signature and asymmetric encryption, blockchain data
is authenticated and auditable, implying non-repudiation of the transaction
initiator. The length of blockchain keeps growing with the new validated
transaction being appended at end of the chain. Data analytics on blockchain
data can potentially extract valuable information.

The development of blockchain technologies has experienced two phases: 1)
blockchain 1.0 (i.e., symbolized by digital currency) and 2) blockchain 2.0
(i.e., symbolized by smart contracts) [1]. In blockchain 1.0, blockchain has
been mainly used for digital currencies like Bitcoin. The appearance of
blockchain has promoted the development of smart contracts. A smart contract
essentially consists of a number of computerized contractual agreements
consented by multiple parties [2]. The contractual clauses embedded in smart
contracts will be triggered and automatically executed when a certain
condition is satisfied (e.g., who breaches the contract will be automatically
imposed with a fine).

Smart contracts have been implemented on top of blockchain as shown in Fig. 1.
The approved contractual clauses are converted into executable computer
programs. The logical connections between contractual clauses have also been
preserved in the form of logical flows in programs (e.g., if-else-if
statement). The execution of each contract statement is recorded as an
immutable transaction stored in the blockchain. Meanwhile, smart contracts
guarantee appropriate access control and contract enforcement. In particular,
developers can assign access permissions for each function in the contract.

Although blockchain and blockchain-enabled smart contracts are promising in
reshaping various industrial sectors, the intrinsic limitations of blockchain
systems also lead to the following challenges.

_1) Operational maintenance_. Due to the decentralization and heterogeneity of
blockchain systems, it is difficult to identify the potential factors
affecting the performance of blockchain. For example, the _transaction
throughput_ bottleneck of Hyperledger Fabric is different from that of Bitcoin
and Ethereum since different consensus algorithms are adopted. Moreover, like
other software systems, smart contracts consist of a number of computer
programs, which may suffer from software bugs, malicious codes and
incompatibility of running environments. Consequently, it is crucial to
achieve the intelligent and robust operational maintenance of complex
blockchain systems.

Figure 2: Opportunities brought by artificial intelligence to address
challenges of blockchain

_2) Quality assurance of smart contracts_. Smart contracts suffer from a
number of software vulnerabilities such as re-entrancy vulnerability [1],
overcharging issue [3], randomness controlling [4] and Decentralized
Autonomous Organization (DAO) attack [5]. In addition, contract correctness is
also crucial to smart contracts since it is nearly impossible to make any
revisions once they are deployed on top of blockchains. However, like software
systems, smart contracts often contain programming bugs which may lead to
crashes or misbehaviours while it is challenging to detect and identify these
bugs due to the complexity of smart contracts.

_3) Malicious behaviour detection_. Besides legal businesses, blockchain may
be exploited for malicious activities which are nevertheless difficult to be
detected due to the _pseudonymity_ of blockchain (i.e., anonymous blockchain
addresses). On the other hand, the encrypted blockchain data also leads to the
difficulty of detecting and identifying malicious behaviours via simply data
analytics. Moreover, the massive volume and heterogeneity of blockchain data
as well as diversity of user behaviours make the problem even worse. As a
result, conventional classification-based methods (e.g., machine learning
methods) cannot be directly applied.

##  III Opportunities brought by Artificial Intelligence

Artificial intelligence (AI) as a broad discipline covering machine learning
and cognitive computing is an ability of intelligent agents conducting
intellectual tasks. The recent advances in big data, AI technologies (such as
deep neural networks) and general purpose computer hardware such as graphic
processing units (GPUs) have greatly driven the development of AI.
Consequently, we have witnessed the proliferation of diverse AI applications
such as computer vision, natural language processing, speech recognition,
sentimental analysis. Big data plays a critical role in propelling AI as well
as AI applications. For example, deep learning mainly based on deep neural
networks (DNNs) has achieved superior performance thanks to the availability
of massive data so that DNNs can extract (or learn) enough features from large
volume of data.

The appearance of diverse blockchain systems has generated the enormous
volumes of blockchain data, which are publicly available to everyone. Take
Bitcoin as an example. As reported by Statista (https://www.statista.com/) at
the end of the third quarter of 2019, Bitcoin contains nearly 242 GB data.
Data analytics on the massive blockchain data cannot only extract huge
business values but also bring great opportunities to overcome the
aforementioned challenges of blockchain systems. The recent advances in AI
have also greatly driven the development of big data analytics [7]. Thus, the
integration of AI and blockchain technologies can potentially overcome the
aforementioned challenges of blockchain systems, thereby forming intelligent
blockchain systems. We name such integration of blockchain with AI as
_blockchain intelligence_. It is worth mentioning that there are several
research efforts [14, 15] on integrating blockchain with AI while most of them
are mainly concentrated on exploiting blockchain for AI so as to overcome the
emerging security and privacy vulnerabilities of AI. In contrast to these
studies, our work in this paper is mainly focused on solving the intrinsic
issues of blockchains by using AI technologies.

We summarize the opportunities brought by AI to enhance incumbent blockchain
systems as follows (as shown in Fig. 2).

_1) Intelligent operational maintenance of blockchain._ Blockchain generates
huge amount of data in a real-time manner. Analyzing blockchain data, we can
detect the possible faults, forecast the failures and identify the performance
bottleneck so as to tune or adjust the performance of blockchain systems.
There are four different levels of data analytics including: descriptive
analytics, diagnostic analytics, predictive analytics and prescriptive
analytics. In particular, the work of [8] presents a common platform to
evaluate the performance of three representative blockchain systems: Ethereum,
Parity and Hyperledger Fabric via descriptively analyzing blockchain data.
Meanwhile, the descriptive analytics of blockchain log data can help to
monitor the real-time performance of blockchain systems and identify the
possible faults [6]. In addition to diagnostic analytics on blockchain data,
predictive analytics is also necessary to anticipate the performance
bottleneck of blockchain systems. Unlike diagnostic and predictive analytics,
prescriptive analytics can simulate and optimize blockchain systems so as to
improve the reliability of blockchain systems.

_2) Intelligent quality assurance of smart contracts._ Like computer software,
smart contracts may contain bugs or faulty programming codes, which are
vulnerable to crashes and malicious attacks. It is crucial to detect and
identify bugs in smart contracts so as to achieve the ultimate goal of
intelligent quality assurance of smart contracts. The work of [9] presents a
symbolic-execution platform namely Oyente to detect and recognize potential
bugs. Meanwhile, smart contracts are essentially program codes that are
sensitive to execution cost (e.g., the execution of smart contracts is charged
by gas in Ethereum). Thus, it is a necessity to identify the gas-costly
patterns and correct these vulnerable smart contracts. In [3], Chen et al.
developed a tool namely GASPER to identify and locate seven gas-costly
patterns via analyzing bytecodes of Ethereum smart contracts. Machine learning
methods can be used to detect and recognize vulnerable bugs in smart contracts
automatically. Moreover, the growing number of smart contracts also brings the
opportunities to automate the composition of multiple contracts. In
particular, we can find and identify contracts that fulfill users’
requirements and composite them together to realize more comprehensive
applications. Different from conventional distributed software systems such as
web services [11], smart contracts lack of semantic description and Quality-
of-Service (QoS) evaluation metrics. As a result, new AI-based approaches are
expected to automate labeling semantics of smart contracts and offer data-
driven QoS evaluation of smart contracts.

_3) Automated malicious behaviour detection._ The decentralized blockchain
systems result in the difficulty in auditing malicious behaviours such as
money laundering, phishing, gambling and scams that occurred in blockchain
platforms. Blockchain systems have generated massive transaction data, which
are essentially available to everyone, whereas the historical transaction data
are pseudonymous through anonymizing account addresses. The massive blockchain
data brings the opportunities in auditing and detecting malicious behaviours.
Big data analytics on massive blockchain data can help to identify malicious
users, recognize behaviour pattern, analyze market manipulation, detect scams.
The work of [12] presents a cross-graph analysis on Ethereum data and identify
several major activities occurring on Ethereum blockchain platforms. As in
[10], a machine learning based approach was proposed to detect and capture
Ponzi schemes that took place in Ethereum. The work of [13] analyzes the
leaked transaction history of Mt. Gox Bitcoin exchange and identify a number
of market manipulation patterns via singular value decomposition (SVD) method.
Moreover, malicious users may exploit multiple anonymous accounts to form a
criminal gang to conduct illegal activities on blockchain systems. New machine
learning approaches as well as association analysis on multiple accounts are
expected to address this issue.

The advances in AI, machine learning and big data analytics bring numerous
opportunities to address the aforementioned blockchain challenges. We next
present a case study to demonstrate the feasibility of blockchain
intelligence.

##  IV Case study

Big data analytics of blockchain data is beneficial to fraud recognition of
transactions and vulnerability detection of smart contracts. However, it is
also challenging to conduct big data analytics of blockchain data. 1) It is
extremely time consuming to download the entire blockchain data due to the
bulky blockchain size, e.g., it took more than one week and over 500 GB
storage space to fully synchronize (i.e., download) the entire Ethereum at a
newly-joined peer. 2) It requires substantial efforts in extracting and
processing blockchain data. First, blockchain data is stored at clients in
heterogeneous and complex data structures, which cannot be directly analyzed.
Meanwhile, the underlying blockchain data is either binary or encrypted. Thus,
it is a necessity to extract and process binary and encrypted blockchain data
so as to obtain valuable information while this process is non-trivial as
conventional data analytic methods may not work for this type of data. 3)
There is no general data extract tool for blockchain data. Although several
open source tools for blockchain data extraction are available, most of them
can only support to extract partial blockchain data (not the entire data).

###  IV-A Data Extraction from Ethereum

To address the above challenges, we propose a blockchain data analytics
framework namely XBlock-ETH to analyze Ethereum data. In particular, we
extract raw data consisting of 8,100,000 blocks of Ethereum. Fig. 3(a)
illustrates the typical Ethereum transaction execution flow from Block $N$ to
EVM through blockchain peer. During this procedure, we collect the three types
of blockchain raw data: Block, Receipt and Trace. Since the analysis on the
raw blockchain data is difficult, we process and categorize the obtained
Ethereum Blockchain data into six datasets: (1) Block and Transaction, (2)
Internal Ether Transaction, (3) Contract Information, (4) Contract Calls, (5)
ERC20 Token Transactions, (6) ERC721 Token Transactions as shown in Fig. 3(b).
It is non-trivial to process the raw since it requires substantial efforts in
extracting useful information from raw data and associating with six datasets.

Figure 3: Data processing during Ethereum transaction flow

We then conduct statistic analysis on these refined datasets. In Ethereum, a
miner has a higher priority to package the transactions with higher “gasPrice”
into the block. The visualization of “gasPrice” is shown in Fig. 4. In a macro
view (as shown in Fig. 4(a)), the “gasPrice” is gradually decreasing with the
development of the Ethereum community, except for several peaks caused by
extremely frequent transaction when the network is congested. In a micro view
(as shown in Fig. 4(b)), we extract the time from 8,000,000 to 8,020,000
blocks and find that such fluctuations of “gasPrice” can be observed by the
tidal law. This observation implies that the fluctuations of “gasPrice” can
potentially be predicted.

###  IV-B Detection Ponzi Schemes from Ethereum

Blockchain can also be exploited to conduct illegal activities such as scams.
For example, in [10], we propose a method to detect Ponzi scams in Ethereum
blockchain through extracting and analyzing key characteristics of user
accounts and operation codes in Ethereum contracts. Fig. 5 makes a comparison
between a normal contract and a Ponzi scheme contract in terms of Ether Flow
Graph, where the horizontal axis denotes the time line, the vertical axis
represents the number of participants in a particular contract, red circles
and blue circles denote the investment transactions and payment transactions,
respectively. In addition, the size of circle also represents the amount of
transactions, i.e., the larger circle means the larger amount of transactions.

Fig. 5(a) is a normal lottery contract while Fig. 5(b) shows a typical Ponzi
scam (namely Rubixi). We can observe several significant differences between
Fig. 5(a) and Fig. 5(b): 1) there are more participants in Fig. 5(b) than Fig.
5(a); 2) there are more payment transactions in Fig. 5(b) than Fig. 5(a) which
exhibits more randomness in the number of transactions. After extracting the
key features and applying other data mining and machine learning methods, we
can successfully classify Ponzi scams from other normal activities.

(a) Macro view of GasPrice

(b) Micro view of GasPrice

Figure 4: Data visualization of Gas Price of Ethereum

##  V Conclusion and future directions

(a) LooneyLottery contract (i.e., normal contract)

(b) Rubixi contract (i.e., Ponzi scam contract)

Figure 5: Ether Flow Graph of two smart contracts [10].

This article first reviews the blockchain technologies and analyze the
challenges in blockchain systems. We then introduce artificial intelligence
(AI) as well as opportunities brought by AI to blockchain systems. We name
such integration of blockchain and AI as _blockchain intelligence_. We mainly
discuss that AI bring benefits to blockchain in aspects of _intelligent
operational maintenance of blockchain_ , _intelligent quality assurance of
smart contracts_ and _automated malicious behaviour detection_. In addition,
we also give a case study to further demonstrate great potentials of
blockchain intelligence.

We believe that the integration of AI with blockchain technology will further
drive the benignant development of blockchain systems. We outline the future
directions in blockchain intelligence as follows.

  * •

_Real-time and automated operational maintenance of blockchain._ Instead of
performance monitoring and fault detection, the future intelligent operational
blockchain systems are expected to conduct real-time monitoring on multiple
performance metrics of blockchain systems and achieve the automated restoring
from crash spots.

  * •

_Collective intelligence bestowing smart contracts._ The current QoS assurance
approaches of smart contracts are mainly based on the analysis on contract
patterns (i.e., detecting and classifying vulnerable contracts) at a sole peer
in the blockchain. In contrast to a single intelligent agent, _collective
intelligence_ can motivate all participants to engage in analyzing and
reasoning, thereby contributing their collective knowledge to make better
decision in a global context. In the future, collective intelligence is
expected to integrate with decentralized blockchain system so as to offer a
trustworthy and intelligent provision of blockchain services.

  * •

_Integrating multiple machine learning approaches to monitor and supervise
blockchain data._ Decentralization of blockchain brings the difficulty in
monitoring and supervising transactions in blockchain platforms, consequently
resulting in a number of illegal behaviours. Meanwhile, both heterogeneity and
pseudonymity of blockchain data make this situation even worse. In the future,
multiple machine learning approaches should be integrated together to extract
key features from different types of blockchain data. In addition, a dynamic
graph (or network) of transactions is also expected to identify the
association between different accounts so as to recognize the malicious
behaviours.

## References

  * [1] X. Li, P. Jiang, T. Chen, X. Luo, Q. Wen, “A survey on the security of blockchain systems”, Future Generation Computer Systems, 2017, https://doi.org/10.1016/j.future.2017.08.020.
  * [2] N. Szabo, “The idea of smart contracts”, Nick Szabo’s Papers and Concise Tutorials. http://www.fon.hum.uva.nl/rob/Courses/InformationInSpeech/CDROM/Literature/LOTwinterschool2006/szabo.best.vwh.net/smart_contracts_2.html
  * [3] T. Chen, X. Li, X. Luo, X. Zhang, “Under-optimized smart contracts devour your money”, Proceedings of 24th International Conference on Software Analysis, Evolution and Reengineering (SANER), 2017, pp. 442–446.
  * [4] J. Bonneau, J. Clark, S. Goldfeder, “On bitcoin as a public randomness source”, IACR Cryptology ePrint Archive, 1015, 2015
  * [5] The DAO, The Hack, The Soft Fork and The Hard Fork (2017). https://www.cryptocompare.com/coins/guides/the-dao-the-hack-the-soft-fork-and-the-hard-fork/
  * [6] P. Zheng, Z. Zheng, X. Luo, X. Chen, X. Liu, “A detailed and real-time performance monitoring framework for blockchain systems,” 2018 IEEE/ACM 40th International Conference on Software Engineering: Software Engineering in Practice Track, pp. 134–143, 2018. (conference proceedings)
  * [7] H.-N. Dai et al., “Big data analytics for large-scale wireless networks: Challenges and opportunities,”, ACM Computing Surveys, vol. 52, no. 5, 2019
  * [8] T. T. A. Dinh, R. Liu, M. Zhang, G. Chen, B. C. Ooi and J. Wang, “Untangling Blockchain: A Data Processing View of Blockchain Systems,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 7, pp. 1366-1385, 1 July 2018
  * [9] L. Luu, D.-H. Chu, H. Olickel, P. Saxena, and A. Hobor, “Making Smart Contracts Smarter,”Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security (CCS ’16), 2016
  * [10] W. Chen, Z. Zheng, J. Cui, E. Ngai, P. Zheng, and Y. Zhou, “Detecting Ponzi Schemes on Ethereum: Towards Healthier Blockchain Technology,” Proceedings of the 2018 World Wide Web Conference (WWW ’18), 1409-1418.
  * [11] P. Rodriguez-Mier, C. Pedrinaci, M. Lama and M. Mucientes, “An Integrated Semantic Web Service Discovery and Composition Framework,” IEEE Transactions on Services Computing, vol. 9, no. 4, pp. 537-550, 1 July-Aug. 2016.
  * [12] T. Chen et al., “Understanding Ethereum via Graph Analysis,”IEEE INFOCOM 2018 - IEEE Conference on Computer Communications, 2018, pp. 1484-1492.
  * [13] W. Chen et al., “Market Manipulation of Bitcoin: Evidence from Mining the Mt. Gox Transaction Network”,IEEE Conference on Computer Communications, 2019, pp. 964-972.
  * [14] T. N. Dinh and M. T. Thai, “AI and Blockchain: A Disruptive Integration”, Computer, vol. 51, no. 9, pp. 48-53, September 2018.
  * [15] Nassar, M, Salah, K, ur Rehman, MH, Svetinovic, D., “Blockchain for explainable and trustworthy artificial intelligence”, WIREs Data Mining Knowl Discov, 2020; 10:e1340. https://doi.org/10.1002/widm.1340


# Multitrees in random graphs

Alan Frieze and Wesley Pegden
Department of Mathematical Sciences
Carnegie Mellon University
Pittsburgh PA 15213 Research supported in part by NSF grant DMSResearch
supported in part by NSF grant DMS

###### Abstract

Let $N=\binom{n}{2}$ and $s\geq 2$. Let
$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of
the edges $E(K_{n})$ of the complete graph $K_{n}$. A MultiTree is a set
$I\subseteq[N]$ such that the edge sets $E_{I,j}$ induce spanning trees for
$j=1,2,\ldots,s$. In this paper we study the following question: what is the
smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a
hitting time result for $s=2$ and an $O(n\log n)$ bound for $s\geq 3$.

##  1 Introduction

Let $N=\binom{n}{2}$ and $s\geq 2$. Let
$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$ be $s$ independent permutations of
the edges $E(K_{n})$ of the complete graph $K_{n}$. Let ${\bf
e}_{i}=(e_{i,1},e_{i,2},\ldots,e_{i,s})$ and for $I\subseteq[N]$ let
$E_{I,j}=\left\\{e_{i,j}:i\in I\right\\}$ for $j=1,2,\ldots,s$. A MultiForest
is a set $I\subseteq[N]$ such that the edge sets $E_{I,j}$ induce forests for
$j=1,2,\ldots,s$. A MultiTree is a MultiForest in which each forest is a
spanning tree. In this paper we study the following question: what is the
smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree.

This is a particular case of the following more general question: given
matroids ${\mathcal{M}}_{1},{\mathcal{M}}_{2},\ldots,{\mathcal{M}}_{s}$ over a
common ground set $E=\left\\{e_{1},e_{2},\ldots,e_{M}\right\\}$ let

${\cal I}_{k}=\left\\{I\in\binom{[M]}{k}:\;\left\\{e_{i},i\in I\right\\}\text{
is independent in }{\mathcal{M}}_{i},i=1,2,\ldots,s\right\\}.$

Then let $m^{*}=\max\left\\{k:{\cal I}_{k}\neq\emptyset\right\\}$. Then we can
ask what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a member of
${\cal I}_{m^{*}}$. In general this is a rather challenging question, mainly
because the structure of randomly chosen matroids is not as well understood as
the structure of random graphs.

There is at least one instance where we already have a precise answer to the
above matroid question. We let $M=N$ and let ${\mathcal{M}}_{1}$ be the
graphic matroid of $K_{n}$. For ${\mathcal{M}}_{2}$ we randomly color each
edge $e\in E(K_{n})$ uniformly with $c(e)\in C,|C|\geq n-1$ and
${\mathcal{M}}_{2}$ is the partition matroid where a set $I\subseteq E(K_{n})$
is independent if $e_{1},e_{2}\in I$ implies that $c(e_{1})\neq c(e_{2})$. In
more familiar terminology, $I$ is rainbow colored. This problem was solved in
Frieze and McKay [5] where it was shown that w.h.p. $m^{*}$ is the smallest
integer $m$ such that the graph induced by $e_{1},e_{2},\ldots,e_{m}$ is (i)
connected and (ii) $|\left\\{c(e_{i}):i=1,2,\ldots,m\right\\}|\geq n-1$.

Going back to MultiTree’s, we prove two theorems.

######  Theorem 1.

We have w.h.p. that $m^{*}=O(n\log n)$.

When $s=2$ we can use Edmond’s theorem [2] to prove the following: let
$\Gamma_{j,m}=([n],E_{[m],j})$.

######  Theorem 2.

W.h.p. $m^{*}=\max\left\\{m_{1},m_{2}\right\\}$ where for $j=1,2$,
$m_{j},=\min\left\\{m:\Gamma_{j,m}\text{ is connected}\right\\}$.

There is no actual need to restrict attention to matroid intersection. For
example let $I$ be a Multimatching if the sets $E_{I,j},j=1,2,\ldots,s$ induce
matchings and let $I$ be a MultiPerfectMatching if $|I|={\left\lfloor
n/2\right\rfloor}$ i.e. if the associated matchings are (near) perfect.

######  Theorem 3.

W.h.p. $[m]$ contains a MultiPerfectMatching if $m\geq Kn\log n$ for some
absolute constant $K$.

One thing missing from this paper is what might be called MultiHamiltonCycle,
where the edge sets $E_{I,j},j=1,2,\ldots,s$ induce Hamilton cycles. We have
no results on this at present, but we conjecture that $m\geq Kn\log n$ should
be enough for the existence of such a structure, w.h.p.

##  2 Proof of Theorem 1

Phase 1: In this phase we greedily add $s$-tples until we have a MultiForest
of linear size. Consider the following construction: let $I_{0}=\emptyset$ and
$k_{0}=0$. After $t$ steps we will have a MultiForest
$I_{t}=\left\\{k_{1}=1,k_{2},\ldots,k_{t}\right\\}$. Given $I_{t}$ we say that
an $s$-tple ${\bf e}_{k}$ is addable to $I_{t}$ if
$I_{t}\cup\left\\{k\right\\}$ is a MultiForest. Let
$k_{t+1}=\min\\{k>k_{t}:{\bf e}_{k}$ is addable to $I_{t}\\}$. We let
$F_{t,j}$ denote the forest induced by
$\left\\{e_{k_{i},j}:i=1,\ldots,t\right\\}$. We stop this greedy process after
we have constructed $I_{m_{0}}$ where $m_{0}$ is defined below.

To analyse this process, we need to understand the component structure of the
forests $F_{t,j}$. Consider the ordinary graph process
$\Gamma_{i},i=1,2,\ldots,N$. For $r\geq 1$, let
$a_{\ell}=\min\left\\{r:\Gamma_{r}\text{ has $n-\ell$ components}\right\\}$.
The distribution of component sizes in $F_{\ell,j}$ will be the same as the
distribution of component sizes in $\Gamma_{a_{\ell}}$. This follows by
induction on $\ell$. In all cases, we merge two components with probability
proportional to the product of their sizes.

Recall next that if $c>1$ is a constant then w.h.p. the random graph
$\Gamma_{cn/2}$ has $\approx\kappa(c)n$ components and a unique giant
component of size $\approx ng(c)$ where $\kappa(c),g(c)$ are known functions
of $c$. For a proof of this, see for example Frieze and Karoński [4], Chapter
2.

Suppose now that we let $c_{0}=g^{-1}(1/2)$. Thus w.h.p. $G_{n,c_{0}n/2}$
contains a unique giant component of size $\approx n/2$. With regard to our
greedy process, after examining some number of $s$-tples we will w.h.p. have
constructed a multi-forest $I_{m_{0}}$ on $m_{0}\approx n(1-\kappa(c_{0}))$
$s$-tuples, where each individual forest $F_{m_{0},j}$ (i) contains a giant
tree of size $\approx n/2$ and (ii) has $n_{0}=n-m_{0}-2$ small components.
The vertices of forest $F_{m_{0},j}$ not in $T_{j}$ form a collection $S_{j}$
of small trees $T_{1,j},T_{2,j}\ldots,T_{n_{0},j}$, each of size $O(\log n)$.

We next consider as to how long we have to run this part of the process
altogether. We first consider the time taken to get giant trees of size
$\approx n/2$. We know that w.h.p. up until we have added $c_{0}n$ $s$-tples
the probability that an $s$-tple f can be added to our forest is at least
$\gamma\approx\left(\frac{3}{4}\right)^{s}$. This is because (i) the larger
the forest, the less likely a random edge can be added without creating a
cycle and (ii) unless a random edge has both vertices in the giant, it is
unlikely to create a cycle. This follows from the fact that w.h.p. each non-
giant component is of size $O(\log n)$, in which case the the probability of
choosing an edge with both vertices in the same small component is
$O(n\times\left(\frac{\log n}{n}\right)^{2})$. Thus w.h.p. it requires at most
$\frac{2c_{0}n}{\gamma}$ iterations to produce a giant tree of size $n/2$.

Phase 2: We now discuss how we can complete $I_{m_{0}}$ to a multi-tree. An
$s$-tuple ${\bf e}_{u}$ will be acceptable if for each $j\in[s]$, the edge
$e_{u,j}$ has one vertex $x_{u,j}\in A_{j}=[n]\setminus V(T_{j})$ and the
other $y_{u,j}\in T_{j}$. An acceptable $s$-tple defines an edge in a random
$s$-uniform multi-partite hypergraph $H$ with edges in $A_{1}\times
A_{2}\times\cdots\times A_{s}$. The vertices of $H$ are $A_{1}\sqcup
A_{2}\sqcup\cdots\sqcup A_{s}$.

We continue the process of adding acceptable $s$-tples until $H$ contains a
set of edges $(x_{t,1},x_{t,2}\ldots,x_{t,s}),t\in K$ for some set $K$ of size
$n_{0}$ that satisfies the following property: if $X_{j}=\left\\{x_{t,j}:t\in
K\right\\}$ then $|X_{j}\cap V(T_{l,j})|=1$ for all $1\leq i\leq n_{0},1\leq
j\leq s$. This ensures that for each $j$ and each non-giant tree $T$ of
$F_{m_{0},j}$ that exactly one of the $n_{0}$ edges added to the $j$th forest
joins $T$ and the giant $T_{j}$, thus creating a MultiTree. We call such
matchings MultiTree inducing.

We next consider the number of random $s$-tples we need to generate before we
have a MultiTreeinducing matching in $H$ w.h.p. Suppose now that $T_{i,j}$ has
$t_{i,j}$ vertices for $i=1,2,\ldots,n_{0},j=1,2,\ldots,s$. We consider the
hypergraph ${\mathcal{H}}$ with vertex set $X$ equal to the edges of the
complete $s$-partite hypergraph ${\mathcal{A}}_{s}$ on $A_{1}\times
A_{2}\times\cdots\times A_{s}$. An edge of ${\mathcal{H}}$ corresponds to a
MultiTree inducing matching of ${\mathcal{A}}_{s}$. We will argue that w.h.p.
$O(n\log n)$ randomly chosen vertices of ${\mathcal{H}}$ contain an edge of
${\mathcal{H}}$. To do this we will use a recent breakthrough result of
Frankston, Kahn, Narayanan and Park [3]. For this we need a definition. For a
set $S\subseteq X=V({\mathcal{H}})$ we let $\langle
S\rangle=\left\\{T:\;S\subseteq T\subseteq X\right\\}$ denote the subsets of
$X$ that contain $S$. We say that ${\mathcal{H}}$ is $\kappa$-spread if

$|{\mathcal{H}}\cap\langle
S\rangle|\leq\frac{|{\mathcal{H}}|}{\kappa^{|S|}},\quad\forall S\subseteq X.$

The following theorem is from [3]

######  Theorem 4.

Let ${\mathcal{K}}$ be an $r$-uniform, $\kappa$-spread hypergraph and let
$X=V({\mathcal{K}})$. There is an absolute constant $C>0$ such that if

$m\geq\frac{(C\log r)|X|}{\kappa}$ (1)

then w.h.p. $X_{m}$ contains an edge of ${\mathcal{K}}$. Here w.h.p. assumes
that $r\to\infty$.

To apply the lemma we prove

######  Lemma 5.

W.h.p., ${\mathcal{H}}$ is $\kappa$-spread, where $\kappa=(n_{0}/3)^{s-1}$.

###### Proof.

We begin with the claim that

$|{\mathcal{H}}|=n_{0}!^{s-1}\prod_{i=1}^{n_{0}}\prod_{j=1}^{s}t_{i,j}.$ (2)

We justify (2) as follows: if we fix a $j$ then there are
$\prod_{i=1}^{n_{0}}t_{i,j}$ ways of choosing a single vertex from each
$T_{i,j}$. After this, there are $n_{0}!$ ways of ordering these choices
giving $\tau_{j}$ choices altogether. We then multiply the $\tau_{j}$ together
to get the number choices for an edge ordered MultiTree inducing matching. We
divide by $n_{0}!$ to remove the overcount due to ordering.

Suppose now that $S\subseteq X$ and $|S|=k$ and ${\mathcal{H}}\cap\langle
S\rangle\neq\emptyset$. Each element of $S$ is an $s$-tple. Let $S_{j}$ denote
the $j$th component of the tples of $S$. Then

$|{\mathcal{H}}\cap\langle S\rangle|=(n_{0}-k)!^{s-1}\prod_{i\notin
S_{j}}\prod_{j=1}^{s}t_{i,j}$

So, if $k<n_{0}$ then

$\frac{|{\mathcal{H}}\cap\langle
S\rangle|}{|{\mathcal{H}}|}\leq\left(\frac{(n_{0}-k)!}{n_{0}!}\right)^{s-1}\leq\left(2\cdot\frac{(n_{0}-k)^{n_{0}-k}e^{n_{0}}(2\pi
n_{0})^{1/2}}{n_{0}^{n_{0}}e^{n_{0}-k}(2\pi(n_{0}-k))^{1/2}}\right)^{s-1}<\left(\frac{2^{1/k}\exp\left\\{\frac{1}{2(n_{0}-k)}+\frac{k}{n_{0}}\right\\}}{n_{0}}\right)^{k(s-1)},$

and the lemma follows. ∎

In the application of Theorem 4 we have $r=sn_{0}$ and $|X|\approx(n/2)^{s}$.
Applying the theorem we see that $C_{1}n\log n$ acceptable $s$-tples suffice
to contain a MultiTree-inducing matching w.h.p. (Here we can take
$C_{1}=(3\nu_{0})^{s-1}2^{-s}C$ where $\nu_{0}=n/n_{0}=O(1)$ w.h.p.) An
$s$-tple is acceptable with probability $\approx 2^{-2s}$ and so w.h.p. we
need at most $2^{2s+1}Cn\log n$ $s$-tples overall before we obtain a MultiTree
w.h.p. This completes the proof of Theorem 1.

##  3 Proof of Theorem 2

For the special case of $k=2$, we can use Edmond’s analysis [2] of the matroid
intersection problem. Let
$X_{m}=\left\\{(e_{i},f_{i}):i=1,2,\ldots,m\right\\}$ be the set of pairs of
random edges selected and let $\Gamma_{1,m},\Gamma_{2,m}$ be the two copies of
$G_{n,m}$ induced by $X_{m}$. For $A\subseteq X_{m}$ let $\Gamma_{1,m}(A)$ be
the subgraph of $\Gamma_{1,m}$ induced by the set of edges $e_{i},i\in A$.
Define $\Gamma_{2,m}(A)$ similarly. We have to show that w.h.p. that for all
$A\subseteq X_{m}$, we have

$\kappa(A)=\kappa_{1}(A)+\kappa_{2}(X_{m}\setminus A)\leq n+1.$

Here $\kappa_{i}(A),i=1,2$ denotes number of components in the graph
$\Gamma_{i,m}(A)$.

Throughout this section: $N=\binom{n}{2}$ and

$m=\tfrac{1}{2}n(\log n+O(\log\log n))\text{ and }p=\frac{m}{N}.$

For $I\subseteq[m]$, we let $e(I)=\left\\{e_{i}:i\in I\right\\}$ and
$f(I)=\left\\{f_{i}:i\in I\right\\}$ (with respect to
$X_{m}=\left\\{(e_{i},f_{i}):i=1,\dots,m\right\\}$).

In the context of $G_{n,p}$, given a set of edges $A$, we let
$V_{m}(A),V_{p}(A)$ be the set of vertices of $G_{n,m},G_{n,p}$ induced by $A$
and we let $v_{m}(A)=|V_{m}(A)|$ and $v_{p}(A)=|V_{p}(A)|$. Conversely, for a
set of vertices $S$ let $E_{m}(S),E_{p}(S)$ denote the set of edges of
$G_{n,m},G_{n,p}$ induced by $S$ and let
$e_{m}(S)=|E_{m}(S),e_{p}(S)=|E_{p}(S)|$. For a set of vertices $S$ let
$b_{m}(S)=e_{m}(S)/|S|,b_{p}(S)=e_{p}(S)/|S|$.

#### Universal Parameters

$\omega=\log^{2/5}n;\ \varepsilon=\frac{1}{\omega};\
\theta_{0}=\frac{5\log\log n}{\log n};\ \sigma_{0}=\frac{10\omega^{2}\log\log
n}{\log n};\ a_{max}=\frac{m}{2n\log n}\approx\frac{1}{4};\ s_{1}=\frac{\log
n}{10\log\log n}.$ (3)

Define $\sigma(a)$ by

$an\log
n=(1+\varepsilon)\binom{\sigma(a)n}{2}p=(1+\varepsilon)\binom{\sigma(a)n}{2}\frac{m}{N},$

so that this is roughly the order of a subgraph expected to have $an\log n$
edges. Then,

$\sigma(a)=\left(\frac{2a(1+\theta)}{1+\varepsilon}\right)^{1/2}\text{ where
}|\theta|\leq\theta_{0}.$ (4)

We now bound $\kappa(A)=\kappa_{1}(A)+\kappa_{2}(X_{m}\setminus A)$ for
$A\subseteq X$ with various ranges for

$|A|=an\log n\leq|X_{m}\setminus A|.$

We begin each case analysis with a structural lemma. Let

$I_{conn}=[m_{-},m_{+}]\text{ where }m_{-}=\tfrac{1}{2}n(\log n-\log\log
n),\,m_{+}=\tfrac{1}{2}n(\log n+\log\log n).$

We consider the graph process $\mathcal{G}=(G_{m},m=0,1,\ldots,N)$ where as
usual $G_{m+1}$ is obtained from $G_{m}$ by adding a random edge. We say that
$\mathcal{G}$ holds property ${\mathcal{P}}$ strongly if w.h.p.
$G_{m}\in{\mathcal{P}}$ simultaneously for all $m\in I_{conn}$. We note that
$G_{m}$ is distributed as $G_{n,m}$ and we when we refer to $G_{p}$ we mean
$G_{n,p}$ for $p=m/N$, for some $m\in I_{conn}$.

###  3.1 First Structural Lemmas

We will assume from now on that $A$ induces components
$C_{1},C_{2},\ldots,C_{\ell}$ in $\Gamma_{1,m}$, where

$1=|C_{1}|=\cdots=|C_{k}|<|C_{k+1}|\leq\cdots\leq|C_{\ell}|.$

######  Lemma 6.

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$ and
$m\in I_{conn}$.

  1. (a)

If $|S|\geq\sigma_{0}n$ then $e_{m}(S)\in(1\pm\varepsilon)\binom{s}{2}p$.

  2. (b)

If $|S|\leq n_{0}=\frac{n}{\log^{3}n}$ then $b_{m}(S)\leq 2$.

  3. (c)

Let $i_{0}=\max\left\\{i:|C_{i}|\leq n_{0}\right\\}$. Then $|\ell-
i_{0}|\leq\log^{3}n$.

  4. (d)

$e_{1,m}(C_{1})+\cdots+e_{1,m}(C_{i_{0}})\leq
2(|C_{1}|+\cdots+|C_{i_{0}}|)\leq 2n$.

As with most of the structural lemmas, the proof of Lemma 6 is deferred to an
appendix.

We break the possible range for $a$ into 3 intervals. We show for each
individual range that the assumption $\kappa(A)>n+1$ leads w.h.p. to a
contradiction.

###  3.2 Case 1: $a_{1}=10^{-3}\leq a\leq a_{\max}$

######  Lemma 7.

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$ and
$m\in I_{conn}$ and $a_{1}\leq a\leq a_{\max}$.

  1. 1.

If $|A|=an\log n$ then $v_{m}(A)\geq\sigma(a)n$.

  2. 2.

$|C_{k+1}|+\cdots+|C_{\ell}|\geq\left(\frac{2a(1-\theta_{0})}{1+\varepsilon}\right)^{1/2}n$.

  3. 3.

$i_{0}\leq\left(1-\frac{(2a-3\theta_{0})^{1/2}}{1+\varepsilon}\right)n$.

If $|A|=an\log n$ where $a_{1}\leq a\leq a_{max}$ and using that $m\in
I_{conn}$,

$|X_{m}\setminus A|=m-an\log n=\left(\frac{1}{2}-a+O\left(\frac{\log\log
n}{\log n}\right)\right)n\log n.$

Applying Lemma 6(c) and Lemma 7(c) we see that

$\kappa(A)\leq\left(\left(1-\frac{(2a-3\theta_{0})^{1/2}}{1+\varepsilon}\right)+\left(1-\frac{(1-2a-3\theta_{0})^{1/2}}{1+\varepsilon}\right)\right)n+2\log^{3}n.$
(5)

Using that

$(2a-3\theta_{0})^{1/2}=(2a)^{1/2}\left(1-\frac{3\theta_{0}}{2a}\right)^{1/2}\geq(2a)^{1/2}\left(1-\frac{3\theta_{0}}{4a}\right)\geq(2a)^{1/2}-\frac{2\theta_{0}}{a^{1/2}},$

we have then that

$\kappa(A)\leq
2\log^{3}n+\left(2+\frac{2\theta_{0}}{a^{1/2}}+\frac{2\theta_{0}}{(1-2a)^{1/2}}-\frac{(2a)^{1/2}+(1-2a)^{1/2}}{1+\varepsilon}\right)n.$

But if $x=2a<1$ then

$x^{1/2}+(1-x)^{1/2}\geq x^{1/2}+1-\frac{x}{2}\geq 1+\frac{x^{1/2}}{2}.$

So,

$\displaystyle\kappa(A)$ $\displaystyle\leq
2\log^{3}n+\left(2+\frac{2\theta_{0}}{a^{1/2}}+\frac{2\theta_{0}}{(1-2a)^{1/2}}-\frac{1+a^{1/2}}{1+\varepsilon}\right)n$
$\displaystyle\leq
2\log^{3}n+\left(1+\frac{2\theta_{0}}{a^{1/2}}+\frac{2\theta_{0}}{(1-2a)^{1/2}}+\frac{\varepsilon-a^{1/2}}{1+\varepsilon}\right)n\leq
n.$

since $a^{1/2}\geq
a_{1}^{1/2}\gg\max\left\\{\varepsilon,\tfrac{\log^{3}n}{n}\right\\}$ and
$a_{1}\gg\theta_{0}$.
End of Case 1

###  3.3 Another structural lemma

######  Lemma 8.

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$.

  1. (a)

If $S$ induces a bridgeless subgraph which is not an induced cycle, then
$|S|\geq s_{1}=\frac{\log n}{10\log\log n}$.

  2. (b)

There are at most $n^{1/2}$ cycles of length at most $s_{1}$.

In what follows, we will assume that $A$ maximises $\kappa(A)$ subject to
$|A|\leq a_{1}n\log n$. Suppose also that $|A|$ is as small as possible
subject to this maximisation.

######  Remark 1.

If $C_{i}$ is not an isolated vertex, then we can assume that $C_{i}$ has no
bridges. If $e_{i},i\in A$ is a bridge of $\Gamma_{1,m}(A)$ then replacing $A$
by $A\setminus\left\\{i\right\\}$ does not decrease $\kappa(A)$ and decreases
$|A|$.

We can therefore assume that

$1=|C_{1}|=\cdots=|C_{k}|<3\leq|C_{k+1}|\leq\cdots\leq|C_{\ell}|,$ (6)

where $C_{k+1},\ldots,C_{\ell}$ are bridgeless.

######  Lemma 9.

The following hold strongly in $\mathcal{G}$: if $a_{2}:=3n^{-4/25}\leq a\leq
a_{1}$ then $e_{m}(S:\bar{S})\geq 2an\log n$ for all $S,|S|\in[10an,n-10an]$.

######  Remark 2.

If follows from Lemma 9 that if $a_{2}\leq a\leq a_{1}$ then w.h.p.
$\Gamma_{2,m}(X_{m}\setminus A)$ contains a component of size $n-10an$.

###  3.4 Case 2: $a_{2}=3n^{-4/25}\leq a<a_{1}=10^{-3}$

######  Lemma 10.

The following hold strongly in $\mathcal{G}$: if $a_{2}\leq a\leq a_{1}$ and
$|S|\leq 12an$ then $b_{m}(S)<\frac{\log n}{12}$.

It follows from Lemma 8(a)(b) and Remark 2 that if $a\geq a_{2}$ then with $k$
as in (6),

$\kappa(A)\leq
k+\frac{n-k}{s_{1}}+n^{1/2}+10an+1\leq\left(n-(n-k)\left(1-\frac{10\log\log
n}{\log n}\right)\right)+11an.$ (7)

Explanation: In $\Gamma_{1,m}$ there are $k$ isolated vertices plus at most
$(n-k)/s_{1}$ bridgeless non-cycle components/large cycles plus at most
$n^{1/2}$ small cycles. In $\Gamma_{2,m}$ there is one giant component plus at
most $10an$ vertices on small components.

Equation (7) implies that if $\kappa(A)\geq n$ then $n-k\leq 12an$. Lemma 10
gives us a contradiction in that w.h.p. $12an$ vertices do not induce $an\log
n$ edges.
End of Case 2

######  Lemma 11.

The following holds strongly in $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ where
we consider the two processes defined by $e_{i},f_{i},i=1,2,\ldots,N$:

  1. (a)

$\Gamma_{2,m}$ contains at most $\log^{12}n$ vertices of degree at most 10.

  2. (b)

The vertices of degree at most 10 in $\Gamma_{2,m}$ are at distance at least 3
from each other.

  3. (c)

If $f_{i},i\in I,\,|I|\leq 10\log^{12}n$ are incident with vertices of degree
at most 10 in $\Gamma_{2,m}$ then $\left\\{e_{i},i\in I\right\\}$ is not
contained in any set of at most $s_{1}|I|$ vertices that induce a 2-edge-
connected subgraph of $\Gamma_{1,m}$.

###  3.5 Case 3: $0<a<a_{2}$

######  Lemma 12.

The following holds strongly in $\mathcal{G}$: if $|S|\leq n^{9/10}$ then
$b_{m}(S)\leq 1+o(1)$.

Let $S^{*}=\bigcup_{j=k+1}^{\ell}C_{j}$ and $s^{*}=|S^{*}|$ and observe that
$m^{*}:=|A|=e_{1,m}(S^{*})$. We are left to consider the situation where we
delete $m^{*}\leq m_{1}=a_{2}n\log n=3n^{21/25}\log n$ edges from
$\Gamma_{2,m}(X_{m})$. Suppose that $\rho(m^{*})$ is the maximum number of
components obtainable by deleting $m^{*}$ edges from $\Gamma_{2,m}$. Since we
can assume there are no bridges in $\Gamma_{1,m}(A)$, any nontrivial component
in $\Gamma_{1,m}(A)$ has size at least 3 and we have that

$\kappa(A)\leq k+\frac{n-k}{3}+\rho(m^{*}).$ (8)

And

$m^{*}\approx n-k.$ (9)

This is because w.h.p. the number of edges in a bridgeless component of size
$3\leq s\leq n^{9/10}$ lies in $[s,(1+o(1))s]$ edges. The lower bound is true
for all such sets and the upper bound follows from Lemma 12.

Suppose that after removing $m^{*}$ edges from $\Gamma_{2,m}$ we have
components $K_{1},K_{2},\ldots,K_{\rho},\rho=\rho(m^{*})$ where
$|K_{1}|\leq|K_{2}|\leq\cdots\leq|K_{\rho}|$. We then know from Remark 2 that
$|K_{\rho}|\geq n-10a_{2}n$. We have from Lemma 12 that
$e_{2,m}(K_{i})\approx|K_{i}|$ for $1\leq i\leq\rho-1$. Let
$\text{deg}_{2}(v)$ denote the degree of vertex $v$ in $\Gamma_{2,m}$ and
$\text{deg}_{2}(X)=\sum_{x\in X}\text{deg}_{2}(x)$. For a fixed
$i\in[\rho-1]$, the set $f_{j},j\in A$ must contain
$\text{deg}_{2}(K_{i})-2e_{2,m}(K_{i})\geq\text{deg}_{2}(K_{i})-(2+o(1))|K_{i}|$
edges with exactly one end in $K_{i}$. Thus, if there are $\rho_{1}$ single
vertex components then

$m^{*}\geq\frac{1}{2}\sum_{i=1}^{\rho-1}(\text{deg}_{2}(K_{i})-(2+o(1))|K_{i}|)=\frac{1}{2}\sum_{i=1}^{\rho_{1}}\text{deg}_{2}(K_{i})+\frac{1}{2}\sum_{i=\rho_{1}+1}^{\rho-1}(\text{deg}_{2}(K_{i})-(2+o(1))|K_{i}|).$

Define $\rho_{0}\leq\rho_{1}$ such that, among the single-vertex components,
we have $\text{deg}_{2}(K_{i})\leq 10$ for $1\leq i\leq\rho_{0}$ and
$\text{deg}_{2}(K_{1})\geq 11$ for $\rho_{0}+1\leq i\leq\rho_{1}$. It follows
from Lemma 11(b) that at least half of the vertices in any non-trivial
$K_{i},i>\rho_{1}$ have degree at least 11. This is because the neighborhoods
of the low degree vertices are disjoint and non-empty. So,
$\text{deg}_{2}(K_{i})\geq 8|K_{i}|/2$ for all $i>\rho_{0}$. Thus,

$m^{*}\geq\frac{1}{2}\left(\rho_{0}+\frac{8(\rho-1-\rho_{0})}{2}\right)=\frac{8(\rho-1)}{4}-\frac{8\rho_{0}}{4}.$

The initial factor of $\tfrac{1}{2}$ arises because the same edge might be
counted twice, once for each of the $K_{i}$ that it is incident with.

It follows from Lemma 11(c) and (6) that $\rho_{0}\leq m^{*}/s_{1}$. (The
edges deleted from $\Gamma_{2,m}$ correspond to edges of bridgeless components
in $\Gamma_{1,m}$. And then Lemma 11(c) implies that each edge that was
deleted in $\Gamma_{2,m}$ to create $K_{i},i\leq\rho_{0}$ can be “charged” to
$s_{1}$ distinct edges of $\Gamma_{1,m}$.) So, $\rho-1\leq(4+o(1))m^{*}/8$. In
which case (8) and (9) imply that

$\kappa(A)\leq
k+(n-k)\left(\frac{1}{s_{1}}+\frac{1}{3}+\frac{4+o(1)}{8}\right)+1\leq n+1.$

End of Case 3

When $a=0$ we rely on the connectivity of both $\Gamma_{1,m},\Gamma_{2,m}$.

###  3.6 Hitting time

The essence of the above argument is that if $\Gamma_{1,m},\Gamma_{2,m}$ are
both connected and satisfy the conditions of Lemmas 6 – 12 then there is a
MultiTree. It is well known that the hitting time $m_{c}$ for connectivity and
minimum degree at least one satisfies $m_{c}\in[m_{-},m_{+}]$ w.h.p. Thus to
verify the claim for a hitting time, we only have to show that Lemmas 6 – 12
are valid for $G_{n,m},m\in[m_{-},m_{+}]$. The reader will observe that we
have been careful to do precisely this.

##  4 Proof of Theorem 3

We first consider a multi-partite version where the edges $e_{i,s}$ are drawn
from disjoint copies of the edges of the complete bipartite graph $K_{n,n}$.
In this case, MultiPerfectMatching’s are in 1-1 correspondence with perfect
matchings in the complete $2s$-uniform multi-partite hypergraph with edges set
$[n]^{2s}$. As such it is known that a random set of $Kn\log n$ edges is
sufficient for a perfect matching w.h.p. It is tempting to take $K=1$ and
refer to Kahn [7], [8]. On the other hand, one can legitimately cite [6] or
[1] and get some constant $K$.

With the above case in hand, one gets Theorem 3 by partitioning $[n]$ randomly
into $2s$ parts of $V_{1},V_{2},\ldots,V_{2s}$ of size ${\left\lfloor
n/2s\right\rfloor}$ and discarding at most $2s-1$ vertices. Then we only
consider those ${\bf e}_{i}=(x_{1},x_{2},\ldots,x_{2s})$ and appeal to the
above multi-partite version.

If we want to assume that $n$ is even and consider $s$ perfect matchings in
$K_{n}$ then we can partition $[n]$ into two sets $A,B$ of size $n/2$ and only
consider those ${\bf e}_{i}$ where all the $e_{i,j}$ have one end in $A$ and
the other in $B$. We then have to inflate the $K$ of the first paragraph by at
most $2^{s}$. This idea can be extended to deal with tree factors as in Łuczak
and Ruciński [9].

##  5 Final Remarks

We have proved some threshold results for the intersections of cycle matroids.
It would be of interest to extend this to other classes of matroid, e.g.
binary matroids. There is also the analogous problem with respect to Hamilton
cycles. This seems to be more difficult.

## References

  * [1] D. Bal and A.M. Frieze, Rainbow Matchings and Hamilton Cycles in Random Graphs, Random Structures and Algorithms 48 (2016) 503-523.
  * [2] J. Edmonds, Submodular functions, matroids, and certain polyhedra”, in R. Guy; H. Hanam; N. Sauer; J. Schonheim (eds.), Combinatorial structures and their applications (Proc. 1969 Calgary Conference), Gordon and Breach, New York, pp. 69-87.
  * [3] K. Frankston, J. Kahn, B. Narayanan and J. Park, Thresholds versus fractional expectation thresholds.
  * [4] A.M. Frieze and M. Karoński, Introduction to Random Graphs, Cambridge University Press, 2015.
  * [5] A.M. Frieze and B. McKay, Multicoloured trees in random graphs, Random Structures and Algorithms 5 (1994) 45-56.
  * [6] A. Johansson, J. Kahn and V. Vu, Factors in Random Graphs, Random Structures and Algorithms 33 (2008) 1-28.
  * [7] J. Kahn, Asymptotics for Shamir’s Problem.
  * [8] J. Kahn, Hitting times for Shamir’s Problem.
  * [9] T. Łuczak and A. Ruciński, Tree-matchings in graph processes, SIAM Journal on Discrete Mathematics 4 (1991) 107-120.

##  Appendix A Proof of Structural Lemmas

#### Universal Parameters

$\omega=\log^{2/5}n;\quad\varepsilon=\frac{1}{\omega};\quad\theta_{0}=\frac{5\log\log
n}{\log n};\quad\sigma_{0}=\frac{10\omega^{2}\log\log n}{\log n};\quad
a_{max}=\frac{m}{2n\log n}\approx\frac{1}{4}.$

#### Lemma 6

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$ and
$m\in I_{conn}$.

  1. (a)

If $|S|\geq\sigma_{0}n$ then $e_{m}(S)\in(1\pm\varepsilon)\binom{s}{2}p$.

  2. (b)

If $|S|\leq n_{0}=\frac{n}{\log^{3}n}$ then $b_{m}(S)\leq 2$.

  3. (c)

Let $i_{0}=\max\left\\{i:|C_{i}|\leq n_{0}\right\\}$. Then $|\ell-
i_{0}|\leq\log^{3}n$.

  4. (d)

$e_{1,m}(C_{1})+\cdots+e_{1,m}(C_{i_{0}})\leq
2(|C_{1}|+\cdots+|C_{i_{0}}|)\leq 2n$.

###### Proof.

(a) It follows from the Chernoff bounds that in $G_{n,p}$

$\mathbb{P}\left(\exists
S,|S|=s\geq\sigma_{0}n:e_{p}(S)\notin(1\pm\varepsilon)\binom{s}{2}p\right)\leq
2\sum_{s=\sigma_{0}n}^{n}\binom{n}{s}\exp\left\\{-\frac{\varepsilon^{2}s(s-1)p}{6}\right\\}\leq\\\
2\sum_{s=\sigma_{0}n}^{n}\left(\frac{ne}{s}\cdot\exp\left\\{-\frac{\varepsilon^{2}s\log
n}{7n}\right\\}\right)^{s}=2\sum_{s=\sigma_{0}n}^{n}\left(\frac{ne}{s}\cdot\exp\left\\{-\frac{s\log
n}{7\omega^{2}n}\right\\}\right)^{s}=o(n^{-3}).$ (10)

Now for any graph property ${\mathcal{P}}$ we have

$\mathbb{P}(G_{n,m}\in{\mathcal{P}})\leq
10m^{1/2}\mathbb{P}(G_{n,p}\in{\mathcal{P}}).$ (11)

There are many possible references for this result, see for example Lemma 1.2
of [4]. We will generally use [4] for references.

The claim for all $m\in I_{conn}$ then follows directly from (10) and (11).
The probability there exists an $S$ being $O(n^{-3}\times(n\log n)^{1/2}\times
n\log\log n)$.

(b)

$\mathbb{P}\left(\exists S,|S|=s:b_{p}(S)\geq
b\right)\leq\binom{n}{s}\binom{\binom{s}{2}}{bs}p^{bs}\leq\left(\frac{ne}{s}\cdot\left(\frac{s^{2}e^{1+o(1)}\log
n}{2bsn}\right)^{b}\right)^{s}\\\
=\left(\frac{ne}{s}\left(\frac{se^{1+o(1)}\log
n}{2bn}\right)^{b}\right)^{s}=\left(\left(\frac{se^{1+o(1)}\log
n}{2bn}\right)^{b-1}\cdot\frac{e^{2+o(1)}\log n}{2b}\right)^{s}.$ (12)

It follows that

$\mathbb{P}\left(\exists S,|S|=s\leq n_{0}:b_{p}(S)\geq
2\right)\leq\sum_{s=5}^{n_{0}}\left(\frac{e^{3+o(1)}}{8\log
n}\right)^{s}=o(1).$ (13)

Now the event $\left\\{\exists S,|S|=s\leq n_{0}:b_{p}(S)\geq 2\right\\}$ is
monotone increasing. For monotone increasing events ${\mathcal{P}}$, (11) can
be strengthened to

$\mathbb{P}(G_{n,m}\in{\mathcal{P}})\leq
3\mathbb{P}(G_{n,p}\in{\mathcal{P}}).$ (14)

See for example Lemma 1.3 of [4]. Note also that we need only to prove this
for $m=m_{+}$. In which case, (13) also implies (b).

(c) This is obvious.

(d) This follows from (b). ∎

#### Lemma 7

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$ and
$m\in I_{conn}$ and $a_{1}=10^{-3}\leq a\leq a_{\max}\approx\tfrac{1}{4}$.

  1. (a)

If $|A|=an\log n$ then $v_{m}(A)\geq\sigma(a)n$.

  2. (b)

$|C_{k+1}|+\cdots+|C_{\ell}|\geq\left(\frac{2a(1-\theta_{0})}{1+\varepsilon}\right)^{1/2}n$.

  3. (c)

$i_{0}\leq\left(1-\frac{(2a-3\theta_{0})^{1/2}}{1+\varepsilon}\right)n$.

###### Proof.

(a) Since $a\geq a_{1}$ we have that $\sigma(a)\geq\sigma(a_{1})$. We claim
next that w.h.p. $V_{m}(A)$ is not the union of components. If
$s=v_{m}(A)<\sigma(a)n$ then in $G_{n,p}$ we can bound this probability by

$\binom{n}{s}\binom{\binom{s}{2}}{an\log n}p^{an\log
n}(1-p)^{s(n-s)}=\binom{n}{s}\binom{\binom{s}{2}}{(1+\varepsilon)\binom{\sigma(a)n}{2}p}p^{an\log
n}(1-p)^{s(n-s)}\leq\\\
\left(\frac{ne}{s}\right)^{s}\left(\frac{s^{2}}{(1+\varepsilon)(\sigma(a)n)^{2}}\right)^{an\log
n}e^{-snp(1-\sigma(a))}\leq\left(\frac{en^{\sigma(a)}}{s}\right)^{s}(1+\varepsilon)^{-a_{1}n\log
n}\leq e^{-n}.$

We can add vertices to create $B\supseteq V_{m}(A)$ with $|B|=\sigma(a)n$.
Because $V_{m}(a)$ is not the union of components, we can assume that
$e_{m}(B)>|A|$. We then see that w.h.p. $|A|<e_{m}(B)\leq an\log n$,
contradiction. (The second inequality follows from Lemma 6(a) and the
definition of $\sigma$.)

(b) This follows from (4) and (a). We remind the reader that $|A|=an\log n$
and $a\geq a_{1}$ in this case and that $|C_{k+1}|+\cdots+|C_{\ell}|$ is the
number of vertices in the subgraph of $\Gamma_{1,m}$ induced by $A$.

(c) It follows from Lemma 6(a) that

$|C_{i_{0}+1}|+\cdots+|C_{\ell}|\geq\sigma\left(\frac{an\log n-2i_{0}}{n\log
n}\right)\geq\sigma\left(a-\frac{2}{\log
n}\right)\geq\left(\frac{2a-3\theta_{0}}{1+\varepsilon}\right)^{1/2}n.$

So,

$i_{0}\leq|C_{1}|+\cdots+|C_{i_{0}}|\leq\left(1-\frac{(2a-3\theta_{0})^{1/2}}{1+\varepsilon}\right)n.$
(15)

∎

#### Lemma 8

The following hold strongly in $\mathcal{G}$: in the statements, $p=m/N$.

  1. (a)

If $S$ induces a bridgeless subgraph which is not an induced cycle, then
$|S|\geq s_{1}=\frac{\log n}{10\log\log n}$.

  2. (b)

There are at most $n^{1/2}$ cycles of length at most $s_{1}$.

###### Proof.

(a) A bridgeless graph is either a cycle or has $s$ vertices and at least
$s+1$ edges. But then, in $G_{n,p}$,

$\mathbb{P}(\exists S:|S|\leq
2s_{1},e_{p}(S)\geq|S|+1)\leq\sum_{s=4}^{2s_{1}}\binom{n}{s}\binom{\binom{s}{2}}{s+1}\left(\frac{e^{o(1)}\log
n}{n}\right)^{s+1}\leq\\\
\sum_{s=4}^{2s_{1}}\left(\frac{ne}{s}\right)^{s}\left(\frac{se}{2}\right)^{s+1}\left(\frac{e^{o(1)}\log
n}{n}\right)^{s+1}=\sum_{s=4}^{2s_{1}}\frac{2\log
n}{n}\left(\frac{e^{2+o(1)}\log n}{2}\right)^{s}=o(1).$ (16)

Having such a set $S$ is a monotone increasing property and so we obtain the
needed result from (14). Again, we only need verify the property from
$m=m_{+}$. (We use $2s_{1}$ in place of $s_{1}$ for use in (b).)

(b) If two small cycles share a vertex then there is a set $S$ of size at most
$2s_{1}$ that contains at least $|S|+1$ edges. This was ruled out in the
analysis of (b). So, we can count selfish small cycles, i.e. those that do not
share vertices with other small cycles. Let $\nu_{0}=n^{1/2}$ and let $s$ be a
positive integer. Then

$\mathbb{P}(Z\geq\nu_{0})=\mathbb{P}\left(\binom{Z}{s}\geq\binom{\nu_{0}}{s}\right)\leq\frac{\mathbb{E}\left(\binom{Z}{s}\right)}{\binom{\nu_{0}}{s}}$
(17)

Now

$\displaystyle\mathbb{E}\left(\binom{Z}{s}\right)$
$\displaystyle=\sum_{3\leq\ell_{1},\ell_{2},\ldots,\ell_{s}\leq
s_{1}}\binom{n}{\ell_{1},\ell_{2},\ldots,\ell_{s},n-\ell_{1}-\cdots-\ell_{s}}\prod_{i=1}^{s}\frac{(\ell_{i}-1)!}{2}p^{\ell_{i}}$
$\displaystyle\leq\sum_{3\leq\ell_{1},\ell_{2},\ldots,\ell_{s}\leq
s_{1}}\prod_{i=1}^{s}\frac{e^{o(1)}\log
n}{2\ell_{i}}\leq\left(\sum_{3\leq\ell\leq s_{1}}\frac{e^{o(1)}\log
n}{2\ell}\right)^{s}$ $\displaystyle\leq n^{s/9}.$

Going back to (17) we see that

$\mathbb{P}(Z\geq\nu_{0})\leq\frac{n^{s/9}s^{s}}{\nu_{0}^{s}}=o(n^{-3})$

if we take $s=30$. Thus the probability the claim fails for any $m\in
I_{conn}$ is at most $O(m\log\log n\times m^{1/2}\times n^{-3})=o(1)$. ∎

#### Lemma 9

The following hold strongly in $\mathcal{G}$: if $3n^{-4/25}=a_{2}\leq a\leq
a_{1}=10^{-3}$ then $e_{m}(S:\bar{S})\geq 2an\log n$ for all
$S,|S|\in[10an,n-10an]$.

###### Proof.

We only have to prove this for $m=m_{-}$. First observe that if $10an\leq
s\leq n/2$ then

$\frac{s(n-s)p}{an\log
n}=\frac{e^{o(1)}s(n-s)}{an^{2}}\geq\frac{e^{o(1)}s}{2an}\geq 5-o(1).$

It follows from Chernoff bounds, that in $G_{n,p}$ we have

$\mathbb{P}(\exists S,|S|\in[10an,n-10an]:e_{p}(S,\bar{S})\leq 2an\log n)\leq
2\sum_{s=10an}^{n/2}\binom{n}{s}e^{-s((3-o(1))/5)^{2}\log n/2}\leq\\\
2\sum_{s=10an}^{n/2}\left(\frac{ne^{1-4\log n/25}}{s}\right)^{s}\leq
2\sum_{s=10an}^{n/2}\left(\frac{e}{3}\right)^{s}=o(n^{-2}).$

Now use (14). ∎

#### Lemma 10

The following hold strongly in $\mathcal{G}$: if $a_{2}\leq a\leq a_{1}$ and
$|S|\leq 12an$ then $b_{m}(S)\leq\frac{\log n}{12}$.

###### Proof.

We only have to prove this for $m=m_{+}$. Applying (12), we have that in
$G_{n,p}$,

$\mathbb{P}\left(\exists S,|S|=s\leq 12an:b_{p}(S)\geq\frac{\log
n}{12}\right)\leq\sum_{s=5}^{12an}\left(\left(\frac{12e^{1+o(1)}a\log n}{2\log
n/12}\right)^{\log n/12-1}\cdot\frac{12e^{1+o(1)}\log n}{2\log
n}\right)^{s}\\\ \leq\sum_{s=5}^{12an}\left((73ea)^{\log n/12-1}\cdot
20\right)^{s}=o(n^{-2}).$

The property in question is monotone decreasing. We can use (14). ∎

#### Lemma 11

The following holds strongly in $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ where
we consider the two processes defined by $e_{i},f_{i},i=1,2,\ldots,N$:

  1. (a)

$G_{2,m}$ contains at most $\log^{12}n$ vertices of degree at most 10.

  2. (b)

The vertices of degree at most 10 in $\Gamma_{2,m}$ are at distance at least 3
from each other.

  3. (c)

If $f_{i},i\in I,\,|I|\leq 10\log^{12}n$ are incident with vertices of degree
at most 10 in $\Gamma_{2,m}$ then $\left\\{e_{i},i\in I\right\\}$ is not
contained in any set of at most $s_{1}|I|$ vertices that induce a bridge free
connected subgraph of $\Gamma_{1,m}$.

###### Proof.

(a) We only have to prove this for $m=m_{-}$. Let $S$ denote the set of
vertices of degree at most 10 in $G_{m_{-}}$. If $p=p_{-}=m_{-}/N$ then in
$G_{n,p}$ the expected size of $S$ can be bounded by

$n\sum_{i=0}^{10}\binom{n}{i}p^{i}(1-p)^{n-i}\leq
2n\sum_{i=0}^{10}\log^{i}n\times\frac{\log n}{n}.$

The bound on the size of $S$ now follows from the Markov inequality. A bound
on the size of $S$ is a monotone increasing property and so we can translate
this error bound to $G_{n,m_{-}}$ via (14).

(b) Let $S$ denote the set of vertices of degree at most 10 in
$G_{n,p},p=p_{-}$ . The probability that there is a path of length at most two
between two vertices in $S$ is at most

$\binom{n}{2}(p+np^{2})\left(\sum_{i=0}^{10}\binom{n-3}{i}p^{i}(1-p)^{n-3-i}\right)^{2}=O\left(\frac{\log^{12}n}{n^{1-o(1)}}\right).$

Given (a), the probability that the $m_{+}-m_{-}$ additional edges in
$G_{m_{+}}-G_{m_{-}}$ add an edge between two vertices in $S$ can be bounded
by $O\left(n\log\log n\times\log^{24}n/\binom{n}{2}\right)=o(1)$.

Given (a), the probability that the $m_{+}-m_{-}$ additional edges add an edge
between $S$ and a neighbor of $S$ can be bounded by $O\left(n\log\log
n\times\log^{12}n/\binom{n}{2}\right)=o(1)$.

Given (a), the probability that the $m_{+}-m_{-}$ additional edges join a pair
of vertices in $S$ to a $G_{m_{-}}$ non-neighbor can be bounded by
$O\left((n\log\log n)^{2}\times\log^{24}n\times
n/\binom{n}{2}^{2}\right)=o(1)$.

(c) Given the bound on the number of low degree vertices in (a), the
probability that there exists a cycle of length $s$ in $\Gamma_{1,m},m=m_{+}$
containing $t$ edges $e_{i}$ for which $f_{i}$ is incident with a vertex of
degree at most 10 in $\Gamma_{2,m_{-}}$ is at most

$n^{s}\binom{s}{t}\frac{\binom{N-s}{m-s}}{\binom{N}{m}}\left(\frac{10\log^{12}n}{n}\right)^{t}\leq(2\log
n)^{s}\left(\frac{10\log^{12}n}{n}\right)^{t}.$ (18)

We must sum the RHS of (18) for $1\leq t\leq 10\log^{12}n$ and $3\leq s\leq
s_{1}t$. Observing that $\log^{s_{1}+10}n=n^{1/10+o(1)}$, we see that this sum
is $o(1)$. (Recall that $s_{1}=\frac{\log n}{10\log\log n}$.) If there is a
cycle that contradicts (c) in the process then this cycle will occur in
$G_{m_{+}}$ and the offending $f_{i}$ will be incident with low degree
vertices in $G_{m_{-}}$.

Now consider bridge free connected sets. The probability that there is a set
of size $s$ with $t$ edges $e_{i}$ of the required sort can be bounded by

$\binom{n}{s}\binom{\binom{s}{2}}{s+1}\frac{\binom{N-s-1}{m-s-1}}{\binom{N}{m}}\binom{s+1}{t}\left(\frac{10\log^{12}n}{n}\right)^{t}\leq\frac{se}{n}\left(\frac{ne}{s}\cdot\frac{se}{2}\cdot\frac{m}{N}\cdot
2\right)^{s+1}\left(\frac{10\log^{12}n}{n}\right)^{t}\leq\\\ (e^{2+o(1)}\log
n)^{s}\left(\frac{10\log^{12}n}{n}\right)^{t}.$

We finish the argument as we did for cycles. ∎

#### Lemma 12

The following holds strongly in $\mathcal{G}$: if $|S|\leq n^{9/10}$ then
$b(S)\leq 1+10\theta_{0}$.

###### Proof.

We only have to prove this for $m=m_{+}$. Applying (12), we have that in
$G_{n,p}$,

$\mathbb{P}\left(\exists S,|S|=s\leq n^{9/10}:b_{p}(S)\geq 1+\frac{50\log\log
n}{\log n}\right)\leq\\\ \sum_{s=4}^{n^{9/10}}\left(\left(\frac{e^{1+o(1)}\log
n}{2n^{1/10}}\right)^{50\log\log n/\log n}\cdot e^{2+o(1)}\log
n\right)^{s}\leq\sum_{s=4}^{n^{9/10}}\left(\frac{e^{5}}{\log^{3}n}\right)^{s}=o(1).$

The property in question is monotone increasing and so we can apply (14). ∎