Surprising identities for the greedy independent set on Cayley trees. (25th December 2022)
- Record Type:
- Journal Article
- Title:
- Surprising identities for the greedy independent set on Cayley trees. (25th December 2022)
- Main Title:
- Surprising identities for the greedy independent set on Cayley trees
- Authors:
- Contat, Alice
- 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.
- Is Part Of:
- Journal of applied probability. Volume 59:Number 4(2022)
- Journal:
- Journal of applied probability
- Issue:
- Volume 59:Number 4(2022)
- Issue Display:
- Volume 59, Issue 4 (2022)
- Year:
- 2022
- Volume:
- 59
- Issue:
- 4
- Issue Sort Value:
- 2022-0059-0004-0000
- Page Start:
- 1042
- Page End:
- 1058
- Publication Date:
- 2022-12-25
- Subjects:
- Cayley trees -- independent set -- greedy
05C80 -- 68W20 -- 60J10
519.2 - Journal URLs:
- https://www.cambridge.org/core/journals/journal-of-applied-probability ↗
- DOI:
- 10.1017/jpr.2022.3 ↗
- Languages:
- English
- ISSNs:
- 0021-9002
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library HMNTS - ELD Digital store
- Ingest File:
- 24278.xml