Surprising identities for the greedy independent set on Cayley trees. (25th December 2022)

• Record Type: Journal Article
• Authors: Contat, Alice
• Is Part Of: Journal of applied probability. Volume 59:Number 4(2022)
• Page Start: 1042
• Page End: 1058
• Publication Date: 2022-12-25
• Subjects: Cayley trees -- independent set -- greedy; 05C80 -- 68W20 -- 60J10; 519.2
• DOI: 10.1017/jpr.2022.3
• Languages: English
• ISSNs: 0021-9002

Abstract

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.