# Majority dynamics on random graphs: the multiple states case

Jordan Chellig Nikolaos Fountoulakis111Email for correspondence:
<EMAIL_ADDRESS>

School of Mathematics
University of Birmingham
Edgbaston, B15 2TT
United Kingdom

###### Abstract

We study the evolution of majority dynamics with more than two states on the
binomial random graph $G(n,p)$. In this process, each vertex has a state in
$\\{1,\ldots,k\\}$, with $k\geq 3$, and at each round every vertex adopts
state $i$ if it has more neighbours in state $i$ that in any other state. Ties
are resolved randomly. We show that with high probability the process reaches
unanimity in at most three rounds, if $np\gg n^{2/3}$.

##  1 Majority dynamics on a graph

Majority dynamics on a graph $G=(V,E)$ is a process that evolves
_synchronously_. Each vertex $v\in V$ will be in one of the states in
$\mathcal{S}_{k}:=\\{1,\ldots,k\\}$, for an integer $k\geq 2$. For $t\geq 1$,
let $S_{t}:V\to\mathcal{S}_{k}$ be the _state_ of the vertices after the
completion of the $t$th round, whereas $S_{0}:V\to\mathcal{S}_{k}$ is the
initial state. The version of the process we will analyse evolves as follows.
Let $t\geq 1$ and for each vertex $v\in V$ and $i\in\mathcal{S}_{k}$, let
$n_{t-1}(v;i)=\left|N_{G}(v)\cap\\{u:S_{t-1}(u)=i\\}\right|$; this is the
number of neighbours of $v$ in $G$ which follow strategy $s$ after round
$t-1$. Then $S_{t}(v)$ is selected uniformly at random from the set
$\operatorname*{argmax}\\{n_{t-1}(v;i)\\}_{i\in\mathcal{S}_{k}}$. In
particular, if there is $i\in\mathcal{S}_{k}$ such that
$n_{t-1}(v;i)>n_{t-1}(v;j)$ for all $j\not=i$, that is,
$\operatorname*{argmax}\\{n_{t-1}(v;j)\\}_{j\in\mathcal{S}_{k}}=\\{i\\}$, then
$S_{t}(v)=i$.

Such a model has its origins in the field of sociology and the question of the
emergence of collective behaviour in a population. It was M. Granovetter [11]
who introduced the family of _threshold models_ in order to explain the
emergence of collective behaviour through the interaction of individual
preferences and their aggregation. With such models, Granovetter tried to
explain social phenomena such as the diffusion of innovations, the spreading
of rumours and diseases. In this setting the choice is binary, that is, $k=2$,
but each vertex in the network has a different threshold. The vertex having
threshold $t$ having observed at least $t$ other vertices adopting a new
behaviour it adopts it too and this activates the individual with threshold
$t+1$. This process is assumed to take place on the complete graph and leads
to a stable configuration where all vertices have reached unanimity having
adopted the new behaviour. The existence of equilibria were also shown for
different distributions of thresholds. Processes of similar flavour were also
described in [5, 6, 20].

A model with similar flavour had been developed in the 1940s by McCulloch and
Pitts [13] to describe neuronal activity. In this model, a neuron receives
positive and negative inputs and it fires, if their sum is positive. Neurons
are interconnected forming a large hierarchical network.

Now, from a purely mathematical perspective, it would make sense to study the
behaviour of such a process in a general graph, which may be thought of as a
representation of a population. A simpler nevertheless non-trivial version of
the above would be to consider a version where all vertices have the same
threshold which corresponds to at least half of the neighbours having adopted
the same opinion before the vertex adopts it too. This modification gives rise
to _majority dynamics_ with $k=2$ states.

When two states are available one can adopt a deterministic resolution rule,
whereby a vertex does not change state if there is a tie among the numbers of
neighbours having each one of the two states. In this case, a result of Goles
and Olivos [10] implies that if the underlying graph is finite, then the
system will eventually become periodic with period at most 2. In other words,
there is a limiting behaviour and one may further ask how does this limit look
like.

Such a question is about how does the geometry of the underlying graph $G$
determine this limit. Mossel et al. [14] considered a classification of the
vertices into _social types_ where two vertices have the same social type if
there is an automorphism of the graph that maps one vertex to the other. Let
$m(G)$ be the size of the smallest of the social types. Their main result
shows that the probability that the dynamics arrives at unanimity of one of
the two states converges to 1 exponentially fast in $\log m(G)$ with
coefficient $\delta/\log(1/\delta)$ where $\delta$ is the bias of initial
distribution towards that state. On the other hand, they show the existence of
a sequence of graphs $(G_{n})_{n\in\mathbb{N}}$ on $n$ vertices for which this
probability stays bounded away from 1 as $n\to\infty$. In this example,
$m(G_{n})$ is small and does not tend to infinity.

The other parameter they considered is the expansion of the underlying graph.
In particular, Mossel et al. [14] considered a sequence
$(G_{n})_{n\in\mathbb{N}}$ of $d$-regular graphs which are $\lambda$-expanders
(the absolute value of the second largest eigenvalue of their adjacency matrix
is no larger than $\lambda$) with $\lambda/d\leq 3/16$. In majority dynamics
with $k\geq 2$ states $\\{1,\ldots,k\\}$ starting from random initial
configuration where the probability if state $1$ exceeds the probability of
state $i\not=1$ by at least $c\log k/\sqrt{d}$, then state $1$ eventually
dominates and unanimity is achieved with high probability as $n\to\infty$.

Benjamini et al. [2] considered this question in the context of the binomial
random graph $G(n,p)$, where each pair of vertices from the set
$V_{n}=\\{1,\ldots,n\\}$ appears as an edge with probability $p=p(n)$
independently of any other pair. They conjectured that if $np\to\infty$ as
$n\to\infty$, then this dynamics on two states starting from a uniformly
random configuration will arrive at almost unanimity with one of the two
states occupying at least $(1-\varepsilon)n$ of the vertices with high
probability as $n\to\infty$, for any $\varepsilon>0$. They proved that
unanimity is attained for $np\gg n^{1/2}$ with probability that is
asymptotically bounded away from 0. Later Fountoulakis et al. [7] showed that
this is the case with probability tending to $1$ as $n\to\infty$. Moreover,
they showed that unanimity occurs in at most 4 rounds. This result was refined
by Berkowitz and Devlin [3]. They showed that for any given initial
configuration, the number of vertices in one of the two states after the
execution of one round satisfies a central limit theorem (over the random
choice of the graph). Using this result, they obtained more precise results
for the number of rounds until unanimity is achieved, when the initial
configuration is uniformly random, provided that $np\gg n^{1/2}$. Tran and Vu
[19] also gave another proof of the main theorem of [7]. Furthermore,
Chakraborti et al. [4] reduced the value of $p$ for which unanimity is reached
by majority dynamics under a uniformly random initial configuration to $p\gg
n^{-3/5}\log n$.

Tran and Vu [19] also explored non-random initial configurations and, in
particular, configurations where one of the states has a very small majority.
They showed that when one of the two states has a majority of 6, majority
dynamics on $G(n,1/2)$ reaches unanimity with that state dominating with
probability at least $0.9$. They extended this to $G(n,p)$ for any fixed
$p\in(0,1)$ and majority $c_{n}$ (possibly depending on $n$). This result was
strengthened by Sah and Sawhney [16], who gave a precise estimate on the
probability that the initial majority of one of the two states becomes
dominance of that state, for values of $p$ such that $(\log n)^{-1/16}\leq
p\leq 1-(\log n)^{-1/16}$.

On the other hand, initial configurations with relatively high initial
majority have been proved to be reinforced and lead to unanimity for much
smaller values of $p$. For example, Tran and Vu [19] show that if
$np\geq(2+o(1))\log n$ an initial majority of order $1/p$ is re-inforced to
unanimity with high probability as $n\to\infty$. Zehmakan [21], had shown this
for $np>(1+o(1))\log n$ (that is, just above the connectivity threshold) and
an initial majority that is asymptotically larger than $(n/p)^{1/2}$. In the
same work, Zehmakan refined the results on Mossel et al. [14] for $d$-regular
expander graphs. Earlier versions of this result were shown by Gärtner and
Zehmakan in [9] and in [8] (where the underlying graph is a grid).

###  1.1 Results

The aim of this contribution is to consider this process for $k$ states with
$k>2$ and study the limiting behaviour of $S_{t}$ as $t\to\infty$ when the
underlying graph is $G(n,p)$, the _binomial random graph_ on $n$ vertices. As
it is customary in the theory of random graphs, we will be interested in
asymptotics as $n\to\infty$. Let
$\boldsymbol{\lambda}:=(\lambda_{1},\ldots,\lambda_{k})$ be such that
$\sum_{i=1}^{k}\lambda_{i}=1$ and $\lambda_{i}>0$, for $i=1,\ldots,k$; we
write that $\boldsymbol{\lambda}\in\triangle_{1}$. The initial configuration
$S_{0}$ will be selected randomly, where each $v\in V_{n}$ will have
$S_{0}(v)=i\in\mathcal{S}_{k}$ with probability $\lambda_{i}$, independently
of all other vertices and the edges of $G(n,p)$. We write
$S_{0}\sim\boldsymbol{\lambda}$ to denote this random choice.

Our main result is that for any choice of
$\boldsymbol{\lambda}\in\triangle_{1}$, if $p$ is not too rapidly decaying as
a function of $n$, then the dynamics will reach unanimity in a bounded number
of rounds with high probability.

######  Theorem 1.1.

Let $\varepsilon>0$ and $\boldsymbol{\lambda}\in\triangle_{1}$. Consider
majority dynamics on $G(n,p)$ with $np\gg n^{2/3}$ but
$\limsup_{n\to\infty}p<1$. For any $n$ sufficiently large, with probability at
least $1-\varepsilon$ the following holds: if $S_{0}\sim\boldsymbol{\lambda}$,
then $S_{3}(v)=s$, for all $v\in V_{n}$, for some $s\in\mathcal{S}_{k}$.

###  1.2 Outline of the proof and the structure of this work

The first step of the proof of Theorem 1.1 is to show that during the first
round all states but those which are in
$\mathcal{M}_{0}:=\operatorname*{argmax}\\{\lambda_{i}\\}_{i\in\mathcal{S}_{k}}$
are eliminated with high probability - this is Claim 1.4. Using a first moment
argument, we show that with high probability for any two states
$i,j\in\mathcal{S}_{k}$ with $\lambda_{i}<\lambda_{j}$, all vertices have more
neighbours at state $j$ in $S_{0}$ than in state $i$. Thereafter, for any
vertex $v\in V_{n}$ we estimate the probability that
$S_{1}(v)=i\in\mathcal{M}_{0}$. To this end we show first that with high
probability a small number of vertices faces a tie during the execution of the
first round (Claim 1.3). So most vertices adopt their state
$i\in\mathcal{M}_{0}$ in round 1 through a clear majority within the
corresponding subset of vertices that have been set at state $i$ initially.
For such a vertex $v$ we say that $S_{1}(v)=i$ in _a strong sense_. Now, we
estimate this probability in Section 1.7. In particular, we estimate this
probability conditional on the size of the neighbourhood of $v$ among the
vertices who are initially in a state in $\mathcal{M}_{0}$. We show a local
limit theorem (Lemma 1.6), through which we obtain an asymptotic estimate on
the probability that $v$ has a certain number of neighbours in each subset of
vertices that are initially at some state in $\mathcal{M}_{0}$. We further
condition on the sizes of these sets. Thereafter, a second moment argument in
Section 1.7.1 shows that the number of vertices that adopt a state
$i\in\mathcal{M}_{0}$ is concentrated around its expected value. So after the
execution of first round, the vertex set is partitioned into as many sets as
$|\mathcal{M}_{0}|$ together with a smaller set that consists of the vertices
that face a tie during the first round. Ordering those parts that corresponds
to states in $\mathcal{M}_{0}$ according to their size, we show that
consecutive parts differ in size by $\Omega(np^{1/2})$. So, finally Lemma 1.19
implies that most vertices will have many neighbours in the largest among
those parts and the corresponding state will dominate after the execution of
the second. This means that all vertices in $V_{n}$, expect for subset of size
$o(n)$, will have adopted that state. So in the third round all vertices will
have switched to that state.

###  1.3 Some notation and concentration bounds

We denote by $\mathbb{N}_{0}$ the set of non-negative integers, that is
$\mathbb{N}_{0}=\\{0\\}\cup\mathbb{N}$.

For a graph $G=(V,E)$ a vertex $v\in V$ and a subset $S\subseteq V$, we let
$N_{S}(v)$ be the set of neighbours of $v$ in $S$ and $d_{S}(v)=|N_{S}(v)|$.
We also set $N_{G}(v)=N_{V}(v)$, that is, the set of all neighbours of $v$ in
the graph $G$.

For $n\in\mathbb{N}$ and $p\in[0,1]$, we denote by $\mathrm{Bin}(n,p)$ the
binomial distribution with parameters $n$ and $p$. For a vector
$\boldsymbol{q}=(q_{1},\ldots,q_{k-1})$ such that
$(q_{1},\ldots,q_{k-1},1-\sum_{j<k}q_{j})\in\triangle_{1}$, we denote by
$\operatorname{Mult}(n;\boldsymbol{q})$ the multinomial distribution on a
collection of i.i.d. random variables that has size $n$, where each member of
it takes value $i\in\\{1,\ldots,k\\}$ with probability $q_{i}$, if $i<k$, or
$1-\sum_{j<k}q_{j}$, if $i=k$.

We will be using the standard Chernoff bound for the concentration of
binomially distributed random variables. The inequality we will use follows
from Theorem 2.1 in [12]. If $X$ is a random variable such that
$X\sim\mathrm{Bin}(n,q)$, then for any $\delta\in(0,1)$ we have

$\mathbb{P}\left(|X-nq|\geq\delta nq\right)\leq 2e^{-\delta^{2}nq/3}.$ (1)

A Chernoff-type bound also holds for the hypergeometric distribution
$\mathrm{Hyper}(n,m;s)$. Suppose that on a groundset $X_{n}$ of size $n$ a
subset $S$ of size $s$ is selected unifomly at random among all subsets of $n$
of this size. Let $M\subset X_{n}$ be a subset that has size $m$. Then
$\mathrm{Hyper}(n,m;s)$ is the distribution of the random variable that is the
size of $S\cap M$. Note that $\mathbb{E}\left[|S\cap M|\right]=s(m/n)$. For
the concentration of $|S\cap M|$ around its expected value we will use a
Chernoff-type inequality by Serfling [17] (in fact, a special case of it):

$\mathbb{P}\left(|S\cap M|-s(m/n)|\geq\lambda\sqrt{s}\right)\leq
2e^{-2\lambda^{2}/(1-f_{s})},$ (2)

where $f_{s}=(s-1)/n$.

We will also use the local limit theorem for the binomial distribution - see
for example the monograph by Petrov [15].

######  Theorem 1.2.

Let $X\sim\mathrm{Bin}(n,q)$ for some fixed $q\in(0,1)$. Then with
$\sigma^{2}=nq(1-q)$ we have

$\sup_{k\in\mathbb{Z}}\left|\mathbb{P}\left(X=k\right)-\frac{1}{\sqrt{2\pi\sigma^{2}}}e^{-\frac{(k-np)^{2}}{2\sigma^{2}}}\right|=O\left(\frac{1}{nq}\right).$

We say that a sequence of events $E_{n}$ defined on a sequence of probability
spaces with probability measure $\mathbb{P}_{n}$ occurs _asymptotically almost
surely_ (or _a.a.s._) if $\mathbb{P}_{n}(E_{n})\to 1$ as $n\to\infty$.

###  1.4 Some observations about the initial configuration and the
configuration after the first round

For $i\in\mathcal{S}_{k}$, let $S_{0}^{-1}(i)=\\{v\in V_{n}\ :\
S_{0}(v)=i\\}$, and $n_{i}=|S_{0}^{-1}(i)|$. The definition of the initial
state implies that the vector $(n_{1},\ldots,n_{k})$ follows the multinomial
distribution $\operatorname{Mult}(n;\boldsymbol{\lambda})$. In particular,
$n_{i}\sim\mathrm{Bin}(n,\lambda_{i})$ for any $i\in\mathcal{S}_{k}$. Thus,
the Chernoff bound (1) together with the union bound imply that a.a.s. for all
$i\in\mathcal{S}_{k}$ we have $|n_{i}-n\lambda_{i}|\leq\log n\sqrt{n}$. We
denote this event $\mathcal{E}_{0}$.

Moreover, we let $n_{0}(v;i)=|N_{V_{n}}(v)\cap S_{0}^{-1}(i)|$, for any
$i\in\mathcal{S}_{k}$ and any $v\in V_{n}$. Note that conditinal on an initial
configuration $\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$, we have
$n_{0}(v;i)\sim\mathrm{Bin}(n_{i}-1_{S_{0}(v)=i},p)$, where
$1_{S_{0}(v)=i}=1$, if $v\in S^{*}$ and 0 otherwise. If
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$ satisfies
$|n_{i}-n\lambda_{i}|\leq\log n\sqrt{n}$ for all $i\in\mathcal{S}_{k}$, the
following holds: a.a.s. all vertices $v\in V_{n}$ have
$|n_{0}(v;i)-n_{i}p|\leq\log n\sqrt{np}$. This follows from the Chernoff bound
and Markov’s inequality. Indeed, conditional on a configuration
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$ that satisfies $\mathcal{E}_{0}$,
the Chernoff bound yields that for a vertex $v\in V_{n}$
$\mathbb{P}\left(|n_{0}(v;i)-n_{i}p|>\log
n\sqrt{np}\right)=\exp\left(-\Omega(\log^{2}n)\right)=o(n^{-1})$.

Another useful bound is on the (conditional) probability that a vertex $v$ has
the same number of neighbours in two parts $S_{0}^{-1}(i)$ and
$S_{0}^{-1}(j)$, for $i\not=j$. This will be useful as any vertex which ends
up choosing its state during round 1 through the resolution of a tie should
have the same number of neighbours in at least two parts. Note that
conditional on a realisation of $\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$ the
random variables
$n_{0}(v;\ell)\sim\mathrm{Bin}(n_{\ell}-1_{S_{0}(v)=\ell},p)$, for
$\ell\in\\{i,j\\}$, are independent. To bound the probability that
$n_{0}(v;i)=n_{0}(v;j)$ we will make use of the local limit theorem (Theorem
1.2). Firstly, the Chernoff bound implies that with probability $1-o(n^{-1})$
we have $|n_{0}(v;\ell)-(n_{\ell}-1_{S_{0}(v)=\ell})p|\leq\log n\sqrt{np}$ for
$\ell\in\\{i,j\\}$. Theorem 1.2 implies that for $s_{i}\in\mathbb{N}$ such
that $|s_{i}-(n_{i}-1_{S_{0}(v)=i})p|\leq\log n\sqrt{np}$ we have that

$\displaystyle\mathbb{P}\left(n_{0}(v;i)=n_{0}(v;j)=s_{i}\right)=\mathbb{P}\left(n_{0}(v;i)=s_{i}\right)\mathbb{P}\left(n_{0}(v;j)=s_{i}\right)=O\left(\frac{1}{np}\right).$

Moreover, this upper bound is uniform over these choices of $s_{i}$. As there
are $O(\log n\sqrt{np})$ choices for the value of $s_{i}$ we conclude that

$\mathbb{P}\left(n_{0}(v;i)=n_{0}(v;j)\right)=O\left(\frac{\log
n}{(np)^{1/2}}\right)+o(n^{-1})=O\left(\frac{\log n}{(np)^{1/2}}\right).$ (3)

If $T_{1}$ denotes the set of vertices that face a tie during round 1, it
follows that

$\mathbb{E}\left[|T_{1}|\right]\leq\sum_{v\in V_{n}}\mathbb{P}\left(\exists
i\not=j\ n_{0}(v;i)=n_{0}(v;j)\right)=O\left(\log n\sqrt{\frac{n}{p}}\right).$

Markov’s inequality then implies the following.

######  Claim 1.3.

The set $R_{1}\subset V_{n}$ which consists of those vertices that face a tie
during round 1 a.a.s. has

$|T_{1}|\leq\log^{2}n\sqrt{\frac{n}{p}}.$

We call this event $\mathcal{E}_{T_{1}}$.

We let
$\mathcal{M}_{0}=\operatorname*{argmax}\\{\lambda_{i}\\}_{i\in\mathcal{S}_{k}}$
and $\lambda_{\max}=\max\mathcal{S}_{k}$; thus any $i\in\mathcal{M}_{0}$ has
$\lambda_{i}=\lambda_{\max}$. Suppose that the parameters
$\lambda_{1},\ldots,\lambda_{k}$ are fixed. There exists $\varepsilon>0$ such
that a.a.s. for any $j\not\in\mathcal{M}_{0}$ and any $i\in\mathcal{M}_{0}$,
we have $\frac{1}{n}\left(|S_{0}^{-1}(i)|-|S_{0}^{-1}(j)|\right)>\varepsilon$.

Let us condition on a realisation of
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$ such that the above event is
realised. A simple application of the Chernoff bound together with a union
bound imply that a.a.s. all vertices $v\in V_{n}$ have $n_{0}(v;j)<n_{0}(v;i)$
for any $j\not\in\mathcal{M}_{0}$ and any $i\in\mathcal{M}_{0}$. Thus, the
following holds.

######  Claim 1.4.

A.a.s. all $v\in V_{n}$ have $S_{1}(v)\in\mathcal{M}_{0}$.

In other words, all states outside $\mathcal{M}_{0}$ are eliminated in the
first round and only that states in $\mathcal{M}_{0}$ survive. This means
that, with high probability, what determines $S_{1}(v)$, for any $v\in V_{n}$
are the random variables $\\{n_{0}(v;i)\\}_{i\in\mathcal{M}_{0}}$.

We will exploit this observation using a two-round exposure of the multinomial
distribution $\operatorname{Mult}(n;\boldsymbol{\lambda})$. Let
$\lambda_{*}=\sum_{i\not\in\mathcal{M}_{0}}\lambda_{i}$ and, with
$k_{0}=|\mathcal{M}_{0}|$,
$\lambda^{*}=\sum_{i\in\mathcal{M}_{0}}\lambda_{i}=k_{0}\lambda_{\max}$; thus
$\lambda_{*}+\lambda^{*}=1$. Let
$S_{*}=\cup_{i\not\in\mathcal{M}_{0}}S_{0}^{-1}(i)$ and
$S^{*}=\cup_{i\in\mathcal{M}_{0}}S_{0}^{-1}(i)$. If we condition on a
realisation of $S_{*},S^{*}$, then each vertex $v\in S^{*}$ will take state
$i\in\mathcal{M}_{0}$ with probability $1/k_{0}$ independently of any other
vertex in $S^{*}$ as well as of the random graph on $V_{n}$. Note that
$|S^{*}|\sim\mathrm{Bin}(n,\lambda^{*})$. The Chernoff bound implies that
a.a.s. $\left||S^{*}|-n\lambda^{*}\right|<n^{1/2}\log n$. We denote this event
by $\mathcal{P}_{0}$.

Another useful bound will be on the absolute difference
$|n_{0}(v;i)-n^{*}(v)(n_{i}/n^{*})|$, conditional on a realisation of
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k_{0})\\}$, that satisfies the event
$\mathcal{E}_{0}$, and on the value of $|N_{S^{*}}(v)|=:n^{*}(v)$. On this
conditional space, $n_{0}(v;i)\sim\mathrm{Hyper}(n^{*},n_{i};n^{*}(v))$. The
Chernoff-type bound for the hypergeometric distribution (2) implies that
$\mathbb{P}\left(|n_{0}(v;i)-n^{*}(v)(n_{i}/n^{*})|\geq\log
n\sqrt{n^{*}(v)}\right)=\exp\left(-\Omega(\log^{2}n)\right)$. The union bound
yields the following result.

######  Claim 1.5.

With probability $1-e^{-\Omega(\log^{2}n)}$ (on the conditional space that was
described above) all $v\in V_{n}$ satisfy

$|n_{0}(v;i)-n^{*}(v)(n_{i}/n^{*})|<\log n\sqrt{n^{*}(v)}$

for all $i\in\mathcal{M}_{0}$.

###  1.5 A local limit theorem

We let $n^{*}=|S^{*}|$. We work on the event $\mathcal{P}_{0}$, that is
$|n^{*}-n\lambda^{*}|<n^{1/2}\log n$. Consider a vertex $v\in V_{n}$ and let
$S_{v}^{*}=S^{*}\setminus\\{v\\}$ having size $n_{v}^{*}=n^{*}-1_{v\in
S^{*}}$, where $1_{v\in S^{*}}=1$ if $v\in S^{*}$, but it is equal to $0$
otherwise.

With a slight abuse of notation, for an event $\mathcal{E}$ and
$\mathbf{1}\left(\mathcal{E}\right)$ denoting its indicator function, and
random variables $X,Y$ we write,

$\mathbb{P}\left[\mathcal{E}|X,Y\right]=\mathbb{E}\left[\mathbf{1}\left(\mathcal{E}\right)|X,Y\right].$

Recall that we let $N_{S^{*}}(v)$ denote the neighbourhood of $v$ in $S^{*}$
and let $n^{*}(v)=|N_{S^{*}}(v)|$. So $n^{*}(v)\sim\mathrm{Bin}(n_{v}^{*},p)$.
We will condition on the event that $|n^{*}(v)-n_{v}^{*}p|\leq\log
n\cdot(np)^{1/2}$ \- we call this event $\widehat{\mathcal{N}}_{v}$. The
Chernoff bound (1) yields

$\mathbb{P}\left(\widehat{\mathcal{N}}_{v}|n^{*}\right)=1-o(1/n).$ (4)

Without loss of generality, suppose that
$\mathcal{M}_{0}=\\{1,\ldots,k_{0}\\}$. Let
$c_{1},\ldots,c_{k_{0}}\in\mathbb{R}$ be such that
$|S_{0}^{-1}(i)|=n^{*}/k_{0}+c_{i}\sqrt{n^{*}}$; thus
$\sum_{i=1}^{k_{0}}c_{i}=0$. Let $\hat{n}_{i}=|S_{v}^{*}\cap S_{0}^{-1}(i)|$;
so $\hat{n}_{i}=n^{*}/k_{0}+c_{i}\sqrt{n^{*}}+O(1)$. Note that
$n_{i}-1\leq\hat{n}_{i}\leq n_{i}$. Furthermore, we write
$\hat{n}_{i}=n_{v}^{*}p_{i}$. Since $n_{v}^{*}=n^{*}-1_{v\in S^{*}}$, it
follows that $p_{i}=1/k_{0}+c_{i}/\sqrt{n^{*}}+O(n^{-1})$.

Let us condition on $n^{*}(v)$ taking a particular value such that
$\widehat{\mathcal{N}}_{v}$ occurs. For $i=1,\ldots,k_{0}-1$ let us write
$m_{i}=\lceil n^{*}(v)p_{i}\rceil$ and
$m_{k}=\hat{n}^{*}(v)-\sum_{i=1}^{k_{0}-1}m_{i}$; so $n(v;i)=|N_{S^{*}}(v)\cap
S_{v}^{*}\cap S_{0}^{-1}(i)|$, for $i=1,\ldots,k_{0}$.

We will give an estimate on the probability that
$(n(v;0),\ldots,n(v;k_{0}))=(s_{1},\ldots,s_{k_{0}})$ conditional on the value
of $n^{*}(v)$ and on
$\boldsymbol{c}^{*}:=(c_{1},\ldots,c_{k_{0}-1})^{T}\in\mathbb{R}^{k_{0}}$.
Note that this probability is:

$\mathbb{P}\left((n(v;0),\ldots,n(v;k_{0}))=(s_{1},\ldots,s_{k_{0}})\mid
n_{v}^{*},n^{*}(v),\boldsymbol{c}^{*}\right)=\frac{\binom{\hat{n}_{1}}{s_{1}}\cdots\cdot\binom{\hat{n}_{k_{0}}}{s_{k_{0}}}}{\binom{n_{v}^{*}}{n^{*}(v)}}.$
(5)

We will show that this probability is approximated by the probability
distribution function of a multivariate gaussian random vector, provided that
$s_{i}$ is close to $m_{i}$ for all $i=1,\ldots,k_{0}-1$. Let
$\mathbf{\mathrm{I}}_{\ell}$ denote the $\ell\times\ell$ unit matrix and
$\mathbf{1}_{\ell\times\ell}$ the all-ones $\ell\times\ell$ matrix.

######  Lemma 1.6.

Let $p=p(n)\in[0,1]$ be such that $\limsup_{n\to\infty}p(n)<1$ and
$n^{1/2}p\geq\log^{3}{n}$. Consider a realisation of
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k)\\}$ such that $\mathcal{P}_{0}$ occurs
and let $\hat{n}^{*}(v)$ be such that $\widehat{\mathcal{N}}_{v}$ occurs.
Suppose that $s_{i}=m_{i}+\delta_{i}$ with $|\delta_{i}|\leq\log
n\cdot(n^{*}p)^{1/2}$, for $i=1,\ldots,k_{0}-1$. Then uniformly over these
values of $(\delta_{1},\ldots,\delta_{k_{0}-1})$ and $\boldsymbol{c}^{*}$ such
that $\|\boldsymbol{c}^{*}\|_{\infty}\leq\log n$, with
$\boldsymbol{x}=(x_{1},\ldots,x_{k_{0}-1})^{T}:=(\delta_{1},\ldots,\delta_{k_{0}-1})^{T}/n^{*}(v)^{1/2}$
and

$\Sigma=\frac{k_{0}}{1-n^{*}(v)/n_{v}^{*}}\left(\mathbf{\mathrm{I}}_{k_{0}-1}+\mathbf{1}_{(k_{0}-1)\times(k_{0}-1)}\right),$

we have

$\displaystyle\mathbb{P}\left((n(v;0),\ldots,n(v;k_{0}))=(s_{1},\ldots,s_{k_{0}})\mid
n_{v}^{*},n^{*}(v),\boldsymbol{c}^{*}\right)=$ $\displaystyle\hskip
99.58464pt\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\phi(\boldsymbol{x})\left(1+o(p^{1/2})\right),$

where
$\phi(\boldsymbol{x})=\left(\frac{|\Sigma|}{2\pi}\right)^{\frac{k_{0}-1}{2}}\exp\left(-\frac{1}{2}\boldsymbol{x}^{T}\Sigma\boldsymbol{x}\right)$
and $|\Sigma|=\mathrm{det}(\Sigma)$.

###### Proof.

For notational convenience we will write $n(v)$ for $n^{*}(v)$, $k$ for
$k_{0}$ and $n$ for $n_{v}^{*}$ and $n_{i}$ for $\hat{n}_{i}$. We will give
asymptotic estimates for each one of the binomial coefficients that appear in
(5). Before we do this, let us give some relations, which we will use in our
estimates later. Firstly, let us observe

$\frac{1}{np}\leq\frac{\log^{3}{n}}{\sqrt{np}}=o\left(p^{1/2}\right).$ (6)

This is equivalent to $1/(np)^{2}=o(p)$ which in turn is equivalent to
$1/n^{2}=o(p^{3})$. But this holds, since $1/n^{1/2}=o(p)$. Also,

$\frac{\log^{2}n}{np}=o\left(p^{1/2}\right).$ (7)

This is equivalent to $\log^{2}n/n=o(p^{3/2})$. But

$\frac{\log^{4/3}n}{n^{2/3}}\ll\frac{1}{n^{1/2}}\ll p.$

We begin with the denominator of (5). Let $H(x)=-x\ln x-(1-x)\ln(1-x)$ denote
the entropy function defined for $x\in(0,1)$. We recall a standard estimate
for this binomial coefficient which relies on the Stirling approximation for
the factorial: $n!=\sqrt{2\pi n}n^{n}e^{-n}(1+O(1/n))$. Using this, we write

$\displaystyle\binom{n}{n(v)}=\frac{n!}{n(v)!(n-n(v))!}$ $\displaystyle=$
$\displaystyle\frac{1+O(1/n(v))}{\sqrt{2\pi}}\cdot\sqrt{\frac{n}{n(v)(n-n(v))}}\cdot\frac{n^{n}e^{-n}}{n(v)^{n(v)}e^{-n(v)}(n-n(v))^{n-n(v)}e^{-(n-n(v))}}$
$\displaystyle=$
$\displaystyle\frac{1+O(1/np)}{\sqrt{2\pi}}\cdot\sqrt{\frac{n}{n(v)(n-n(v))}}\cdot
e^{nH\left(n(v)/n\right)}.$

Therefore,

$\binom{n}{n(v)}\stackrel{{\scriptstyle\eqref{eq:est3}}}{{=}}(1+o(p^{1/2}))\sqrt{\frac{1}{1-n(v)/n}}\cdot\frac{1}{\sqrt{2\pi
n(v)}}\cdot e^{nH\left(n(v)/n\right)}.$ (8)

Now, we will consider $\binom{n_{i}}{s_{i}}$. In fact, we will express this in
terms of $\binom{n_{i}}{m_{i}}$. In turn, we will express the latter using
(8). Recalling that $s_{i}=m_{i}+\delta_{i}$, we write

$\displaystyle\binom{n_{i}}{s_{i}}/\binom{n_{i}}{m_{i}}=\frac{m_{i}!}{(m_{i}+\delta_{i})!}\cdot\frac{(n_{i}-m_{i})!}{(n_{i}-m_{i}-\delta_{i})!}.$

Suppose first that $\delta_{i}>0$. Then

$\frac{m_{i}!}{(m_{i}+\delta_{i})!}=\frac{1}{m_{i}^{\delta_{i}}}\prod_{j=1}^{\delta_{i}}\left(1+\frac{j}{m_{i}}\right)^{-1}.$

Writing $1+j/m_{i}=\exp\left(\ln(1+j/m_{i})\right)$ and expanding the $\ln$
function around 1, we get that

$\prod_{j=1}^{\delta_{i}}\left(1+\frac{j}{m_{i}}\right)^{-1}=\exp\left(-\frac{\delta_{i}^{2}}{2m_{i}}+O\left(\frac{|\delta_{i}|}{m_{i}}+\frac{|\delta_{i}|^{3}}{m_{i}^{2}}\right)\right).$

Similarly, we get

$\frac{(n_{i}-m_{i})!}{(n_{i}-m_{i}-\delta_{i})!}=(n_{i}-m_{i})^{\delta_{i}}\exp\left(-\frac{\delta_{i}^{2}}{2(n_{i}-m_{i})}+O\left(\frac{|\delta_{i}|}{n_{i}-m_{i}}+\frac{|\delta_{i}|^{3}}{(n_{i}-m_{i})^{2}}\right)\right).$

As $n_{i}-m_{i}=\Omega(n)$, we deduce that

$\frac{|\delta_{i}|}{n_{i}-m_{i}}+\frac{|\delta_{i}|^{3}}{(n_{i}-m_{i})^{2}}=O\left(\frac{\log
n\cdot(np)^{1/2}}{n}+\frac{\log^{3}n\cdot(np)^{3/2}}{n^{2}}\right)=o(p^{1/2}).$

Furthermore, as $|\delta_{i}|\leq(np)^{1/2}\log{n}$,

$\frac{\sum_{i=1}^{k-1}|\delta_{i}|}{np}+\frac{\sum_{i=1}^{k-1}|\delta_{i}|^{3}}{(np)^{2}}=O\left(\frac{\log^{3}{n}}{\sqrt{np}}\right)\stackrel{{\scriptstyle\eqref{eq:est1}}}{{=}}o(p^{1/2}).$

We thus conclude that

$\begin{split}&\binom{n_{i}}{s_{i}}=\left(1+o(p^{1/2})\right)\binom{n_{i}}{m_{i}}\cdot\left(\frac{n_{i}-m_{i}}{m_{i}}\right)^{\delta_{i}}\cdot\exp\left(-\frac{\delta_{i}^{2}}{2}\cdot\frac{n_{i}}{m_{i}(n_{i}-m_{i})}\right).\end{split}$
(9)

Note that as $m_{i}=\lceil n(v)p_{i}\rceil=n(v)p_{i}+r$, for some $0\leq r<1$,
and $n_{i}=np_{i}$, we have

$\frac{n_{i}}{m_{i}}=\frac{np_{i}}{n(v)p_{i}+r}=\frac{n}{n(v)}\left(1+O\left(\frac{1}{n(v)}\right)\right).$
(10)

Since $|\delta_{i}|=O(\log n\cdot(np)^{1/2})$, we deduce that

$\begin{split}\left(\frac{n_{i}-m_{i}}{m_{i}}\right)^{\delta_{i}}&=\left(\frac{n}{n(v)}-1+O\left(\frac{n}{n(v)^{2}}\right)\right)^{\delta_{i}}\\\
&=\left(\frac{n}{n(v)}-1\right)^{\delta_{i}}\left(1+O\left(\frac{|\delta_{i}|}{n(v)}\right)\right)\\\
&=\left(\frac{n}{n(v)}-1\right)^{\delta_{i}}\left(1+O\left(\frac{\log
n}{(np)^{3/2}}\right)\right)\\\
&\stackrel{{\scriptstyle\eqref{eq:est3}}}{{=}}\left(\frac{n}{n(v)}-1\right)^{\delta_{i}}(1+o(p^{1/2})).\end{split}$

Furthermore,

$\frac{\delta_{i}^{2}}{2}\cdot\frac{n_{i}}{m_{i}(n_{i}-m_{i})}=\frac{\delta_{i}^{2}}{2n(v)p_{i}}\left(\frac{1}{1-n(v)/n}\right)+O(\delta_{i}^{2}/(np)^{2}).$

But $\delta_{i}^{2}=O(\log^{2}n\cdot(np))$ and therefore

$\frac{\delta_{i}^{2}}{2}\cdot\frac{n_{i}}{m_{i}(n_{i}-m_{i})}=\frac{\delta_{i}^{2}}{2n(v)p_{i}}\left(\frac{1}{1-n(v)/n}\right)+O(\log^{2}n/(np)).$

By (7), $\log^{2}n/(np)=o(p^{1/2})$ and, thereby,

$\exp\left(-\frac{\delta_{i}^{2}}{2}\cdot\frac{n_{i}}{m_{i}(n_{i}-m_{i})}\right)=(1+o(p^{1/2}))\exp\left(-\frac{\delta_{i}^{2}}{2n(v)p_{i}}\left(\frac{1}{1-n(v)/n}\right)\right).$

As $n_{i}=\Theta(n)$ and $m_{i}=\Theta(np)$, applying (8), we can also deduce
that

$\binom{n_{i}}{m_{i}}=(1+o(p^{1/2}))\sqrt{\frac{1}{1-n(v)/n}}\cdot\frac{1}{\sqrt{2\pi
m_{i}}}\cdot e^{n_{i}H(m_{i}/n_{i})}.$ (11)

Combining (8), (9) and (11), we deduce that

$\displaystyle\mathbb{P}\left((n(v;1),\ldots,n(v;k))=(s_{1},\ldots,s_{k})\mid
n,n(v),\boldsymbol{c}^{*}\right)=$ (12)
$\displaystyle\left(1+o(p^{1/2})\right)\times$
$\displaystyle\frac{1}{(1-n(v)/n)^{\frac{k-1}{2}}}\cdot\frac{1}{(2\pi)^{\frac{k-1}{2}}}\cdot\sqrt{\frac{n(v)}{\prod_{i=1}^{k}m_{i}}}\cdot\left(\prod_{i=1}^{k}\left(\frac{n}{n(v)}-1\right)^{\delta_{i}}\right)\times$
$\displaystyle\hskip
56.9055pt\exp\left(-\frac{1}{2}\sum_{i=1}^{k}\frac{\delta_{i}^{2}}{n(v)}\frac{1}{p_{i}(1-n(v)/n)}\right)\times$
$\displaystyle e^{\sum_{i=1}^{k}n_{i}H(m_{i}/n_{i})-nH(n(v)/n)}$
$\displaystyle\stackrel{{\scriptstyle\delta_{0}+\cdots+\delta_{k}=0}}{{=}}$
$\displaystyle\left(1+o(p^{1/2})\right)\times$
$\displaystyle\frac{1}{(1-n(v)/n)^{\frac{k-1}{2}}}\cdot\frac{1}{(2\pi
n(v))^{\frac{k-1}{2}}}\cdot\sqrt{\frac{1}{\prod_{i=1}^{k}p_{i}}}\times$
$\displaystyle\exp\left(-\frac{1}{2}\sum_{i=1}^{k}\frac{\delta_{i}^{2}}{n(v)}\frac{1}{p_{i}(1-n(v)/n)}\right)\times$
$\displaystyle\hskip
56.9055pte^{\sum_{i=1}^{k}n_{i}H(m_{i}/n_{i})-nH(n(v)/n)}.$

######  Claim 1.7.

With $\boldsymbol{x}=(\delta_{1},\ldots,\delta_{k-1})^{T}/n(v)^{1/2}$ and

$\Sigma=\frac{k}{1-n(v)/n}\left[\begin{array}[]{ccc}2&\cdots&1\\\
\vdots&\ddots&\vdots\\\ 1&\cdots&2\end{array}\right],$

we have

$\exp\left(-\frac{1}{2}\sum_{i=1}^{k}\frac{\delta_{i}^{2}}{n(v)}\frac{1}{p_{i}(1-n(v)/n)}\right)=(1+o(p^{1/2}))\exp\left(-\frac{1}{2}\boldsymbol{x}^{T}\Sigma\boldsymbol{x}\right).$

###### Proof.

Since $\delta_{1}+\cdots+\delta_{k}=0$ we write, with
$\boldsymbol{\delta}=(\delta_{1},\ldots,\delta_{k-1})^{T}$,

$\displaystyle\sum_{i=1}^{k}\frac{\delta_{i}^{2}}{p_{i}}$ $\displaystyle=$
$\displaystyle\sum_{i=1}^{k-1}\frac{\delta_{i}^{2}}{p_{i}}+\frac{(\delta_{1}+\cdots+\delta_{k-1})^{2}}{p_{k}}$
$\displaystyle=$
$\displaystyle\sum_{i=1}^{k-1}\delta_{i}^{2}\left(\frac{1}{p_{i}}+\frac{1}{p_{k}}\right)+\sum_{i\not=j}\delta_{i}\delta_{j}\frac{1}{p_{k}}$
$\displaystyle=$
$\displaystyle\boldsymbol{\delta}^{T}\left[\begin{array}[]{ccc}\frac{1}{p_{1}}+\frac{1}{p_{k}}&\cdots&\frac{1}{p_{k}}\\\
\vdots&\ddots&\vdots\\\
\frac{1}{p_{k}}&\cdots&\frac{1}{p_{k-1}}+\frac{1}{p_{k}}\end{array}\right]\boldsymbol{\delta}.$

Thus, setting

$\Sigma^{\prime}=\frac{1}{1-n(v)/n}\left[\begin{array}[]{ccc}\frac{1}{p_{1}}+\frac{1}{p_{k}}&\cdots&\frac{1}{p_{k}}\\\
\vdots&\ddots&\vdots\\\
\frac{1}{p_{k}}&\cdots&\frac{1}{p_{k-1}}+\frac{1}{p_{k}}\end{array}\right],$

and using the scaling
$\boldsymbol{x}=(\delta_{1},\ldots,\delta_{k-1})^{T}/n(v)^{1/2}$ we get

$\exp\left(-\frac{1}{2}\sum_{i=1}^{k}\frac{\delta_{i}^{2}}{n(v)}\frac{1}{p_{i}(1-n(v)/n)}\right)=\exp\left(-\frac{1}{2}\boldsymbol{x}^{T}\Sigma^{\prime}\boldsymbol{x}\right).$

Now, note that $p_{i}=1/k_{0}+\Theta(\log n\cdot n^{-1/2})$. Therefore,
uniformly for $\boldsymbol{x}$ such that $\|\boldsymbol{x}\|_{\infty}\leq\log
n$, we have
$\boldsymbol{x}^{T}\Sigma^{\prime}\boldsymbol{x}=\boldsymbol{x}^{T}\Sigma\boldsymbol{x}+O(\log^{3}n/n^{1/2})=\boldsymbol{x}^{T}\Sigma\boldsymbol{x}+o(p^{1/2})$.
The claim then follows. ∎

We now calculate $|\Sigma|$.

######  Claim 1.8.

We have

$|\Sigma|=\frac{k^{k}}{\left(1-n(v)/n\right)^{k-1}}.$

###### Proof.

We will consider first the matrix
$\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}$. We will show that

$|\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}|=k.$ (14)

We will show this by finding the eigenvalues of
$\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}$ and using the fact
that $|\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}|$ is equal to
their product. The eigenvectors of
$\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}$ are
$\mathbf{1}_{k-1}$ (the all-one vector), and the vectors $e_{1j}$, for
$1<j\leq k$ with 1 in the first component and $-1$ at the $j$th component and
$0$ everywhere else. The associated eigenvalues are $k$ for $\mathbf{1}_{k-1}$
and $1$ for the eigenvectors $e_{1j}$, for $j=2,\ldots,k-1$. Thus, the product
of the eigenvalues is equal to $k$ whereby (14) follows. Therefore,

$|\Sigma|=\left(\frac{k}{1-n(v)/n}\right)^{k-1}\cdot|\mathbf{\mathrm{I}}_{k-1}+\mathbf{1}_{(k-1)\times(k-1)}|=\frac{k^{k}}{\left(1-n(v)/n\right)^{k-1}}.$

∎

Returning to (12), the we will show that the term

$\left(\frac{1}{1-n(v)/n}\right)^{\frac{k-1}{2}}\sqrt{\frac{1}{p_{1}\cdots
p_{k}}}=(1+o(p^{1/2}))|\Sigma|^{1/2}.$

By the above claim, it suffices to show that

$\sqrt{\frac{1}{p_{1}\cdots p_{k}}}=(1+o(p^{1/2}))k^{k/2}.$

Recall that $p_{i}=1/k+O(\log n\cdot n^{-1/2})$, for $i=1,\ldots,k$.
Therefore,

$\sqrt{\frac{1}{p_{1}\cdots p_{k}}}=k^{k/2}\left(1+O(\log n\cdot
n^{-1/2})\right)=k^{k/2}\left(1+o(p^{1/2}))\right),$

as $p\gg\log^{2}n/n$.

Finally, we will deal with last exponential in (12).

######  Claim 1.9.

We have

$\sum_{i=1}^{k}n_{i}H(m_{i}/n_{i})-nH(n(v)/n)=O(1/np).$

∎

###### Proof.

We will approximate $H(m_{i}/n_{i})$ by $H(n(v)/n)$ using (the second order)
Taylor’s theorem around $n(v)/n$. Let $i\in\\{1,\ldots,k-1\\}$. Then
$m_{i}\geq n(v)p_{i}$, whereby $n(v)/n\leq m_{i}/n_{i}$. Furthermore, for $n$
sufficiently large $m_{i}/n_{i}<1$ and therefore
$[n(v)/n,m_{i}/n_{i}]\subset(0,1)$. Since the entropy function $H$ is twice
differentiable in $(0,1)$, there exists $\xi\in[n(v)/n,m_{i}/n_{i}]$

$H\left(\frac{m_{i}}{n_{i}}\right)=H\left(\frac{n(v)}{n_{i}}\right)+H^{\prime}\left(\frac{n(v)}{n}\right)\left(\frac{m_{i}n-n_{i}n(v)}{nn_{i}}\right)+\frac{1}{2}H^{\prime\prime}(\xi)\left(\frac{m_{i}n-n_{i}n(v)}{nn_{i}}\right)^{2}.$

By (10), we have that

$\left(\frac{m_{i}n-n_{i}n(v)}{nn_{i}}\right)^{2}=O\left(\frac{1}{n^{2}}\right).$

Also, $H^{\prime\prime}(x)=-\frac{1}{x(1-x)}$, for any $x\in(0,1)$. As
$\xi=p+o(p)$ and $p$ is asymptotically bounded away from 1, we have

$|H^{\prime\prime}(\xi)|=\frac{1}{\xi(1-\xi)}=O(1/\xi)=O(1/p).$

We can deduce the same for $i=k$, except that in that case $m_{k}/n_{k}\leq
n(v)/n$. Using these, we can write

$\displaystyle\sum_{i=1}^{k}n_{i}H\left(\frac{m_{i}}{n_{i}}\right)=$
$\displaystyle\sum_{i=1}^{k}n_{i}H\left(\frac{n(v)}{n}\right)+\sum_{i=1}^{k}n_{i}H^{\prime}\left(\frac{n(v)}{n}\right)\left(\frac{m_{i}n-n_{i}n(v)}{nn_{i}}\right)+O\left(\frac{1}{n^{2}p}\right)\sum_{i=1}^{k}n_{i}$
$\displaystyle=$ $\displaystyle
nH\left(\frac{n(v)}{n}\right)+H^{\prime}\left(\frac{n(v)}{n}\right)\left(\frac{n\sum_{i}m_{i}-n(v)\sum_{i}n_{i}}{n}\right)+O\left(\frac{1}{np}\right)$
$\displaystyle=$ $\displaystyle
nH\left(\frac{n(v)}{n}\right)+O\left(\frac{1}{np}\right),$

since $\sum_{i}m_{i}=n(v)$ and $\sum_{i}n_{i}=n-t$. ∎

Therefore,

$e^{\sum_{i=1}^{k}n_{i}H(m_{i}/n_{i})-nH(n(v)/n)}=e^{O(1/np)}=1+O(1/(np))\stackrel{{\scriptstyle\eqref{eq:est1}}}{{=}}1+o(p^{1/2}).$
(15)

We thus conclude that

$\mathbb{P}\left((n(v;0),\ldots,n(v;k))=(s_{1},\ldots,s_{k})\mid
n,n(v),\boldsymbol{c}^{*}\right)=\frac{1}{n(v)^{\frac{k-1}{2}}}\cdot\phi(\boldsymbol{x})\cdot\left(1+o(p^{1/2})\right).$

###  1.6 Some basic (anti-)concentration properties of the initial
configuration

Conditional on $|S^{*}|=n^{*}$, for any $i\in\mathcal{M}_{0}$ we have
$n_{i}\sim\mathrm{Bin}(n^{*},1/k_{0})$. The local limit theorem (Theorem 1.2)
implies that the probability that $n_{i}$ is too close to $n^{*}/k_{0}$ is
small.

######  Lemma 1.10.

For any $\varepsilon>0$ there exists $\delta>0$ such that

$\mathbb{P}\left(\left|n_{i}-n^{*}/k_{0}\right|\leq\delta\sqrt{n^{*}}\mid
n^{*}\right)<\varepsilon.$

###### Proof.

We use the local limit theorem (Theorem 1.2). We denote the variance of
$n_{i}$ (conditional on $n^{*}$) by $\sigma_{*}^{2}=n^{*}(1/k_{0})(1-1/k_{0})$
and write

$\displaystyle\mathbb{P}\left(|n_{i}-n^{*}/k_{0}|\leq\delta\sqrt{n^{*}}\mid
n^{*}\right)$ $\displaystyle=$
$\displaystyle\sum_{k:|k-n^{*}/k_{0}|\leq\delta\sqrt{n^{*}}}\mathbb{P}\left(n_{i}=k\right)$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2\pi\sigma_{*}^{2}}}\sum_{k:|k-n^{*}/k_{0}|\leq\delta\sqrt{n^{*}}}e^{-\frac{(k-n^{*}/k_{0})^{2}}{2\sigma_{*}}}+O\left(\frac{1}{\sqrt{n^{*}}}\right)$
$\displaystyle\leq$
$\displaystyle\frac{2\delta\sqrt{n^{*}}}{\sqrt{2\pi\sigma_{*}^{2}}}+O\left(\frac{1}{\sqrt{n^{*}}}\right)=O(\delta).$

The lemma follows. ∎

Also, the Chernoff bound (1) implies that $n_{i}$ is not too far from
$n^{*}/k_{0}$ too.

######  Lemma 1.11.

For any $\varepsilon>0$, there exists $C>0$ such that

$\mathbb{P}\left(|n_{i}-n^{*}/k_{0}|>C\sqrt{n^{*}}\mid
n^{*}\right)<\varepsilon/6.$

Furthermore, we will show the following.

######  Lemma 1.12.

Let $X=(X_{1},\ldots,X_{k_{0}-1})$ be a random vector with
$X\sim\mathrm{Mult}(n^{*};(1/k_{0},\ldots,1/k_{0}))$ and let
$\boldsymbol{c}^{*}=(n^{*})^{-1/2}\cdot(X-n^{*}(1/k_{0},\ldots,1/k_{0}))$. Let
$\boldsymbol{C}\in\mathbb{R}^{k_{0}-1}$ be such that
$\boldsymbol{C}\not=\boldsymbol{0}\in\mathbb{R}^{k_{0}-1}$. For any
$\varepsilon>0$, there exists $\delta=\delta(\varepsilon,\boldsymbol{C})>0$
such that

$\mathbb{P}\left(|\boldsymbol{c}^{*}\cdot\boldsymbol{C}|<\delta\mid
n^{*}\right)<\varepsilon,$

for any $n^{*}$ that is sufficiently large.

###### Proof.

For $j=1,\ldots,k_{0}-1$, the component $X_{j}$ is binomially distributed with
parameters $n^{*}$ and $1/k_{0}$. The same holds for
$X_{k_{0}}=n^{*}-\sum_{j<k_{0}}X_{j}$. Thus, for any $\varepsilon>0$ and any
$j\in[k_{0}]$, there is $\Lambda_{j}=\Lambda_{j}(\varepsilon)>0$, such that

$\mathbb{P}\left((n^{*})^{-1/2}\cdot\left|X_{j}-n^{*}/k_{0}\right|>\Lambda_{j}\right)<\varepsilon/k_{0}.$

By the union bound, for any $\varepsilon$ there is
$\Lambda=\max\\{\Lambda_{j}(\varepsilon/3)\\}_{j\in[k_{0}]}$, such that

$\mathbb{P}\left(\left\|\boldsymbol{c}^{*}\right\|_{\infty}>\Lambda\right)<\varepsilon/3.$
(16)

For a given $\varepsilon>0$, select this $\Lambda$.

We will use the local limit theorem for the multinomial distribution. This was
first shown by Arenbaev [1] (see Lemma 2 therein), but we will use a version
that was shown by Siotani and Fujikoshi in [18]. Let
$X=(X_{1},\ldots,X_{k_{0}})$ be the random vector that follows the multinomial
distribution with parameters $n^{*}$ and
$\boldsymbol{q}:=(1/k_{0},\ldots,1/k_{0})\in\mathbb{R}^{1\times k_{0}-1}$. Let
$\phi$ denote the pdf of the $k_{0}-1$-dimensional normal distribution with
expected value equal to $\boldsymbol{0}\in\mathbb{R}^{k_{0}-1}$ and covariance
matrix
$\mathrm{diag}(1/k_{0},\ldots,1/k_{0})-\boldsymbol{q}^{T}\boldsymbol{q}$. The
Local Limit Theorem for the multinomial distribution implies that for any
$\boldsymbol{x}=(x_{1},\ldots,x_{k_{0}-1})$:

$\mathbb{P}\left(\boldsymbol{c}^{*}=\boldsymbol{x}\right)\leq\frac{1}{(n^{*})^{\frac{k_{0}-1}{2}}\sqrt{(1/k_{0})\cdot\cdots\cdot(1/k_{0})}}\phi(\boldsymbol{x})(1+O((n^{*})^{-1/2})).$
(17)

For a vector
$\boldsymbol{C}=(C_{1},\ldots,C_{k_{0}-1})^{T}\in\mathbb{R}^{k_{0}-1}$, we
define the set

$S_{\delta,\Lambda,\boldsymbol{C}}=\\{\boldsymbol{x}=(x_{1},\ldots,x_{k_{0}-1}):|\boldsymbol{x}\cdot\boldsymbol{C}|<\delta,\left\|\boldsymbol{x}\right\|_{\infty}\leq\Lambda,\
\mbox{$\forall j\in[k_{0}-1]$}\
n^{*}/k_{0}+x_{j}\sqrt{n^{*}}\in\mathbb{N}_{0}\ \\}.$

We claim that
$|S_{\delta,\Lambda,\boldsymbol{C}}|=O(\delta\cdot(n^{*})^{\frac{k_{0}-1}{2}}\cdot\Lambda^{k_{0}-1})$.
Indeed, we can select freely $x_{1},\ldots,x_{k_{0}-2}$, whereby there are
$\left(2\Lambda\sqrt{n^{*}}\right)^{k_{0}-2}$ such choices. For each such
choice, the component $x_{k_{0}-1}$ must be selected so that
$-\delta<\sum_{j=1}^{k_{0}-2}x_{j}C_{j}+x_{k_{0}-1}C_{k_{0}-1}<\delta$. There
are at most $2\delta\sqrt{n^{*}}\Lambda/|C_{k_{0}-1}|$ such choices. We
conclude that

$|S_{\delta,\Lambda,\boldsymbol{C}}|=\delta\cdot(n^{*})^{\frac{k_{0}-1}{2}}\cdot(2\Lambda)^{k_{0}-1}/|C_{k_{0}-1}|.$

Now, choose
$\delta=\frac{1}{2}\varepsilon(2\Lambda)^{-(k_{0}-1)}\cdot|C_{k_{0}-1}|$.

$\displaystyle\mathbb{P}\left(|\boldsymbol{c}^{*}\cdot\boldsymbol{C}|<\delta\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:LLL}}}{{\leq}}$
$\displaystyle(1+o(1))\sum_{\boldsymbol{x}\in
S_{\delta,\Lambda,\boldsymbol{C}}}\phi(\boldsymbol{x})+\mathbb{P}\left(\left\|\boldsymbol{c}^{*}\right\|_{\infty}>\Lambda\right)$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:cv_infty_norm}}}{{\leq}}$
$\displaystyle(1+o(1))\varepsilon/2+\varepsilon/3<\varepsilon.$

∎

The two lemmas together with the union bound imply that for any $\varepsilon$
there exists $\delta>0$ such that with probability at least $1-\varepsilon/2$,
for $i\in\mathcal{M}_{0}$ we have

$\delta<\frac{1}{\sqrt{n^{*}}}|n_{i}-n^{*}/k_{0}|\leq 1/\delta,$

and for distinct $i=1,\ldots,k_{0}-1$

$|c_{i}-c_{i+1}|>\delta,$

with $c_{k_{0}}=-\sum_{j<k_{0}}c_{j}$. The latter follows from Lemma 1.12 with
$\boldsymbol{C}=(0,\ldots,0,1,-1,0,\ldots,0)^{T}$, where $1$ and $-1$ are in
places $i$ and $i+1$, respectively, with $i<k_{0}-1$, or taking
$\boldsymbol{C}=(1,\ldots,1,2)^{T}$.

We denote this event $\mathcal{E}_{\delta,}$. In what follows, we will
condition on $\mathcal{E}_{\delta,n}$. More specifically, we shall assume that
the initial configuration on $S^{*}$ is such that for each
$i\in\mathcal{M}_{0}$

$n_{i}=n^{*}/k_{0}+c_{i}\sqrt{n^{*}},$

with $\delta<c_{i}<1/\delta$ and $c_{i+1}-c_{i}>\delta$, for any
$i\in\mathcal{M}_{0}\setminus\\{k_{0}\\}$. We write
$S_{0}\in\mathcal{E}_{\delta,n}$.

###  1.7 The expected evolution of the system after one step

For $i\in\mathcal{M}_{0}$, we let $\mathcal{S}\mathcal{S}_{1}^{(i)}$ denote
the subset of vertices $v\in V_{n}$ such that $S_{1}(v)=i$ in a _strong sense_
, that is, $n_{0}(v;i)>n_{0}(v;j)$ for any $j\in\mathcal{M}_{0}$ with
$j\not=i$. For a vertex $v\in V_{n}$, we will give a tight approximation of
the probability that $v\in\mathcal{S}\mathcal{S}_{1}^{(i)}$, for
$i\in\mathcal{M}_{0}$.

Recall that $p_{i}=1/k_{0}+\frac{c_{i}}{\sqrt{n^{*}}}+O(1/n)$ and we wrote
$n_{0}(v;i)=m_{i}+\delta_{i}$, where $m_{i}=\lceil n^{*}(v)p_{i}\rceil$, for
$i=1,\ldots,k_{0}-1$, but $m_{k_{0}}=n^{*}(v)-\sum_{i=1}^{k-1}m_{i}$.

Now, we write $m_{j}=n^{*}(v)p_{j}+r_{j}$, for $0\leq r_{j}<1$, and using that
$p_{i}=1/k_{0}+\frac{c_{i}}{\sqrt{n^{*}}}+O(1/n)$, we have that

$\displaystyle m_{i}$ $\displaystyle=$ $\displaystyle
n^{*}(v)/k_{0}+\frac{n^{*}(v)}{\sqrt{n^{*}}}c_{i}+r_{i}+O\left(\frac{n^{*}(v)}{n^{*}}\right)$
$\displaystyle=:$ $\displaystyle
n^{*}(v)/k_{0}+h_{i}(\boldsymbol{c}^{*},n^{*}(v)).$

In other words, we have set
$h_{i}(\boldsymbol{c}^{*},n^{*}(v)):=m_{i}-n^{*}(v)/k_{0}$. Note that
$\sum_{i=1}^{k_{0}}h_{i}(\boldsymbol{c}^{*},n^{*}(v))=0$.

Thus, we write

$n_{0}(v;i)=n^{*}(v)/k_{0}+h_{i}(\boldsymbol{c}^{*},n^{*}(v))+\delta_{i}.$

Rescaling by $n^{*}(v)^{1/2}$ and recalling that
$\boldsymbol{x}=\boldsymbol{\delta}/n^{*}(v)^{1/2}$ we get

$\displaystyle n^{*}(v)^{-1/2}n_{0}(v;i)$ $\displaystyle=$ $\displaystyle
n^{*}(v)^{1/2}/k_{0}+\frac{h_{i}(\boldsymbol{c}^{*},n^{*}(v))}{n^{*}(v)^{1/2}}+\frac{\delta_{i}}{n^{*}(v)^{1/2}}$
$\displaystyle=$ $\displaystyle
n^{*}(v)^{1/2}/k_{0}+\sqrt{\frac{n^{*}(v)}{n}}c_{i}+x_{i}+O(n^{*}(v)^{-1/2}).$

Let $\mathcal{L}$ denote the set of points
$\\{n^{*}(v)^{-1/2}\cdot(\delta_{1},\ldots,\delta_{k_{0}-1}):\delta_{i}\in\mathbb{Z},i=1,\ldots,k_{0}-1\\}$
and let $\mathcal{L}^{\prime}$ denote its restriction
$\\{(x_{1},\ldots,x_{k_{0}-1})\in\mathcal{L}\ :\ |x_{i}|\leq\log
n,i=1,\ldots,k_{0}-1\\}$. By Claim 1.5, conditional on a realisation of
$\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k_{0})\\}$, that satisfies the event
$\mathcal{E}_{\delta,n}\cap\mathcal{E}_{0}$, and on the value of $n^{*}(v)$ we
have

$\displaystyle\mathbb{P}\left(\mbox{for some $i\in\mathcal{M}_{0}$
}(n^{*}(v))^{-1/2}|n_{0}(v;i)-n^{*}(v)(n_{i}/n^{*})|>\log n\mid
n^{*}(v),n^{*},\boldsymbol{c}^{*}\right)=$ $\displaystyle\hskip
56.9055pt\exp\left({-\Omega(\log^{2}n)}\right)=o(p^{1/2}).$ (18)

In other words, realisations of
$(n^{*}(v))^{-1/2}(n_{0}(v;i))_{i\in\mathcal{M}_{0}}$ that do not belong to
$\mathcal{L}^{\prime}$ have probability $o(p^{1/2})$. Furthermore, for
$i=1,\dots,k_{0}$, we let
$\mathcal{D}_{i}=\\{\boldsymbol{x}\in\mathbb{R}^{k_{0}-1}\ :\
x_{i}>x_{j},\mbox{for all $j\not=i$}\\}$ and
$\mathcal{D}_{i}^{\prime}=\\{\boldsymbol{x}\in\mathbb{R}^{k_{0}-1}\ :\
x_{i}+h_{i}(\boldsymbol{c}^{*},n(v))>x_{j}+h_{j}(\boldsymbol{c}^{*},n(v)),\mbox{for
all $j\not=i$}\\}$, where $x_{k_{0}}=-\sum_{i<k_{0}}x_{i}$.

Using Lemma 1.6 and (18), we can then write

$\displaystyle\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\mid
n^{*}(v),n^{*},\boldsymbol{c}^{*}\right)=(1+o(p^{1/2}))\cdot\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\sum_{\boldsymbol{x}\in\mathcal{D}_{i}^{\prime}\cap\mathcal{L}^{\prime}}\phi(\boldsymbol{x})+o(p^{1/2}).$
(19)

Let us now assume, without loss of generality, that $c_{1}>\ldots>c_{k_{0}}$.
Recall that if the event $\mathcal{E}_{n,\delta}$ is realised, then
$c_{i}-c_{i+1}>\delta$ for $i=1,\ldots,k_{0}-1$. (This event occurs with
probability $1-\varepsilon$ for any $\varepsilon>0$ and for some
$\delta=\delta(\varepsilon)$ \- cf. Section 1.6.)

We will show the following.

######  Lemma 1.13.

There is $\Lambda>0$ such that for any $n$ sufficiently large, on the events
$\mathcal{P}_{0},\mathcal{E}_{\delta,n}$ and $\widehat{\mathcal{N}_{v}}$ we
have:

$n^{*}(v)^{-\frac{k_{0}-1}{2}}\cdot\left(\sum_{\boldsymbol{x}\mathcal{D}_{i}^{\prime}\cap\mathcal{L}^{\prime}}\phi(\boldsymbol{x})-\sum_{\boldsymbol{x}\in\mathcal{D}_{i+1}^{\prime}\cap\mathcal{L}^{\prime}}\phi(\boldsymbol{x})\right)>\Lambda(c_{i}-c_{i+1})p^{1/2}.$

###### Proof.

Let
$\boldsymbol{h}_{n}=(h_{1}(\boldsymbol{c}^{*},n^{*}(v)),\ldots,h_{k_{0}-1}(\boldsymbol{c}^{*},n^{*}(v)))^{T}$.
We use the transformation $\boldsymbol{y}=\boldsymbol{x}+\boldsymbol{h}_{n}$
and write

$\displaystyle\sum_{\boldsymbol{x}\in\mathcal{D}_{i}^{\prime}\cap\mathcal{L}^{\prime}}\phi(\boldsymbol{x})=\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n}).$

Our aim now is to replace $\phi(\boldsymbol{y}-\boldsymbol{h}_{n})$ in the
above sum with $\phi(\boldsymbol{y})$. To estimate the error, we need to
consider the difference
$\phi(\boldsymbol{y}-\boldsymbol{h}_{n})-\phi(\boldsymbol{y})$. We write:

$\displaystyle\phi(\boldsymbol{y}-\boldsymbol{h}_{n})$ $\displaystyle=$
$\displaystyle\phi(\boldsymbol{y})\cdot\exp\left(\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}\right).$

For $i=1,\ldots,k_{0}-2$, we will define a bijection between the sets
$\mathcal{D}_{i}$ and $\mathcal{D}_{i+1}$:

$\boldsymbol{y}=(y_{1},\ldots,y_{i},y_{i+1},\ldots,y_{k_{0}-1})\mapsto\hat{\boldsymbol{y}}=(y_{1},\ldots,y_{i+1},y_{i},\ldots,y_{k_{0}-1})\in\mathcal{D}_{i+1},$

whereas for $i=k_{0}-1$ we set

$\boldsymbol{y}=(y_{1},\ldots,y_{i},y_{i+1},\ldots,y_{k_{0}-1})\mapsto\hat{\boldsymbol{y}}=(y_{1},\ldots,y_{i+1},y_{i},\ldots,-\sum_{i<k_{0}}y_{i})\in\mathcal{D}_{k_{0}}.$

######  Claim 1.14.

For any $\boldsymbol{y}\in\mathcal{D}_{i}$, with $i\in\\{1,\ldots,k_{0}-1\\}$,
we have

$\boldsymbol{y}^{T}\Sigma\boldsymbol{y}=\hat{\boldsymbol{y}}^{T}\Sigma\hat{\boldsymbol{y}}.$

###### Proof.

Indeed, with $\Sigma^{\prime}=\left[\begin{array}[]{ccc}2&\cdots&1\\\
\vdots&\ddots&\vdots\\\ 1&\cdots&2\end{array}\right]$, it suffices to prove
that
$\boldsymbol{y}^{T}\Sigma^{\prime}\boldsymbol{y}=\hat{\boldsymbol{y}}^{T}\Sigma^{\prime}\hat{\boldsymbol{y}}$,
as $\Sigma$ is a multiple of $\Sigma^{\prime}$ by a scalar. For $i<k_{0}-1$,
we have

$\displaystyle\boldsymbol{y}^{T}\Sigma^{\prime}\boldsymbol{y}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-1}y_{i}^{2}+\sum_{j^{\prime}\not=j}y_{j}y_{j^{\prime}}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-1}\hat{y}_{i}^{2}+\sum_{j^{\prime}\not=j}\hat{y}_{j}\hat{y}_{j^{\prime}}.$

For $i=k_{0}-1$,

$\displaystyle\hat{\boldsymbol{y}}^{T}\Sigma^{\prime}\hat{\boldsymbol{y}}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-1}\hat{y}_{i}^{2}+\sum_{j^{\prime}\not=j}\hat{y}_{j}\hat{y}_{j^{\prime}}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-2}y_{i}^{2}+2\left(\sum_{i<k_{0}}y_{i}\right)^{2}+\sum_{j^{\prime}\not=j<k_{0}-1}\hat{y}_{j}\hat{y}_{j^{\prime}}+2\hat{y}_{k_{0}-1}\sum_{i<k_{0}-1}y_{i}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-2}y_{i}^{2}+2\left(\sum_{i<k_{0}}y_{i}\right)^{2}+\sum_{j^{\prime}\not=j<k_{0}-1}y_{j}y_{j^{\prime}}-2\left(\sum_{i<k_{0}}y_{i}\right)\left(\sum_{i<k_{0}-1}y_{i}\right)$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-2}y_{i}^{2}+2\left(\sum_{i<k_{0}}y_{i}\right)^{2}+\sum_{j^{\prime}\not=j<k_{0}-1}y_{j}y_{j^{\prime}}-2\left(\sum_{i<k_{0}}y_{i}\right)\left(\sum_{i<k_{0}}y_{i}-y_{k_{0}-1}\right)$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-2}y_{i}^{2}+\sum_{j^{\prime}\not=j<k_{0}-1}y_{j}y_{j^{\prime}}+2y_{k_{0}-1}^{2}+2y_{k_{0}-1}\sum_{j<k_{0}-1}y_{j}$
$\displaystyle=$ $\displaystyle
2\sum_{j=1}^{k_{0}-1}y_{i}^{2}+\sum_{j^{\prime}\not=j}y_{j}y_{j^{\prime}}=\boldsymbol{y}^{T}\Sigma^{\prime}\boldsymbol{y}.$

∎

The above claim implies that
$\phi(\boldsymbol{y})=\phi(\hat{\boldsymbol{y}})$, for any
$\boldsymbol{y}\in\mathcal{D}_{i}$. We will use this in bounding from below
the difference:

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})-\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})=$
$\displaystyle=$ $\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}-\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}.$

Using the above bijection, the last term can be written as:

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}$
$\displaystyle=$ $\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\hat{\boldsymbol{y}})e^{\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}$
$\displaystyle\stackrel{{\scriptstyle\phi(\boldsymbol{y})=\phi(\hat{\boldsymbol{y}})}}{{=}}$
$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}.$

Thereby, the difference can be written as:

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})-\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})=$
$\displaystyle=$ $\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}-\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\hat{y}^{T}\Sigma\boldsymbol{h}_{n}-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}$
$\displaystyle=$ $\displaystyle
e^{-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})\left(e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}}-e^{\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}}\right).$

By the mean value theorem, for any $\boldsymbol{y}\in\mathcal{D}_{i}$, there
is $\xi$ such that
$\max\\{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n},\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}\\}>\xi>\min\\{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n},\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}\\}$
and

$e^{\boldsymbol{y}^{T}\Sigma\boldsymbol{h}_{n}}-e^{\hat{\boldsymbol{y}}^{T}\Sigma\boldsymbol{h}_{n}}=e^{\xi}\cdot\left((\boldsymbol{y}-\hat{\boldsymbol{y}})^{T}\Sigma\boldsymbol{h}_{n}\right).$

Suppose, firstly, that $i<k_{0}-1$. With
$\boldsymbol{e}_{i}\in\mathbb{R}^{k_{0}-1}$ being the vector that has 0s
everywhere apart from the $i$th component which is equal to 1, we express:

$\boldsymbol{y}-\hat{\boldsymbol{y}}=(y_{i}-y_{i+1})(\boldsymbol{e}_{i}-\boldsymbol{e}_{i+1}).$

As, for each $i=1,\ldots,k_{0}-1$,
$\boldsymbol{e}_{i}\Sigma^{\prime}\boldsymbol{h}_{n}=(1,\ldots,1,2,1,\ldots,1)\boldsymbol{h}_{n}=\sum_{j=1}^{k_{0}-1}h_{j}+h_{i}$,
it follows that

$(\boldsymbol{e}_{i}-\boldsymbol{e}_{i+1})^{T}\Sigma^{\prime}\boldsymbol{h}_{n}=h_{i}-h_{i+1}.$

Therefore,

$(\boldsymbol{y}-\hat{\boldsymbol{y}})^{T}\Sigma^{\prime}\boldsymbol{h}_{n}=(y_{i}-y_{i+1})(h_{i}-h_{i+1}).$

Now, suppose that $i=k_{0}-1$. In this case and recalling that
$\hat{y}_{k_{0}-1}=y_{k_{0}}=-\sum_{j<k_{0}}y_{j}$ we have

$\boldsymbol{y}-\hat{\boldsymbol{y}}=(y_{k_{0}-1}-\hat{y}_{k_{0}-1})\boldsymbol{e}_{k_{0}-1}=(y_{k_{0}-1}-y_{k_{0}})\boldsymbol{e}_{k_{0}-1}.$

But
$\boldsymbol{e}_{k_{0}-1}^{T}\Sigma_{i}^{\prime}\boldsymbol{h}_{n}=\sum_{i=1}^{k_{0}-1}h_{i}+h_{k_{0}-1}=-h_{k_{0}}+h_{k_{0}-1}$.
Therefore,

$(\boldsymbol{y}-\hat{\boldsymbol{y}})^{T}\Sigma^{\prime}\boldsymbol{h}_{n}=(y_{k_{0}-1}-y_{k_{0}})(h_{k_{0}-1}-h_{k_{0}}).$

Now, recall that $h_{i}=\sqrt{\frac{n^{*}(v)}{n^{*}}}c_{i}+o(p^{1/2})$ and
$n^{*}(v)/n^{*}=p(1+o(1))$. These imply that

$h_{i}-h_{i+1}=\frac{k_{0}}{1-n^{*}(v)/n^{*}}p^{1/2}(c_{i}-c_{i+1})(1+o(1)).$

So, uniformly over $\boldsymbol{y}\in\mathcal{D}_{i}$,

$(\boldsymbol{y}-\hat{\boldsymbol{y}})^{T}\Sigma\boldsymbol{h}_{n}=\frac{k_{0}}{1-n^{*}(v)/n^{*}}(y_{i}-y_{i+1})p^{1/2}(c_{i}-c_{i+1})(1+o(1))$

and substituting this into (LABEL:eq:sum_diff) we finally obtain:

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})-\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})=$
$\displaystyle=$
$\displaystyle\frac{k_{0}}{1-n^{*}(v)/n^{*}}(1+o(1))p^{1/2}(c_{i}-c_{i+1})e^{-\frac{1}{2}\boldsymbol{h}_{n}^{T}\Sigma\boldsymbol{h}_{n}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\xi}(y_{i}-y_{i+1}).$

Now, for some $0<\zeta<1$, let
$\mathcal{D}_{i}^{(\zeta)}=\\{\boldsymbol{y}\in\mathcal{D}_{i}\ :\
y_{i}-y_{i+1}>\zeta\ \mbox{and}\ \zeta<y_{j}<1/\zeta\ \mbox{for all
$j=1,\ldots,k_{0}-1$}\\}$. Since $\|\boldsymbol{c}^{*}\|_{\infty}<1/\delta$,
there is a $\Xi=\Xi(\zeta,\varepsilon,\boldsymbol{c}^{*})>0$ such that
$e^{\xi}>\Xi$ for any $\boldsymbol{x}\in\mathcal{D}_{i}^{(\zeta)}$. Moreover,
since any $\boldsymbol{y}\in\mathcal{D}_{i}$ satisfies $y_{i}-y_{i+1}>0$, we
can bound the last sum from below restricting it on
$\mathcal{D}_{i}^{(\zeta)}$:

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\xi}(y_{i}-y_{i+1})$
$\displaystyle\geq$
$\displaystyle\sum_{\boldsymbol{x}\in\mathcal{D}_{i}^{(\zeta)}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})e^{\xi}(y_{i}-y_{i+1})$
$\displaystyle\geq$
$\displaystyle(\Xi\zeta)\cdot\sum_{\boldsymbol{x}\in\mathcal{D}_{i}^{(\zeta)}:\
\boldsymbol{x}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}).$

We use this lower bound in (LABEL:eq:sum_diff) and conclude that

$\displaystyle\sum_{\boldsymbol{y}\in\mathcal{D}_{i}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})-\sum_{\boldsymbol{y}\in\mathcal{D}_{i+1}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}-\boldsymbol{h}_{n})\geq$
$\displaystyle(1+o(1))\frac{k_{0}}{1-n^{*}(v)/n^{*}}\cdot
p^{1/2}(c_{i}-c_{i+1})\cdot(\Xi\zeta)\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y}).$

We will approximate the last sum (scaled by $n^{*}(v)^{-\frac{k_{0}-1}{2}}$)
by an integral of the multivariate gaussian pdf over
$\mathcal{D}_{i}^{(\zeta)}$. In particular, we will show the following.

######  Claim 1.15.

If $n^{*}(v)$ is such that $\widehat{\mathcal{N}_{v}}$ is realised and $n^{*}$
is such that $\mathcal{P}_{0}$ is realised, then

$\liminf_{n\to\infty}\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\
\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})>0.$

This concludes the proof of the lemma.

∎

The proof of the Lemma 1.13 together with (19) yield that for $n$ sufficiently
large and $i=1,\ldots,k_{0}-1$:

$\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\mid
n^{*}(v),n^{*},\boldsymbol{c}^{*}\right)-\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\mid
n^{*}(v),n^{*},\boldsymbol{c}^{*}\right)>\Lambda\cdot(c_{i}-c_{i+1})p^{1/2}.$
(21)

###### Proof of Claim 1.15.

We argue by considering an approximation of the sum of $\phi(\boldsymbol{y})$,
for $\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}$ such that
$\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L^{\prime}}$, to an appropriate
Gaussian integral. For any $\boldsymbol{x}=(x_{1},\ldots,x_{k_{0}-1})$, let
$\mathcal{B}_{\boldsymbol{\boldsymbol{x}}}$ denote the box
$\prod_{j=1}^{k_{0}-1}[x_{i},x_{i}+n(v)^{-1/2})$.

######  Lemma 1.16.

For any
$\boldsymbol{x}^{\prime},\boldsymbol{x}^{\prime\prime}\in\mathcal{B}_{\boldsymbol{x}}$
we have

$\lvert\phi(\boldsymbol{x}^{\prime})-\phi(\boldsymbol{x}^{\prime\prime})\rvert=O\left(\frac{1}{\sqrt{n(v)}}\right),$

uniformly over the choices of $\boldsymbol{x},\boldsymbol{x}^{\prime}$ and
$\boldsymbol{x}^{\prime\prime}$.

###### Proof.

Suppose we have
$\boldsymbol{x}^{\prime}=(x^{\prime}_{1},\ldots,x^{\prime}_{k_{0}-1})^{T}$ and
$\boldsymbol{x}^{\prime\prime}=(x^{\prime\prime}_{1},\ldots,x^{\prime\prime}_{k_{0}-1})^{T},$
both belonging to $\mathcal{B}_{\boldsymbol{x}}$. We appeal to the
multidimensional mean value theorem: there exists some $c\in(0,1)$ such that,

$\lvert\phi(\boldsymbol{x}^{\prime})-\phi(\boldsymbol{x}^{\prime\prime})\rvert\leq\lVert\nabla\phi(\left(1-c)\boldsymbol{x}^{\prime}+c\boldsymbol{x}^{\prime\prime}\right)\rVert_{2}\lVert\boldsymbol{x}^{\prime}-\boldsymbol{x}^{\prime\prime}\rVert_{2}.$

For $i=1,\ldots,k_{0}-1$, we set
$z_{i}=x^{\prime}_{i}(1-c)+x^{\prime\prime}_{i}c$ and consider the order of
$\lVert\nabla\phi((z_{1},\ldots z_{k_{0}-1}))\rVert_{2}.$ We remark that the
exponent in $\phi((z_{1},\ldots z_{k_{0}-1}))$ is a quadratic form in
$\boldsymbol{z}=(z_{1},\ldots z_{k_{0}-1})^{T}$. We set

$-\frac{1}{2}\boldsymbol{z}^{T}\Sigma\boldsymbol{z}=:h(\boldsymbol{z}).$

Hence it follows from the definition of $\phi$ that,

$\lVert\nabla\phi(\boldsymbol{z})\rVert_{2}=\lvert\phi(\boldsymbol{z})\rvert\lVert\nabla
h(\boldsymbol{z})\rVert_{2}.$

Now we observe that as $h$ is quadratic in $z_{1},\ldots,z_{k_{0}-1}$ it
follows that,

$\lVert\nabla
h(\boldsymbol{z})\rVert_{2}=O(\left|\boldsymbol{z}\right|_{\infty}^{2})=O(1).$

We also have that $\phi(\boldsymbol{z})\leq 1$. Therefore,

$\lvert\phi(\boldsymbol{x}^{\prime})-\phi(\boldsymbol{x^{\prime\prime}})\rvert=O(\lVert\boldsymbol{x}^{\prime}-\boldsymbol{x}^{\prime\prime}\rVert_{2}).$

However, as $\boldsymbol{x}^{\prime}$ and
$\boldsymbol{x}^{\prime\prime}\in\mathcal{B}_{\boldsymbol{x}}$ then we have
that
$\lVert\boldsymbol{x}^{\prime}-\boldsymbol{x}^{\prime\prime}\rVert_{2}=O\left(1/\sqrt{n(v)}\right),$
which concludes the proof of this lemma. ∎

Thus applying the above we can consider an approximation of the above sums by
a Gaussian integral. Recall that
$\mathcal{B}^{\infty}_{\log{n}}=\\{\boldsymbol{z}=(z_{1},\ldots,z_{k_{0}-1})\in\mathbb{R}^{k_{0}-1}:\lVert\boldsymbol{z}\rVert_{\infty}<\log{n}\\}$.

For each $\boldsymbol{x}\in\mathcal{L}^{\prime}$ such that
$\boldsymbol{x}+\boldsymbol{h}_{n}\in\mathcal{D}_{i}^{(\zeta)}$, let us
consider

$\boldsymbol{z}_{\textrm{max}}(\boldsymbol{x})\in\operatorname*{argmax}_{\boldsymbol{z}\in\mathcal{B}_{\boldsymbol{x}}}\\{\phi(\boldsymbol{z})\\},$

a maximiser of $\phi$ inside $\mathcal{B}_{\boldsymbol{x}}$.

We write:

$\displaystyle\frac{1}{n(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{y})=\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{z}_{\textrm{max}}(\boldsymbol{y}))$
$\displaystyle\hskip
56.9055pt-\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\lvert\phi(\boldsymbol{z}_{\textrm{max}}(\boldsymbol{y}))-\phi(\boldsymbol{y})\rvert.$

The first sum is asymptotically bounded from below by an integral:

$\liminf_{n\to\infty}\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{z}_{\textrm{max}}(\boldsymbol{x}))\geq\int_{\mathcal{D}_{i}^{(\zeta)}}\phi(\boldsymbol{x})\mathrm{d}\boldsymbol{x}.$

For the second term, let us observe that
$|\\{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}\\}|\leq|\mathcal{L}^{\prime}|=O(n(v)^{(k_{0}-1)/2}\log^{2}{n})$.
By Lemma 1.16

$\lvert\phi(\boldsymbol{z}_{\textrm{max}}(\boldsymbol{y}))-\phi(y)\rvert=O\left(n^{*}(v)^{-1/2}\right).$

Therefore,

$\displaystyle\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\lvert\phi(\boldsymbol{z}_{\textrm{max}}(\boldsymbol{x}))-\phi(\boldsymbol{x})\rvert$
$\displaystyle\hskip
28.45274pt=O\left(n^{*}(v)^{-1/2-(k_{0}-1)/2}\right)\cdot|\\{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}\\}|$
$\displaystyle\hskip 28.45274pt=O(1)\cdot n^{*}(v)^{-1/2}\log^{2}n.$

As $p\geq n^{-1/2}\log^{3}n$, it follows that
$p^{1/2}\geq\log^{3}n(np)^{-1/2}$ and, since $\widehat{\mathcal{N}_{v}}$ is
realised,

$\frac{\log^{2}n}{\sqrt{n^{*}(v)}}=O\left(\frac{\log^{2}n}{(np)^{1/2}}\right)=o(p^{1/2}).$

We conclude that

$\liminf_{n\to\infty}\frac{1}{n^{*}(v)^{\frac{k_{0}-1}{2}}}\cdot\sum_{\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}:\boldsymbol{y}-\boldsymbol{h}_{n}\in\mathcal{L}^{\prime}}\phi(\boldsymbol{x})\geq\int_{\mathcal{D}_{i}^{(\zeta)}}\phi(\boldsymbol{y})\mathrm{d}\boldsymbol{y}-o(p^{1/2}).$

Since $\limsup_{n\to\infty}\|\boldsymbol{h}_{n}\|_{\infty}<\infty$, we
conclude that for some $\kappa>0$ we have $\phi(\boldsymbol{y})>\kappa$ for
any $\boldsymbol{y}\in\mathcal{D}_{i}^{(\zeta)}$. Therefore,

$\liminf_{n\to\infty}\int_{\mathcal{D}_{i}^{(\zeta)}}\phi(\boldsymbol{y})\mathrm{d}\boldsymbol{y}\geq\kappa\cdot\mathrm{Leb}(\mathcal{D}_{i}^{(\zeta)})>0,$

and the claim follows. ∎

####  1.7.1 Concentration after the first step

Let $X_{i}$ denote the random variable that is the number of vertices that
obtain state $i\in\mathcal{M}_{0}$ during round 1 in a strong sense. We will
condition on $\boldsymbol{c}^{*}$ which satisfies $\mathcal{E}_{n,\delta}$ and
moreover $c_{i}-c_{i+1}>\delta$, for $i=1,\ldots,k_{0}-1$. We will prove the
following:

$\mathbb{E}\left[X_{i}-X_{i+1}|n^{*},\boldsymbol{c}^{*}\right]\geq\Omega(1)np^{1/2}(c_{i+1}-c_{i}).$
(22)

###### Proof.

To see this, we write $X_{i}=\sum_{v\in
V_{n}}\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)$. With this
we can express:

$\displaystyle X_{i}-X_{i+1}=\sum_{v\in
V_{n}}\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\sum_{v\in
V_{n}}\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right).$

Thus,

$\mathbb{E}\left[X_{i}-X_{i+1}|n^{*},\boldsymbol{c}^{*}\right]=\mathbb{E}\left[\sum_{v\in
V_{n}}\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\sum_{v\in
V_{n}}\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n^{*},\boldsymbol{c}^{*}\right].$

Using the linearity of the conditional expectation, it is sufficient to show
that

$\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n^{*},\boldsymbol{c}^{*}\right]=\Omega(1)p^{1/2}(c_{i}-c_{i+1}).$

We write

$\displaystyle\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n^{*},\boldsymbol{c}^{*}\right]=$
(23) $\displaystyle\hskip
28.45274pt\mathbb{E}\left[\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n(v)\right]|n^{*},\boldsymbol{c}^{*}\right]$
$\displaystyle\geq$
$\displaystyle\mathbb{E}\left[\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n(v)\right]|n^{*},\boldsymbol{c}^{*}\right]$
$\displaystyle\hskip
42.67912pt-\mathbb{E}\left[1-\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)|n^{*},\boldsymbol{c}^{*}\right]$
$\displaystyle\stackrel{{\scriptstyle\eqref{eq:Nv_prob}}}{{=}}$
$\displaystyle\mathbb{E}\left[\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n(v)\right]|n^{*},\boldsymbol{c}^{*}\right]-o(1/n),$

since $n^{*}(v)$ is independent of $\boldsymbol{c}^{*}$ and therefore
$\mathbb{E}\left[1-\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)|n^{*},\boldsymbol{c}^{*}\right]=\mathbb{E}\left[1-\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)|n^{*}\right]$.
Now, by(21) we deduce that

$\mathbb{E}\left[\mathbf{1}\left(\widehat{\mathcal{N}_{v}}\right)\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n(v)\right]|n^{*},\boldsymbol{c}^{*}\right]=\Omega(1)\cdot
p^{1/2}(c_{i}-c_{i+1}).$

Thus, (23) yields

$\mathbb{E}\left[\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbf{1}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i+1)}\right)|n^{*},\boldsymbol{c}^{*}\right]=\Omega(1)\cdot
p^{1/2}(c_{i}-c_{i+1})$

and (22) follows. ∎

We will show that for any $\gamma>0$, with probability $1-o(1)$, for
$i=1,\ldots,k_{0}-1$

$X_{i}-X_{i+1}\geq\Omega(1)np^{1/2}(c_{i+1}-c_{i})-\gamma np^{1/2}.$ (24)

We will show that

$\mathbb{P}\left(|X_{i}-\mathbb{E}\left[X_{i}\right]|>\gamma np^{1/2}\mid
n^{*},\boldsymbol{c}^{*}\right)=o(1),$ (25)

We will use a second moment argument - Chebyschev’s inequality yields

$\mathbb{P}\left(|X_{i}-\mathbb{E}\left[X_{i}\right]|>\gamma np^{1/2}\mid
n^{*},\boldsymbol{c}^{*}\right)\leq\frac{1}{\gamma^{2}}\cdot\frac{\mathrm{Var}(X_{i}\mid
n^{*},\boldsymbol{c}^{*})}{n^{2}p}.$

We will bound $\mathrm{Var}(X_{i}\mid n^{*},\boldsymbol{c}^{*})$ and, in
particular, we will show that if $n^{*}$ satisfies $\mathcal{P}_{0}$ and
$\boldsymbol{c}^{*}$ satisfies $\mathcal{E}_{\delta,n}$, then

$\mathrm{Var}(X_{i}\mid n^{*},\boldsymbol{c}^{*})=O\left(n^{3/2}\right).$ (26)

This implies that on $\mathcal{P}_{0}$ and $\mathcal{E}_{\delta,n}$

$\mathbb{P}\left(|X_{i}-\mathbb{E}\left[X_{i}\right]|>\gamma np^{1/2}\mid
n^{*},\boldsymbol{c}^{*}\right)=O\left(\frac{1}{n^{1/2}p}\right)=o(1).$

Hence, conditional on $n^{*},\boldsymbol{c}^{*}$ being such that
$\mathcal{P}_{0}$ and $\mathcal{E}_{\delta,n}$ occur, a.a.s.

$|X_{i}-\mathbb{E}\left[X_{i}\right]|<\gamma np^{1/2}$

and thus (25) holds.

###### Proof of (26).

To keep the presentation simple, we will drop the conditioning from our
notation. As it will be obvious from in our subsequent calculations, we work
with a given value of $n^{*}$ that satisfies $\mathcal{P}_{0}$ and a given
realisation of $\\{S_{0}^{-1}(1),\ldots,S_{0}^{-1}(k_{0})\\}$ such that
$\mathcal{E}_{\delta,n}$ is satisfied. Recall that for $i\in\mathcal{M}_{0}$
we let $\mathcal{S}\mathcal{S}_{1}^{(i)}$ denote the subset of vertices $v\in
V_{n}$ such that $S_{1}(v)=i$ in a _strong sense_ , that is,
$n_{0}(v;i)>n_{0}(v;j)$ for any $j\in\mathcal{M}_{0}$ with $j\not=i$. By the
linearity of the expected value:

$\mathbb{E}\left[X_{i}\right]=\sum_{v\in
V_{n}}\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right),$

and

$\mathrm{Var}(X_{i})\leq\sum_{v\neq
v^{\prime}}\left(\mathbb{P}\left(v,v^{\prime}\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)\mathbb{P}\left(v^{\prime}\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)\right)+\mathbb{E}\left[X_{i}\right].$

We will show that uniformly over all distinct $v,v^{\prime}\in V_{n}$ we have

$\mathbb{P}\left(v,v^{\prime}\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)-\mathbb{P}\left(v\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)\mathbb{P}\left(v^{\prime}\in\mathcal{S}\mathcal{S}_{1}^{(i)}\right)=O\left(\frac{1}{n^{1/2}}\right).$
(27)

Using the trivial bound that $\mathbb{E}\left[X_{i}\right]\leq n$ we obtain:

$\mathrm{Var}(X_{i})=O\left(\frac{n^{2}}{n^{1/2}}+n\right)=O\left(n^{3/2}\right).$

∎

For any $v\in V_{n}$ let $J_{v}$ denote the indicator random variable that is
equal to 1 precisely when $v\in\mathcal{S}\mathcal{S}_{1}^{(i)}$. We will
bound

$d(v,v^{\prime}):=\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\right]-\mathbb{E}\left[J_{v}\right]\cdot\mathbb{E}\left[J_{v^{\prime}}\right].$

Recall that $S^{*}=\cup_{j\in\mathcal{M}_{0}}S_{0}^{-1}(j)$. Firstly, let us
observe that if $v,v^{\prime}\not\in S^{*}$, then the random variables $J_{v}$
and $J_{v^{\prime}}$ are independent. In other words, if $v,v^{\prime}\not\in
S^{*}$, then $d(v,v^{\prime})=0$. Thus, it suffices to bound the sum

$\sum_{(v,v^{\prime}):v\not=v^{\prime},\ v^{\prime}\in S^{*}}d(v,v^{\prime}).$
(28)

(This sum is taken over ordered pairs.) Let us fix such a pair
$(v,v^{\prime})$ with $v\in V_{n}$ but $v^{\prime}\in S^{*}$ and, moreover,
$v\not=v^{\prime}$. We set $n_{v,v^{\prime}}^{*}=n^{*}-1_{v\in
S^{*}}-1_{v^{\prime}\in S^{*}}=n^{*}-1_{v\in S^{*}}-1$. Recall that in Section
1.5 we set $n^{*}_{v}=n^{*}-1_{v\in S^{*}}$; thus,
$n^{*}_{v,v^{\prime}}=n^{*}_{v}-1$.

We define $\hat{n}^{*}_{v,v^{\prime}}(v)=|(N_{G}(v)\cap
S^{*})\setminus\\{v,v^{\prime}\\}|$; hence
$\hat{n}^{*}_{v,v^{\prime}}(v)\sim\mathrm{Bin}(n_{v,v^{\prime}}^{*},p)$. We
apply the law of total probability conditioning on whether or not $v\sim
v^{\prime}$ as well as on the values of $\hat{n}^{*}_{v,v^{\prime}}(v)$ and
$\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})$:

$\displaystyle\mathbb{E}\left[J_{v}\cdot J_{v^{\prime}}\right]=$
$\displaystyle\hskip
28.45274ptp\cdot\mathbb{E}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\mid
v\sim v^{\prime}\right]$ $\displaystyle\hskip
42.67912pt+(1-p)\cdot\mathbb{E}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\mid
v\not\sim v^{\prime}\right].$ (29)

We will start with the first summand on the right-hand side. Recall that we
are conditioning on the initial configuration
$\mathcal{S}_{\mathcal{M}_{0}}=\left\\{S^{-1}_{0}(1),\ldots,S^{-1}_{0}(k_{0})\right\\}$
being such that $n_{j}:=|S^{-1}_{0}(j)|=n^{*}/k_{0}+c_{j}\sqrt{n^{*}}$, for
$j\in\mathcal{M}_{0}$, where $\delta<|c_{j}|<1/\delta$.

Let us abbreviate
$\mathbb{E}_{\sim}\left[\cdot\right]=\mathbb{E}\left[\cdot\mid v\sim
v^{\prime}\right]$. Using these abbreviations, we can write explicitly

$\displaystyle\mathbb{E}_{\sim}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\right]=$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{\hat{k^{\prime}}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right).$

Note that conditional on $v\sim v^{\prime}$ and on
$\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}$,
the random variables $J_{v}$ and $J_{v^{\prime}}$ are independent.
Furthermore, $J_{v}$ depends only on the realisation of $N_{G}(v)$ inside
$S^{*}$.

So each summand in the above double sum can be written as:

$\displaystyle\mathbb{E}_{\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right)=$
$\displaystyle\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{E}_{\sim}\left[J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\times$
$\displaystyle\hskip
28.45274pt\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right)$
$\displaystyle=\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{E}_{\sim}\left[J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right).$

Therefore, the double sum itself can be factorised as follows:

$\displaystyle\mathbb{E}_{\sim}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\right]=$
$\displaystyle=$
$\displaystyle\left(\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)\right)\times$
$\displaystyle\hskip
56.9055pt\left(\sum_{\hat{k}^{\prime}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\sim}\left[J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right)\right).$

Let us fix $\hat{k}\in\\{0,\ldots,n^{*}_{v,v^{\prime}}\\}$ and define

$\hat{\mathcal{K}}^{(i)}_{\hat{k}}=\\{(\hat{k}_{1},\ldots,\hat{k}_{k_{0}})\in\mathbb{N}_{0}^{k_{0}}\
:\ \sum_{j=1}^{k_{0}}\hat{k}_{j}=\hat{k},\ \hat{k}_{i}>\hat{k}_{j},\mbox{for
all $j\not=i$}\\}.$

Using this, with
$\hat{n}_{0}(v;j)=|N_{S_{0}^{-1}(j)\setminus\\{v^{\prime}\\}}(v)|$, we
express:

$\displaystyle\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]=\sum_{(\hat{k}_{0},\ldots,\hat{k}_{k_{0}})\in\hat{\mathcal{K}}_{\hat{k}}^{(i)}}\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right).$ (32)

Now, set $k_{j}=\hat{k}_{j}+1_{S_{0}(v^{\prime})=j}$, for
$j\in\mathcal{M}_{0}$. We compare
$\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)$ with
$\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right)$. Let
$\mathcal{K}_{\hat{k}}^{(i)}=\\{(k_{1},\ldots,k_{k_{0}})\in\mathbb{N}_{0}^{k_{0}}\
:\ \sum_{j\in\mathcal{M}_{0}}k_{j}=\hat{k}+1,\ k_{i}>k_{j}\ \mbox{for all
$j\not=i$}\\}$.

######  Claim 1.17.

For any $\hat{k}\in\\{0,\ldots,n^{*}_{v,v^{\prime}}\\}$ and all
$(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}_{\hat{k}}^{(i)}$ the following holds:

$\displaystyle\frac{\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)}{\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right)}=$
$\displaystyle\frac{\prod_{j\in\mathcal{M}_{0}}\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}-1_{s(v^{\prime})=j}}}{\binom{n^{*}_{v,v^{\prime}}}{\hat{k}}}\cdot\left(\frac{\prod_{i\in\mathcal{M}_{0}}\binom{n_{j}-1_{s(v)=j}}{k_{j}}}{\binom{n^{*}_{v}}{\hat{k}+1}}\right)^{-1}$
$\displaystyle=$
$\displaystyle\frac{n^{*}-1_{s(v)\in\mathcal{M}_{0}}}{\hat{k}+1}\cdot\frac{k_{s(v^{\prime})}}{n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}.$

###### Proof.

Note that if $s(v^{\prime})=j$

$\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}-1_{s(v^{\prime})=j}}\cdot\binom{n_{j}-1_{s(v)=j}}{k_{j}}^{-1}=\frac{k_{j}}{n_{j}-1_{s(v)=j}}$

but otherwise

$\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}-1_{s(v^{\prime})=j}}\cdot\binom{n_{j}-1_{s(v)=j}}{k_{j}}^{-1}=1.$

Similarly, since $v^{\prime}\in S^{*}$

$\binom{n^{*}_{v}}{\hat{k}+1}\cdot\binom{n_{v,v^{\prime}}^{*}}{\hat{k}}^{-1}=\frac{n^{*}_{v}}{\hat{k}+1}.$

So the claim follows as $n_{v}^{*}=n^{*}-1_{s(v)\in\mathcal{M}_{0}}$. ∎

The above claim implies that

$\displaystyle\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)=$
$\displaystyle\hskip
2.84544pt\frac{n^{*}_{v}}{\hat{k}+1}\cdot\frac{k_{s(v^{\prime})}}{n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}\cdot\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right).$

Now, let us relate
$\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)$ with
$\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right)$:

$\displaystyle\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)$
$\displaystyle=$
$\displaystyle\binom{n^{*}_{v,v^{\prime}}}{\hat{k}}p^{\hat{k}}(1-p)^{n^{*}_{v,v^{\prime}}-\hat{k}}=\binom{n^{*}_{v}-1}{\hat{k}}p^{\hat{k}}(1-p)^{n^{*}_{v}-1-\hat{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{p}\cdot\frac{\hat{k}+1}{n^{*}_{v}}\cdot\binom{n^{*}_{v}}{\hat{k}+1}p^{\hat{k}+1}.(1-p)^{n^{*}_{v}-(\hat{k}+1)}$
$\displaystyle=$
$\displaystyle\frac{1}{p}\cdot\frac{\hat{k}+1}{n^{*}_{v}}\cdot\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right).$

With these we can write

$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)=$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right)\times$
$\displaystyle\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{k_{s(v^{\prime})}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\cdot\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right).$

We express
$k_{s(v^{\prime})}=(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p+\delta_{s(v^{\prime})}$.
Using this, we get:

$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)=$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right)\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right)$
$\displaystyle+\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right)\times$
$\displaystyle\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{\delta_{s(v^{\prime})}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right).$

The first term is precisely equal to $\mathbb{E}\left[J_{v}\right],$ while,
for the second term, we combine:

$\displaystyle\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}+1\right)\cdot\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}+1\right)=$
$\displaystyle\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\right).\hskip 170.71652pt$

Note that the random variables $n_{0}(v;j)$ for $j\in\mathcal{M}_{0}$ form an
independent family and are all binomially distributed. Let
$\mathcal{S}_{\hat{k}+1}=\\{(k_{1},\ldots,k_{k_{0}}):\sum_{j=1}^{k_{0}}k_{j}=\hat{k}+1,0\leq
k_{j}\leq n^{*}_{v}\\}$. We bound

$\displaystyle\left|\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{\delta_{s(v^{\prime})}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\right)\right|\leq$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\right)$
$\displaystyle\leq\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{S}_{\hat{k}+1}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\right)$
$\displaystyle\leq\sum_{\hat{k}=0}^{n^{*}_{v}}\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{S}_{\hat{k}+1}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\right)$
$\displaystyle\leq\sum_{k_{1}=0}^{n_{1}}\cdots\sum_{k_{k_{0}}=0}^{n_{k_{0}}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\prod_{j=1}^{k_{0}}\mathbb{P}\left(n_{0}(v;j)=k_{j}\right)$
$\displaystyle=\sum_{k_{s(v^{\prime})}=0}^{n_{s(v^{\prime})}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})p}\mathbb{P}\left(n_{0}(v;s(v^{\prime}))=k_{s(v^{\prime})}\right)\stackrel{{\scriptstyle
n_{s(v^{\prime})}=n^{*}p_{s(v^{\prime})}}}{{=}}O\left(\frac{1}{\sqrt{np}}\right).$

Therefore,

$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)\leq\mathbb{E}_{\sim}\left[J_{v}\right]+O\left(\frac{1}{\sqrt{np}}\right).$

Using this upper bound in (LABEL:eq:factorised), we get

$\mathbb{E}_{\sim}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\right]\leq\mathbb{E}\left[J_{v}\right]\cdot\mathbb{E}\left[J_{v^{\prime}}\right]+O\left(\frac{1}{\sqrt{np}}\right).$
(33)

Now, let us abbreviate
$\mathbb{E}_{\not\sim}\left[\cdot\right]=\mathbb{E}\left[\cdot\mid v\not\sim
v^{\prime}\right]$. Using the law of total probability and conditioning on the
values of $\hat{n}^{*}_{v,v^{\prime}}(v)$ and
$\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})$, we get

$\displaystyle\mathbb{E}_{\not\sim}\left[\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v),\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\right]=$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\sum_{\hat{k^{\prime}}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{E}_{\not\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]\cdot\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right).$

We will bound $\mathbb{E}_{\not\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]$.
Note that

$\begin{split}&\mathbb{E}_{\not\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k},\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right]=\\\
&\hskip
56.9055pt\mathbb{E}_{\not\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]\cdot\mathbb{E}_{\not\sim}\left[J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})=\hat{k}^{\prime}\right].\end{split}$

We will deal with
$\mathbb{E}_{\not\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]$,
as the analogous calculation can be carried out for $v^{\prime}$. With
$\mathcal{K}^{(i)}_{\hat{k}}=\\{(k_{1},\ldots,k_{k_{0}})\ :\
\sum_{j=1}^{k_{0}}k_{j}=\hat{k},\ k_{i}>k_{j}\ \mbox{for all $j\not=i$}\\}$ we
write

$\mathbb{E}_{\not\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right]=\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\mathbb{P}\left(\hat{n}_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right).$ (34)

We show the analogue of Claim 1.17. Recall that we are assuming that
$s(v^{\prime})\in\mathcal{M}_{0}$.

######  Claim 1.18.

For all $(k_{1},\ldots,k_{0})\in\mathcal{K}^{(i)}_{\hat{k}}$ the following
holds:

$\displaystyle\frac{\mathbb{P}\left(\hat{n}_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)}{\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right)}=$
$\displaystyle\frac{\prod_{j=1}^{k_{0}}\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}}}{\binom{n^{*}_{v,v^{\prime}}}{\hat{k}}}\cdot\left(\frac{\prod_{j=1}^{k_{0}}\binom{n_{j}-1_{s(v)=j}}{k_{j}}}{\binom{n^{*}_{v}}{\hat{k}}}\right)^{-1}$
$\displaystyle=$
$\displaystyle\frac{n^{*}_{v}}{n^{*}_{v}-\hat{k}}\cdot\frac{n_{s(v^{\prime})}-k_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}{n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}.$

###### Proof.

We follow a similar calculation to that in Claim 1.17. We consider two cases.
Firstly suppose $s(v)=s(v^{\prime})=j$ for some $j\in\mathcal{M}_{0}$. Then we
have:

$\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}}\cdot\binom{n_{j}-1_{s(v)=j}}{k_{j}}^{-1}=\frac{n_{j}-k_{j}-1}{n_{j}-1},$

whereas for any $j^{\prime}\neq j$ we have that:

$\binom{n_{j^{\prime}}-1_{s(v)=j^{\prime}}-1_{s(v^{\prime})=j^{\prime}}}{k_{j^{\prime}}}\cdot\binom{n_{j^{\prime}}-1_{s(v)=j^{\prime}}}{k_{j^{\prime}}}^{-1}=1.$

In the case where $s(v)=j$ but $s(v^{\prime})=j^{\prime}$ with $j\neq
j^{\prime}$, the following hold:

$\binom{n_{j}-1_{s(v)=j}-1_{s(v^{\prime})=j}}{k_{j}}\cdot\binom{n_{j}-1_{s(v)=j}}{k_{j}}^{-1}=1,$

but

$\binom{n_{j^{\prime}}-1_{s(v)=j^{\prime}}-1_{s(v^{\prime})=j^{\prime}}}{k_{j^{\prime}}}\cdot\binom{n_{j^{\prime}}-1_{s(v)=j^{\prime}}}{k_{j^{\prime}}}^{-1}=\binom{n_{j^{\prime}}-1}{k_{j^{\prime}}}\cdot\binom{n_{j^{\prime}}}{k_{j^{\prime}}}^{-1}=\frac{n_{j^{\prime}}-k_{j^{\prime}}}{n_{j^{\prime}}}.$

For any $j^{\prime\prime}\not=j^{\prime},j$, we have

$\binom{n_{j^{\prime\prime}}-1_{s(v)=j^{\prime\prime}}-1_{s(v^{\prime})=j^{\prime\prime}}}{k_{j^{\prime\prime}}}\cdot\binom{n_{j^{\prime\prime}}-1_{s(v)=j^{\prime\prime}}}{k_{j^{\prime\prime}}}^{-1}=1.$

Furthermore, since $s(v^{\prime})\in\mathcal{M}_{0}$, then
$n^{*}_{v,v^{\prime}}=n^{*}_{v}-1$, whereby

$\binom{n^{*}_{v}}{\hat{k}}\cdot\binom{n^{*}_{v,v^{\prime}}}{\hat{k}}^{-1}=\frac{n^{*}_{v}}{n^{*}_{v}-\hat{k}}.$

Thus, the claim follows. ∎

Therefore,

$\displaystyle\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)=$
$\displaystyle\frac{n^{*}_{v}}{n^{*}_{v}-\hat{k}}\cdot\frac{n_{s(v^{\prime})}-k_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}{n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}\cdot\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right).$

Furthermore, (since $v^{\prime}\in\mathcal{M}_{0}$, whereby
$n^{*}_{v,v^{\prime}}=n^{*}_{v}-1$)

$\displaystyle\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)$
$\displaystyle=$
$\displaystyle\binom{n^{*}_{v,v^{\prime}}}{\hat{k}}p^{\hat{k}}(1-p)^{n^{*}_{v,v^{\prime}}-\hat{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{1-p}\cdot\frac{n^{*}_{v}-\hat{k}-1}{n^{*}_{v}}\cdot\binom{n^{*}_{v}}{\hat{k}}p^{\hat{k}}(1-p)^{n^{*}_{v}-\hat{k}}$
$\displaystyle=$
$\displaystyle\frac{1}{1-p}\cdot\frac{n^{*}_{v}-\hat{k}}{n^{*}_{v}}\cdot\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}\right).$

Therefore,

$\displaystyle\mathbb{P}\left(\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)\mathbb{P}\left(\hat{n}_{0}(v;j)=\hat{k}_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}_{v,v^{\prime}}(v)=\hat{k}\right)=$
$\displaystyle=\frac{n_{s(v^{\prime})}-k_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})(1-p)}\cdot\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid
n(v)=\hat{k}\right)\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}\right).$

Now, we express
$k_{s(v^{\prime})}=p(n_{s(v^{\prime})}-1_{s(v)=s(v^{\prime})})+\delta_{s(v^{\prime})}$,
where $n_{s(v^{\prime})}=n^{*}p_{s(v^{\prime})}$. Using this, we get

$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}\right)\times$
$\displaystyle\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{n_{s(v^{\prime})}-k_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})(1-p)}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right)=$
$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}\right)\times$
$\displaystyle\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\frac{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})(1-p)+\delta_{s(v^{\prime})}}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})(1-p)}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right).$

As in the above calculation, the first summand is,

$\displaystyle\sum_{\hat{k}=0}^{n^{*}_{v,v^{\prime}}}\mathbb{P}\left(\hat{n}^{*}(v)=\hat{k}\right)\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{K}^{(i)}_{\hat{k}}}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right)\leq\mathbb{E}\left[J_{v}\right].$

As above, the second summand is bounded as

$\sum_{(k_{1},\ldots,k_{k_{0}})\in\mathcal{S}_{\hat{k}}}\frac{|\delta_{s(v^{\prime})}|}{(n_{s(v^{\prime})}-1_{s(v^{\prime})=s(v)})(1-p)}\mathbb{P}\left(n_{0}(v;j)=k_{j},\
j\in\mathcal{M}_{0}\mid\hat{n}^{*}(v)=\hat{k}\right)=O\left(\sqrt{\frac{p}{n}}\right).$

These two imply that

$\displaystyle\mathbb{E}\left[\mathbb{E}_{\not\sim}\left[J_{v}\cdot
J_{v^{\prime}}\mid\hat{n}(v),\hat{n}(v^{\prime})\right]\right]$
$\displaystyle=$
$\displaystyle\mathbb{E}\left[\mathbb{E}_{\not\sim}\left[J_{v}\mid\hat{n}^{*}_{v,v^{\prime}}(v)\right]\right]\cdot\mathbb{E}\left[\mathbb{E}_{\not\sim}\left[J_{v^{\prime}}\mid\hat{n}^{*}_{v,v^{\prime}}(v^{\prime})\right]\right]$
(36) $\displaystyle\leq$
$\displaystyle\mathbb{E}\left[J_{v}\right]\cdot\mathbb{E}\left[J_{v^{\prime}}\right]+O\left(\sqrt{\frac{p}{n}}\right).$

Using the bounds of (33) and (36) into (29) we deduce that

$\mathbb{E}\left[J_{v}\cdot
J_{v^{\prime}}\right]\leq\mathbb{E}\left[J_{v}\right]\cdot\mathbb{E}\left[J_{v^{\prime}}\right]+O\left(\frac{1}{n^{1/2}}\right).$

###  1.8 After the first round

In the previous subsection, we used a second moment argument to show that
a.a.s. after the execution of the first round the system ends up with sets
$S_{1}^{(1)},\ldots,S_{1}^{(k_{0})}$ where $S_{1}^{(i)}$ consists of all
vertices in $V_{n}$ that have adopted state $i$ in a strong sense during the
execution of round 1, as well as with a subset $R_{1}\subset V_{n}$ with
$|R_{1}|=O(\log^{2}n\sqrt{n/p})$ that consists of all those vertices that
faced a tie during round 1 (cf. Claim 1.3). Moreover, by (24), if
$\boldsymbol{c}^{*}$ is such that $\mathcal{E}_{\delta,n}$ is realised and
$c_{1}>\cdots>c_{k_{0}}$, then $|S_{1}^{(i)}|=b_{i}(n)$, where
$b_{i+1}(n)-b_{i}(n)>\Omega(1)(c_{i+1}-c_{i})np^{1/2}$, for
$i=1,\ldots,k_{0}-1$. Moreover, as $\mathcal{E}_{\delta,n}$ is realised,
$c_{i}-c_{i+1}>\delta$. We prove the following.

######  Lemma 1.19.

Let $\omega=\omega(n):\mathbb{N}\to\mathbb{R}$ be such that
$\omega(n)\to\infty$ as $n\to\infty$ and $n^{1/3}p\geq\omega$. Suppose that
for $i=1,\ldots,k_{0}$, the functions $b_{i}:\mathbb{N}\to\mathbb{R}$ satisfy
$b_{i+1}(n)-b_{i}(n)>\Omega(1)np^{1/2}$, for $i=1,\ldots,k_{0}-1$. For any
$\varepsilon>0$ a.a.s. the following holds: for any partition
$(P_{1},\ldots,P_{k_{0}},R)$ of $V_{n}$ with $|P_{i}|=b_{i}(n)$ and
$|R|=O(\log^{2}n\sqrt{n/p})$, all but fewer than $np/\omega^{1/2}$, vertices
$v\in V_{n}$ have

$d_{P_{i+1}}(v)-d_{P_{i}}(v)>\frac{\delta}{4}np^{1/2},$

for all $i=1,\ldots,k_{0}-1$.

###### Proof.

Let $S\subset V_{n}$ be such that $|S|=np/\sqrt{\omega}$ and let
$(P_{1},\ldots,P_{k_{0}},R)$ be a partition of $V_{n}$ as specified above.
Firstly, we apply the Chernoff bound to deduce the concentration of the number
of edges within $S$; we denote it by $e(S)$. We have

$\mathbb{P}\left(\left|e(S)-\binom{|S|}{2}p\right|\geq\frac{p|S|^{2}}{\sqrt{\omega}}\right)\leq\exp\left(-\Omega\left(\frac{p|S|^{2}}{\omega}\right)\right).$

As $p\geq\omega n^{-1/3}$, we deduce that $p|S|^{2}/\omega=\Omega(n\omega)$.
Hence with probability at least $1-2^{-\Omega(\omega\cdot n)}$, we have that
$e(S)$ is suitably concentrated about its expected value. Thereby, on this
event, the average degree of $G(n,p)[S]$ is

$\frac{2e(S)}{|S|}\leq p|S|(1+o(1)).$

So on the above event and for $n$ sufficiently large, there exists a subset
$S^{\prime}\subset S$ with $|S^{\prime}|=|S|/2$ such that every vertex $v\in
S^{\prime}$ has $d_{S}(v)\leq 3|S|p$.

Let us set $\alpha(n)=np^{1/2}$ and consider $P_{i}$. We will first bound the
probability that a given $v\in S^{\prime}$ has

$\left|d_{P_{i}\setminus S}(v)-|P_{i}\setminus
S|p\right|>\frac{\varepsilon}{2}\alpha(n)p,$

where $\varepsilon>0$ is some constant. To this end we can apply the Chernoff
bound since $d_{P_{i}\setminus S}(v)\sim\mathrm{Bin}(|P_{i}\setminus S|,p)$.
Inequality (1) yields:

$\mathbb{P}\left(\left|d_{P_{i}\setminus S}(v)-|P_{i}\setminus
S|p\right|>\frac{\varepsilon}{2}\alpha(n)p\right)\stackrel{{\scriptstyle|P_{i}\setminus
S|\leq
n}}{{=}}\exp\left(-\Omega\left(\frac{\alpha(n)^{2}p^{2}}{np}\right)\right).$

Note that by the choice of $\alpha(n)$, the quantity in the exponent on the
right-hand side is

$\frac{\alpha(n)^{2}p^{2}}{np}=\frac{n^{2}p^{3}}{np}=np^{2}.$

Note that $np^{2}\to\infty$ as $n\to\infty$, since we have assumed that $p\gg
n^{-1/3}$.

Now, the union bound implies that for any $v\in S^{\prime}$ and any fixed
$\varepsilon>0$ with probability $1-\exp(-\Omega(np^{2}))$, we have for $1\leq
i<k_{0}$

$\left|d_{P_{i}\setminus S}(v)-|P_{i}\setminus
S|p\right|\leq\frac{\varepsilon}{2}\alpha(n)p.$

On this event,

$\displaystyle d_{P_{i+1}\setminus S}(v)-d_{P_{i}\setminus S}(v)$
$\displaystyle\geq$ $\displaystyle\left(|P_{i+1}\setminus S|-|P_{i}\setminus
S|\right)p-\varepsilon\alpha(n)p$ $\displaystyle\geq$
$\displaystyle\left(b_{i+1}(n)-b_{i}(n)-2|S|\right)p-\varepsilon\alpha(n)p.$

Now, we write

$\displaystyle d_{P_{i+1}}(v)-d_{P_{i}}(v)$ $\displaystyle\geq$ $\displaystyle
d_{P_{i+1}\setminus S}(v)-d_{P_{i}\setminus S}(v)-d_{P_{i}\cap S}(v)$
$\displaystyle\geq$ $\displaystyle d_{P_{i+1}\setminus S}(v)-d_{P_{i}\setminus
S}(v)-d_{S}(v)$ $\displaystyle\geq$ $\displaystyle d_{P_{i+1}\setminus
S}(v)-d_{P_{i}\setminus S}(v)-3|S|p$ $\displaystyle\geq$
$\displaystyle\left(b_{i+1}(n)-b_{i}(n)-5|S|\right)p-\varepsilon\alpha(n)p.$

But for some $\delta>0$, we have $b_{i+1}(n)-b_{i}(n)\geq\delta np^{1/2}$, for
any $n$ sufficiently large, whereas $|S|=o(np)$. Therefore, the right-hand
side of the above is for $n$ sufficiently large

$\left(b_{i+1}(n)-b_{i}(n)-5|S|\right)p-\varepsilon\alpha(n)p>\frac{\delta}{2}np^{3/2}-\varepsilon
np^{3/2}>\frac{\delta}{4}np^{3/2},$

if $\varepsilon<\delta/4$. Thus, we have shown that if $\varepsilon<\delta/4$
and $n$ sufficiently large, then

$d_{P_{i+1}}(v)-d_{P_{i}}(v)>\frac{\delta}{4}np^{3/2}.$

Note that the family $\\{d_{P_{i}\setminus S}(v)\\}_{v\in
S^{\prime},i=1,\dots,k_{0}}$ consists of i.i.d. random variables which are
binomially distributed with parameters $|P_{i}\setminus S|,p$. The Chernoff
bound (1) together with the union bound implies that for any $v\in S^{\prime}$

$\mathbb{P}\left(\mbox{for some $1\leq i\leq k_{0}$}\ |d_{P_{i}\setminus
S}(v)-|P_{i}\setminus
S|p|>\frac{\varepsilon}{2}\alpha(n)p\right)=\exp\left(-\Omega\left(\frac{\alpha(n)^{2}p^{2}}{np}\right)\right).$

Since the family $\\{d_{P_{i}\setminus S}(v)\\}_{v\in
S^{\prime},i=1,\dots,k_{0}}$ is independent we then deduce that

$\mathbb{P}\left(\mbox{$\forall v\in S^{\prime}$ $\exists 1\leq i\leq
k_{0}$:}\ |d_{P_{i}\setminus S}(v)-|P_{i}\setminus
S|p|>\frac{\varepsilon}{2}\alpha(n)p\right)=\exp\left(-\Omega\left(\frac{|S^{\prime}|\alpha(n)^{2}p^{2}}{np}\right)\right).$

But since $|S^{\prime}|=|S|/2$ and $|S|=np/\sqrt{\omega}$ we have

$\frac{|S^{\prime}|\alpha(n)^{2}p^{2}}{np}=\Omega\left(\frac{\alpha^{2}(n)p^{2}}{\sqrt{\omega}}\right).$

As $\alpha(n)=np^{1/2}$, the numerator on the right hand side is

$\alpha(n)^{2}p^{2}=\Omega(n^{2}p^{3}).$

Hence as $p\geq\omega n^{-1/3}$ we have that
$\alpha^{2}(n)p^{2}/\sqrt{\omega}\geq n\omega^{5/2},$ thus this probability is
$o(e^{-n})$. As there are $2^{O(n)}$ choices for $S$ and the partition
$(P_{1},\ldots,P_{k_{0}},R)$, the union bound implies the lemma. ∎

We now apply Lemma 1.19 to deduce the evolution of the behaviour of all but at
most $np/\omega^{1/2}$ vertices from round 1 into round 2. In particular, as
$np^{1/2}\gg\log n\sqrt{n/p}$, the above lemma implies that all but at most
$np/\omega^{1/2}$ will adopt state 1 after round 2. Finally, a union bound
over all partitions of $V_{n}$ into two parts where one of the parts has size
at most $n/\omega^{1/2}$ and the Chernoff bound imply that conditional on the
above evolution of the process after the third round a.a.s. all vertices will
have adopted state 1. This concludes the proof of Theorem 1.1.

##  2 Conclusions and some further directions

In paper we generalised the results of [3, 4, 7] showing that majority
dynamics on the random graph $G(n,p)$ and $k>2$ states will reach unanimity
after at most 3 rounds, provided that $np\gg n^{2/3}$. As in the case of 2
states, the proof relies on a tight analysis of the configuration after the
first round.

We do not believe that the lower bound imposed on $p$ is tight. It is needed
in the proof of Lemma 1.19 for the union bound argument to work. It could be
possible to extend Theorem 1.1 to $p\gg n^{-1/2}$ or even lower densities as
in [4].

The “power-of-the-few” question becomes more intriguing in the context of more
than 2 states. If the initial configuration is random, then one of the states
dominates over each one of the other states by $\sqrt{n}$. What would happen
if we started the process from a configuration where two or more of the states
had exactly the same size? Could one extend the results of Tran and Vu [19]
and those of Sah and Sawhney [16] in this context?

## References

  * [1] N.K. Arenbaev, Asymptotic behavior of the multinomial distribution, _Teor. Veryatnost. i Primenen._ , 21(4) (1976), 826–831.
  * [2] I. Benjamini, S.-O. Chan, R. O’Donnell, O. Tamuz, and L.-Y. Tan.  Convergence, unanimity and disagreement in majority dynamics on unimodular graphs and random graphs.  Stochastic Processes and their Applications, 16 (2016), 2719–2733.
  * [3] R. Berkowitz and P. Devlin, Central limit theorem for majority dynamics: bribing three voters suffices, _Stochastic Processes and their Applications_ , 146 (2022), 187–206.
  * [4] D. Chakraborti, J.H. Kim, J. Lee and T. Tran, Majority dynamics on sparse random graphs, _Random Structures and Algorithms_ , 63 (2023),171–191.
  * [5] P. Clifford and A. Sudbury, A model for spatial conflict, _Biometrika_ , 60 (1973), 581–588.
  * [6] G. Ellison and D. Fudenberg, Rules of thumb for social learning, _Journal of Political Economy_ , 104 (1993), 612–643.
  * [7] N. Fountoulakis, M. Kang and T. Makai, Resolution of a conjecture on majority dynamics: rapid stabilisation in dense random graphs, _Random Structures and Algorithms_ , 57 (2020), 1134–1156.
  * [8] B. Gärtner and A. N. Zehmakan, Color war: cellular automata with majority-rule, In Proceeding of Language and Automata Theory and Applications (LATA 2017), volume 10168 of Lecture Notes in Computer Science. Springer, 2017.
  * [9] B. Gärtner and A. N. Zehmakan. Majority model on random regular graphs. In Proceedings of LATIN 2018: Theoretical Informatics, volume 10807 of Lecture Notes in Computer Science. Springer, 2018.
  * [10] E. Goles and J. Olivos.  Periodic behaviour of generalized threshold functions.  Discrete Mathematics, 30 (1980), 187–189.
  * [11] M. Granovetter, Threshold models of collective behavior, _Am. J. Sociol._ 83 (6) (1978), 1420–1443.
  * [12] S. Janson, T. Łuczak, and A. Ruciński, Random graphs, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley-Interscience, New York, 2000.
  * [13] W.S. McCulloch and W. Pitts, A logical calculus of the ideas immanent in nervous activity, _The Bulletin of Mathematical Biophysics_ , 5 (1943), 115–133.
  * [14] E. Mossel, J. Neeman, and O. Tamuz.  Majority dynamics and aggregation of information in social networks.  Autonomous Agents and Multi-Agent Systems, 28(3) (2014), 408–429.
  * [15] V. V. Petrov.  Sums of independent random variables.  Springer-Verlag, New York-Heidelberg, 1975.  Translated from the Russian by A. A. Brown, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 82.
  * [16] A. Sah and M. Sawhney, Majority dynamics: the power of one, arXiv210513301v1.
  * [17] R.J. Serfling, Probability inequalities for the sum of sampling without replacement, _Ann. Statist._ 2 (1974), 39–48.
  * [18] M. Siotani and Y. Fujikoshi, Asymptotic approximations for the distributions of multinomial goodness-of-fit statistics, _Hiroshima Math. J._ , 14(1) (1984), 115–124.
  * [19] L. Tran and V. Vu, Reaching a consensus on random networks: the power of few, In Proceedings of Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020), Article No. 20, pp. 20:1–20:15, 2020.
  * [20] B. Venkatesh and G. Sanjeev, Learning from neighbours, _Rev. Econ. Stud._ , 65 (3) (1998), 595-621.
  * [21] A. N. Zehmakan, Opinion forming in Erdős-Rényi random graph and expanders, In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018), Article No.168, pp. 1–14, 2018.