Surprising identities for the greedy independent set on Cayley trees. (25th December 2022) - 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 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 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.