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

m a t h c a l 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

m a t h c a l 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.

Recommendations

Cites Work

Cited In (2)

This page was built for publication: Surprising identities for the greedy independent set on Cayley trees