Paper detail

Counting independent sets of a fixed size in graphs with a given minimum degree

Galvin showed that for all fixed $δ$ and sufficiently large $n$, the $n$-vertex graph with minimum degree $δ$ that admits the most independent sets is the complete bipartite graph $K_{δ,n-δ}$. He conjectured that except perhaps for some small values of $t$, the same graph yields the maximum count of independent sets of size $t$ for each possible $t$. Evidence for this conjecture was recently provided by Alexander, Cutler, and Mink, who showed that for all triples $(n,δ, t)$ with $t\geq 3$, no $n$-vertex {\em bipartite} graph with minimum degree $δ$ admits more independent sets of size $t$ than $K_{δ,n-δ}$. Here we make further progress. We show that for all triples $(n,δ,t)$ with $δ\leq 3$ and $t\geq 3$, no $n$-vertex graph with minimum degree $δ$ admits more independent sets of size $t$ than $K_{δ,n-δ}$, and we obtain the same conclusion for $δ> 3$ and $t \geq 2δ+1$. Our proofs lead us naturally to the study of an interesting family of critical graphs, namely those of minimum degree $δ$ whose minimum degree drops on deletion of an edge or a vertex.