





















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)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。