Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2409.15555 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918316127289344 |
|---|---|
| author | Galvin, David Sharpe, Courtney |
| author_facet | Galvin, David Sharpe, Courtney |
| contents | The independent set sequence of trees has been well studied, with much effort devoted to the (still open) question of Alavi, Malde, Schwenk and Erdős on whether the independent set sequence of a tree is always unimodal.
Much less attention has been given to the independent set sequence of hypertrees. Here we study some natural first questions in this realm. We show that the strong independent set sequences of linear hyperpaths and of linear hyperstars are unimodal (actually, log-concave). For uniform linear hyperpaths we obtain explicit expressions for the number of strong independent sets of each possible size, both via generating functions and via combinatorial arguments. We also consider the uniform linear hypercomb with $n$ edges on the spine, and show that its strong independent set sequence is unimodal except possibly for a portion of length $o(n)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_15555 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Independent set sequence of some linear hypertrees Galvin, David Sharpe, Courtney Combinatorics 05C30 The independent set sequence of trees has been well studied, with much effort devoted to the (still open) question of Alavi, Malde, Schwenk and Erdős on whether the independent set sequence of a tree is always unimodal. Much less attention has been given to the independent set sequence of hypertrees. Here we study some natural first questions in this realm. We show that the strong independent set sequences of linear hyperpaths and of linear hyperstars are unimodal (actually, log-concave). For uniform linear hyperpaths we obtain explicit expressions for the number of strong independent sets of each possible size, both via generating functions and via combinatorial arguments. We also consider the uniform linear hypercomb with $n$ edges on the spine, and show that its strong independent set sequence is unimodal except possibly for a portion of length $o(n)$. |
| title | Independent set sequence of some linear hypertrees |
| topic | Combinatorics 05C30 |
| url | https://arxiv.org/abs/2409.15555 |