Two problems on independent sets in graphs

Let it(G) denote the number of independent sets of size t in a graph G. Levit and Mandrescu have conjectured that for all bipartite G the sequence (it(G))t≥0 (the independent set sequence of G) is unimodal. We provide evidence for this conjecture by showing that this is true for almost all equibipartite graphs. Specifically, we consider the random equibipartite graph G(n,n,p), and show that for any fixed p∈(0,1] its independent set sequence is almost surely unimodal, and moreover almost surely log-concave except perhaps for a vanishingly small initial segment of the sequence. We obtain similar results for p=Ω̃(n−1/2).We also consider the problem of estimating i(G)=∑t≥0it(G) for G in various families. We give a sharp upper bound on the number of independent sets in an n-vertex graph with minimum degree δ, for all fixed δ and sufficiently large n. Specifically, we show that the maximum is achieved uniquely by Kδ,n−δ, the complete bipartite graph with δ vertices in one partition class and n−δ in the other.We also present a weighted generalization: for all fixed x>0 and δ>0, as long as n=n(x,δ) is large enough, if G is a graph on n vertices with minimum degree δ then ∑t≥0it(G)xt≤∑t≥0it(Kδ,n−δ)xt with equality if and only if G=Kδ,n−δ.

► The stable set sequence of the random equibipartite graph is almost surely unimodal. ► Apart from perhaps a short initial segment, it is almost surely log-concave. ► The n vertex graph with minimum degree d with the most stable sets is K(d,n−d).