1. Introduction
An independent set of a graph
$ \mathcal{G} = (V,E)$
is a subset of vertices where no pair of vertices are connected to each other. Finding an independent set of maximal size is a notoriously difficult problem in general [Reference Frieze and McDiarmid15]. However, using a greedy procedure, we can construct a maximal (for the inclusion order) independent set by inspecting the vertices of the graph one by one in random order, adding the current vertex and blocking its neighbours if it is not connected to any previously added vertex. More precisely, the vertices are divided into three possible statuses: the undetermined vertices
$ \mathcal{U}_k$
, the active vertices
$ \mathcal{A}_k$
, and the blocked vertices
$ \mathcal{B}_k$
. We start with
$\mathcal{U}_0 = V$
and
$ \mathcal{A}_0 = \mathcal{B}_0 = \emptyset$
. At step
$k \geq 1$
, we choose an undetermined vertex
$v_k$
uniformly at random, change its status to active, and change the status of all its undetermined neighbours to blocked. We stop at
$ \tau = \min \{ k \geq 0, \ \mathcal{U}_k = \emptyset\}$
. Note that at each step k, no vertices of
$ \mathcal{A}_k$
are neighbours and
$ \mathcal{A}_{\tau}$
is a maximal independent set, which we call the (random) greedy independent set; see Figure 1.
Example of the greedy independent set obtained on a tree of size 30. The labels represent the order in which vertices are inspected in the construction of the greedy independent set. The green vertices are the active vertices and the red vertices are the blocked vertices.
Of course, the independent set obtained by the greedy algorithm is usually not maximum in the sense that it does not have the maximal possible size. In the case of trees, finding an independent set of maximal size is much simpler than in general. However, from a probabilistic or combinatorial point of view, the greedy independent set is still worth investigation even on (random) trees. Greedy independent sets on (random) graphs have been studied extensively, with a particular focus on the proportion of vertices of the graph in the greedy independent set called the greedy independence ratio or jamming constant. Recently, Krivelevich, Mészáros, Michaeli, and Shikhelman [Reference Krivelevich, Mészáros, Michaeli and Shikhelman18] used Aldous’s objective method [Reference Aldous and Steele4] to prove under mild assumptions that if a sequence of random finite graphs with a root vertex chosen uniformly at random converges locally, then the sequence of their greedy independence ratios also converges in probability.
Recall that a Cayley tree of size n is an unrooted and unordered tree over the n labelled vertices
$\{1, \ldots , n\}$
and we let
$ \mathcal{T}_n$
be a random Cayley tree sampled uniformly at random among the
$n^{n-2}$
Cayley trees of size n. We let
$ \mathcal{T}_n^{\bullet}$
denote the rooted tree obtained from
$ \mathcal{T}_n$
by distinguishing a vertex uniformly at random. Using the local limit of
$ \mathcal{T}_n^{ \bullet}$
given by Kesten’s infinite tree, Krivelevich, Mészáros, Michaeli, and Shikhelman [Reference Krivelevich, Mészáros, Michaeli and Shikhelman18, Section 6.3] proved the ‘intriguing fact’ that the asymptotic greedy independence ratio of uniform Cayley trees is
$1/2$
. Meir and Moon proved in [Reference Meir and Moon20] that the size of a maximum independent set of a uniform Cayley tree concentrates around
$ \rho n$
, where
$\rho \approx 0.5671$
is the unique solution of
$x {\mathrm{e}}^x = 1$
.
In this note we prove a much stronger – and perhaps surprising – statement concerning the size of the greedy independent set on a uniform Cayley tree showing that it has (almost) the same law as that of its complement! We let
$G_n$
denote the size of the greedy independent set
$ | \mathcal{A}_{\tau}|$
on a uniform Cayley tree
$ \mathcal{T}_n$
and let
$H_n$
be the number of vertices at even height in
$ \mathcal{T}_n^{ \bullet}$
. Our first observation is that
$G_n$
has the same law as
$H_n$
, which enables us to compute the exact law of
$G_n$
.
Theorem 1. The size
$G_n$
of the greedy independent set on
$ \mathcal{T}_n$
has the same law as the number
$H_n$
of vertices at even height in
$ \mathcal{T}_n^{ \bullet}.$
As a consequence, for
$1 \leq k \leq n-1$
,
\begin{equation} \mathbb{P} (G_n = k) =\mathbb{P}(H_n = k) = \binom{n}{k} \dfrac{k^{n-k} (n-k)^{k-1}}{n^{n-1}}.\end{equation}
The proof of Theorem 1 relies on the invariance of Cayley trees under rerooting at a uniform vertex. The exact computation of the law of
$H_n$
is a consequence of a result of [Reference Féray and Kortchemski14] on bi-type alternating Galton–Watson trees. This equality in distribution of
$G_n$
and
$H_n$
suggests that their common law is almost symmetric with respect to
$n/2$
. But
$H_n$
(as well as
$G_n$
) has a little drift caused by the root vertex of
$ \mathcal{T}_n^{ \bullet}$
which is always at even height. Indeed, it follows from Theorem 1 that
$G_n/n$
converges in probability to
$1/2$
(thus recovering [Reference Krivelevich, Mészáros, Michaeli and Shikhelman18, Section 6.3]) and we also have a local central limit theorem for
$ G_n$
: for all
$ A \geq 0$
,
\begin{equation} \mathbb{P} \biggl( G_n = \biggl\lfloor \dfrac{n}{2} + x \sqrt{n} \biggr\rfloor \biggr) \underset{n \to \infty}{\sim} \dfrac{1}{\sqrt{n}} \dfrac{1}{\sqrt{2 \pi (1/4)^2}} \exp \biggl(- \dfrac{x^2}{2 \cdot (1/4)^2}\biggr) \end{equation}
uniformly for
$ x \in [\!-A,A]$
. We also give a ‘Markovian’ construction of the greedy independent set which brings to light this symmetry of
$G_n$
.
Theorem 2. There exists a random variable
$ \mathcal{E}_n$
with values in
$\{ 0,1\}$
such that we have
\begin{equation*} G_n \stackrel{(d)}{=} (n- G_n) + \mathcal{E}_n.\end{equation*}
Moreover
$\mathbb{P} ( \mathcal{E}_n = 1 ) \to 1/4$
as n goes to
$\infty$
.
This symmetry between
$G_n$
and
$n-G_n$
is striking because the geometry of a greedy independent set and that of its complement are totally different (see Figure 1). The main idea for the proof of Theorem 2 is to consider the underlying tree as ‘unknown’ and to discover it as we build the greedy independent set. See [Reference Bermolen, Jonckheere and Moyal5], [Reference Brightwell, Janson and Luczak6], and [Reference Jonckheere and Sáenz17] for similar applications of this technique to other random graph models. In our case, we develop in Section 3 a new type of Markovian exploration of uniform Cayley trees, which is inspired by Pitman’s famous algorithm [Reference Pitman22] but is more flexible in the sense that we can choose which vertex to explore at each step of the procedure. By choosing the next vertex to explore as the next vertex inspected by the greedy algorithm, we connect these Markovian explorations to the construction of the greedy independent set. We expect these explorations to be applicable to a wider range of contexts; for example, we will shed new light on the Aldous–Broder algorithm [Reference Aldous1, Reference Broder7] and Pitman’s construction [Reference Pitman22] of
$ \mathcal{T}_n$
using particular cases of our Markovian explorations (see Section 3). Similar explorations are used in a forthcoming work [Reference Contat and Curien10] on the parking process on Cayley trees.
Independent sets of edges. Instead of an independent set of vertices, we could have considered an independent set of edges or a matching, i.e. a set of edges in which no pair of elements have a vertex in common. As for the vertices, we can construct a maximal independent set of edges greedily by inspecting the edges one by one in a uniform random order, keep it if our edge set stays independent, and stop once we have inspected all the edges. Letting
$M_n$
denote the number of edges kept after applying this algorithm on a uniform Cayley tree
$ \mathcal{T}_n$
of size n, our Markovian exploration allows us to show that
$M_n/n$
concentrates around
$3/8$
and to obtain a central limit theorem for
$M_n$
. We do not include th details here since this result has already been shown by Dyer, Frieze, and Pittel in [Reference Dyer, Frieze and Pittel12, Theorem 2] by other means.
But in the case of plane trees, i.e. on rooted and ordered unlabelled trees, the invariance under rerooting at a uniform edge plays the same role as the invariance under rerooting at a uniform vertex above, and enables us to compute the exact law of the size of the greedy independent set of edges. More precisely, we let
$ \widetilde{\mathcal{T}}_n$
be a uniform plane tree, i.e. rooted and ordered (unlabelled) tree of size n (i.e. with n vertices), and let
$ \widetilde{M}_n$
be the size of the greedy independent set of edges obtained on
$ \widetilde{\mathcal{T}}_n$
.
Theorem 3. The size
$ \widetilde{M}_n$
of the greedy independent set of edges on
$ \widetilde{ \mathcal{T}}_n$
has law given by
\begin{equation*} \mathbb{P} ( \widetilde{M}_n = k) = \dfrac{n}{k} \dfrac{\binom{n+k-2}{2k-1}\binom{n-k-1}{k-1}}{\binom{2n-2}{n-1}} = \dfrac{n!(n-1)!(n+k-2)!}{k!(2k-1)!(n-2k)!(2n-2)!},\end{equation*}
for
$1 \leq k \leq \lfloor n/2 \rfloor$
. As a consequence, for all
$ A \geq 0$
,
\begin{equation*} \mathbb{P} \biggl( \widetilde{M}_n = \biggl\lfloor \dfrac{n}{3} + x \sqrt{n} \biggr\rfloor \biggr) \underset{n \to + \infty}{\sim} \dfrac{1}{\sqrt{n}} \dfrac{1}{\sqrt{2 \pi (2/9)^2}} \exp \biggl(- \dfrac{x^2}{2 \cdot (2/9)^2}\biggr) \end{equation*}
uniformly for
$ x \in [\!-A,A]$
.
We prove this theorem at the end of Section 2.
2. Greedy independent sets and bicoloured trees
In this section we prove Theorems 1 and 3 by relating the construction of greedy independent sets to bicoloured Galton–Watson trees with alternating colours. Our main tool will be invariance of the underlying random tree with respect to rerooting at a uniform vertex or edge.
2.1. Independent set of vertices for Cayley trees
The following lemma is well known (see e.g. [Reference Le Gall19, end of Section 1.5]) and implies in particular the invariance of a uniform Cayley tree under independent uniform relabelling of the vertices.
Lemma 1. If
$ \mathscr{T}_n$
is a Galton–Watson plane tree with
$ \mathrm{Poisson}(1)$
offspring distribution conditioned to have n vertices, then the tree
$ \mathcal{T}_n^{\bullet}$
obtained by labelling its vertices by
$ \{ 1 , \ldots , n\}$
uniformly at random, forgetting the planar ordering but keeping the root vertex, is a uniform rooted Cayley tree.
In particular, if
$ \sigma_n$
is a uniform permutation of
$ \{ 1, 2, \ldots , n\}$
independent of
$ \mathcal{T}_n$
, then the tree
$\mathcal{T}^{\sigma_n}_n$
obtained by relabelling the vertex i of
$ \mathcal{T}_n$
by
$ \sigma_n (i)$
for
$ 1 \leq i \leq n$
is still a uniform Cayley tree. In the rest of this section we shall always consider
$ \mathcal{T}_n$
and
$ \mathcal{T}_n^{\bullet}$
to be built from
$ \mathscr{T}_n$
as above.
Remark 1. By invariance under rerooting, the tree
$ \mathcal{T}_n^{ \bullet}$
has the same law, seen as an unlabelled rooted tree, as the tree
$ \mathcal{T}_n$
rooted at any deterministic vertex
$ i \in \{ 1, \ldots, n \}$
. In the next section we shall always suppose that our Cayley trees are rooted at the vertex with label n, but in this section it is better to think of them as rooted on a uniform vertex.
We break down the proof of Theorem 1 into two parts. We first prove that
$G_n$
has the same law as
$ H_n$
, and then compute explicitly the law of
$H_n$
using bi-type alternating Galton–Watson trees.
Proof of the first half of Theorem 1. The proof of this lemma relies on Lemma 1. We will show that
$G_n$
and
$H_n$
obey the same characteristic recursive distributional equation.
Let us start with
$H_n$
. Recall that
$ \mathcal{T}_n^{ \bullet}$
is built from the conditioned Galton–Watson plane tree
$ \mathscr{T}_n$
by assigning uniform labels, keeping the root vertex, and forgetting about the plane ordering. We let
$K \geq 0$
denote the number of vertices of height 2 in
$ \mathscr{T}_n$
, let
$T_1, \ldots, T_K$
be the plane trees (ordered from left to right) attached to these vertices in
$ \mathscr{T}_n$
, and let
$N_1, \ldots, N_K$
denote their respective sizes (see Figure 2). Then, by the Markov branching property of the Galton–Watson measure [Reference Haas and Miermont16], conditionally on
$( K, N_1, \ldots, N_K)$
, the plane rooted trees
$(T_1 , \ldots, T_K)$
are independent Galton–Watson plane trees with
$ \mathrm{Poisson}(1)$
offspring distribution conditioned to have sizes
$(N_1, \ldots, N_K)$
. Since the number of vertices at even height in
$ \mathscr{T}_n$
is just 1 (for the root vertex) plus the sum of the number of vertices at even height in every tree
$ T_i$
for
$ 1 \leq i \leq K$
, it follows that
\begin{equation} H_{n} \stackrel{(d)}{=} 1 + \sum_{i = 1}^{K} H_{N_i}^{(i)},\end{equation}
where
$\bigl(H_{j}^{(i)} \colon 1 \leq i,j\bigr)$
are independent variables also independent of
$(K, N_1, \ldots, N_K)$
, and
$H_{j}^{(i)}$
has law
$H_j$
for every
$ i,j \geq 1$
.
(a) Illustration of the recursive equation in law for the number
$H_n$
of vertices at even height on
$ \mathscr{T}_n$
. In black at the bottom is the root vertex, in white its neighbours, and the next vertices to include are the black roots in each tree
$T_i$
. (b) Illustration of the first step of the greedy algorithm. With our coupling with
$ \mathscr{T}_n$
, the first vertex that we add in the greedy independent set is the root vertex of
$ \mathscr{T}_n$
(in green at the bottom and in red its neighbours). The next vertices (in green) to inspect in each
$T_i$
are then not necessarily the root vertices of
$T_i$
.
Let us now move on to the size of the greedy independent set. By construction, it is built first by including a uniform vertex V with label in
$ \{ 1, \ldots, n\}$
and blocking its neighbours (which are the vertices at distance 1 from the vertex V). We can assume that this vertex is actually the root vertex of
$ \mathcal{T}_n^{\bullet}$
(or equivalently of
$ \mathscr{T}_n$
) since it is a uniform vertex of
$ \{ 1, \ldots, n\}.$
Using the same notation as above (see Figure 2), the crucial observation is that the greedy independent set is obtained by joining the existing root vertex of
$ \mathscr{T}_n$
together with the independent sets obtained by applying the greedy algorithm on the trees
$ T_1, \ldots, T_K$
independently. The difference from the case of
$H_n$
above is that in each tree
$T_i$
the next vertex to inspect is not necessarily the root of
$ T_i$
(induced by
$ \mathscr{T}_n$
) but a ‘new’ uniform vertex of
$ T_i$
(see Figure 2). But by invariance of uniform Cayley trees under uniform rerooting, we still have
\begin{equation} G_{n} \stackrel{(d)}{=} 1 + \sum_{i = 1}^K G_{N_i}^{(i)},\end{equation}
where
$\bigl(G_{j}^{(i)} \colon 1 \leq i,j\bigr)$
are independent variables also independent of
$(K, N_1, \ldots, N_K)$
, and
$G_{j}^{(i)}$
has law
$G_j$
for
$ i,j \geq 1$
.
Moreover, equations (3) and (4) characterize the law of
$H_n$
and
$G_n$
since
$ N_1 + \cdots + N_K \leq n-1$
almost surely. Hence
$G_n$
and
$H_n$
have the same law and we get the desired result.
Proof of the second half of Theorem 1. By Lemma 1, the variable
$H_n$
has the same law as the number of vertices at even height in a Galton–Watson tree with
$ \mathrm{Poisson}(1)$
offspring distribution conditioned to have n vertices. To compute it, we artificially introduce two types of vertices (white vertices and black vertices) and let
$ \mathscr{T}_{b}$
be a two-type alternating Galton–Watson tree with a black root and with
$\mathrm{Poisson}(1)$
offspring distribution (for both types of vertices), so that all vertices at even height are black and have white children, and all vertices at odd height are white and have black children. We let
$N_b$
(resp.
$N_w$
) denote the number of black (resp. white) vertices in
$ \mathscr{T}_b$
. Using the result of [Reference Chaumont and Liu9] and more precisely [Reference Féray and Kortchemski14, Corollary 3.4], and letting
$S_j$
denote the sum of j independent and identically distributed (i.i.d.) random variables with law
$ \mathrm{Poisson}(1)$
for
$j \geq 1$
, so that
$S_j$
has law
$ \mathrm{Poisson}(j)$
, we obtain, for all
$ k \geq 1$
,
\begin{align*}\mathbb{P}( H_n = k) &= \mathbb{P}( N_b = k, N_w = n-k | N_b + N_w = n) \\[5pt] &= \dfrac{n}{k} \dfrac{ \mathbb{P}(S_k = n-k) \mathbb{P}(S_{n-k} = k-1)}{ \mathbb{P}(S_n = n-1)} \\[5pt] &= \binom{n}{k} \dfrac{k^{n-k}(n-k)^{k-1}}{n^{n-1}}.\end{align*}
A straightforward application of Stirling’s formula gives equation (2). We then easily deduce the local central limit theorem and the law of large numbers.
2.2. Independent set of edges for plane trees
As mentioned in the Introduction, this construction of the greedy independent set of vertices on uniform Cayley trees, which are invariant under rerooting at a uniform vertex, suggests a similar construction for the greedy independent set of edges on uniform plane trees which are invariant under rerooting at a uniform edge.
Recall that we let
$ \widetilde{\mathcal{T}}_n$
denote a uniform plane tree of size n (i.e. with n vertices). It can be seen as a graph that is properly embedded in the plane, has only one face of degree
$2n-2$
, and is rooted at the oriented edge going from the root vertex to its leftmost child (see Figure 3). The crucial observation is that if, conditionally on
$ \widetilde{ \mathcal{T}}_n$
, we let
$ \vec{e}$
be a uniform oriented edge of
$ \widetilde{ \mathcal{T}}_n$
, then the tree
$ \widetilde{ \mathcal{T}}_n^{ \vec{e}}$
obtained by rerooting the tree
$ \widetilde{ \mathcal{T}}_n$
at the edge
$ \vec{e}$
is still a uniform plane tree.
(a) A plane tree rooted at the black oriented edge. (b) The usual representation of this plane tree rerooted at the green oriented edge.
Moreover, as uniform Cayley trees, uniform plane trees of size n can be seen as conditioned Galton–Watson trees with the appropriate offspring distribution (see e.g. [Reference Aldous3]).
Lemma 2. A Galton–Watson plane tree with
$\mathrm{Geom}(1/2)$
offspring distribution conditioned to have n vertices is a uniform (rooted) plane tree of size n, where a random variable X has law
$\mathrm{Geom}(1/2)$
if, for all
$ k \geq 0$
, we have
$\mathbb{P} (X = k) = 2^{-k-1}. $
Using this lemma and the invariance under rerooting at a uniform oriented edge, we now prove Theorem 3.
(a) Illustration of the first step of the greedy algorithm for the independent set of edges. The first edge that we add in the independent set is the green root edge, and we block its neighbouring edges (red). The next edge to inspect is a uniform edge in each tree
$T_i^{j}$
, but can be taken as the root edge by invariance under rerooting. (b) A plane tree
$ \textbf{t}$
with black vertices and with edges coloured as follows. We colour the root edge green, its neighbouring edges red, and reapply the procedure in each tree by taking first the root edge (in green). Its corresponding bi-type alternating plane tree
$ \textbf{t}_g$
is obtained by considering the edges of
$ \textbf{t}$
as the vertices of
$ \textbf{t}_g$
: the children of a green vertex in
$ \textbf{t}_g$
correspond to its children followed by its brothers in
$ \textbf{t}$
, and a red vertex has a green child in
$ \textbf{t}_g$
if the red corresponding edge has (at least) a child in
$ \textbf{t}$
.
Proof of Theorem 3. By invariance under rerooting at a uniform oriented edge, we can assume that our greedy algorithm on
$ \widetilde{\mathcal{T}}_n$
first includes the root edge and blocks its ‘neighbouring edges’, i.e. the edges adjacent to one of its endpoints (see Figure 4(a)). We let
$K_2$
denote the number of children of the root vertex minus 1 (or number of brothers of the root edge), let
$K_1$
be the number of children of the first child of the root, and let
$T_1^1, \ldots,T_{K_1}^1$
and
$T_1^2, \dots T_{K_2}^2$
be the trees attached to these vertices (ordered from left to right: see Figure 4), which have respective sizes
$N_1^1, \ldots,N_{K_1}^1$
and
$N_1^2, \ldots, N_{K_2}^2$
. Then, conditionally on
$\bigl(K_1, K_2, N_1^1, \ldots,N_{K_1}^1, N_1^2, \ldots,N_{K_2}^2\bigr)$
, the trees
$\bigl(T_1^1, \dots T_{K_1}^1, T_1^2, \ldots,T_{K_2}^2\bigr)$
are independent Galton–Watson trees with
$ \mathrm{Geom}(1/2)$
offspring distribution conditioned to have respective sizes
$\bigl(N_1^1, \ldots,N_{K_1}^1, N_1^2, \ldots, N_{K_2}^2\bigr)$
. By the same argument as in the proof of Theorem 1, we deduce that
$ \widetilde{M}_n$
satisfies the following recursive distributional equation:
\begin{equation} \widetilde{M}_{n} \stackrel{(d)}{=} 1 + \sum_{i = 1}^{K_1} \widetilde{M}_{N_i^1}^{(i)}+ \sum_{i = 1}^{K_2} \widetilde{M}_{N_i^2}^{(K_1+i)},\end{equation}
where
$\bigl( \widetilde{M}_{j}^{(i)} \colon 1 \leq i,j\bigr)$
are independent variables also independent of
\begin{equation*}\bigl(K_1, K_2, N_1^1, \ldots,N_{K_1}^1, N_1^2, \ldots,N_{K_2}^2\bigr),\end{equation*}
and
$ \widetilde{M}_{j}^{(i)}$
has law
$ \widetilde{M}_j$
for
$1 \leq i,j$
.
As in the proof of Theorem 1, we interpret the last recursive distributional equation using two-type Galton–Watson trees. Specifically, let
$ \mathbb{T}$
be a two-type alternating Galton–Watson tree, with green and red vertices, with a green root and where the red vertices have a Bernoulli offspring distribution with parameter
$1/2$
, and the offspring distribution of the green vertices is the law of the sum of two independent variables with law
$ \mathrm{Geom} (1/2)$
. We let
$N^g$
(resp.
$N^r$
) be the number of green (resp. red) vertices in
$ \mathbb{T}$
. Writing
$ N^g_{n}$
for the number of green vertices in the tree
$ \mathbb{T}$
conditioned to have
$n-1$
vertices in total, then
$ N^g_{n}$
obeys the same recursive equation (5) as
$ \widetilde{M}_n$
(see Figure 4).
Using [Reference Féray and Kortchemski14, Corollary 3.4] again and letting
$ \widetilde{S}_j^g$
denote the sum of j i.i.d. random variables with law
$ \mathrm{Geom}(1/2)$
and
$ \widetilde{S}_j^{r}$
the sum of j i.i.d. random variables with Bernoulli law of parameter
$1/2$
for
$j \geq 1$
, so that
$ \widetilde{S}_j^{r}$
has binomial distribution of parameters j and
$1/2$
, we obtain, for all
$ k \geq 1$
,
\begin{align*}\mathbb{P}( \widetilde{M}_n = k) &= \mathbb{P}( N^g = k, N^r = n-1-k \mid N^g + N^r = n-1) \\[5pt] &= \dfrac{1}{k} \dfrac{ \mathbb{P}\bigl( \widetilde{S}_{2k}^{g} = n-1-k\bigr) \mathbb{P}\bigl( \widetilde{S}_{n-1-k}^{r} = k-1\bigr)}{ \mathbb{P}\bigl( \widetilde{S}_{n}^{g} = n-1\bigr) } \\[5pt] &= \dfrac{n}{k} \dfrac{\binom{n+k-2}{2k-1}\binom{n-k-1}{k-1}}{\binom{2n-2}{n-1}}. \end{align*}
3. Markovian explorations of a rooted tree
In this section we introduce the Markovian explorations of Cayley trees which we will use to prove the symmetry of the law of
$G_n$
(Theorem 2) and which we shall call ‘peeling explorations’ by analogy with the peeling process in the theory of random planar maps; see [Reference Curien11]. Given a Cayley tree
$ \textbf{t}$
, an exploration of
$ \textbf{t}$
will be a sequence of forests
$( \textbf{f}_0 , \ldots, \textbf{f}_{n-1})$
starting from the forest
$ \textbf{f}_0$
made of n isolated vertices and ending at
$ \textbf{f}_{n-1} = \textbf{t}$
, such that we pass from
$ \textbf{f}_i$
to
$ \textbf{f}_{i+1}$
by adding one edge. In our setup, the edge to add at each step will be the edge linking the vertex peeled at step i to its parent. To do so, we thus need to root our tree
$ \textbf{t}$
by distinguishing a vertex and orienting all edges towards it. That is why in the rest of the paper (and contrary to the previous section) we will always see a Cayley tree
$ \textbf{t}$
as rooted at the vertex of index n.
Specifically, for
$0 \leq k \leq n-1$
, we let
$\mathcal{F}^{*}(n,k)$
be the set of (unordered) rooted forests on labelled vertices
$\{ 1, \ldots, n \} $
with exactly k edges, where one of the trees is distinguished: in the following, the distinguished tree and its vertices are seen as being blue whereas the other trees and vertices are white; see Figure 5. We let
$\mathcal{F}_n^{*} = \cup_{k=0}^{n-1} \mathcal{F}^{*}(n,k)$
denote the set of such rooted forests on
$\{ 1, \ldots, n \}$
. Below, the blue component will correspond to the component of the ‘real’ root of the tree in our peeling exploration of rooted Cayley trees. Given a forest
$ \textbf{f} \in \mathcal{F}^{*}(n,k)$
, we say that a rooted Cayley tree
$ \textbf{t}$
contains
$ \textbf{f}$
if
$ \textbf{t}$
can be obtained from
$ \textbf{f}$
by adding edges between each white root of a tree and another compatible vertex, i.e. a vertex contained in a different tree of
$ \textbf{f}$
. Moreover, if
$v_1$
is the root of a white tree and
$v_2$
is a vertex of another tree, we let
$\textbf{f}_{v_1 \to v_2}$
denote the forest obtained from
$ \textbf{f}$
by adding an edge from
$v_1$
to
$v_2$
and colouring the resulting component with the colour of
$v_2$
. Assume now that we have a function
$\mathfrak{a}$
called the peeling algorithm which associates
$ \textbf{f} \in \mathcal{F}^{*}_n \setminus \mathcal{F}^* (n, n-1)$
with a white root of a tree of the forest
$ \textbf{f}$
.
Example of a forest
$ \textbf{F}_{10}^{\mathfrak{a}}$
which can be obtained after 10 steps of exploration of a given tree
$ \textbf{t}$
of size 18. The edges that are still unknown are shown by dashed lines. If the vertex labelled
$ \mathfrak{a}\bigl( \textbf{F}_{10}^{\mathfrak{a}}\bigr) = 16$
is the next peeled vertex, then the next edge to be added will be the dashed orange edge.
Definition 1. Let
$\textbf{t}$
be a Cayley tree with n vertices rooted at the vertex labelled n. The peeling exploration of
$ \textbf{t}$
with algorithm
$\mathfrak{a}$
is the sequence
\begin{equation*}\textbf{F}_{0}^{\mathfrak{a}} \longrightarrow \textbf{F}_{1}^{\mathfrak{a}} \longrightarrow \cdots \longrightarrow \textbf{F}_{n-2}^{\mathfrak{a}} \longrightarrow \textbf{F}_{n-1}^{\mathfrak{a}}\end{equation*}
obtained by starting from
$\textbf{F}_0^{\mathfrak{a}}$
, the unique element of
$\mathcal{F}^{*} (n,0) $
with isolated vertices, which are all white except the blue vertex n, and at step
$i \geq 1$
, the forest
$\textbf{F}_{i}^{\mathfrak{a}}$
is obtained from
$\textbf{F}_{i-1}^{\mathfrak{a}}$
and
$\mathfrak{a} (\textbf{F}_{i-1}^{\mathfrak{a}})$
as follows: if v is the parent of
$\mathfrak{a} (\textbf{F}_{i-1}^{\mathfrak{a}})$
in
$ \textbf{t}$
, then we add the edge from
$\mathfrak{a} (\textbf{F}_{i-1}^{\mathfrak{a}})$
to v to
$ \textbf{F}_{i-1}^{ \mathfrak{a}}$
and colour the vertices of the resulting component with the colour of v to obtain
\begin{equation*}\textbf{F}_{i}^{ \mathfrak{a}} = \bigl(\textbf{F}_{i-1}^{ \mathfrak{a}} \bigr)_{\mathfrak{a} (\textbf{F}_{i-1}^{\mathfrak{a}}) \to v}.\end{equation*}
Notice that
$\textbf{F}_{n-1}^{\mathfrak{a}}$
is the tree
$ \textbf{t}$
with blue vertices, regardless of the choice of
$\mathfrak{a}$
. Moreover, when
$\textbf{t}=\mathcal{T}_n$
is a uniform Cayley tree rooted at n, then the sequence
$(\textbf{F}_{i}^{\mathfrak{a}})_{0 \leq i \leq n-1}$
is a Markov chain.
Proposition 1. Fix a peeling algorithm
$ \mathfrak{a}$
. If
$\mathcal{T}_n$
is a uniform Cayley tree of size n rooted at n, then the exploration
$(\textbf{F}_{i}^{\mathfrak{a}})_{0 \leq i \leq n-1}$
of
$ \mathcal{T}_n$
with algorithm
$ \mathfrak{a}$
is a Markov chain whose probability transitions are described as follows: for
$i \geq 0$
, conditionally on
$\textbf{F}_{i}^{\mathfrak{a}}$
and on
$\mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
, we let
$m \geq 1$
denote the size of the connected component of
$\mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
and let
$\ell \geq 1$
denote the number of blue vertices in
$ \textbf{F}_{i}^{ \mathfrak{a}}$
.
-
For every blue vertex v, the parent of
$ \mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
is v with probability
$(\ell+m)/(\ell n)$
, and in that case we add an edge from
$\mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
to v and colour the resulting component blue to obtain
$ \textbf{F}_{i+1}^{ \mathfrak{a}}$
. -
For every white vertex v that does not belong to the component of
$\mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
, the parent of
$ \mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
is v with probability
$1/n$
, and in that case we add an edge from
$\mathfrak{a} (\textbf{F}_{i}^{\mathfrak{a}})$
to v to obtain
$ \textbf{F}_{i+1}^{ \mathfrak{a}}$
.
This proposition is a direct corollary of the following lemma.
Lemma 3. If
$ \textbf{f} \in \mathcal{F}^{*} (n,k)$
is a forest on
$\{ 1, \ldots, n\}$
with k edges and
$\ell \geq 1$
blue vertices (hence
$n-k-1$
white trees and a blue tree), then the number
$N( \textbf{f})$
of rooted Cayley trees containing
$ \textbf{f}$
is equal to
$\ell n^{n-k-2}$
.
Proof. The proof is similar to that of Pitman in [Reference Pitman22, Lemma 1]. We introduce the number
$N^*(\textbf{f} )$
of refining sequences of
$ \textbf{f}$
, i.e. the number of sequences
$(\textbf{f}_j , \ldots, \textbf{f}_{1})$
where
$ \textbf{f}_j = \textbf{f}$
, and for
$i \leq j$
, the forest
$ \textbf{f}_i$
has a blue tree and
$i-1$
white trees, and
$ \textbf{f}_{i-1}$
can be obtained from
$ \textbf{f}_i$
by adding an edge as above. Note that
$j = n-k$
since
$\textbf{f}$
has
$n-k-1$
white trees. Given a fixed target
$ \textbf{f}_1$
, any forest
$ \textbf{f}_j$
that contains a
$ \textbf{f}_1$
has
$j-1$
fewer edges than
$ \textbf{f}_1$
. Hence there are
$(j-1)!$
refining sequences from
$ \textbf{f}_j$
to
$ \textbf{f}_1$
and
$N^*( \textbf{f}_j) = (j-1)! N( \textbf{f}_j)$
. Now we prove the result on
$N( \textbf{f})$
by induction over
$j-1$
, the number of white trees of
$ \textbf{f}$
. When
$j =1$
, then
$ \textbf{f} \in \mathcal{F}^* (n,n-1)$
is simply a blue rooted tree and the result is clear.
Suppose the result holds for some
$ j-1 \geq 0$
. Let
$ \textbf{f} \in \mathcal{F}^* (n,n-j-1)$
be a forest on
$\{ 1, \ldots, n\}$
with
$n_1 \geq 1$
blue vertices and j white trees
$( \textbf{t}_2, \ldots, \textbf{t}_{j+1})$
of size
$(n_2, \ldots, n_{j+1})$
. Then, if
$r_i$
is the root of the white tree
$ \textbf{t}_i$
,
-
for each blue vertex
$v_1$
, by the induction hypothesis, there are
$ N^*( \textbf{f}_{r_i \to v_1}) = (n_1 + n_i) n^{j-2} (j-2)!$
refinements of
$ \textbf{f}_{r_i \to v_1}$
and there are
$n_1$
such vertices
$v_1$
, -
for each vertex
$v_j$
in a white tree
$ \textbf{t}_j$
with
$ i \neq j$
, by the induction hypothesis, there are
$ N^*( \textbf{f}_{r_i \to v_j}) = n_1 n^{j-2} (j-2)!$
refinements of
$ \textbf{f}_{r_i \to v_j}$
and there are
$n -(n_i + n_1)$
such vertices
$v_j$
.
In total, the number of refinements of
$ \textbf{f}$
is
\begin{equation*} N^*( \textbf{f}) = \sum_{i = 2}^{j+1} n_1 (n_1 + n_i) n^{\,j-2} (\,j-2)! + (n -(n_i + n_1))n_1 n^{\,j-2} (\,j-2)! = (\,j-1)! n_1 n^{\,j-1}, \end{equation*}
and we get the desired result.
Now we can prove Proposition 1.
Proof of Proposition 1. It suffices to notice that since
$ \mathcal{T}_n$
is uniform, for all
$i \geq 0$
, conditionally on
$ \textbf{F}_i^{\mathfrak{a}}$
, the tree
$ \mathcal{T}_n$
is a uniform tree among those which contain
$ \textbf{F}_i^{\mathfrak{a}}$
. Hence, for every (compatible) vertex v,
\begin{equation*}\mathbb{P} \bigl( \textbf{F}_{i+1}^{\mathfrak{a}} = ( \textbf{F}_{i}^{\mathfrak{a}})_{\mathfrak{a} ( \textbf{F}_{i}^{\mathfrak{a}}) \to v} \mid \textbf{F}_{i}^{\mathfrak{a}}, \mathfrak{a} ( \textbf{F}_{i}^{\mathfrak{a}})\bigr) = \dfrac{|\{ \text{$\textbf{t}$ such that $ \textbf{t}$ contains $ ( \textbf{F}_{i}^{\mathfrak{a}})_{\mathfrak{a} ( \textbf{F}_{i}^{\mathfrak{a}}) \to v}$} \}|}{| \{\text{$ \textbf{t}$ such that $ \textbf{t}$ contains $ \textbf{F}_{i}^{\mathfrak{a}}$} \} |}.\end{equation*}
Using Lemma 3, we recognize the transition probabilities given in Proposition 1 and obtain the desired result.
The strength of Proposition 1 is that different peeling algorithms yield different explorations (hence different types of information) of the same underlying tree. Let us illustrate this with several examples of peeling algorithms.
Pitman’s algorithm and
$ \mathfrak{a}_{ \mathrm{unif}}$
. A natural choice of algorithm
$ \mathfrak{a}$
is, given a forest
$ \textbf{f}$
, to choose a root of a white tree of
$ \textbf{f}$
uniformly at random for
$ \mathfrak{a}_{ \mathrm{unif}} ( \textbf{f})$
. This does not seem to enter our setup since
$ \mathfrak{a}_{ \mathrm{unif}}$
is not a deterministic function of
$ \textbf{f}$
. However, we can imagine that we first condition on the randomness involved in
$ \mathfrak{a}_{ \mathrm{unif}}$
making it deterministic. Once
$ \mathfrak{a}_{ \mathrm{unif}}$
is fixed, we apply it to a random Cayley tree
$ \mathcal{T}_n$
, thus independent of the choice of
$ \mathfrak{a}_{ \mathrm{unif}}$
. The Markov chain obtained in Proposition 1 to this peeling is reminiscent of (but not identical to) Pitman’s construction [Reference Pitman22] of uniform rooted Cayley trees, which we recall briefly: start from the forest made of the n isolated vertices
$ \{ 1, \ldots, n\}$
, and at step
$ 1 \leq k \leq n-1$
, pick a vertex
$V_k$
uniformly at random and then pick a root
$R_k$
uniformly at random among the
$n-k$
trees that do not contain
$V_k$
, and add the directed edge from
$R_k$
to
$V_k$
. Note that in Pitman’s construction we first pick a uniform vertex, then a uniform compatible root, and the ‘real’ root of the Cayley tree is found out only at the end of the exploration, whereas in our peeling exploration with algorithm
$ \mathfrak{a}_{ \mathrm{unif}}$
, we first fix the root as the vertex labelled n, and during the exploration we choose uniformly a root of a white tree whose parent is chosen almost uniformly among the compatible vertices.
Building branches and the Aldous–Broder algorithm. Let us mention another choice of algorithm which sheds new light on the Aldous–Broder construction [Reference Aldous1, Reference Broder7] of
$ \mathcal{T}_n$
by using a random walk on the complete graph with loops. We assume in this paragraph that
$ n \geq 2$
. Given a forest
$ \textbf{f} \in \mathcal{F}^{*}_n$
, let
$ \mathfrak{a}_{AB} ( \textbf{f})$
be the root of the tree that contains the white vertex with the smallest label. For example, starting at
$\textbf{F}_0^{ \mathfrak{a}_{AB}}$
, then
$ \mathfrak{a}_{AB}(\textbf{F}_i^{ \mathfrak{a}_{AB}})$
is the root of the component of 1 until the exploration hits the blue root n. Let
\begin{equation*}T_1^{\mathfrak{a}_{\text{AB}}} = \min \{ \text{$i \geq 1$ such that 1 is a blue vertex in $ F_{i-1}^{ \mathfrak{a}_{AB}}$}\}\end{equation*}
be the length of the first ‘branch’ built in this exploration. Then, for
$k \geq 2$
,
\begin{equation*} \mathbb{P} (T_1^{\mathfrak{a}_{AB}} = k) =\dfrac{k}{n} \prod_{i = 2}^{k-1} \biggl( 1 - \dfrac{i}{n}\biggr).\end{equation*}
Now recall the Aldous–Broder algorithm [Reference Aldous1, Reference Broder7] on the complete graph on n vertices, i.e. the graph with vertex set
$\{ 1, \ldots, n\}$
, and all possible edges including the loops (i, i): consider a random walk
$(X_i \colon i \geq 0)$
starting at
$X_0 \;:\!=\; n$
and where the
$X_i$
are i.i.d. uniform random variables on
$\{ 1, \dots n \}$
for
$i \geq 1$
. We let
$ \tau_k\;:\!=\; \inf \{i \colon X_i = k\} < \infty$
for any
$ k \in \{ 1, \ldots, n\}$
. The walk induces the tree
$ \mathcal{T}^{AB}$
, which consists of the tree on
$\{ 1, \ldots, n\}$
with the edges
$(X_{\tau_k - 1}, X_{\tau_k})$
for
$ 1 \leq k \leq n-1$
(we only take the edges that lead to newly discovered vertices). Consider
\begin{equation*}T_1^{AB} = \min \{ \text{$i \geq 1$ such that $ X_{i} \in \{ X_0 , \ldots, X_{i-1}$} \} \},\end{equation*}
the time of the first repetition of the walk
$(X_i \colon i \geq 0).$
Then, by construction,
$\mathbb{P} \bigl( T_1^{AB} = 1\bigr) = 1/n$
, and for
$k \geq 2$
,
\begin{equation*}\mathbb{P} \bigl( T_1^{AB} = k\bigr) = \dfrac{k}{n} \prod_{i = 1}^{k-1} \biggl( 1 - \dfrac{i}{n}\biggr) = \dfrac{n-1}{n} \mathbb{P} \bigl(T_1^{\mathfrak{a}_{AB}} = k\bigr) = \mathbb{P}\bigl( T_1^{AB} \neq 1\bigr) \cdot \mathbb{P} \bigl(T_1^{\mathfrak{a}_{AB}} = k\bigr).\end{equation*}
We deduce that conditionally on
$X_1 \neq n$
, the law of the length
$T_1^{AB}$
of the first branch is identical to that of the length of the branch linking n and 1 in
$ \mathcal{T}_n$
; see [Reference Aldous2]. A similar result holds for the next branches in both constructions. This has already been observed by Camarri and Pitman [Reference Camarri and Pitman8, Corollary 3] in the more general context of p-trees.
Greedy construction. In the next section we use a peeling algorithm (with additional decorations) tailored to the construction of the greedy independent set on
$ \mathcal{T}_n$
.
4. Markovian construction of the greedy independent set
This section is devoted to the proof of Theorem 2, which uses our Markovian exploration of Cayley trees.
4.1. Markovian construction and its transitions
Recall the greedy algorithm from the Introduction: given a Cayley tree, we inspect its vertices sequentially in a uniform random order, and at each step, if the considered vertex is undetermined, we change its status to active and change the status of all its undetermined neighbours to blocked. By Lemma 1, we have an invariance property of
$ \mathcal{T}_n$
under independent uniform relabelling. Hence we can and will directly use the labels of
$ \mathcal{T}_n$
to define the order of exploration of the greedy independent set on
$ \mathcal{T}_n$
.
Recall that we rooted our tree at the vertex n. The idea here is to link the greedy construction to a peeling exploration of
$ \mathcal{T}_n$
: at each step we explore and inspect a vertex and update its status and possibly that of its parent in the tree but not those of its children. In particular, the root n of the tree is possibly the last vertex to be considered (when it is not previously blocked).
More precisely, given the Cayley tree
$ \mathcal{T}_n$
rooted at n, we divide its vertices into three statuses (undetermined, active, or blocked) as before, and set
\begin{equation*} \widetilde{\mathcal{U}}_0^n = \{ 1, \ldots, n \} , \quad \widetilde{\mathcal{A}}_0^n = \widetilde{\mathcal{B}}_0^n = \emptyset.\end{equation*}
Then inductively at step i, we inspect
$v_i$
the undetermined vertex with the smallest label and we let
$w_i$
be its parent in
$ \mathcal{T}_n$
(unless
$v_i = n$
). Then we update their statuses as follows.
-
If
$v_i = n$
, then the vertex n becomes active, that is,
\begin{equation*} \widetilde{\mathcal{U}}_{i+1}^n = \emptyset \quad\text{and}\quad \widetilde{\mathcal{A}}_{i+1}^n = \widetilde{\mathcal{A}}_i^n \cup \{v_i\}. \end{equation*}
-
If
$w_i$
is undetermined, then
$v_i$
becomes active (it is taken in the greedy independent set) and
$w_i$
becomes blocked, that is,
\begin{equation*} \widetilde{\mathcal{U}}_{i+1}^n = \widetilde{\mathcal{U}}_{i}^n \setminus\{ v_i ,w_i\},\quad \widetilde{\mathcal{A}}_{i+1}^n = \widetilde{\mathcal{A}}_{i}^n \cup \{ v_i \}\quad\text{and}\quad \widetilde{\mathcal{B}}_{i+1}^n = \widetilde{\mathcal{B}}_{i}^n \cup \{ w_i \}. \end{equation*}
-
If
$w_i$
is blocked (resp. active), then
$v_i$
becomes active (resp. blocked), that is,
\begin{equation*} \widetilde{\mathcal{U}}_{i+1}^n = \widetilde{\mathcal{U}}_{i}^n \setminus\{ v_i \}\quad\text{and}\quad \widetilde{\mathcal{A}}_{i+1}^n = \widetilde{\mathcal{A}}_{i}^n \cup \{ v_i \} \quad \text{(resp. $ \widetilde{\mathcal{B}}_{i+1}^n = \widetilde{\mathcal{B}}_{i}^n \cup \{ v_i \}$).} \end{equation*}
As before, at each step i, the set
$ \widetilde{\mathcal{A}}_i^n$
is an independent set and we stop the process when all vertices are active or blocked, i.e. at time
$ \theta_n = \inf \bigl\{ i \geq 0, \ \widetilde{\mathcal{U}}_i^n = \emptyset\bigr\}$
. It is then easy to check that the random subset
$ \widetilde{ \mathcal{A}}_{ \theta_n}^n$
is equal to the greedy independent set
$ \mathcal{A}_{\tau}$
defined in the Introduction (if we inspect vertices according to their labels in the tree). The advantage of the above construction over that of the Introduction, where we update the status of all neighbours of the inspected vertex, is that it can be seen as a Markovian exploration of
$ \mathcal{T}_n$
in the sense of the preceding section (where we additionally keep track of the status of the vertices). Indeed, it is equivalent to the peeling of
$ \mathcal{T}_n$
started at the forest
$ \textbf{F}_{0}^{ \mathfrak{a}_{ \mathrm{Greedy}}}$
made of an undetermined blue vertex with label n and
$n -1$
isolated white undetermined vertices, and where at step
$i+1$
we peel the vertex
\begin{equation*} v_{i} = \min \widetilde{\mathcal{U}}_i^n\;:\!=\; \mathfrak{a}_{\mathrm{Greedy}}\bigl( \textbf{F}_i^{ \mathfrak{a}_{\mathrm{Greedy}}}\bigr),\end{equation*}
the undetermined vertex with the smallest label, and update the status of the vertices as above; see Figure 6. Recall the two possible colours for the vertices during a peeling exploration: the vertices which are in the connected component of the vertex labelled n, which is the ‘real root’ of the tree, are blue, whereas the other vertices are white. We make the following remarks, which are easily checked by induction: with the possible exception of the vertex n, the undetermined vertices are white, whereas the active or blocked vertices can be white or blue. Moreover, at each step
$i < \theta_n$
the forest
$ \textbf{F}_i^{ \mathfrak{a}_{\mathrm{Greedy}}} $
is made of white isolated undetermined vertices, white trees of size at least 2 rooted at a blocked vertex, and a blue tree; see Figure 7.
Illustration of the possible transitions in the peeling exploration with
$ \mathfrak{a}_{ \mathrm{Greedy}}$
together with the updating of the status of the vertices. The interior colour represents the colour of the vertices (blue or white) in the peeling exploration and the boundary colour represents the status of the vertices in the greedy construction of the independent set: black for the undetermined vertices, green for the active vertices, and red for the blocked vertices. The new edge we explore (between
$v_i$
and
$w_i$
) is shown by a dashed grey line. When
$v_i = n$
there is no peeling step, but
$v_i$
is the last undetermined vertex and it becomes active.
Illustration of a possible value of
$ \textbf{F}_{10}^{\mathfrak{a}_{ \mathrm{Greedy}}}$
. As in Figure 6, the interior colour represents the colour of the vertices in the peeling exploration and the boundary colour represents the status of the vertices in the greedy construction of the independent set: black for the undetermined vertices, green for the active vertices, and red for the blocked vertices. The new vertex to peel has label 12 here.
A small caveat is that a priori the peeling exploration with algorithm
$ \mathfrak{a}_{ \mathrm{Greedy}}$
is not defined after time
$ \theta_n$
: generically, at that time, although the status in the greedy independent set of all vertices is known, the entire geometric structure of
$ \mathcal{T}_n$
is not completely revealed since there are many white vertices in
$ \textbf{F}_{\theta_n}^{ \mathfrak{a}_{ \mathrm{Greedy}}} $
(we never peel the blocked roots of white trees). For the sake of completeness we may continue the peeling exploration (e.g. by peeling the white (blocked) root of a tree with the smallest label), but we shall not use it.
We let
$\bigl(U_i^n, A_i^n , B_i^n\bigr)_{i \geq 0_{_{_{\,}}}}\!$
denote the number of undetermined, active, and blocked vertices in the process on a uniform Cayley tree
$ \mathcal{T}_{n_{_{_{\,}}}}\!$
with the greedy peeling algorithm
$ \mathfrak{a}_{ \mathrm{Greedy}}$
, i.e. the size of
$ \widetilde{\mathcal{U}}_{i}^n$
,
$ \widetilde{\mathcal{A}}_{i}^n$
, and
$ \widetilde{\mathcal{B}}_{i}^n$
. For the active and blocked vertices, we distinguish the number of white vertices
$A_i^{n,w}$
and
$B_i^{n,w}$
from the number of blue vertices
$A_i^{n,b}$
and
$B_i^{n,b}.$
Then, with the notation of Theorem 2, we have
$G_n = A_{ \theta_n}^n$
, and using a decorated version of Proposition 1 we see that
\begin{equation*}\bigl(U^n_i,A^{n,w}_i,B^{n,w}_i,A^{n,b}_i,B^{n,b}_i \colon 0 \leq i \leq \theta_n\bigr)\end{equation*}
is a Markov chain. To describe its probability transitions, we introduce
$ \Delta X_i\;:\!=\; X_{i+1} - X_i$
, the increment of a random process
$(X_j \colon j \geq 0)$
at time
$i \geq 0$
. Suppose that
$ \widetilde{\mathcal{U}}_i^n$
is not empty. On the one hand, when
$n \in \widetilde{\mathcal{U}}_i^n$
, then n is the only blue vertex in
$ \textbf{F}_i^{ \mathfrak{a}_{\mathrm{Greedy}}}$
, hence
$A_i^{n,b} = B_i^{n,b} = 0$
. On the other hand, when
$n \notin \widetilde{\mathcal{U}}_i^n$
, then
$A^{n,b}_{i} \geq 1$
and
$B^{n,b}_i \geq 1.$
Note that as long as
$ \widetilde{\mathcal{U}}_i^n$
is neither
$\{ n\}$
nor the empty set
$ \emptyset$
, the vertex
$ \mathfrak{a}_{\mathrm{Greedy}} ( \textbf{F}_{i}^{ \mathfrak{a}_{\mathrm{Greedy}}})$
is a white isolated vertex in
$\textbf{F}_{i}^{ \mathfrak{a}_{\mathrm{Greedy}}}$
. Therefore, conditionally on
$\bigl(U_i^n , A_i^{n,w}, B_i^{n,w} , A_i^{n,b} , B_i^{n,b}\bigr)$
, the transitions of the increments of
$\bigl(\bigl(U_i^n , A_i^{n,w}, B_i^{n,w} , A_i^{n,b} , B_i^{n,b}\bigr) \colon {i \geq 0}\bigr)$
are as follows.
If
$ A_i^{n,b} = B_i^{n,b} = 0$
and
$U_i^n = 1$
, i.e. if
$ \widetilde{\mathcal{U}}_{i}^n = \{ n\}$
, then almost surely
\begin{equation} \Delta \bigl(U^n_i,A^{n,w}_i,B^{n,w}_i,A^{n,b}_i,B^{n,b}_i\bigr) = (\!-1, 0,0,+1,0). \end{equation}
If
$A_i^{n,b} = B_i^{n,b} = 0$
and
$U_i^n \geq 2$
,
If
$A_i^{n,b} \geq 1$
,
$B_i^{n,b} \geq 1$
, and
$U_i^n \geq 1$
,
4.2. Symmetry of the greedy independent set
We now prove Theorem 2, which states the symmetry between the law of
$A_{ \theta_n}^n$
, the size of the maximal independent set obtained by the greedy algorithm, and
$ B_{ \theta_n}^n$
, that of its complement. The main observation is the following lemma.
Lemma 4. For
$j \geq 0$
, the laws of
$\bigl(A_i^{n,w}, A_i^{n,b}\bigr)_{0 \leq i \leq j+1}$
and
$ \bigl(B_i^{n,w} , B_i^{n,b}\bigr)_{0 \leq i \leq j+1}$
are the same on the event
$\ \widetilde{\mathcal{U}}_i^n \neq \{ n \}$
for all
$i \leq j$
.
Proof. Notice then that the role of
$\bigl(A_{i_{_{_{\,}}}\!}^{n,w}, A_i^{n,b}\bigr)$
and that of
$ \bigl(B_i^{n,w} , B_i^{n,b}\bigr)$
are exchangeable in the probability transitions (6, 7, 8) as long as
$ \widetilde{\mathcal{U}}_i^n \neq \{ n\}$
. The lemma follows.
Thanks to this lemma, we notice that conditionally on
$ \widetilde{\mathcal{U}}_{i}^n \neq \{n \}$
for all
$0 \leq i \leq \theta_n$
, the size
$A_{\theta_n}^n$
of the greedy independent set has the same law as that of its complement
$B_{\theta_n}^n$
. Otherwise, if there exists
$i \geq 0$
such that
$\widetilde{\mathcal{U}}_{i}^n = \{n \}$
, then this i corresponds to
$\theta_n - 1$
, and in that case
$A_{\theta_n-1}^n$
and
$B_{\theta_n-1}^n$
have the same law and
$A_{\theta_n}^n = G_n = A_{\theta_n-1}^n +1$
and
$B_{\theta_n}^n = B_{\theta_n-1_{_{_{\,}}}\!}^n$
. Hence the random variable
$ \mathcal{E}_n$
in Theorem 2 is the indicator function of the event
$ \bigl\{ \exists i \geq 0, \ \widetilde{\mathcal{U}}_{i}^n = \{n \} \bigr\}$
, and to prove Theorem 2 it only remains to show that
\begin{equation*}\mathbb{P} ( \mathcal{E}_n = 1) = \mathbb{P} ( \exists i, \ \widetilde{\mathcal{U}}_{i}^n = \{n \} ) \xrightarrow[n\to\infty]{\ } 1/4.\end{equation*}
To compute the above probability and also obtain the fluctuations of
$G_n$
, we study the fluid limit of our system (see [Reference Ethier and Kurtz13, Chapter 11]). The transition probabilities (6, 7, 8) in both cases point to the idea of gathering blue and white vertices and focusing only on their status. Indeed, the Markov chain
$(U_i^n , A_i^{n}, B_i^{n} \colon i \geq 0)$
has bounded increments, and for
$i < \theta_n$
,
\begin{equation} \left| \mathbb{E} \left[ \begin{pmatrix} \Delta U_i^n \\[5pt] \Delta A_i^n \\[5pt] \Delta B_i^n \end{pmatrix} \middle| \begin{pmatrix} U_i^n \\[5pt] A_i^n \\[5pt] B_i^n \end{pmatrix} \right] - F \biggl(\dfrac{U_i^n}{n}, \dfrac{A_i^n}{n}, \dfrac{B_i^n}{n}\biggr) \right| \leq \dfrac{3}{n}, \quad \mbox{where } F (x,y,z) = \begin{pmatrix} -2x -y-z \\[5pt] x+z \\[5pt] x+y \end{pmatrix}\!.\end{equation}
This suggests studying the deterministic system, which is the solution of the following equations:
\begin{equation*}\begin{cases}u'(t) = -2 u(t) -a(t)-b(t), & u(0) = 1, \\[5pt]a'(t) = u(t) + b(t), & a(0) = 0, \\[5pt]b'(t) = u(t) + a(t), & b(0) = 0.\end{cases}\end{equation*}
The solution is given by
\begin{equation*}\begin{cases}u(t) = 2 {\mathrm{e}}^{-t}- 1, \\[5pt]a(t) = b(t) = 1-{\mathrm{e}}^{-t}.\end{cases}\end{equation*}
In particular,
$t^* = \min \{ t \geq 0, \ u(t) = 0 \} = \ln\!(2)$
and
$a (t^* ) =1/2$
. We can now apply [Reference Ethier and Kurtz13, Theorem 2.1, p. 456] to the process
$ X_n (t) = 1/n \cdot \bigl(U^n_{ \lfloor tn \rfloor}, A^n_{ \lfloor tn \rfloor},B^n_{ \lfloor tn \rfloor_{_{_{\,}}}\!\!}\bigr)$
, which starts at
$X_n (0) = (1, 0, 0)$
with, using the notation of [Reference Ethier and Kurtz13], the function F given by (9) and
\begin{equation*}\begin{cases} \beta_{(-2,1,1)} (x,y,z) = x, \\[5pt] \beta_{(-1,0,1)} (x,y,z) = y, \\[5pt] \beta_{(-1,1,0)} (x,y,z) = z.\end{cases} \end{equation*}
We find that, at least for all
$t<t^*$
, for any
$ \varepsilon > 0$
,
\begin{equation*}\mathbb{P} \biggl( \sup_{0 \leq s \leq t} \biggl| \biggl(\dfrac{U_{ \lfloor sn \rfloor}^n}{n} , \dfrac{A^{n}_{ \lfloor sn \rfloor}}{n}, \dfrac{B^{n}_{ \lfloor sn \rfloor}}{n}\biggr) - (u(s),a(s),b(s)) \biggr| > \varepsilon \biggr) \xrightarrow[n\to\infty]{\ } 0.\end{equation*}
Since
$u'(t^*) < 0$
, we can apply [Reference Ethier and Kurtz13, Theorem 4.1, p. 464], which states that the stopping time of our Markov chain also concentrates around its expected value and has Gaussian fluctuations around it:
\begin{equation}\sqrt{n} \biggl( \dfrac{\theta_n}{n} - t^*\biggr) \xrightarrow[n\to\infty]{(d)}\mathcal{N} (0, 3/4).\end{equation}
Lastly, notice that
$ \mathcal{E}_n = 1$
when the vertex n stays undetermined at each step
$1 \leq i \leq \theta_n- 1$
, that is, with probability
$1 - 2/n $
at each step, and by the previous equation
$(1 - 2/n)^{ \theta_n}$
, converges in probability towards
${\mathrm{e}}^{-2 t^*}$
and is bounded by 1. Hence we obtain
\begin{equation*} \mathbb{P} ( \mathcal{E}_n = 1) = \mathbb{E} \biggl[ \biggl( 1 - \dfrac{2}{n}\biggr)^{\theta_n - 1} \biggr] \xrightarrow[n\to\infty]{ \ } \mathrm{e}^{-2 t^*} = \dfrac{1}{4}, \end{equation*}
which concludes the proof of Theorem 2.
Acknowledgements
The author is very grateful to Mireille Bousquet-Mélou, Vincent Delecroix, and Philippe Duchon for enlightening discussions during the 2021 Aléa days. In particular, we are indebted to Mireille Bousquet-Mélou for first computing the law of
$G_n$
in Theorem 2. We thank Igor Kortchemski for a discussion about bicoloured trees. We also thank Matthieu Jonckheere for stimulating discussions and Nicolas Curien for his constant guidance. I also thank the two anonymous referees for their careful reading and their valuable suggestions that helped to clarify the paper, as well as Peleg Michaeli for pointing out [Reference Panholzer21] and catching shortcomings in the first version of the paper.
Funding information
There are no funding bodies to thank relating to the creation of this article.
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
Added in proof
Peleg Michaeli has recently informed us that formula (1) was also independently proved by Alois Panholzer in 2020 [Reference Panholzer21].
