Maximizing the number of independent sets of a fixed size

Abstract

Let $i_t(G)$ be the number of independent sets of size $t$ in a graph $G$. Engbers and Galvin asked how large $i_t(G)$ could be in graphs with minimum degree at least $\hat{I}´$. They further conjectured that when $n\ge 2\hat{I}´$ and $t\ge 3$, $i_t(G)$ is maximized by the complete bipartite graph $K_{\hat{I}´,n-\hat{I}´}$. This conjecture has drawn the attention of many researchers recently. In this short note, we prove this conjecture.

5 pages