Distribution of independent sets in perfect $r$-ary trees
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914275718594560 |
|---|---|
| author | Iľkovič, Daniel Yan, Jun |
| author_facet | Iľkovič, Daniel Yan, Jun |
| contents | Given a graph $G$, the family of all independent sets of size $k$ containing a fixed vertex $v$ is called a star with centre $v$, and is denoted by $\mathcal{I}_G^k(v)$. Motivated by a generalisation of the Erdős-Ko-Rado Theorem to the setting of independent sets in graphs, Hurlbert and Kamat conjectured that for every tree $T$ and every $k$, the maximum of $|\mathcal{I}_T^k(v)|$ can always be attained by a leaf of $T$. While this conjecture turns out to be false in general, it is known to hold for specific families of trees like spiders and caterpillars. In this paper, we prove that this conjecture holds for a new family of trees, the perfect $r$-ary trees, by constructing injections from stars centred at arbitrary vertices to stars centred at leaves. We also show that the analogous property holds for every forest $\mathcal{T}$ that is the disjoint union of perfect trees with possibly varying sizes and arities, and determine the leaf that maximises $|\mathcal{I}_{\mathcal{T}}^k(v)|$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_16953 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Distribution of independent sets in perfect $r$-ary trees Iľkovič, Daniel Yan, Jun Combinatorics 05C69 (Primary) 05C05, 05C35 (Secondary) Given a graph $G$, the family of all independent sets of size $k$ containing a fixed vertex $v$ is called a star with centre $v$, and is denoted by $\mathcal{I}_G^k(v)$. Motivated by a generalisation of the Erdős-Ko-Rado Theorem to the setting of independent sets in graphs, Hurlbert and Kamat conjectured that for every tree $T$ and every $k$, the maximum of $|\mathcal{I}_T^k(v)|$ can always be attained by a leaf of $T$. While this conjecture turns out to be false in general, it is known to hold for specific families of trees like spiders and caterpillars. In this paper, we prove that this conjecture holds for a new family of trees, the perfect $r$-ary trees, by constructing injections from stars centred at arbitrary vertices to stars centred at leaves. We also show that the analogous property holds for every forest $\mathcal{T}$ that is the disjoint union of perfect trees with possibly varying sizes and arities, and determine the leaf that maximises $|\mathcal{I}_{\mathcal{T}}^k(v)|$. |
| title | Distribution of independent sets in perfect $r$-ary trees |
| topic | Combinatorics 05C69 (Primary) 05C05, 05C35 (Secondary) |
| url | https://arxiv.org/abs/2601.16953 |