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 themaximum 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 ≥ 3, no n-vertex 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 δ ≤ 3 and t ≥ 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 ≥ 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.