We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
Surprising identities for the greedy independent set on Cayley trees.
- Authors
Contat, Alice
- 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 $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 that is of independent interest.
- Subjects
CAYLEY algebras; GEOMETRIC vertices; MARKOV spectrum; INDEPENDENT sets; GRAPH theory
- Publication
Journal of Applied Probability, 2022, Vol 59, Issue 4, p1042
- ISSN
0021-9002
- Publication type
Article
- DOI
10.1017/jpr.2022.3