Alavi, Malde, Schwenk and Erdős 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 Levit and Mandrescu, concerning the final one-third of the independent set sequence of a König-Egerváry graph.
@article{10_37236_9896,
author = {Abdul Basit and David Galvin},
title = {On the independent set sequence of a tree},
journal = {The electronic journal of combinatorics},
year = {2021},
volume = {28},
number = {3},
doi = {10.37236/9896},
zbl = {1470.05121},
url = {http://geodesic.mathdoc.fr/articles/10.37236/9896/}
}
TY - JOUR
AU - Abdul Basit
AU - David Galvin
TI - On the independent set sequence of a tree
JO - The electronic journal of combinatorics
PY - 2021
VL - 28
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/9896/
DO - 10.37236/9896
ID - 10_37236_9896
ER -
%0 Journal Article
%A Abdul Basit
%A David Galvin
%T On the independent set sequence of a tree
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9896/
%R 10.37236/9896
%F 10_37236_9896
Abdul Basit; David Galvin. On the independent set sequence of a tree. The electronic journal of combinatorics, Tome 28 (2021) no. 3. doi: 10.37236/9896
