Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2103.03800 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- 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.