Surprising identities for the greedy independent set on Cayley trees

Abstract

We prove a surprising symmetry between the law of the size $G_n$ of the greedy independent set on a uniform Cayley tree ${\mathcal{T}}_n$ of size $n$ and that of its complement. We show that $G_n$ has the same law as the number of vertices at even height in ${\mathcal{T}}_n$ rooted at a uniform vertex. This enables us to compute the exact law of the $G_n$. We also give a Markovian construction of the greedy independent set, which highlights the symmetry of $G_n$ and whose proof uses a new Markovian exploration of rooted Cayley trees which is of independent interest.

18 pages, 7 figures

Cited by in corpus (1)

• Parking on Cayley trees & Frozen Erdös-Rényi