On the independent set sequence of a tree (Q2048555)

Summary: \textit{Y. Alavi} et al. [Congr. Numerantium 58, 15--23 (1987; Zbl 0679.05061)] asked whether the independent set sequence of every tree is unimodal. Here we make some observations about this question. We show that for the uniformly random (labelled) tree, asymptotically almost surely (a.a.s.) the initial approximately 49.5\% of the sequence is increasing while the terminal approximately 38.8\% is decreasing. Our approach uses the Matrix Tree Theorem, combined with computation. We also present a generalization of a result of \textit{V. E. Levit} and \textit{E. Mandrescu} [Lect. Notes Comput. Sci. 2731, 237--256 (2003; Zbl 1039.05022)], concerning the final one-third of the independent set sequence of a König-Egerváry graph.