# Large induced subgraphs of random graphs with given degree sequences

Angus Southwell
School of Mathematics
Monash University
VIC 3800 Australia
<EMAIL_ADDRESS>Research supported by Australian Government
Research Training Program Scholarship. Nicholas Wormald
School of Mathematics
Monash University
VIC 3800 Australia
<EMAIL_ADDRESS>Research supported by ARC Discovery Project
DP180103684.

###### Abstract

We study a random graph $G$ with given degree sequence ${\bm{d}}$, with the
aim of characterising the degree sequence of the subgraph induced on a given
set $S$ of vertices. For suitable ${\bm{d}}$ and $S$, we show that the degree
sequence of the subgraph induced on $S$ is essentially concentrated around a
sequence that we can deterministically describe in terms of ${\bm{d}}$ and
$S$. We then give an application of this result, determining a threshold for
when this induced subgraph contains a giant component. We also apply a similar
analysis to the case where $S$ is chosen by randomly sampling vertices with
some probability $p$, i.e. site percolation, and determine a threshold for the
existence of a giant component in this model. We consider the case where the
density of the subgraph is either constant or slowly going to $0$ as $n$ goes
to infinity, and the degree sequence ${\bm{d}}$ of the whole graph satisfies a
certain maximum degree condition. Analogously, in the percolation model we
consider the cases where either $p$ is a constant or where $p\to 0$ slowly.
This is similar to work of Fountoulakis in 2007 and Janson in 2009, but we
work directly in the random graph model to avoid the limitations of the
configuration model that they used.

##  1 Introduction

Random graphs with given degree sequences are a well-studied random graph
model. To define the model, let ${\bm{d}}=(d(1),\dots,d(n))$ be the degree
sequence of a graph. Then $\mathcal{G}({\bm{d}})$ is a uniform random graph
with degree sequence ${\bm{d}}$. This graph model has been the focus of much
study recently, both due to improvements in the tools to study the model and
also as it has found applications as a null model for studying networks (see
[7]). Compared to binomial random graphs, this model is much better suited to
studying properties of graphs where the degrees of the vertices are not
concentrated around a particular value. However, this comes at the cost of
ease of analysis: events that are trivial to study in the binomial random
graph model (such as the adjacency of two vertices) are quite non-trivial in
$\mathcal{G}({\bm{d}})$ and not fully understood in general.

In this paper we study induced subgraphs of random graphs with given degree
sequences, i.e. the degree sequence of the subgraph $G[S]$ of
$G\in\mathcal{G}({\bm{d}})$ induced by $S\subseteq V(G)$. Our main results are
that the degree sequence of the induced subgraph is close to a model degree
sequence ${\bm{d}}_{H}$ defined in Definition 2.2. In particular, the
distribution of the degree of a vertex in $G[S]$ is approximately binomial, in
terms of its degree in $G$ and the density of $S$ in $G$ (see Section 2 for a
precise statement). We use this approximation to show that with probability
tending to 1 as $n\to\infty$ (a.a.s.), the large entries in the degree
sequence of $G[S]$ are asymptotically equal to the corresponding entries in
${\bm{d}}_{H}$, and the frequencies of small entries in each sequence are also
close. We formally state this in Theorem 2.3.

The result mentioned above applies to a given subset $S=S(n)$. We also make
use of it to prove a similar result about the model where $G$ is again a
uniformly random graph with degree sequence ${\bm{d}}$, but where $S$ is
chosen randomly by taking each vertex independently with probability $p=p(n)$.
This model is commonly known as _(site-)percolated random graph
$\mathcal{G}({\bm{d}})$ with survival probability $p$_. This is in contrast to
_bond percolation_ , where edges are deleted instead of vertices. Percolation
problems have been studied on a wide range of graphs, both deterministic and
random, since the 1950s. See, for example, the work of Broadbent and
Hammersley [2], Fountoulakis [3], Janson [5], or McDiarmid, Scott, and Withers
[9]. In this paper, we use the phrase “percolated random graph” and the
notation $G_{\bm{d}}(p)$ to refer to a uniformly random graph with degree
sequence ${\bm{d}}$ after site percolation with survival probability $p$. In
this model, $S$ is a random variable, where each subset $S\subset[n]$ occurs
with probability $p^{|S|}(1-p)^{n-|S|}$. We define a model sequence
${\bm{d}}_{A}$ (formally given in Definition 2.5), which is a function of
${\bm{d}}$ and $p$, and show that, for suitable ${\bm{d}}$ and $p$, the degree
sequence of the percolated random graph is close to the model sequence
${\bm{d}}_{A}$.

The relationship between the large entries of ${\bm{d}}_{A}$ and
${\bm{d}}_{S}$ in the percolated random graph model is less precise than the
corresponding relationship between ${\bm{d}}_{H}$ and ${\bm{d}}_{S}$ in the
model where $S$ is given. Instead of estimating each entry, we estimate the
degree of a vertex conditional on it being a member of $S$. As well as this,
we give a result about the sum of the large entries in each sequence. This is
because of the potential lack of concentration of large degrees in the induced
subgraph. For instance, if only one vertex $v$ exists of very large degree
$i$, and the rest have small degree $j$, then the maximum degree in the
induced subgraph will be close to $ip$ with probability $p$ (in the case that
$v\in S$), and at most $j$ otherwise.

A common problem studied in random graphs and percolation models is the
existence of a giant component. Molloy and Reed [11] used the configuration
model (often denoted $\mathcal{C}({\bm{d}})$) to investigate the existence of
a giant component in $\mathcal{G}({\bm{d}})$. The configuration model is a
model proposed by Bollobás [1] to study $\mathcal{G}({\bm{d}})$ which
constructs a random (pseudo)graph with the correct degree sequence from a
random pairing of sets of points in bins corresponding to the vertices. It is
much easier to analyse than $\mathcal{G}({\bm{d}})$, but the need to transfer
results to $\mathcal{G}({\bm{d}})$ resulted in strict conditions on the degree
sequence ${\bm{d}}$ in [11]. Recently, Joos, Perarnau, Rautenbach, and Reed
[6] generalised this to fully describe the threshold for the existence of a
giant component in $\mathcal{G}({\bm{d}})$ in terms of ${\bm{d}}$, for all
sequences ${\bm{d}}$.

The results of Molloy and Reed [11] were used by Fountoulakis [3] to study the
threshold for the existence of a giant component in a percolated random graph.
Again this was done by studying the configuration model. A key element of his
proof is the following fact: the percolated random graph is distributed
uniformly at random conditioned on its degree sequence. He then studied the
distribution of the resulting degree sequence in both site and bond
percolation models. This result has strict requirements on ${\bm{d}}$, such as
a maximum degree of at most $n^{1/9}$, bounded average degree, and a
sufficiently nice limiting distribution. Fountoulakis then applied the
aforementioned results of [11] to prove a threshold for the existence of a
giant component in (site or bond) percolated $\mathcal{G}({\bm{d}})$. Janson
[5] used similar ideas and tools from the theory of branching processes to
prove a similar result for a wider range of degree sequences. Recently,
Fountoulakis, Joos, and Perarnau [4] used results in [6] to prove results
about the threshold for the existence of a giant component in bond percolated
$\mathcal{G}({\bm{d}})$. These results apply for a wider range of degree
sequences than considered in [3] and [5], but also assume that
$\mathcal{G}({\bm{d}})$ has bounded average degree and that the survival
probability $p\in(0,1]$ is a constant.

In this paper we apply the recent result of Joos et al. [6] and results about
our model degree sequences (${\bm{d}}_{H}$ for when $S$ is fixed and
${\bm{d}}_{A}$ for when $S$ is random) to determine a threshold for the
existence of a giant component in $G[S]$. This serves as an example of how our
main result can be used to study induced subgraphs of $\mathcal{G}({\bm{d}})$:
by combining this result with known thresholds for properties of
$\mathcal{G}({\bm{d}})$, one can determine thresholds for these properties in
$G[S]$. Notably, our results allow for cases where $\mathcal{G}({\bm{d}})$ has
maximum degree slightly less than $\sqrt{|E(G)|}$ (see 2.1 for the precise
condition), as long as the density of the subgraph (relative to the whole
graph $G$) is either bounded away from 0 and 1, or goes to $0$ sufficiently
slowly (roughly up to $n^{-\varepsilon}$ for some small constant
$\varepsilon>0$). We can achieve this extension of the results in [3] on site
percolation by carrying out our analysis in $\mathcal{G}({\bm{d}})$ directly,
as opposed to using the configuration model, and we utilise the switching
method heavily. In contrast to the results in [4] on bond percolation, our
results also apply in cases where $\mathcal{G}({\bm{d}})$ has average degree
only slightly less than $\sqrt{|E(G)|}$ and the survival probability is at
least $|E(G)|^{-\varepsilon^{\prime}}$, for a small constant
$\varepsilon^{\prime}$. In particular, for nearly regular degree sequences
${\bm{d}}$ (e.g. typical degree sequences arising from $\mathcal{G}(n,p)$ or
$\mathcal{G}(n,m)$), our results apply when the maximum degree is
$O(n^{1-\varepsilon})$ for any $\varepsilon>0$. In upcoming work, we also use
our degree sequence characterisation to prove thresholds for the connectivity
of $G[S]$, as well as results on its chromatic number and its automorphism
group.

##  2 Main results

Here we give much of the notation we use, as well as describing our main
results. Let ${\bm{d}}$ be a graphical sequence of length $n$, that is, let
${\bm{d}}=(d(1),\dots,d(n))$ be a sequence of non-negative integers such that
there exists a graph with vertex set $[n]=\\{1,\dots,n\\}$ where each vertex
$i\in[n]$ has degree $d(i)$. Without loss of generality, we assume that all
entries of ${\bm{d}}$ are at least $1$ and are in non-decreasing order, so
$1\leq d(1)\leq d(2)\leq\dots\leq d(n)$. We also define
$\Delta=\Delta({\bm{d}})$ to be the value of the largest entry in ${\bm{d}}$.
For a set $A\subseteq[n]$, let $d(A)=\sum_{i\in A}d(i)$ be the _total degree_
of $A$. We also use $M({\bm{d}})$ to denote $d([n])$, and call it the _total
degree_ of a sequence ${\bm{d}}$. For brevity, we use $M$ to denote
$M({\bm{d}})$ where ${\bm{d}}$ is the degree sequence of the underlying random
graph $G\in\mathcal{G}({\bm{d}})$. We always use
$S=\\{i_{1},\dots,i_{s}\\}\subset[n]$ to denote the vertices of the induced
subgraph of $\mathcal{G}({\bm{d}})$, and we define
${\overline{S}}=[n]\backslash S$ and $\gamma=\gamma(S)=d(S)/M$.

###  2.1 Subgraphs induced on a vertex set

Suppose $S=S(n)\subseteq[n]$, and suppose $({\bm{d}},S)$ satisfies

$\displaystyle\Delta^{2}(\gamma^{-1}\log M)^{12}\leq\delta d(S)$ (2.1)

for some $\delta\to 0$ sufficiently slowly as $n\to\infty$ (equivalently,
$M\to\infty$). Throughout the proofs, we use $\delta$ and various powers of it
to bound the rate at which certain functions grow or shrink. We assume that
$\delta=\Omega((\log\log M)^{-1})$, or equivalently that
$\delta^{-1}=O(\log\log M)$. Define ${J}=\delta^{-1/16}\gamma^{-1}\log M$. We
suppose that $\gamma<1-c$ for some constant $c>0$, but we allow
$\gamma=\gamma(n)\to 0$. That is, $d({\overline{S}})\geq cM$ for some constant
$c>0$, but $d(S)=o(M)$ is possible. The condition on $\gamma$ given in 2.1
implies that

$\displaystyle\gamma\geq\delta^{-1/13}\frac{(\Delta^{2}\log^{12}M)^{1/13}}{M^{1/13}}.$

This immediately implies that $\gamma=\omega(M^{-1/13})$, a fact used
throughout the proofs. The powers of $\log M$ in our definitions and results
are not necessarily optimised, either for studying the distribution of the
induced degree sequence in general or for studying the threshold for the
existence of giant components.

We also note that the conditions given in 2.1 imply that
$\mathcal{G}({\bm{d}})$ is non-empty.

######  Proposition 2.1.

If ${\bm{d}}$ is a sequence of length $n$ with even sum such that there exists
a set $S\subset[n]$ satisfying (2.1), then ${\bm{d}}$ is graphical, that is,
there exists a graph with degree sequence ${\bm{d}}$.

###### Proof.

The inequality (2.1) implies that $\Delta^{2}=o(d(S))$, which implies that
$\Delta^{2}=o(M)$ (since $\gamma\leq 1$). Koren [8] (Section 1) states that if
a sequence ${\bm{d}}$ is not graphical, then there exist disjoint, non-empty
sets $A,B\subset[n]$ such that

$\displaystyle\sum_{i\in A}d(i)-\sum_{j\in B}d(j)>a(n-1-b),$

where $a=|A|$ and $b=|B|$. Suppose that such sets $A$ and $B$ existed. The
left hand side of this inequality is at most $a\Delta$. Thus, this inequality
could only be true if $b>n-1-\Delta$. This implies that $a<\Delta+1$, and also
that $\sum_{j\in B}d(j)=\sum_{j\in[n]}d(j)-\sum_{j\notin B}d(j)\geq
M({\bm{d}})-\Delta^{2}$. Since $\sum_{i\in A}d(i)\leq\Delta^{2}=o(M)$, it
follows that the left hand side tends to $-\infty$ as $n\to\infty$, which is a
contradiction. Therefore the inequality cannot hold, and the sequence is
graphical. ∎

In view of this lemma, by supposing that ${\bm{d}}$ is a sequence of length
$n$ with all entries at least 1 and even sum that satisfies 2.1, we may assume
that ${\bm{d}}$ is graphical, which is useful when talking about probabilities
in associated random graph models. We next define a deterministic sequence
${\bm{d}}_{H}$ that in some sense represents a typical degree sequence of
$G[S]$. Let ${\bm{d}}_{S}$ be the degree sequence of the graph $G[S]$. For an
arbitrary sequence ${\bm{d}}$, let $n_{k}({\bm{d}})$ be the number of entries
of ${\bm{d}}$ that are equal to $k$.

######  Definition 2.2.

Let $d$, a sequence of length $n$, and a set
$S=\\{i_{1},\dots,i_{s}\\}\subset[n]$ be given. To define
${\bm{d}}_{H}={\bm{d}}_{H}(S)$, let
$Z_{j}\sim\textup{Bin}\left(j,\frac{d(S)}{M}\right)$ and define

$\displaystyle N(k)=\left\lfloor\sum_{i\in S}\mathbb{P}\left(Z_{d(i)}\leq
k\right)+\frac{1}{2}\right\rfloor$

for $k\geq 0$, and $N(-1)=0$. Then define ${\bm{d}}_{H}$ to be the non-
decreasing sequence in which $n_{k}({\bm{d}}_{H})$, i.e. the number of
occurrences of $k$ in ${\bm{d}}_{H}$, is given by
$n_{k}({\bm{d}}_{H})=N(k)-N(k-1)$.

We note that ${\bm{d}}_{H}$ may not be a graphical sequence, but we do not
need it to be. The main result on the degree sequence of $G[S]$ is the
following theorem, in which each of the sequences ${\bm{d}}_{S}$ and
${\bm{d}}_{H}$ is essentially segmented into two parts (with some overlap to
ensure that all entries of both sequences are covered by the theorem). Part
(a) of the theorem implies that, beyond a certain index, the corresponding
entries in the two sequences are a.a.s. asymptotic to each other. It also
gives an explicit formula for these entries which would be suggested by a
naive intuition based on expectation, and is useful for practical purposes.
Below this index, it is difficult to obtain asymptotic values for each entry
of ${\bm{d}}_{S}$, so we just give rough bounds in (b), and a distributional
result in (c). The latter, applying for a slightly larger range than (b) in
order to overlap with the range for which part (a) applies, states that the
number entries that are equal to any given $k\leq\frac{1}{2}\gamma{J}$ is
similar in each sequence.

######  Theorem 2.3.

Let ${\bm{d}}$ be a sequence of length $n$ with all entries at least 1 and
even sum, and let $S\subset[n]$ be such that $({\bm{d}},S)$ satisfies 2.1 for
some $\delta\to 0$ and $\gamma<1-c$ for some constant $c>0$. The following
claims hold with probability $1-O(1/\sqrt{\log M})$:

  1. (a)

$d_{S}(k)=\gamma d(i_{k})(1\pm 8\delta^{1/64})=d_{H}(k)\left(1\pm
12\delta^{1/64}\right)$ for all $k$ such that $d(i_{k})\geq\delta^{1/32}{J}$;

  2. (b)

$\max\\{d_{S}(k),d_{H}(k)\\}\leq 2\gamma\delta^{1/32}{J}$ for all $k$ such
that $d(i_{k})<\delta^{1/32}{J}$;

  3. (c)

$|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H})|\leq\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5}$ for all
$i\leq\frac{1}{2}\gamma{J}$.

We apply this and the results of Joos et al. [6] to prove the following
threshold for the existence of giant components in induced subgraphs of
$\mathcal{G}({\bm{d}})$.

######  Theorem 2.4.

Let ${\bm{d}}$ be a sequence of length $n$ with all entries at least $1$ and
even sum, and let $S$ be a subset of $[n]$. Let $\gamma=d(S)/M$, and suppose
that $\Delta^{2}\gamma^{-12}\log^{12}M=o(\gamma M)$. Then $G[S]$ a.a.s.
contains $(|S|-n_{0}({\bm{d}}_{H}))(1+o(1))$ non-isolated vertices.
Furthermore, $G[S]$ a.a.s. contains a component on a positive fraction of the
non-isolated vertices if and only if there exists some constant
$\varepsilon>0$ such that $R({\bm{d}}_{H})\geq\varepsilon\gamma^{2}M$.

We prove this result by applying Theorem 2.3 and the result of Joos et al. [6]
about the threshold for giant components in $\mathcal{G}({\bm{d}})$ (formally
stated in Theorem 5.1). We show that for two sequences that are close in the
sense described in Theorem 2.3, the thresholds for the existence of a giant
component coincide. We defer the proof of Theorem 2.3 for now, and give this
and all the intermediate results in Section 3.

###  2.2 Random induced subgraphs of $G$

Now we consider the (site-)percolated random graph model $G_{\bm{d}}(p)$, for
some $p\in(0,1)$. In this model, $S$ is a random variable where, for each
subset $T\in[n]$, $\mathbb{P}\left(S=T\right)=p^{|T|}(1-p)^{n-|T|}$. Thus, the
subgraph $G[S]$ is the subgraph of a uniformly random
$G\in\mathcal{G}({\bm{d}})$ induced on $S$, where $S$ is chosen by randomly
keeping vertices of $G$ independently with some probability $p$, and deleting
the rest. Again we suppose that ${\bm{d}}$ is ordered in non-decreasing order
with all entries at least $1$. Analogously to the case where $S$ is fixed, we
impose the condition that

$\displaystyle\Delta^{2}(p^{-1}\log M)^{12}\leq\delta pM$ (2.2)

for some $\delta\to 0$ sufficiently slowly as $n\to\infty$. We now define a
model degree sequence of the percolated random graph $G_{\bm{d}}(p)$.

######  Definition 2.5.

Let ${\bm{d}}=(d(1),\dots,d(n))$ be a non-decreasing sequence of length $n$.
Let $p\in(0,1)$, and let $X_{j}\sim\textup{Bin}\left(j,p\right)$. For
$k\in\left\\{0,\dots,{J}\right\\}$, define

$\displaystyle\tilde{N}(k)$ $\displaystyle:=\left\lfloor p\sum_{i\in
V}\mathbb{P}\left(X_{d(i)}\leq k\right)+\frac{1}{2}\right\rfloor$

for $k\geq 0$, and $\tilde{N}(-1)=0$. Then define
$n_{k}({\bm{d}}_{A})=\tilde{N}(k)-\tilde{N}(k-1)$ to be the number of entries
in ${\bm{d}}_{A}$ with value $k$.

Now we state the main result of our paper for degree sequences of site-
percolated $\mathcal{G}({\bm{d}})$.

######  Theorem 2.6.

Let ${\bm{d}}$ be a sequence of length $n$ with even sum and all entries at
least 1, and let $p\in(0,1)$ be such that $p<1-\varepsilon$ for some constant
$\varepsilon>0$ and $\Delta^{2}p^{-12}\log^{12}M\leq\delta pM$ for some
$\delta\to 0$. Then the following statements hold with probability $1-o(1)$ in
the percolated random graph $G_{\bm{d}}(p)$.

  1. (a)

$|S|=np\left(1\pm 3\sqrt{\frac{\log n}{pn}}\right)$.

  2. (b)

$d(S)=pM\left(1\pm\frac{p^{2}}{M^{1/4}}\right)$.

  3. (c)

$d_{S}(v)=pd(v)\left(1\pm 9\delta^{1/64}\right)$ for all $v\in S$ such that
$d(v)>2\delta^{1/32}{J}(p)$.

  4. (d)

For all $i\leq\frac{1}{3}p{J}(p)$,

$\displaystyle|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{A})|\leq\frac{pn_{i}({\bm{d}}_{A})}{{J}(p)^{3}}(1+o(1))+\frac{p{J}(p)^{6}}{\sqrt{\log
M}}.$

Analogously to the definition of $\tilde{y}_{i}$, we also define

$\displaystyle\tilde{w}_{k}:=p\sum_{i\in V}\mathbb{P}\left(X_{d(i)}=k\right).$

It follows immediately that $n_{k}({\bm{d}}_{A})=\tilde{w}_{k}\pm 1$. We also
analogously define ${J}(p):=\delta^{-1/16}p^{-1}\log M$. For $p=\gamma$ this
is equivalent to the definition of ${J}$ used previously. This also allows us
to consider ${J}(\gamma(S))$, the corresponding value of ${J}$ for a given set
$S\subset[n]$. This is useful as we often prove results for the percolation
model by conditioning on a “nice” choice of $S$ and then applying results
proved in the case where $S$ is fixed. As such, when proving results about the
percolation model, we often write definitions from the previous section (e.g.
$\gamma$, $Z_{j}$, ${\bm{d}}_{H}$, $\tilde{y}_{i}$) with the extra argument of
$S$ to highlight the conditional probability space on which we define them. As
in the case where $S$ is fixed, we apply Theorem 2.6 to determine the
threshold for the existence of a giant component in the site-percolated random
graph under the conditions given in 2.2.

######  Theorem 2.7.

Let ${\bm{d}}$ be a sequence of length $n$ with even sum and all entries at
least 1. Let $p\in(0,1)$ be such that $\Delta^{2}p^{-12}\log^{12}M=o(pM)$. Let
$G_{\bm{d}}(p)$ be the site-percolated random graph, where
$G\sim\mathcal{G}({\bm{d}})$. Then $G_{\bm{d}}(p)$ a.a.s. contains $(np-
n_{0}({\bm{d}}_{A}))(1+o(1))$ non-isolated vertices. Furthermore,
$G_{\bm{d}}(p)$ a.a.s. contains a component on a positive fraction of the non-
isolated vertices if and only if $R({\bm{d}}_{A})\geq\varepsilon p^{2}M$ for
some constant $\varepsilon>0$.

Much like in the case where $S$ is fixed, we prove this by showing that
${\bm{d}}_{S}$ and ${\bm{d}}_{A}$ are a.a.s. close, and then showing that for
sequences that are close these thresholds coincide. We give the proof of
Theorem 2.6 in Section 6.

##  3 Distribution of the induced vertex degree

In this section we prove Theorem 2.3. Let $A_{v}^{i}$ denote the set of
$G\in\mathcal{G}({\bm{d}})$ such that $d_{S}(v)=i$.

######  Lemma 3.1.

Let $v$ be an arbitrary vertex in $S$. Then

$\displaystyle\frac{|A_{v}^{i}|}{|A_{v}^{i+1}|}=\frac{i+1}{d(v)-i}\cdot\frac{d({\overline{S}})}{d(S)}\left(1+O\left(\frac{\Delta^{2}}{d(S)}\right)\right).$

###### Proof.

We define an operation called a switching that takes a graph $G\in
A_{v}^{i+1}$ to some $G^{\prime}\in A_{v}^{i}$. Let $G\in A_{v}^{i+1}$. To
perform a switching, choose a vertex $y$ such that $vy\in E(G)$ and $y\in S$,
as well as an ordered pair of vertices $(u,x)$ such that $ux\in E(G)$ and
$u\in{\overline{S}}$ ($x$ can be in either $S$ or ${\overline{S}}$). It is
also required that

  1. (a)

the vertices $\left\\{u,v,x,y\right\\}$ are distinct, and

  2. (b)

$xy\notin E(G)$ and $uv\notin E(G)$.

The switching deletes edges $vy$ and $ux$, replacing these edges with $uv$ and
$xy$ and hence creating a new multigraph $G^{\prime}$, and the conditions (a)
and (b) imply that $G^{\prime}\in A_{v}^{i}$. This switching is illustrated in
Figure 1.

$y$$v$$u$$x$$G\in A^{i+1}_{v}$

$y$$v$$u$$x$$G^{\prime}\in A^{i}_{v}$

Figure 1: A switching. Here $v,y\in S$ and $u\in{\overline{S}}$. Edges present
in $G$ (on the left, respectively $G^{\prime}$ on the right) are given as
solid lines, forbidden edges are given as dashed. Other edges may be present
or absent.

Now we find upper and lower bounds on the number of switchings that create a
particular $G^{\prime}\in A_{v}^{i}$. Given $G\in A_{v}^{i+1}$, there are
$i+1$ choices for a vertex $y$ such that $vy\in E(G)$ and $y\in S$. There are
$d({\overline{S}})$ choices for a vertex $u\in{\overline{S}}$ and neighbour
$x$. Thus, there are at most $(i+1)d({\overline{S}})$ switchings that take
$G\in A_{v}^{i+1}$ to some $G^{\prime}\in A_{v}^{i}$. To determine a
corresponding lower bound, we note that since $G$ has maximum degree at most
$\Delta$, the number of choices for $\\{u,x,y\\}$ as described above that
violate (a) is $O((i+1)\Delta)$ and for (b) it is $O((i+1)\Delta^{2})$. Hence
the number of valid switchings that can be applied to each $G\in A_{v}^{i+1}$
is $(i+1)(d({\overline{S}})+O(\Delta^{2}))$.

Now we use a very similar argument to count the switchings that create a
particular $G^{\prime}\in A_{v}^{i}$. There are $d(v)-i$ choices for the
vertex $u$, and $d(S)$ choices for an ordered pair of vertices $(x,y)$ such
that $y\in S$ and $xy\in E(G^{\prime})$. So an upper bound is $(d(v)-i)d(S)$.
The number of these combinations that are invalid, due to a vertex being
repeated or the edge $ux$ or $vy$ being present, is $O(\Delta^{2})(d(v)-i)$.
It follows that the number of switchings that create $G^{\prime}$ is
$(d(v)-i)(d(S)+O(\Delta^{2}))$.

From the conclusions of the previous two paragraphs, the total number of
switchings applicable to graphs in $A_{v}^{i+1}$ can be counted in two
different ways as $|A_{v}^{i+1}|(i+1)(d({\overline{S}})+O(\Delta^{2}))$ and
$|A_{v}^{i}|(d(v)-i)(d(S)+O(\Delta^{2}))$. The lemma follows, since
$d({\overline{S}})=\Theta(M)$ and $\Delta^{2}=o(d(S))$. ∎

Define $S_{\rm{small}}=\\{i_{1},\dots,i_{\ell}\\}$ where $\ell$ is the
smallest index such that $d(i_{j})>{J}$ for all $j>\ell$. That is,
$S_{\rm{small}}$ is the set of vertices in $S$ with degree (in $G$) at most
${J}$. Naturally, we can also define $S_{\rm{big}}=S\backslash
S_{\rm{small}}$. Define

$\displaystyle\tilde{y}_{i}=\sum_{v\in
S_{\rm{small}}}\mathbb{P}\left(Z_{d(v)}=i\right).$

For small $i$ (that is, smaller than $c\gamma{J}$ for some constant $c<1$),
$\tilde{y}_{1}$ is very close to $n_{i}({\bm{d}}_{H})$, the number of entries
in the sequence ${\bm{d}}_{H}$ with value $i$. One noteworthy and
straightforward consequence of Theorem 2.3 is that
$n_{i}({\bm{d}}_{H})=\tilde{y}_{i}\pm(1+o(M^{-5}))$ for all
$i\leq\frac{1}{2}\gamma{J}$. For the sequence ${\bm{d}}_{S}$, we can
analogously define

$\displaystyle Y_{i}=\sum_{v\in
S_{\rm{small}}}\mathbbm{1}_{\left\\{d_{S}(v)=i\right\\}}.$ (3.1)

These definitions allow us to consider the behaviour of vertices in
$S_{\rm{small}}$ and $S_{\rm{big}}$ somewhat separately. This is useful in
certain circumstances, particularly when studying the distribution of the
number of vertices with very low degrees (e.g. 0, 1, or 2) in ${\bm{d}}_{H}$
and ${\bm{d}}_{S}$, as the number of vertices in $S_{\rm{big}}$ with very low
induced degree is a.a.s. $0$. More specifically, Theorem 2.3 implies that
a.a.s. $n_{i}({\bm{d}}_{S})=Y_{i}$ for all $i\leq\frac{1}{2}\gamma{J}$. A
later result (Lemma 3.6) then implies that
$\mathbb{E}\left[Y_{i}\right]=\tilde{y}_{i}\left(1+o({J}^{-6})\right)$ for all
$i\leq{J}$.

######  Remark 3.2.

Let $S_{j}$ be the set of $i\in S$ such that $d(i)=j$. Then for
$k\in\left[1,\frac{1}{2}\gamma{J}\right]$,

$\displaystyle\tilde{y}_{k}$ $\displaystyle=\sum_{i\in
S_{\rm{small}}}\mathbb{P}\left(Z_{d(i)}=k\right)=\sum_{j\leq{J}}|S_{j}|\mathbb{P}\left(Z_{j}=k\right)=\sum_{j\leq{J}}\frac{d(S)}{d({\overline{S}})}\frac{j-k+1}{k}|S_{j}|\mathbb{P}\left(Z_{j}=k-1\right).$

With some naive bounds on the value of $\frac{j-k+1}{k}$, this gives useful
bounds on the ratios between successive values of $\tilde{y}_{i}$, and thus on
$n_{i}({\bm{d}}_{H})$. Since $j\leq{J}$,

$\displaystyle\tilde{y}_{k}$
$\displaystyle=\sum_{j\leq{J}}|S_{j}|\mathbb{P}\left(Z_{j}=k\right)\leq\frac{{J}}{k}\frac{d(S)}{d({\overline{S}})}\sum_{j\leq{J}}|S_{j}|\mathbb{P}\left(Z_{j}=k-1\right)=\frac{\gamma{J}}{k(1-\gamma)}\tilde{y}_{k-1}.$

Thus, $\tilde{y}_{k}=O(\gamma{J}\tilde{y}_{k-1})$. More commonly, we use the
form $\tilde{y}_{k-1}=\Omega\left(\frac{\tilde{y}_{k}}{\gamma{J}}\right)$.

###  3.1 Concentration of large degrees

Recall that $d_{S}(v)$ is the degree of vertex $v$ in $G[S]$. Also recall the
definition of $\gamma=d(S)/M$, and that $\delta$ is an arbitrary function such
that $\delta\to 0$ and $\Delta^{2}(\gamma^{-1}\log M)^{12}\leq\delta d(S)$.

######  Lemma 3.3.

Suppose $\varepsilon=4\delta^{1/64}$ and define $i_{0}=i_{0}(v)=\gamma d(v)$
(not necessarily an integer). Then, for $n$ sufficiently large,

$\displaystyle\mathbb{P}\big{(}d_{S}(v)\in[i_{0}(1-2\varepsilon),i_{0}(1+2\varepsilon)]\big{)}<2d(v)\exp\left(-\varepsilon^{2}i_{0}/2\right).$

###### Proof.

We first prove that the probability that $d_{S}(v)<i_{0}(1-2\varepsilon)$ is
less than $d(v)\exp\left(-\frac{1}{2}\varepsilon^{2}i_{0}\right)$. Define
$i_{k}=(1-k\varepsilon)i_{0}$ for all $k>0$. Recall that $|A_{v}^{i}|$ is the
number of graphs in $\mathcal{G}({\bm{d}})$ such that $d_{S}(v)=i$. For all
$i\leq i_{1}-1$, Lemma 3.1 implies that

$\displaystyle\frac{|A_{v}^{i}|}{|A_{v}^{i+1}|}$
$\displaystyle=\frac{i+1}{d(v)-i}\frac{d({\overline{S}})}{d(S)}\left(1+O\left(\frac{\Delta^{2}}{d(S)}\right)\right)\leq\left(1-\varepsilon\right)\frac{i_{0}}{d(v)-i_{0}}\frac{d({\overline{S}})}{d(S)}\left(1+O\left(\frac{\Delta^{2}}{d(S)}\right)\right).$

By definition of $i_{0}$,

$\displaystyle\frac{i_{0}}{d(v)-i_{0}}=\frac{\frac{d(S)}{M}}{1-\frac{d(S)}{M}}=\frac{d(S)}{d({\overline{S}})}.$

Thus, for all $i\leq i_{1}-1$,

$\displaystyle\frac{|A_{v}^{i}|}{|A_{v}^{i+1}|}\leq(1-\varepsilon)\left(1+O\left(\frac{\Delta^{2}}{d(S)}\right)\right)<1-\frac{3}{4}\varepsilon,$
(3.2)

for $n$ sufficiently large, since $\Delta^{2}=o(\varepsilon d(S))$. Hence for
all $i\leq\lceil i_{2}\rceil-1$,

$\displaystyle\frac{|A_{v}^{i}|}{|A_{v}^{\lfloor i_{1}\rfloor}|}$
$\displaystyle\leq\left(1-\frac{3}{4}\varepsilon\right)^{\varepsilon
i_{0}-1}<\exp\left(-\frac{2}{3}\varepsilon^{2}i_{0}+O\left(\varepsilon^{3}i_{0}\right)\right)<\exp\left(-\frac{1}{2}\varepsilon^{2}i_{0}\right),$

where the last inequality holds for $n$ sufficiently large. So if $i\leq\lceil
i_{2}\rceil-1$, it follows that
$\mathbb{P}\left(d_{S}(v)=i\right)<\exp\left(-\frac{1}{2}\varepsilon^{2}i_{0}\right)$.
Performing a union bound over all possible induced degrees $i\leq i_{2}$ gives
that

$\displaystyle\mathbb{P}\left(d_{S}(v)\leq
i_{2}\right)<d(v)\exp\left(-\frac{1}{2}\varepsilon^{2}i_{0}\right).$

The argument for the upper bound is obtained symmetrically mutatis mutandis,
and the lemma follows from the union bound. ∎

######  Lemma 3.4.

As in Lemma 3.3, suppose $\varepsilon=4\delta^{1/64}$. The probability that

$\displaystyle d_{S}(v)\in\left[\gamma d(v)(1-2\varepsilon),\gamma
d(v)(1+2\varepsilon)\right]$

for all vertices $v\in S$ such that $d(v)>\delta^{-1/32}\gamma^{-1}\log M$ is
$1-o\left(M^{-5}\right)$.

###### Proof.

We apply Lemma 3.3 along with the union bound over all vertices $v\in S$ such
that $d(v)>\delta^{-1/32}\gamma^{-1}\log M$. Lemma 3.3 implies that the
probability that $d_{S}(v)$ is outside the specified range is at most
$2n\exp\left(-\frac{1}{2}\varepsilon^{2}i_{0}\right)$. Note that by
assumption, $i_{0}>\delta^{-1/32}\log M$, where $\delta\to 0$. Combining this
with the union bound implies that the probability that there exists some
vertex $v$ with degree greater than $\delta^{-1/32}\gamma^{-1}\log M$ such
that $d_{S}(v)$ is outside its specified range is at most
$2n^{2}\exp\left(-\frac{1}{2}\varepsilon^{2}\delta^{-1/32}\log
M\right)=2n^{2}M^{-8}$. Since $n\leq M$, the claim holds. ∎

###  3.2 Distribution of small vertex degrees

Define ${\bar{{J}}}=\min\\{{J},\Delta\\}$. Using this notation simplifies some
arguments by allowing us to combine cases where ${J}\leq\Delta$ and
${J}>\Delta$. In the following lemma, we use a slightly more complicated
switching than in Lemma 3.1, moving three edges instead of the usual two. The
reason for this is that we wish to preserve the degrees of two adjacent
vertices, $v_{1}$ and $v_{2}$, in $G[S]$, while switching away the edge
between them. To use the previous switching, this means that the two other
adjacent vertices in the switching must be in $S$, and adjacent. Possible
variations in the number of choices of such a pair of adjacent vertices would
cause a problem. Instead, we use a trick with its origins in the switchings
introduced by McKay and Wormald [10], whereby a third pair of vertices are
involved in order to make the number of switchings much more stable.

######  Lemma 3.5.

Suppose $({\bm{d}},S)$ satisfies condition 2.1. Let $k$ be fixed, let
$\\{v_{1},\dots,v_{k}\\}\subset S_{\rm{small}}$, and let $G$ be a uniformly
random graph with degree sequence ${\bm{d}}$. Then

$\displaystyle\mathbb{P}\left(\left.v_{1}v_{2}\in
E(G)\right|d_{S}(v_{1})=i_{1},\dots,d_{S}(v_{k})=i_{k}\right)=O\left(\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)$

for all $i_{j}\leq d(v_{j})$ for $j\leq k$, and $\mathbb{P}\left(v_{1}v_{2}\in
E(G)\right)=O\left(\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)$.

###### Proof.

First note that if one of $i_{1}$ or $i_{2}$ is equal to $0$, then the
probability in question is 0. Thus we may suppose that $i_{1},~{}i_{2}>0$.

Let $A_{v_{1},v_{2}}$ be the subset of $\mathcal{G}({\bm{d}})$ consisting of
the graphs where $v_{1}$ and $v_{2}$ are adjacent and each vertex $v_{j}$ has
induced degree $i_{j}$ for $j\leq k$. Similarly, let $B_{v_{1},v_{2}}$ be the
subset of $\mathcal{G}({\bm{d}})$ where $v_{1}$ and $v_{2}$ are not adjacent
and each vertex $v_{j}$ has induced degree $i_{j}$ for $j\leq k$. We define a
switching between $A_{v_{1},v_{2}}$ and $B_{v_{1},v_{2}}$ as follows. Suppose
$G\in A_{v_{1},v_{2}}$. To perform a switching, choose two ordered pairs of
vertices in $V(G)$, $(x,y)$ and $(a,b)$, such that $ab,\ xy\in E(G)$, and $y,\
b\in S$, and with the additional requirements that

  1. (a)

the vertices $\left\\{v_{1},v_{2},a,b,x,y\right\\}$ are distinct, with the
exception that $y=b$ is permissible,

  2. (b)

$v_{1}y,\ ax,\ v_{2}b\notin E(G)$, and

  3. (c)

the degrees of $v_{1},\dots,v_{k}$ in $G[S]$ are unchanged by the switching.

The switching deletes the edges $v_{1}v_{2},\ xy,\ ab$ and replaces them with
$v_{1}y,\ ax,\ v_{2}b$, creating a graph $G^{\prime}\in B_{v_{1},v_{2}}$. A
diagram illustrating this switching is given in Figure 2.

$b$$v_{2}$$v_{1}$$y$$x$$a$$G\in A_{v_{1},v_{2}}$

$b$$v_{2}$$v_{1}$$y$$x$$a$$G^{\prime}\in B_{v_{1},v_{2}}$

Figure 2: A switching. Present edges are given as solid lines, forbidden edges
are given as dashed. Other edges can be present or absent.

First we determine a lower bound on the number of switchings that can be
applied to each $G\in A_{v_{1},v_{2}}$. Since $y$ and $b$ are in $S$, there
are $d(S)^{2}$ choices for $\\{a,b,x,y\\}$ ignoring the constraints (a) – (c).
Noting that the induced degrees of $v_{1},\dots,v_{k}$ are unchanged by the
switching if $b,y\in S$ and $\\{v_{1},\dots,v_{k},a,b,x,y\\}$ are distinct, we
see that the number of choices for $\\{v_{1},v_{2},a,b,x,y\\}$ that violate
(a) or (c) is $O(d(S)k{\bar{{J}}})$, and the number of choices that violate
(b) is $O(d(S)\Delta^{2})$. Since $k$ is fixed, this implies that the number
of switchings that can be applied to each $G\in A_{v_{1},v_{2}}$ is
$d(S)(d(S)-O(\Delta^{2}))$.

Now we determine an upper bound on the number of switchings that create a
particular $G^{\prime}\in B_{v_{1},v_{2}}$. The definition of
$B_{v_{1},v_{2}}$ implies that the number of choices for $y$ is $i_{1}$, and
similarly the number of choices for $b$ is $i_{2}$. The number of choices for
the adjacent pair $(a,x)$ is at most $M$. Thus, the number of switchings that
create $G^{\prime}$ is at most $i_{1}i_{2}M$.

Combining these two bounds gives

$\displaystyle\frac{|A_{v_{1},v_{2}}|}{|B_{v_{1},v_{2}}|}$
$\displaystyle\leq\frac{i_{1}i_{2}M}{d(S)^{2}}\left(1+O\left(\frac{\Delta^{2}}{d(S)}\right)\right).$

Since $\Delta^{2}=o(d(S))$ by assumption, the multiplicative error term is
$1+o(1)$. Thus, the probability that the vertices $v_{1}$ and $v_{2}$ are
adjacent, conditional on the induced degrees of $\\{v_{1},\dots,v_{k}\\}$, is
at most

$\displaystyle\mathbb{P}\left(\left.v_{1}v_{2}\in
E(G)\right|d_{S}(v_{1})=i_{1},\dots,d_{S}(v_{k})=i_{k}\right)$
$\displaystyle=\frac{|A_{v_{1},v_{2}}|}{|A_{v_{1},v_{2}}|+|B_{v_{1},v_{2}}|}\leq\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}(1+o(1)),$

since both $i_{1}$ and $i_{2}$ are at most $d(v_{1})$ and $d(v_{2})$
respectively and $v_{1},v_{2}\in S_{\rm{small}}$. This proves the first claim,
and the second claim follows immediately from the law of total probability. ∎

######  Lemma 3.6.

Suppose $({\bm{d}},S)$ satisfies condition 2.1. Let $k$ be fixed and
$\\{v_{1},\dots,v_{k}\\}\subset S_{\rm{small}}$. Let
$Z_{j}\sim\textup{Bin}\left(j,\frac{d(S)}{M}\right)$. Then, uniformly for all
$i_{1},\ldots,i_{k}\leq{\bar{{J}}}$, we have

$\displaystyle\mathbb{P}\left(d_{S}(v_{1})=i_{1},\dots,d_{S}(v_{k})=i_{k}\right)$
$\displaystyle=\prod_{j=1}^{k}\mathbb{P}\left(d_{S}(v_{j})=i_{j}\right)\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right)$
$\displaystyle=\prod_{j=1}^{k}\mathbb{P}\left(Z_{d(v_{j})}=i_{j}\right)\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right).$

###### Proof.

We condition on the event that $d_{S}(v_{j})=i_{j}$ for all $j\geq 2$, for an
arbitrary choice of $(i_{2},\dots,i_{k})$ where $i_{j}\leq d(v_{j})$. It
suffices to show that

$\displaystyle\mathbb{P}\left(\left.d_{S}(v_{1})=i_{1}\right|d_{S}(v_{2})=i_{2},\dots,d_{S}(v_{k})=i_{k}\right)=\mathbb{P}\left(Z_{d(v_{1})}=i_{1}\right)\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right),$

as well as

$\displaystyle\mathbb{P}\left(d_{S}(v_{1})=i_{1}\right)=\mathbb{P}\left(Z_{d(v_{1})}=i_{1}\right)\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right).$

Let $C_{i}$ be the set of graphs in $\mathcal{G}({\bm{d}})$ such that
$d_{S}(v_{1})=i$ and $d_{S}(v_{j})=i_{j}$ for all $j\geq 2$. That is, for all
$G\in C_{i}$,
$(d_{S}(v_{1}),d_{S}(v_{2}),\dots,d_{S}(v_{k}))=(i,i_{2},\dots,i_{k})$. We
apply a switching similar to the one used in Lemma 3.1 to switch between
$C_{i+1}$ and $C_{i}$. This switching is illustrated in Figure 3. The
important difference between this switching and the switching used in the
proof of Lemma 3.1 is that the induced degrees of vertices $v_{2},\dots,v_{k}$
are maintained. Other than this extra restriction, the edges are chosen in the
same way as the switching used in Lemma 3.1.

$y$$v_{1}$$u$$x$$G\in C_{i+1}$

$y$$v_{1}$$u$$x$$G^{\prime}\in C_{i}$

Figure 3: The switching used in this proof. Here $v_{1},y\in S$ and
$u\in{\overline{S}}$. Importantly, the switching does not alter
$d_{S}(v_{2}),\dots,d_{S}(v_{k})$.

Now we define the switching formally. Suppose $G\in C_{i+1}$. Choose a vertex
$y$ such that $v_{1}y\in E(G)$ and $y\in S$, as well as an ordered pair of
vertices $(u,x)$ such that $ux\in E(G)$ and $u\in{\overline{S}}$, with the
extra restrictions that

  1. (a)

the vertices $\left\\{u,v_{1},x,y\right\\}$ are distinct,

  2. (b)

$xy\notin E(G)$ and $uv_{1}\notin E(G)$,

  3. (c)

the degrees of $v_{1},\dots,v_{k}$ in $G[S]$ are unchanged by the switching.

The switching deletes edges $v_{1}y$ and $ux$, replacing these edges with
$uv_{1}$ and $xy$ and hence creating a new graph $G^{\prime}\in C_{i}$.

To count the switchings that can be applied to each $G\in C_{i+1}$, we carry
out a computation analogous to that in the proof of Lemma 3.1. For each $G\in
C_{i+1}$, there are $(i+1)d({\overline{S}})$ choices for $\\{u,v_{1},x,y\\}$
such that $v_{1}y,ux\in E(G)$, $y\in S$ and $u\notin S$. To estimate the
number of switchings, we bound from above the expected number of choices for
$\\{u,v_{1},x,y\\}$ such that (a), (b) or

  1. (c′)

$\\{v_{2},\dots,v_{k}\\}\cap\\{u,v_{1},x,y\\}=\emptyset$

is false. Note that (c′) is slightly stricter than (c). As before, there are
at most $3(i+1)\Delta^{2}$ choices for $\\{u,v_{1},x,y\\}$ that do not satisfy
(a) or (b). Now we consider (c). By assumption, $v_{1}\neq v_{j}$ for $j\geq
2$, and $u\notin S$. Thus, the only possibilities for a non-empty intersection
are if $x\in\\{v_{2},\dots,v_{k}\\}$ or $y\in\\{v_{2},\dots,v_{k}\\}$. In the
former case, there are at most $k\Delta$ choices for a neighbour $u$ of $x$.
With at most $i+1$ choices for $y$ adjacent to $v_{1}$, this means that there
are at most $(i+1)k\Delta$ choices for $\\{u,v_{1},x,y\\}$. In the second
case, there are $O(1)$ choices for $y\in\\{v_{2},\dots,v_{k}\\}$, and for each
one Lemma 3.5 gives

$\displaystyle\mathbb{P}\left(\left.v_{1}y\in
E(G)\right|d_{S}(v_{1})=i+1,\dots,d_{S}(v_{k})=i_{k}\right)$
$\displaystyle=O\left(\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right).$

In such cases, there are $d({\overline{S}})$ choices for $ux$. Thus, the
expected number of choices for $\\{u,v_{1},x,y\\}$ where
$y\in\\{v_{2},\dots,v_{k}\\}$, for a random $G\in C_{i+1}$, is
$d({\overline{S}})O\left(\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)$. Therefore,
the average number of valid switchings that can be applied to each $G\in
C_{i+1}$ is

$\displaystyle(i+1)(d({\overline{S}})-O(\Delta^{2}))-d({\overline{S}})O\left(\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)=(i+1)d({\overline{S}})\left(1-O\left(\frac{\Delta^{2}}{M}+\frac{{\bar{{J}}}^{2}M}{(i+1)d(S)^{2}}\right)\right),$

since $d({\overline{S}})=\Theta(M)$.

Next we determine upper and lower bounds for the number of switchings that
create a particular $G^{\prime}\in C_{i}$. There are $d(v_{1})-i$ choices for
the vertex $u\notin S$ such that $v_{1}u\in E(G)$, and $d(S)$ choices for an
ordered pair of adjacent vertices $(x,y)$ such that $y\in S$. Each such choice
is valid if all of the following conditions are satisfied:

  1. (i)

the vertices $\left\\{u,v_{1},x,y\right\\}$ are distinct,

  2. (ii)

$v_{1}y\notin E(G^{\prime})$ and $ux\notin E(G^{\prime})$,

  3. (iii)

the induced degrees of $v_{2},\dots,v_{k}$ are unchanged by the switching.

By the same reasoning as used in the proof of Lemma 3.1, the number of choices
for these vertices that do not satisfy one of (i) or (ii) is
$O((d(v_{1})-i)\Delta^{2})$.

Again, as an upper bound on the number of choices that do not satisfy (iii),
we count the choices where $\\{u,v_{1},x,y\\}$ and $\\{v_{2},\dots,v_{k}\\}$
intersect non-trivially. Note that $v_{1}\neq v_{j}$ for any $j\geq 2$ by
assumption, and $u\neq v_{j}$ since $u\in{\overline{S}}$. Thus, we only need
to consider $x\in\\{v_{2},\dots,v_{k}\\}$ or $y\in\\{v_{2},\dots,v_{k}\\}$,
which give at most $2(d(v_{1})-i)\sum_{j=2}^{k}d(v_{j})$ choices for
$\\{u,v_{1},x,y\\}$. Since $k=O(1)$ and each $v_{j}$ has degree at most
${\bar{{J}}}$ (since ${\bar{{J}}}$ bounds the maximum degree of the vertices
in $S_{\rm{small}}$), the number of switchings that can create a given
$G^{\prime}\in C_{i}$ is

$\displaystyle(d(v_{1})-i)d(S)\left(1-O\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}}{d(S)}\right)\right).$

Thus, it follows that

$\displaystyle\frac{|C_{i}|}{|C_{i+1}|}=\frac{i+1}{d(v_{1})-i}\frac{d({\overline{S}})}{d(S)}\left(1+O\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$
(3.3)

Let
$p_{i}=\mathbb{P}\left(\left.d_{S}(v_{1})=i\right|d_{S}(v_{2})=i_{2},\dots,d_{S}(v_{k})=i_{k}\right)$
for $i\in\left\\{0,\dots,d(v_{1})\right\\}$. Recall that $\gamma=d(S)/M$. Then
3.3 implies that, for all $i\in\left\\{0,\dots,d(v_{1})\right\\}$,

$\displaystyle\frac{p_{i+1}}{p_{i}}=\frac{d(v_{1})-i}{i+1}\frac{d(S)}{d({\overline{S}})}\left(1+O\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)=\frac{d(v_{1})-i}{i+1}\frac{\gamma}{1-\gamma}\left(1+O\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$

Thus, we can express $p_{i}$ in terms of $p_{0}$:

$\displaystyle p_{i}$ $\displaystyle={d(v_{1})\choose
i}\left(\frac{1-\gamma}{\gamma}\right)^{i}p_{0}\left(1+O\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)^{i}$
$\displaystyle={d(v_{1})\choose
i}\left(\frac{1-\gamma}{\gamma}\right)^{i}p_{0}\exp\left(O\left(i\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right)$
$\displaystyle={d(v_{1})\choose
i}\left(\frac{1-\gamma}{\gamma}\right)^{i}p_{0}\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right),$
(3.4)

since $i\leq d(v_{1})$ and the error term goes to 0 when
$d(v_{1})\leq{\bar{{J}}}$. The sum of all $p_{i}$ must be equal to 1, and thus

$\displaystyle 1$ $\displaystyle=\sum_{i=0}^{d(v_{1})}\left[{d(v_{1})\choose
i}\left(\frac{\gamma}{1-\gamma}\right)^{i}\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right)p_{0}\right].$

Since the error is uniformly bounded for all terms in the sum, and all terms
are positive, the relative error of the whole sum is at most
$O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)$.
Thus,

$\displaystyle\sum_{i=0}^{d(v_{1})}\left[{d(v_{1})\choose
i}\left(\frac{\gamma}{1-\gamma}\right)^{i}p_{0}\right]=1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$

It follows from the previous equation that

$\displaystyle p_{0}$
$\displaystyle=\left(\sum_{i=0}^{d(v_{1})}{d(v_{1})\choose
i}\left(\frac{\gamma}{1-\gamma}\right)^{i}\right)^{-1}\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right)$
$\displaystyle=(1-\gamma)^{d(v_{1})}\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right).$

Applying Section 3.2 for all $i\leq d(v_{1})$, we obtain that

$\displaystyle\mathbb{P}\left(\left.d_{S}(v_{1})=i_{1}\right|d_{S}(v_{2})=i_{2},\dots,d_{S}(v_{k})=i_{k}\right)$
$\displaystyle=\mathbb{P}\left(Z_{d(v_{1})}=i_{1}\right)\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right)$
(3.5)

for each choice of $i_{j}\leq d(v_{j})$ for all $j\leq k$. By the law of total
probability, summing over all ordered tuples $(i_{2},\dots,i_{k})$ such that
$i_{j}\leq d(v_{j})$ for all $j\geq 2$ gives that

$\displaystyle\mathbb{P}\left(d_{S}(v_{1})=i_{1}\right)$
$\displaystyle=\sum_{(i_{2},\dots,i_{k})}\mathbb{P}\left({d_{S}(v_{1})=i_{1}}\left|{\bigcup_{j=2}^{k}\\{d_{S}(v_{j})=i_{j}\\}}\right.\right)\mathbb{P}\left(\bigcup_{j=2}^{k}\\{d_{S}(v_{j})=i_{j}\\}\right)$
$\displaystyle=\mathbb{P}\left(Z_{d(v_{1})}=i_{1}\right)\left(1+O\left(d(v_{1})\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right).$
(3.6)

Since $d(v_{1})\leq{\bar{{J}}}$, the two required bounds follow. ∎

With this result, we can prove Theorem 2.3(b). We also use the following
Chernoff bound: if $X\sim\textup{Bin}\left((\right)n,p)$ and $\varepsilon>0$,
then

$\displaystyle\mathbb{P}\left(|X-np|\geq\varepsilon np\right)\leq
2\exp\left(-\varepsilon^{2}np/3\right).$ (3.7)

######  Lemma 3.7.

For all $k$ such that $d(i_{k})\leq\delta^{1/32}{J}$, the following holds. We
have $d_{H}(k)\leq 2\gamma\delta^{1/32}{J}$, and with probability
$1-o(M^{-2})$, we have $d_{S}(k)\leq 2\gamma\delta^{1/32}{J}$.

###### Proof.

Suppose that $k$ is such that $d(i_{k})\leq\delta^{1/32}{J}$. The first claim
is equivalent to the claim that $N(2\gamma\delta^{1/32}{J})\geq k$, where
$N(x)$ is defined in Definition 2.2 as the sum over all $i\in S$ of the
probability that $Z_{d(i)}\leq x$, rounded to the nearest integer. Since
${\bm{d}}$ is ordered in non-decreasing order, we know that $d(i_{j})\leq
d(i_{k})\leq\delta^{1/32}{J}$ for all $j\leq k$. Thus, the Chernoff bound
given in 3.7 implies that

$\displaystyle\mathbb{P}\left(Z_{d(i_{j})}\leq
2\gamma\delta^{1/32}{J}\right)\leq\mathbb{P}\left(Z_{d(i_{k})}\leq
2\gamma\delta^{1/32}{J}\right)\leq\mathbb{P}\left(Z_{\delta^{1/32}{J}}\leq
2\gamma\delta^{1/32}{J}\right)=1-o(M^{-3})$ (3.8)

for all $j\leq k$. Therefore,

$\displaystyle\sum_{i\in S}\mathbb{P}\left(Z_{d(i)}\leq
2\gamma\delta^{1/32}{J}\right)\geq k-o(M^{-2}),$

and thus $N(2\gamma\delta^{1/32}{J})\geq k$. This proves the first claim. For
the second claim, note that if $d(k)\leq\delta^{1/32}{J}$, then $k\in
S_{\rm{small}}$. Therefore, Lemma 3.6 implies that
$\mathbb{P}\left(d_{S}(k)=j\right)=\mathbb{P}\left(Z_{d(i_{k})}=j\right)(1+o(1))$.
Thus,

$\displaystyle\mathbb{P}\left(d_{S}(k)>2\gamma\delta^{1/32}{J}\right)=\mathbb{P}\left(Z_{d(i_{k})}>2\gamma\delta^{1/32}{J}\right)(1+o(1))\leq\mathbb{P}\left(Z_{\delta^{1/32}{J}}>2\gamma\delta^{1/32}{J}\right)(1+o(1)).$

Combining this with Equation 3.8 then implies that
$\mathbb{P}\left(d_{S}(k)>2\gamma\delta^{1/32}{J}\right)=o(M^{-3})$. The
second claim then follows from the union bound over all such $k$. ∎

###  3.3 Concentration of the counts of small vertex degrees

Recall the definitions of $Y_{i}$ and $\tilde{y}_{i}$:

$\displaystyle Y_{i}=\sum_{j\in
S_{\rm{small}}}\mathbbm{1}_{\left\\{d_{S}(j)=i\right\\}}\quad\mbox{and}\quad\tilde{y}_{i}=\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(Z_{d(j)}=i\right).$

We can show concentration of $Y_{i}$ around $\tilde{y}_{i}$ for all
$i\leq{J}$. Firstly, Lemma 3.6 implies that

$\displaystyle\mathbb{E}\left[Y_{i}\right]=\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)=\tilde{y}_{i}\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\right).$

We also know that if ${\bm{d}}_{S}$ satisfies the concentration bound given in
Theorem 2.3(a) then $n_{i}({\bm{d}}_{S})=Y_{i}$ for all
$i\leq\frac{1}{2}\gamma{J}$. Since this is a.a.s. true, studying $Y_{i}$ and
$n_{i}({\bm{d}}_{S})$ are effectively equivalent for small $i$. It also
follows that

$\displaystyle n_{i}({\bm{d}}_{H})=N(i)-N(i-1)$
$\displaystyle=\left\lfloor\sum_{i\in S}\mathbb{P}\left(Z_{j}\leq
i\right)+\frac{1}{2}\right\rfloor-\left\lfloor\sum_{i\in
S}\mathbb{P}\left(Z_{j}\leq i-1\right)+\frac{1}{2}\right\rfloor$
$\displaystyle=\sum_{i\in S}\mathbb{P}\left(Z_{j}=i\right)\pm 1=\sum_{i\in
S_{\rm{small}}}\mathbb{P}\left(Z_{j}=i\right)\pm(1+o(M^{-5})).$

Thus, $n_{i}({\bm{d}}_{H})=\tilde{y}_{i}\pm 2$. We study $Y_{i}$ rather than
$n_{i}({\bm{d}}_{S})$ as the analysis is slightly neater. We get the following
bound on the variance of $Y_{i}$.

######  Lemma 3.8.

For all $i\leq{J}$,
$\textup{Var}\left(Y_{i}\right)\leq\mathbb{E}\left[Y_{i}\right]\left(1+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\mathbb{E}\left[Y_{i}\right]\right)$.

###### Proof.

Let $V_{k}$ be the indicator variable for the event that vertex $k\in
S_{\rm{small}}$ has induced degree $i$. Then $Y_{i}=\sum_{k\in
S_{\rm{small}}}V_{k}$. This implies that

$\displaystyle\textup{Var}\left(Y_{i}\right)$
$\displaystyle=\textup{Var}\left(\sum_{k\in
S_{\rm{small}}}V_{k}\right)=\sum_{k\in
S_{\rm{small}}}\textup{Var}\left(V_{k}\right)+\sum_{j\neq
k}{\mbox{Cov}\left(V_{j},V_{k}\right)},$ (3.9)

where the last sum is over all ordered pairs $(j,k)\in S_{\rm{small}}^{2}$
where $j\neq k$. Each $V_{k}$ is a Bernoulli random variable, and thus
$\textup{Var}\left(V_{k}\right)=\mathbb{P}\left(d_{S}(k)=i\right)\left(1-\mathbb{P}\left(d_{S}(k)=i\right)\right)$.
So the first summation is bounded by

$\displaystyle\sum_{k\in
S_{\rm{small}}}\textup{Var}\left(V_{k}\right)=\sum_{k\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(k)=i\right)(1-\mathbb{P}\left(d_{S}(k)=i\right))\leq\mathbb{E}\left[Y_{i}\right].$
(3.10)

Now consider the covariance summation in Equation 3.9. An application of Lemma
3.6 provides a bound on the covariance terms in the second summation when
$j,k\in S_{\rm{small}}$:

$\displaystyle{\mbox{Cov}\left(V_{j},V_{k}\right)}$
$\displaystyle=\mathbb{P}\left(d_{S}(j)=i,\
d_{S}(k)=i\right)-\mathbb{P}\left(d_{S}(j)=i\right)\mathbb{P}\left(d_{S}(k)=i\right)$
$\displaystyle=\mathbb{P}\left(d_{S}(j)=i\right)\mathbb{P}\left(d_{S}(k)=i\right)O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$

Thus, the summation in Equation 3.9 of the covariances over all ordered pairs
$(j,k)\in S_{\rm{small}}^{2}$ where $j\neq k$ is equal to

$\displaystyle\left(\sum_{j\in S_{\rm{small}}}\sum_{k\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)\mathbb{P}\left(d_{S}(k)=i\right)-\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)^{2}\right)O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)$
$\displaystyle=\left(\left(\sum_{k\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(k)=i\right)\right)^{2}-\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)^{2}\right)O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$

Noting that $\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)^{2}\in[0,\mathbb{E}\left[Y_{i}\right]^{2}]$,
we obtain

$\displaystyle\sum_{j\neq k\in
S_{\rm{small}}}{\mbox{Cov}\left(V_{j},V_{k}\right)}$
$\displaystyle\leq\mathbb{E}\left[Y_{i}\right]^{2}\cdot
O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$
(3.11)

Combining (3.10) and (3.11) gives an upper bound on the variance of $Y_{i}$:

$\displaystyle\textup{Var}\left(Y_{i}\right)$
$\displaystyle\leq\mathbb{E}\left[Y_{i}\right]+O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\mathbb{E}\left[Y_{i}\right]^{2}.$

The claim of the lemma immediately follows. ∎

######  Remark 3.9.

Recall that we assume $\Delta^{2}(\gamma^{-1}\log M)^{12}\leq\delta\gamma M$
for some $\delta\to 0$ slowly. Since we suppose that
$\delta=\omega(\log^{-1}M)$, this implies a bound on
$\frac{\Delta^{2}}{d(S)}+\frac{{J}^{2}M}{d(S)^{2}}$:

$\displaystyle\frac{\Delta^{2}}{d(S)}$
$\displaystyle\leq\delta\frac{1}{\gamma^{-12}\log^{12}M}\leq\delta^{1/2}\gamma{J}^{-8}\log^{-1}M,$
$\displaystyle\frac{{J}^{2}M}{d(S)^{2}}$
$\displaystyle=\frac{{J}^{2}M}{\gamma^{2}M^{2}}\leq\gamma{J}^{-8}o(\log^{-2}M)\leq\delta^{1/2}\gamma{J}^{-8}\log^{-1}M,$

and in particular,
$\frac{\Delta^{2}}{d(S)}+\frac{{J}^{2}M}{d(S)^{2}}=o(\gamma{J}^{-8}\log^{-1}M)$.

######  Lemma 3.10.

Suppose $i\leq\frac{1}{2}\gamma{J}$. If
$\mathbb{E}\left[Y_{i}\right]\geq\gamma^{-1}{J}^{7}\sqrt{\log M}$, then

$\displaystyle\mathbb{P}\left(|Y_{i}-\mathbb{E}\left[Y_{i}\right]|\geq\frac{\gamma\mathbb{E}\left[Y_{i}\right]}{2{J}^{3}}\right)=O\left(\frac{\gamma^{-1}{J}^{-1}}{\sqrt{\log
M}}\right),$

and if $\mathbb{E}\left[Y_{i}\right]\leq\gamma^{-1}{J}^{7}\sqrt{\log M}$, then

$\displaystyle\mathbb{P}\left(|Y_{i}-\mathbb{E}\left[Y_{i}\right]|\geq{J}^{4}\sqrt{\log
M}\right)=O\left(\frac{\gamma^{-1}{J}^{-1}}{\sqrt{\log M}}\right).$

###### Proof.

First suppose that
$\mathbb{E}\left[Y_{i}\right]\geq\gamma^{-1}{J}^{7}\sqrt{\log M}$. Applying
Chebyshev’s inequality with $t=\alpha\mathbb{E}\left[Y_{i}\right]$ gives

$\displaystyle\mathbb{P}\left(|Y_{i}-\mathbb{E}\left[Y_{i}\right]|\geq\alpha\mathbb{E}\left[Y_{i}\right]\right)$
$\displaystyle\leq\frac{\textup{Var}\left(Y_{i}\right)}{\alpha^{2}\mathbb{E}\left[Y_{i}\right]^{2}}\leq\frac{1}{\alpha^{2}\mathbb{E}\left[Y_{i}\right]}+\frac{1}{\alpha^{2}}O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right).$

Now let $\alpha=\frac{1}{2}\gamma{J}^{-3}$. Then since ${\bar{{J}}}\leq{J}$,

$\displaystyle\frac{\textup{Var}\left(Y_{i}\right)}{\alpha^{2}\mathbb{E}\left[Y_{i}\right]^{2}}$
$\displaystyle\leq\frac{4{J}^{6}}{\gamma^{2}\mathbb{E}\left[Y_{i}\right]}+4\gamma^{-2}{J}^{7}O\left(\frac{\Delta^{2}}{d(S)}+\frac{{J}^{2}M}{d(S)^{2}}\right)\leq
8(\gamma{J}\sqrt{\log M})^{-1},$

since Remark 3.9 states that
$\frac{\Delta^{2}}{d(S)}+\frac{{J}^{2}M}{d(S)^{2}}=o(\gamma{J}^{-8}\log^{-1}M)$.
This proves the first part of the lemma. Now suppose that
$\mathbb{E}\left[Y_{i}\right]\leq\gamma^{-1}{J}^{7}\sqrt{\log M}$. Then it
follows that

$\displaystyle\textup{Var}\left(Y_{i}\right)$
$\displaystyle=\mathbb{E}\left[Y_{i}\right]+\mathbb{E}\left[Y_{i}\right]^{2}O\left({\bar{{J}}}\left(\frac{\Delta^{2}}{d(S)}+\frac{{\bar{{J}}}^{2}M}{d(S)^{2}}\right)\right)\leq\gamma^{-1}{J}^{7}\sqrt{\log
M}(1+o(1)).$

Then applying Chebyshev’s inequality with $t:={J}^{4}\sqrt{\log M}$ gives that

$\displaystyle\mathbb{P}\left(|Y_{i}-\mathbb{E}\left[Y_{i}\right]|\geq
t\right)\leq\frac{\gamma^{-1}{J}^{7}\sqrt{\log M}(1+o(1))}{{J}^{8}\log M}\leq
2(\gamma{J}\sqrt{\log M})^{-1}.$

This completes the proof. ∎

We note here that the above proof is the only point in the paper that we use
the assumption that $\delta=\Omega((\log\log M)^{-1})$. If the bound on
$\frac{J^{2}M}{d(S)^{2}}$ in Remark 3.9 is replaced with
$\delta^{1/4}\gamma{J}^{-8}\log^{-1}M$, then the bound on $\delta$ can be
removed entirely. This could be useful if slightly different error bounds on
${\bm{d}}_{S}$ were required, trading precision in the frequencies of the
smaller entries for greater precision in the values of the larger entries.

Now we prove Theorem 2.3(c).

######  Corollary 3.11.

With probability $1-o(1)$,

$\displaystyle\left\lvert
n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H})\right\rvert\leq\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5}$

for all $i\leq\frac{1}{2}\gamma{J}$.

###### Proof.

First we bound $\mathbb{E}\left[Y_{i}\right]$ in terms of
$n_{i}({\bm{d}}_{H})$ using Lemma 3.6 and Remark 3.9 bounding the error term.
This implies that for each $i\leq{J}$,

$\displaystyle\mathbb{E}\left[Y_{i}\right]=\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(d_{S}(j)=i\right)=\sum_{j\in
S_{\rm{small}}}\mathbb{P}\left(Z_{d(j)}=i\right)(1+o(\gamma{J}^{-8}))=(n_{i}({\bm{d}}_{H})\pm
2)(1+o(\gamma{J}^{-8})),$

since $n_{i}({\bm{d}}_{H})=\tilde{y}_{i}\pm 2$ for all such $i$. We also know
that, with probability $1-o(1)$, $Y_{i}=n_{i}({\bm{d}}_{S})$ for all
$i\leq\frac{1}{2}\gamma{J}$. Then we apply Lemma 3.10 and the triangle
inequality to say that a.a.s. for all $i\leq\frac{1}{2}\gamma{J}$,

$\displaystyle|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H})|\leq|Y_{i}-\tilde{y}_{i}|+2$
$\displaystyle\leq|Y_{i}-\mathbb{E}\left[Y_{i}\right]|+|\mathbb{E}\left[Y_{i}\right]-\tilde{y}_{i}|+2$
$\displaystyle\leq\frac{\gamma\mathbb{E}\left[Y_{i}\right]}{2{J}^{3}}+{J}^{4}\sqrt{\log
M}+o(\tilde{y}_{i}\gamma{J}^{-8})+2$
$\displaystyle=\frac{\gamma\tilde{y}_{i}(1+o(1))}{2{J}^{3}}+{J}^{4}\sqrt{\log
M}+1+o(\tilde{y}_{i}\gamma{J}^{-8})+2$ $\displaystyle\leq\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5},$

since ${J}=\delta^{-1/16}\gamma^{-1}\log M$. This completes the proof. ∎

The factor of $\gamma$ in the “multiplicative” error term (the $\gamma
n_{i}({\bm{d}}_{H})/{J}^{3}$ term) is particularly useful because it implies
that, for $k\leq\frac{1}{2}\gamma{J}$, a.a.s.

$\displaystyle\left|\sum_{i=0}^{k}n_{i}({\bm{d}}_{H})-n_{i}({\bm{d}}_{S})\right|\leq\sum_{i=0}^{k}\left(\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5}\right)\leq\gamma^{2}{J}^{6}+\frac{\gamma|S|}{{J}^{3}}.$

Since $|S|\leq d(S)=\gamma M$ and $M_{H}\sim\gamma^{2}M$, this implies that
this sum is $O(M_{H}/{J}^{3})$. This is particularly useful in certain proofs.
The bounds given in Lemma 3.10 are not optimal in either the multiplicative or
the additive error. An similar proof of Lemma 3.10 with a different threshold
for $\mathbb{E}\left[Y_{i}\right]$ can give better error margins in one
direction or the other, but this choice strikes a balance that is sufficient
for our purposes. With this result, we can now prove Theorem 2.3.

###### Proof of Theorem 2.3.

Corollary 3.11 proves part (c), and part (b) follows from Lemma 3.7. Now it
remains to prove part (a). We show in Lemma 3.4 that a.a.s. $d_{S}(k)=\gamma
d(i_{k})\left(1\pm 8\delta^{1/64}\right)$ uniformly for all $k$ such that
$d(i_{k})\geq\delta^{1/32}{J}$. Now we prove claim (a) by showing that
deterministically $d_{H}(k)=\gamma d(i_{k})\left(1\pm 3\delta^{1/64}\right)$.
For each $i\in S$ such that $d(i)\geq\delta^{1/32}{J}$, define

$\displaystyle d(i)^{-}$ $\displaystyle=\gamma
d(i)\left(1-3\delta^{1/64}\right)$ and $\displaystyle d(i)^{+}$
$\displaystyle=\gamma d(i)\left(1+3\delta^{1/64}\right).$

The Chernoff bound given in (3.7) implies that
$\mathbb{P}\left(|Z_{d(j)}-\gamma d(j)|\geq\delta^{1/64}\gamma d(j)\right)\leq
2\exp{-3\delta^{1/32}\gamma{J}}=2M^{-3}$. Thus,

$\displaystyle\mathbb{P}\left(Z_{d(i)}\leq
d(i)^{+}\right)-\mathbb{P}\left(Z_{d(i)}<d(i)^{-}\right)=1-o(M^{-2}).$ (3.12)

We use Equation 3.12 to show that

$\displaystyle N\left(d(i_{k})^{-}-1\right)\leq k-1\quad\mbox{and}\quad
N\left(d(i_{k})^{+}\right)\geq k$ (3.13)

for all $k\geq\ell$. Together these statements imply that for all $i_{k}$ such
that $d(i_{k})\geq\delta^{1/32}{J}$, the $k$th entry of ${\bm{d}}_{H}$ is
between $d(i_{k})^{-}$ and $d(i_{k})^{+}$. To prove these claims, recall that
the degree sequence ${\bm{d}}$ is ordered in non-decreasing order, so
$d(i_{j})\leq d(i_{k})$ for all $j\leq k$ and $d(i_{j})\geq d(i_{k})$ for all
$j\geq k$. This means that, by Equation 3.12,

$\displaystyle\sum_{j\geq
k}\mathbb{P}\left(Z_{d(i_{j})}<d(i_{k})^{-}\right)=o(M^{-1}).$

This in turn implies that

$\displaystyle N\left(d(i_{k})^{-}-1\right)$
$\displaystyle=\left\lfloor\sum_{i\in
S}\mathbb{P}\left(Z_{d(i)}<d(i_{k})^{-}\right)+\frac{1}{2}\right\rfloor$
$\displaystyle=\left\lfloor\sum_{j<k}\mathbb{P}\left(Z_{d(i_{j})}<d(i_{k})^{-}\right)+\sum_{j\geq
k}\mathbb{P}\left(Z_{d(i_{j})}<d(i_{k})^{-}\right)+\frac{1}{2}\right\rfloor$
$\displaystyle\leq\left\lfloor k-1+o(M^{-1})+\frac{1}{2}\right\rfloor$
$\displaystyle=k-1.$

This proves the first statement in Equation 3.13. An analogous idea proves the
second half:

$\displaystyle N\left(d(i_{k})^{+}\right)$
$\displaystyle=\left\lfloor\sum_{i\in S}\mathbb{P}\left(Z_{d(i)}\leq
d(i_{k})^{+}\right)+\frac{1}{2}\right\rfloor$
$\displaystyle=\left\lfloor\sum_{j\leq k}\mathbb{P}\left(Z_{d(i_{j})}\leq
d(i_{k})^{+}\right)+\sum_{j>k}\mathbb{P}\left(Z_{d(i_{j})}\leq
d(i_{k})^{+}\right)+\frac{1}{2}\right\rfloor$ $\displaystyle\geq\left\lfloor
k(1-o(M^{-1}))+\frac{1}{2}\right\rfloor$ $\displaystyle=k.$

The combination of these mean that the $k$th entry of ${\bm{d}}_{H}$ has a
value between $d(i_{k})^{-}$ and $d(i_{k})^{+}$, which proves the part (a) of
the lemma. This completes the proof. ∎

##  4 Basic properties of the induced degree sequence

In this section we use Theorem 2.3 to prove some basic properties of the
sequences ${\bm{d}}_{S}$ and ${\bm{d}}_{H}$, such as the sum of their entries
(or squares of the entries) and the number of non-zero entries in each
sequence. These results are useful for proving a wide variety of properties of
$G[S]$, including the threshold for the giant component. Throughout this
section we implicitly suppose that ${\bm{d}}$ is a sequence of length $n$ with
even sum and all entries at least 1 and that $S\subset[n]$ such that
$({\bm{d}},S)$ satisfy (2.1).

###  4.1 Total degree

For brevity, we define $M_{H}:=M({\bm{d}}_{H})$ and $M_{S}:=M({\bm{d}}_{S})$.
For an arbitrary sequence of non-negative integers ${\bm{d}}$, define
$M_{2}({\bm{d}})=\sum_{i=1}^{n({\bm{d}})}d(i)^{2}$.

######  Lemma 4.1.

$M({\bm{d}}_{H})\sim\gamma^{2}M$ always. Furthermore, a.a.s.
$M({\bm{d}}_{S})\sim M({\bm{d}}_{H})$ and
$M_{2}({\bm{d}}_{S})-M_{2}({\bm{d}}_{H})=o(M_{H})$.

###### Proof.

Recall $M({\bm{d}}_{H})=\sum_{i\leq\Delta}in_{i}({\bm{d}}_{H})$ and that
$n_{i}({\bm{d}}_{H})=N(i)-N(i-1)$. Then

$\displaystyle M({\bm{d}}_{H})$
$\displaystyle=\sum_{i\leq\Delta}i(N(i)-N(i-1))=\sum_{i\leq\Delta}i\left(\sum_{j\in
S}\mathbb{P}\left(Z_{d(j)}=i\right)\pm 1\right)$ $\displaystyle=\sum_{j\in
S}\mathbb{E}\left[Z_{d(j)}\right]\pm\Delta^{2}$
$\displaystyle=\gamma^{2}M\pm\Delta^{2}.$

Since $\Delta^{2}\gamma^{-12}\log^{12}M\leq\delta\gamma M$ by assumption, it
follows that $\Delta^{2}=o(\gamma^{2}M)$. This proves the first claim of the
lemma. Now we focus on the second claim. We give the proof that a.a.s.
$M_{2}({\bm{d}}_{S})\sim M_{2}({\bm{d}}_{H})$ and it follows by an identical
proof that a.a.s. $M_{S}\sim M_{H}$, since $d_{H}(i),d_{S}(i)\geq 0$. Let
$k\in\mathbb{N}$ be the smallest index such that
$d_{H}(i)>2\delta^{1/32}\gamma{J}$ for all $i\geq k$. Similarly, let
$k^{\prime}$ be the analogous quantity for ${\bm{d}}_{S}$. Then

$\displaystyle
M_{2}({\bm{d}}_{H})=\sum_{i=1}^{\frac{1}{2}\gamma{J}}i^{2}n_{i}({\bm{d}}_{H})+\sum_{i=k+1}^{s}d_{H}(i)^{2}.$

Now we apply Theorem 2.3. Note that $2\delta^{1/32}\gamma{J}=o(\gamma{J})$.
Without loss of generality, suppose that $k\leq k^{\prime}$. Then a.a.s.

$\displaystyle M_{2}({\bm{d}}_{H})$
$\displaystyle=\sum_{i=1}^{2\delta^{1/32}\gamma{J}}i^{2}n_{i}({\bm{d}}_{H})+\sum_{i=k+1}^{s}d_{H}(i)^{2}$
$\displaystyle=\sum_{i=1}^{2\delta^{1/32}\gamma{J}}i^{2}n_{i}({\bm{d}}_{S})+O\left(\frac{\gamma
M_{H}}{{J}}\right)+o(\gamma{J}^{6})+\sum_{i=k+1}^{s}d_{S}(i)^{2}(1+o(1))$
$\displaystyle=\sum_{i=1}^{2\delta^{1/32}\gamma{J}}i^{2}n_{i}({\bm{d}}_{S})+\sum_{i=k+1}^{s}d_{S}(i)^{2}(1+o(1))+o(M_{H})$
$\displaystyle=M_{2}({\bm{d}}_{S})+\sum_{i=k+1}^{k^{\prime}}d_{S}(i)^{2}(1+o(1))+o(M_{H}).$

Theorem 2.3(c) implies that a.a.s.
$|k-k^{\prime}|\leq\frac{\gamma|S|}{{J}^{3}}+\delta^{1/32}\gamma{J}^{6}$, and
$d_{S}(i)\leq 2\delta^{1/32}\gamma{J}$ for all $i\leq k^{\prime}$ by
definition. Therefore, a.a.s.

$\displaystyle\sum_{i=k+1}^{k^{\prime}}d_{S}(i)^{2}\leq(2\delta^{1/32}\gamma{J})^{2}\left(\frac{\gamma|S|}{{J}^{3}}+\delta^{1/32}\gamma{J}^{6}\right)=o(M_{H}),$

since $\gamma^{3}{J}^{8}=o(\gamma^{2}M/{J})$. Therefore, a.a.s.
$M_{2}({\bm{d}}_{H})=M_{2}({\bm{d}}_{S})(1+o(1))$, which completes the proof.
∎

###  4.2 Concentration of number of non-isolated vertices in $G[S]$

For a sequence ${\bm{d}}$ of non-negative integers, let ${\bm{d}}^{*}$ be the
maximal subsequence of ${\bm{d}}$ with all positive entries (that is, all
entries equal to zero removed).

######  Lemma 4.2.

$n({\bm{d}}_{H}^{*})=\Omega(\gamma|S|)$ always, and a.a.s.
$n({\bm{d}}_{S}^{*})\sim n({\bm{d}}_{H}^{*})$.

###### Proof.

For the first result, recall that $n_{k}({\bm{d}}_{H})=\tilde{y}_{k}\pm 2$ for
all $k\leq\frac{1}{2}\gamma{J}$. Then

$\displaystyle\tilde{y}_{1}=\sum_{i\in
S_{\rm{small}}}\mathbb{P}\left(Z_{d(i)}=1\right)=\frac{\gamma}{1-\gamma}\sum_{i\in
S_{\rm{small}}}d(i)\mathbb{P}\left(Z_{d(i)}=0\right).$

Since ${\bm{d}}$ has a minimum entry of at least 1, this implies that
$\tilde{y}_{1}=\Omega(\gamma\tilde{y}_{0})$, and the first claim follows since
$\tilde{y}_{0}\leq|S|$. For the second claim, we apply the first part of this
lemma as well as Theorem 2.3(c). We know that a.a.s.
$|n_{0}({\bm{d}}_{H})-n_{0}({\bm{d}}_{S})|\leq\frac{\gamma
n_{0}({\bm{d}}_{H})}{{J}^{3}}+{J}^{5}$. Thus, a.a.s.

$\displaystyle|n({\bm{d}}_{S}^{*})-n({\bm{d}}_{H}^{*})|=|n_{0}({\bm{d}}_{S})-n_{0}({\bm{d}}_{H})|\leq\frac{\gamma
n_{0}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5}.$

By the definition of ${J}$ and our assumptions on ${\bm{d}}$ and $S$, it
follows that ${J}^{5}=o(\gamma|S|)$ (since $|S|\geq d(S)/\Delta$). We also
know that $\frac{\gamma n_{0}({\bm{d}}_{H})}{{J}^{3}}=o(\gamma|S|)$, since
$n_{0}({\bm{d}}_{H})\leq n({\bm{d}}_{H})=|S|$. The first claim of this lemma
states that $n({\bm{d}}_{H}^{*})=\Omega(\gamma|S|)$. Therefore, a.a.s.
$|n({\bm{d}}_{S}^{*})-n({\bm{d}}_{H}^{*})|=o(n({\bm{d}}_{H}^{*}))$, which
proves the second claim. ∎

##  5 Giant components in $G[S]$

In this section we prove Theorem 2.4. This is done by applying the following
theorem of Joos, Perarnau, Rautenbach, and Reed to the characterisation of the
degree sequence of the induced subgraph given in Theorem 2.3.

######  Theorem 5.1.

([6], Theorems 1 and 6) Let ${\bm{d}}=(d(1),\dots,d(n))$ with $d(1)\leq
d(2)\leq\dots\leq d(n)$. Define the following quantities:

$\displaystyle j_{\bm{d}}$
$\displaystyle=\min\left(\left\\{j:j\in\left[n\right]\ \mbox{and}\
\sum_{i=1}^{j}d(i)(d(i)-2)>0\right\\}\cup\left\\{n\right\\}\right),$
$\displaystyle R({\bm{d}})$ $\displaystyle=\sum_{i=j_{\bm{d}}}^{n}d(i),$
$\displaystyle\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})$
$\displaystyle=\sum_{i\in[n],d(i)\neq 2}d(i).$

Call a degree sequence _well-behaved_ if $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})$ is at
least $\lambda(n)$ for any function $\lambda:\mathbb{N}\to\mathbb{N}$ where
$\lambda\to\infty$ as $n\to\infty$. Then:

  1. (a)

For every function $\delta\to 0$ as $n\to\infty$, for every $\gamma>0$, if
${\bm{d}}$ is a well-behaved graphical sequence with
$R({\bm{d}})\leq\delta(n)\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})$, then the
probability that $G({\bm{d}})$ has a component of order at least $\gamma n$ is
$o(1)$.

  2. (b)

For every positive constant $\varepsilon$, there is a $\gamma>0$ such that if
${\bm{d}}$ is a well-behaved graphical sequence with
$R({\bm{d}})\geq\varepsilon\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})$, then the
probability that $G({\bm{d}})$ has a component of order at least $\gamma n$
and a component of size at least $\alpha\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})$ is
$1-o(1)$.

  3. (c)

For every $b\geq 0$ and every $0<\gamma<\frac{1}{8}$, there exist a positive
integer $n_{b,\gamma}$ and a $0<\delta<1$ such that if $n>n_{b,\gamma}$ and
${\bm{d}}$ is a degree sequence with $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}})\leq b$,
then the probability that there is a component of order at least $\gamma n$ in
$G({\bm{d}})$ lies between $\delta$ and $1-\delta$.

We prove this theorem by showing that if ${\bm{d}}_{S}$ satisfies the bounds
given in Theorem 2.3 (equivalently, if
${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$), then the corresponding values of
$R(\cdot)$ and $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}(\cdot)$ are close for
each sequence. Lemma 4.2 states that for each such sequence ${\bm{d}}_{S}$,
the number of non-zero entries is close to the number of non-zero entries in
${\bm{d}}_{H}$. With all of these results, the proof follows by applying
Theorem 5.1 and the law of total probability.

######  Lemma 5.2.

$\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})=\Theta(M_{H})$,
and a.a.s. $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})-\leavevmode\hbox
to10.79pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.39583pt\lower-3.41666pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{S})=o(M_{H})$.

###### Proof.

The first claim follows unless $M_{H}\sim 2n_{2}({\bm{d}}_{H})$; we prove that
the definition of ${\bm{d}}_{H}$ means that this does not occur. To do this,
we show that $\mathbb{P}\left(Z_{d(i)}=2\right)\leq
C\left(\mathbb{P}\left(Z_{d(i)}=1\right)+\mathbb{P}\left(Z_{d(i)}=3\right)\right)$
for some constant $C>0$. Firstly, if $d(i)=1$, then this is trivially true.
Next, if $d(i)=2$, then there exists a constant $C>0$ such that

$\displaystyle\mathbb{P}\left(Z_{d(i)}=1\right)=2\gamma(1-\gamma)\leq
C\gamma^{2}=C\mathbb{P}\left(Z_{d(i)}=2\right).$

Finally, if $d(i)\geq 3$, then

$\displaystyle\frac{\mathbb{P}\left(Z_{d(i)}=2\right)}{\mathbb{P}\left(Z_{d(i)}=1\right)+\mathbb{P}\left(Z_{d(i)}=3\right)}$
$\displaystyle=\frac{\frac{1}{2}(d(i)-1)\gamma(1-\gamma)}{(1-\gamma)^{2}+\frac{1}{6}(d(i)-1)(d(i)-2)\gamma^{2}}.$

The expression on the right hand side is decreasing in $d(i)$ if $\gamma
d(i)\geq 6$, and is at most $\frac{3}{1-\gamma}$ if $\gamma d(i)\leq 6$. Thus,
define $C_{\gamma}=\frac{3}{1-\gamma}$. By our assumptions on $\gamma$, we
know that $C_{\gamma}=O(1)$ and

$\displaystyle\mathbb{P}\left(Z_{d(i)}=2\right)\leq
C_{\gamma}\left(\mathbb{P}\left(Z_{d(i)}=1\right)+\mathbb{P}\left(Z_{d(i)}=3\right)\right).$

Since $n_{i}({\bm{d}}_{H})=\sum_{i\in S}\mathbb{P}\left(Z_{d(i)}=i\right)\pm
2$, this implies that

$\displaystyle\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})\geq
n_{1}({\bm{d}}_{H})+3n_{3}({\bm{d}}_{H})\geq\sum_{i\in
S}\left(\mathbb{P}\left(Z_{d(i)}=1\right)+3\mathbb{P}\left(Z_{d(i)}=3\right)\right)-4\geq
C_{\gamma}^{-1}n_{2}({\bm{d}}_{H})+O(C_{\gamma}^{-1}).$

This implies that $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})=\Omega(n_{2}({\bm{d}}_{H}))$
and thus $M_{H}\geq(2+\varepsilon)n_{2}({\bm{d}}_{H})$ for some
$\varepsilon>0$. Therefore, $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})=\Theta(M_{H})$,
which proves the first claim of the lemma.

For the second claim, Theorem 2.3 implies that a.a.s.
$|n_{2}({\bm{d}}_{H})-n_{2}({\bm{d}}_{S})|\leq\frac{\gamma
n_{2}({\bm{d}}_{H})}{{J}^{3}}+{J}^{5}$. Since
$n_{2}({\bm{d}}_{H})\leq\frac{1}{2}M_{H}$ and ${J}^{5}=o(\gamma^{2}M)$, this
implies that a.a.s. $2n_{2}({\bm{d}}_{S})=2n_{2}({\bm{d}}_{H})+o(M_{H})$.
Recall from Lemma 4.1 that a.a.s. $M_{S}\sim M_{H}$. Therefore, a.a.s.

$\displaystyle\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{S})-\leavevmode\hbox
to10.79pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.39583pt\lower-3.41666pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})=M_{S}-M_{H}-2n_{2}({\bm{d}}_{S})+2n_{2}({\bm{d}}_{H})=o(M_{H}).$

This completes the proof. ∎

######  Lemma 5.3.

With probability $1-o(1)$, it holds that
$\sum_{i=1}^{k}\left(d_{S}(i)-d_{H}(i)\right)=o(M_{H})$ for every $k\leq s$
and $\sum_{i=1}^{k}\left(d_{S}(i)^{2}-d_{H}(i)^{2}\right)=o(M_{H})$ for every
$k\leq s$.

###### Proof.

We provide the proof of the second claim, as the first claim follows
immediately from this and the fact that $d_{S}(i),d_{H}(i)\geq 0$ for all
$i\leq s$. We show that deterministically the result holds when ${\bm{d}}_{S}$
satisfies the bounds given in Theorem 2.3. Since these concentration results
hold with probability $1-o(1)$, this is sufficient to prove the claim. First
consider the case where $k$ is such that $d(i_{k})>\delta^{1/32}{J}$. In this
case, we know that a.a.s. $d_{S}(j)\sim d_{H}(j)$ for all $j\geq k$, and thus
by Lemma 4.1 it follows that a.a.s.

$\displaystyle\sum_{i=1}^{k}d_{S}(i)^{2}$
$\displaystyle=M_{2}({\bm{d}}_{S})-\sum_{i=k+1}^{s}d_{S}(i)^{2}=M_{2}({\bm{d}}_{H})+o(M_{H})-\sum_{i=k+1}^{s}d_{H}(i)^{2}(1+o(1))$
$\displaystyle=M_{2}({\bm{d}}_{H})-\sum_{i=k+1}^{s}d_{H}(i)^{2}+o(M_{H})=\sum_{i=1}^{k}d_{H}(i)^{2}+o(M_{H}).$

Thus, it only remains to consider the case where $k$ is such that
$d(i_{k})\leq\delta^{1/32}{J}$. Since we assume ${\bm{d}}_{S}$ satisfies the
bounds given in Theorem 2.3, it follows that
$d_{S}(i),d_{H}(i)\leq\delta^{1/32}{J}$ for all $i\leq k$. Consider that if
$d_{S}(i)=d_{H}(i)$, then the contribution of this term is $0$. Thus,

$\displaystyle\sum_{i=1}^{k}\left(d_{S}(i)^{2}-d_{H}(i)^{2}\right)=\sum_{i\leq
k:d_{S}(i)\neq d_{H}(i)}\left(d_{S}(i)^{2}-d_{H}(i)^{2}\right).$

The difference $d_{S}(j)^{2}-d_{H}(j)^{2}$ is bounded by
$\delta^{1/16}{J}^{2}$ for all $j\leq k$ by assumption. It remains to bound
the size of $\\{i\leq k:d_{S}(i)\neq d_{H}(i)\\}$. Note that for all
$j\leq\delta^{1/32}{J}$, the difference between the index of the first entry
equal to $j$ in ${\bm{d}}_{S}$ and the first entry equal to $j$ in
${\bm{d}}_{H}$ is at most

$\displaystyle\sum_{i=0}^{j-1}\left(n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H})\right).$

Since $d_{S}(i),d_{H}(i)\leq\delta^{1/32}{J}$, Theorem 2.3(c) implies that

$\displaystyle|\\{i\leq k:d_{S}(i)\neq d_{H}(i)\\}|$
$\displaystyle\leq\sum_{x=1}^{\delta^{1/32}{J}}\sum_{i=0}^{x-1}\left(\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}+\gamma{J}^{5}\right)$
$\displaystyle\leq\delta^{1/16}\gamma{J}^{7}+\delta^{1/32}\frac{\gamma|S|}{{J}^{2}}.$

Since $|S|\leq d(S)=\gamma M$ and $M_{H}\sim\gamma^{2}M$, this implies that

$\displaystyle\sum_{i\leq k:d_{S}(i)\neq
d_{H}(i)}\left(d_{S}(i)^{2}-d_{H}(i)^{2}\right)\leq(\delta^{1/32}{J})^{2}\left(\delta^{1/16}\gamma{J}^{7}+\delta^{1/32}\frac{\gamma|S|}{{J}^{2}}\right)\leq\delta^{1/8}\gamma{J}^{9}+\delta^{1/16}M_{H}.$

Since ${J}^{9}=o(\gamma^{2}M/{J})$ and $\delta\to 0$, this completes the
proof. ∎

######  Lemma 5.4.

With probability $1-o(1)$, $R({\bm{d}}_{S})-R({\bm{d}}_{H})=o(M_{H})$.

###### Proof.

Again, we show that the claim holds deterministically when ${\bm{d}}_{S}$
satisfies the bounds given in Theorem 2.3. Since these concentration results
hold with probability $1-o(1)$, this is sufficient to prove the claim. Define
$j_{H}:=j({\bm{d}}_{H})$ and $j_{S}:=j({\bm{d}}_{S})$. Without loss of
generality, we assume that $j_{H}\leq j_{S}$, as the proof is symmetric in the
converse case. We also assume that $j_{H}<n$, otherwise we know that
$R({\bm{d}}_{S}),\ R({\bm{d}}_{H})\leq\Delta$ and the result is immediate.
These assumptions imply that $\sum_{i=1}^{j_{H}}d_{H}(i)(d_{H}(i)-2)>0$. Thus,
Lemma 5.3 implies that

$\displaystyle\sum_{i=1}^{j_{H}}d_{S}(i)(d_{S}(i)-2)\geq-\alpha M_{H}$

for some $\alpha\to 0$. We can choose $\alpha$ such that
$\alpha=\omega(\delta^{1/16})$. We also know that the number of entries in
each sequence with value $0$, $1$, or $2$ differs by at most
$3{J}^{5}+\sum_{i=0}^{2}\frac{\gamma n_{i}({\bm{d}}_{H})}{{J}^{3}}$. We also
know that $d_{H}(j_{H})\geq 3$, as otherwise $j_{H}=n$ by definition.
Therefore, we know that there are at most $3{J}^{5}+\sum_{i=0}^{2}\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}$ entries in ${\bm{d}}_{S}$ with value at most
$2$ and index at least $j_{H}$. Choose $j^{*}$ to be the smallest integer such
that $\sum_{i=j_{H}}^{j^{*}}d_{S}(i)\geq\alpha^{1/2}M_{H}$. Then

$\displaystyle\sum_{i=1}^{j^{*}}d_{S}(i)(d_{S}(i)-2)$
$\displaystyle\geq-\left(\alpha M_{H}+3{J}^{5}+\sum_{i=0}^{2}\frac{\gamma
n_{i}({\bm{d}}_{H})}{{J}^{3}}\right)+\alpha^{1/2}M_{H}$
$\displaystyle\geq\frac{1}{2}\alpha^{1/2}M_{H}.$

Thus, $j_{S}\leq j^{*}$. Therefore,
$R({\bm{d}}_{S})\geq\sum_{i=j^{*}}^{s}d_{S}(i)$. Then Lemmas 4.1 and 5.3 imply
that

$\displaystyle\sum_{i=j_{S}}^{s}d_{S}(i)$
$\displaystyle=M_{S}-\sum_{i=1}^{j_{S}-1}d_{S}(i)=M_{S}-\sum_{i=1}^{j_{H}-1}d_{S}(i)-\sum_{i=j_{H}}^{j_{S}-1}d_{S}(i)$
$\displaystyle=M_{H}-\sum_{i=1}^{j_{H}-1}d_{H}(i)-\sum_{i=j_{H}}^{j_{S}-1}d_{S}(i)+o(M_{H})$
$\displaystyle=R({\bm{d}}_{H})-o(M_{H}),$

since $j_{S}\leq j^{*}$ and
$\sum_{i=j_{H}}^{j^{*}}d_{S}(i)\geq\alpha^{1/2}M_{H}$ by definition. This
completes the proof. ∎

Now we prove Theorem 2.4. Let $\mathcal{D}_{S}$ be the set of all possible
degree sequences of $G[S]$, and let
$\mathcal{D}_{S}^{\prime}\subset\mathcal{D}_{S}$ be the set containing all the
sequences that satisfy Theorem 2.3. Implicitly, $\mathcal{D}_{S}^{\prime}$
depends on the choice of $\delta$. For convenience and brevity we omit this
dependence.

###### Proof of Theorem 2.4.

Lemma 4.2 implies that $n({\bm{d}}_{S}^{*})$, the number of non-isolated
vertices in $G[S]$, is a.a.s.
$n({\bm{d}}_{H}^{*})(1+o(1))=(|S|-n_{0}({\bm{d}}_{H}))(1+o(1))$. Lemmas 4.1,
5.2, and 5.4 imply that for all ${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$, we
have that

$\displaystyle R({\bm{d}}_{S})-R({\bm{d}}_{H})=o(\leavevmode\hbox
to10.79pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.39583pt\lower-3.41666pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})),\quad\leavevmode\hbox
to10.79pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.39583pt\lower-3.41666pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{S})\sim\leavevmode\hbox
to10.79pt{\vbox to9.67pt{\pgfpicture\makeatletter\hbox{\hskip
5.39583pt\lower-3.41666pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H}).$

Since $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})=\Theta(M({\bm{d}}_{H}))$,
this implies that ${\bm{d}}_{H}$ is well-behaved, and thus ${\bm{d}}_{S}$ is
well-behaved for all ${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$. Now suppose
that $R({\bm{d}}_{H})\geq\varepsilon\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})$ for
some $\varepsilon>0$. Then it immediately follows that
$R({\bm{d}}_{S})\geq\frac{1}{2}\varepsilon\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{S})$ for
all ${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$. Then Theorem 5.1(b) implies
that there exists some $\gamma:=\gamma\left(\frac{1}{2}\varepsilon\right)>0$
such that the probability that $G[S]$ contains a component with at least
$\gamma n({\bm{d}}_{S}^{*})$ vertices is $1-o(1)$. Let $A$ be the event that
$G[S]$ contains a component with at least
$\frac{1}{2}\gamma(|S|-n_{0}({\bm{d}}_{H}))$ vertices. Then the law of total
probability gives that

$\displaystyle\mathbb{P}\left(A\right)=\sum_{{\bm{d}}_{S}\in\mathcal{D}_{S}}\mathbb{P}\left(\left.A\right|{\bm{d}}_{S}\right)\mathbb{P}\left({\bm{d}}_{S}\right)=\sum_{{\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}}\mathbb{P}\left(\left.A\right|{\bm{d}}_{S}\right)\mathbb{P}\left({\bm{d}}_{S}\right)+o(1)=1-o(1).$

The argument for the converse case is very similar. Suppose that
$R({\bm{d}}_{H})\leq\delta^{\prime}\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{H})$ for
some $\delta^{\prime}\to 0$. Then immediately it follows that
$R({\bm{d}}_{S})\leq 2\delta^{\prime}\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{S})$ for
all ${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$. Then Theorem 5.1(a) and the law
of total probability imply that for every $\gamma>0$, the probability that
$G[S]$ contains a component with at least $\gamma(|S|-n_{0}({\bm{d}}_{H}))$
vertices is $o(1)$. Since ${\bm{d}}_{S}\in\mathcal{D}_{S}^{\prime}$ a.a.s.
this completes the proof. ∎

##  6 Site percolation: random induced subgraphs

###### Proof of Theorem 2.6.

Immediately we know that $\mathbb{E}\left[|S|\right]=np$, and linearity of
expectation gives that

$\displaystyle\mathbb{E}\left[d(S)\right]=\sum_{i\in[n]}d(i)\mathbb{P}\left(i\in
S\right)=pM.$

First we argue concentration of $|S|$. The Chernoff bound given in (3.7)
implies that

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

Letting $\varepsilon=3\sqrt{\log n/pn}$, it immediately follows that this
probability is at most $2n^{-3}$. This completes the proof of (a). For part
(b), we construct a martingale to show concentration of $d(S)$. At step $i$,
for $i\in[n]$, reveal whether vertex $i$ is in $S$. Define
$M_{i}=d(S\cap[i])$. Then it follows immediately that $|M_{i}-M_{i-1}|\leq
d(i)$ for all $i\leq n$ and $M_{n}=d(S)$. Thus, Azuma’s inequality implies
that

$\displaystyle\mathbb{P}\left(|d(S)-pM|\geq\alpha\right)\leq
2\exp\left(\frac{-\alpha^{2}}{2\sum_{i\in V(G)}d(i)^{2}}\right).$

By assumption,
$\Delta({\bm{d}})=o\left(p^{6}\frac{\sqrt{M}}{\log^{6}M}\right)$, which
implies that

$\displaystyle\sum_{i\in
V(G)}d(i)^{2}\leq\Delta({\bm{d}})\sum_{i\in[n]}d(i)=o\left(p^{6}\frac{M^{3/2}}{\log^{6}M}\right).$

Thus, by setting $\alpha=p^{3}M^{3/4}$, this probability is $M^{-\omega(1)}$,
which proves that $S$ a.a.s. satisfies condition (b). For the remainder of
this proof, we call a set $S$ “good” if $|S|=pn\left(1\pm 3\sqrt{\log
n}/\sqrt{pn}\right)$ and $d(S)=pM\left(1\pm p^{2}M^{-1/4}\right)$. It follows
that $S$ is good with probability at least $1-3n^{-3}$.

Now we focus on part (c). Let $S$ be some arbitrary “good” subset of $[n]$,
and recall that $\gamma(S)=d(S)/M$. Then Theorem 2.3(a) applies and thus it
follows that

$\displaystyle\mathbb{P}\left(\left.d_{S}(v)=\gamma(S)d(v)\left(1\pm
8\delta^{1/64}\right)\ \mbox{for all $v\in S$ such that
$d(v)>{J}(\gamma(S))$}\right|S\right)=1-o(1).$

By parts (a) and (b) of this lemma, we know that $S$ is good with probability
$1-o(1)$. If $S$ is good, then $\gamma(S)=p(1\pm p^{2}M^{-1/4})$. Therefore,
${J}(\gamma(S))<2{J}(p)$ for every good set $S$. Thus, the probability that
there exists some $v\in S$ with $d(v)>2\delta^{1/32}{J}(p)$ with induced
degree that is not $pd(v)\left(1\pm 8\delta^{1/64}\right)(1\pm p^{2}M^{-1/4})$
is $o(1)$. Since $\delta=\omega(M^{-1/4})$, it follows that $(1\pm
8\delta^{1/64})(1\pm p^{2}M^{-1/4})=1\pm 9\delta^{1/64}$. This proves part
(c).

Finally, we focus on part (d) of the lemma. Recall that $n_{j}({\bm{d}})$ is
the number of entries of ${\bm{d}}$ equal to $j$, or equivalently (if
${\bm{d}}$ is graphical) the number of vertices with degree $j$ in a graph
with degree sequence ${\bm{d}}$. Let $S_{j}$ be the set of all degree $j$
vertices in $S$. We can express $|S_{j}|$ as a sum over all vertices in $G$
with degree $i$:

$\displaystyle|S_{j}|$ $\displaystyle=\sum_{d(i)=j}\mathbbm{1}_{\left\\{i\in
S\right\\}},$

where $\mathbbm{1}_{\left\\{i\in S\right\\}}$ is an independent Bernoulli
random variable with $\mathbb{P}\left(\mathbbm{1}_{\left\\{i\in
S\right\\}}=1\right)=p$ for all $i\in[n]$. It follows from linearity of
expectation that $\mathbb{E}\left[|S_{j}|\right]=pn_{j}({\bm{d}})$. Since
these indicators are independent random variables, the Chernoff bound given in
(3.7) implies that

$\displaystyle\mathbb{P}\left(||S_{j}|-pn_{j}({\bm{d}})|>\alpha_{j}pn_{j}({\bm{d}})\right)\leq
2\exp\left(-\frac{1}{3}\alpha_{j}^{2}pn_{j}({\bm{d}})\right)$

for each $j\leq{J}(p)$. Define
$\alpha_{j}=\left(\frac{6\log{J}(p)}{pn_{j}({\bm{d}})}\right)^{1/2}$. Then

$\displaystyle\exp\left(-\frac{2\alpha_{j}^{2}}{n_{j}({\bm{d}})}\right)=\exp\left(-2\log{J}(p)\right).$

Setting $\alpha_{j}=(6pn_{j}({\bm{d}})\log{J}(p))^{1/2}$ and performing the
union bound over ${J}(p)$ such events implies that the probability that each
$S_{j}$ is within of its expectation is at most ${J}(p)^{-2}$. Suppose for
some particular $j$ that $pn_{j}({\bm{d}})\geq p^{-2}{J}(p)^{6}\log^{2}M$.
Then, with probability $1-o(1)$ it follows that

$\displaystyle||S_{j}|-pn_{j}({\bm{d}})|\leq(6pn_{j}({\bm{d}})\log{J}(p))^{1/2}\leq(6\log{J}(p))^{1/2}\frac{pn_{j}({\bm{d}})}{p^{-1}{J}(p)^{3}\log
M}.$

Now suppose that $pn_{j}({\bm{d}})<p^{-2}{J}(p)^{6}\log^{2}M$. Then it follows
that

$\displaystyle||S_{j}|-pn_{j}({\bm{d}})|\leq(6pn_{j}({\bm{d}})\log{J}(p))^{1/2}<(6\log{J}(p))^{1/2}p^{-1}{J}(p)^{3}\log
M.$

Noting that $\log{J}(p)\leq\frac{1}{6}\log M$, it follows that a.a.s. for all
$j\leq{J}(p)$

$\displaystyle||S_{j}|-pn_{j}({\bm{d}})|\leq\frac{p^{2}n_{j}({\bm{d}})}{{J}(p)^{3}\sqrt{\log
M}}+\delta^{1/16}{J}(p)^{4}\sqrt{\log M}.$ (6.1)

Suppose that $S$ is an arbitrary good subset of $[n]$ which also satisfies the
concentration bounds given in Equation 6.1 for all $j\in\\{0,\dots,{J}\\}$.
Since $S$ is good, it follows that $\gamma(S)=p(1\pm p^{2}M^{-1/4})$. The set
$S$ being good also implies that the conditions of Lemma 3.6 are met, and also
that $\frac{1}{3}p{J}(p)<\frac{1}{2}\gamma(S){J}(\gamma(S))$. Recall from
Definition 2.2 the definition of $n_{i}({\bm{d}}_{H}(S))$, the number of
entries in ${\bm{d}}_{H}$ (for a given set $S$) with value $i$. Since
$i\leq\frac{1}{2}\gamma(S){J}(\gamma(S))$,

$\displaystyle n_{i}({\bm{d}}_{H}(S))$
$\displaystyle=\sum_{j\leq{J}(\gamma(S))}|S_{j}|\mathbb{P}\left(Z_{j}(S)=i\right)\pm\left(1+o(M^{-5})\right),$

where $Z_{j}(S)\sim\textup{Bin}\left(j,\gamma(S)\right)$. Suppose
$i\leq\frac{1}{3}p{J}(p)=\frac{1}{3}\gamma(S){J}(\gamma(S))$. Since $S$ is
good, the Chernoff bound (3.7) implies that
$\mathbb{P}\left(Z_{j}(S)=i\right)=o(M^{-5})$ for all
$j\geq\frac{1}{2}{J}(p)$. Thus, for $i\leq\frac{1}{3}p{J}(p)$,

$\displaystyle n_{i}({\bm{d}}_{H}(S))$
$\displaystyle=\sum_{j\leq{J}(p)}|S_{j}|\mathbb{P}\left(Z_{j}(S)=i\right)\pm
2.$ (6.2)

Now we compare the summation to the value of $\tilde{w}_{i}$. If
$d(v)\leq{J}(p)$, then for all $i\leq d(v)$ it follows that

$\displaystyle\frac{\mathbb{P}\left(X_{d(v)}=i\right)}{\mathbb{P}\left(Z_{d(v)}=i\right)}$
$\displaystyle=\left(\frac{p}{\gamma(S)}\right)^{i}\left(\frac{1-p}{1-\gamma(S)}\right)^{d(v)-i}$
$\displaystyle=\left(1+O\left(\frac{p^{2}i}{M^{1/4}}\right)\right)\left(1+O\left(\frac{p^{3}(d(v)-i)}{M^{1/4}}\right)\right)$
$\displaystyle=1+O\left(\frac{p^{2}{J}(p)}{M^{1/4}}\right).$

Recall that the conditions on $p$ (specifically Equation 2.2) imply that
$p=\omega(M^{-1/13})$. This implies that
$\frac{p^{2}{J}(p)}{M^{1/4}}\leq\frac{p}{M^{1/100}{J}(p)^{3}}$. Therefore,

$\displaystyle\sum_{j\leq{J}(p)}|S_{j}|\mathbb{P}\left(Z_{j}(S)=i\right)=\sum_{j\leq{J}(p)}|S_{j}|\mathbb{P}\left(X_{j}=i\right)\left(1+o\left(\frac{p}{{J}(p)^{3}}\right)\right).$
(6.3)

Since $i\leq\frac{1}{3}p{J}(p)$, the Chernoff bound given in (3.7) implies
that

$\displaystyle\tilde{w}_{i}=p\sum_{v\in
V}\mathbb{P}\left(X_{d(v)}=i\right)=p\sum_{j\leq{J}(p)}n_{j}({\bm{d}})\mathbb{P}\left(X_{j}=i\right)+o(1).$

Since we assume that $S$ satisfies the concentration inequalities given in
Equation 6.1, it follows that

$\displaystyle\sum_{j\leq{J}(p)}|S_{j}|\mathbb{P}\left(X_{j}=i\right)$
$\displaystyle=\sum_{j\leq{J}(p)}\mathbb{P}\left(X_{j}=i\right)\left(pn_{j}({\bm{d}})+o\left(\frac{p^{2}n_{j}({\bm{d}})}{{J}(p)^{3}}+{J}(p)^{4}\sqrt{\log
M}\right)\right)$
$\displaystyle=\sum_{j\leq{J}(p)}\mathbb{P}\left(X_{j}=i\right)pn_{j}({\bm{d}})\left(1+o\left(\frac{p}{{J}(p)^{3}}\right)\right)+\sum_{j\leq{J}(p)}\mathbb{P}\left(X_{j}=i\right)o\left(\frac{p{J}(p)^{5}}{\sqrt{\log
M}}\right)$
$\displaystyle=\tilde{w}_{i}+o\left(\frac{p\tilde{w}_{i}}{{J}(p)^{3}}+\frac{p{J}(p)^{6}}{\sqrt{\log
M}}\right).$ (6.4)

Combining Equations 6.2, 6.3, and 6 it follows that, conditional on the
aforementioned good set $S$,

$\displaystyle
n_{i}({\bm{d}}_{H}(S))=\tilde{w}_{i}+o\left(\frac{p\tilde{w}_{i}}{{J}(p)^{3}}+\frac{p{J}(p)^{6}}{\sqrt{\log
M}}\right).$ (6.5)

Since $S$ is good, the pair $({\bm{d}},S)$ also satisfy the conditions of
Theorem 2.3(c). This implies that, for this fixed set $S$, a.a.s.

$\displaystyle|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H}(S))|\leq\frac{\gamma(S)n_{i}({\bm{d}}_{H}(S))}{{J}(\gamma(S))^{3}}+\gamma(S){J}(\gamma(S))^{5}.$
(6.6)

Recall that $n_{i}({\bm{d}}_{A})=\tilde{w}_{i}\pm 1$ for all $i$. Thus, the
bounds given in 6.5 and 6.6 and the triangle inequality imply that,
conditional on the event that $S$ is good and also satisfies the concentration
bounds given in Equation 6.1, a.a.s.

$\displaystyle|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{A})|\leq|n_{i}({\bm{d}}_{S})-n_{i}({\bm{d}}_{H}(S))|+|n_{i}({\bm{d}}_{H}(S))-n_{i}({\bm{d}}_{A})|\leq\frac{pn_{i}({\bm{d}}_{A})}{{J}(p)^{3}}(1+o(1))+o\left(\frac{p{J}(p)^{6}}{\sqrt{\log
M}}\right)$

for all $i\leq\frac{1}{3}p{J}(p)$. Since $S$ satisfies these conditions
a.a.s., this proves part (d). ∎

Recall the definition of $M_{2}({\bm{d}})=\sum_{i=1}^{n}d(i)^{2}$ where $d$ is
a sequence of length $n$. Very similarly to the case where $S$ is fixed, it
follows that $M({\bm{d}}_{S})$ and $M_{2}({\bm{d}}_{S})$ are both concentrated
around their corresponding values for ${\bm{d}}_{A}$. We do not give the full
proof here, as it is practically identical the proof of Lemma 4.1.

######  Lemma 6.1.

$M({\bm{d}}_{A})=p^{2}M(1+o(1))$. With probability $1-o(1)$,
$M({\bm{d}}_{S})\sim M({\bm{d}}_{A})$ and $M_{2}({\bm{d}}_{S})\sim
M_{2}({\bm{d}}_{A})$.

###### Proof sketch.

The proof of this claim is analogous to Lemma 4.1, using Theorem 2.6 instead
of Theorem 2.3. The same proof method works, noting that
$(2\delta^{1/32}\gamma{J}(p))^{2}\frac{p{J}(p)^{6}}{\sqrt{\log
M}}=o(p^{2}M/{J}(p))$. ∎

######  Remark 6.2.

Recall that ${\bm{d}}^{*}$ is the sequence ${\bm{d}}$ with all entries equal
to $0$ removed. An analogous argument to Lemma 4.2, calling on Theorem 2.6
instead of Theorem 2.3, implies that $n({\bm{d}}_{A}^{*})=\Omega(p^{2}n)$ and
a.a.s. $n({\bm{d}}_{A}^{*})\sim n({\bm{d}}_{S}^{*})$.

##  7 Giant components in the percolated graph

The proof of Theorem 2.7 follows quickly from the previously proved results
about the percolated random graph model and arguments analogous to those used
to prove Theorem 2.4.

######  Lemma 7.1.

$\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} }
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{
{}{}{}}}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}({\bm{d}}_{A})=\Theta(M({\bm{d}}_{A}))$,
and a.a.s. $\leavevmode\hbox to10.79pt{\vbox
to9.67pt{\pgfpicture\makeatletter\hbox{\hskip 5.39583pt\lower-3.41666pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{ {}{}}
{{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-5.39583pt}{-3.41666pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$M$}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} {
{}{}{}}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{}{{ {}{}}}{
{}{}} {{}{{}}}{{}{}}{}{{}{}} { }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{1.0}{0.0}{0.0}{1.0}{-3.8889pt}{2.58229pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{$\sim$}}