Maximizing the number of independent sets of a fixed size

Wenying Gan, Po-Shen Loh, Benny Sudakov

Published 2013-11-17, updated 2014-01-09Version 2

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 $\delta$. They further conjectured that when $n\geq 2\delta$ and $t\geq 3$, $i_t(G)$ is maximized by the complete bipartite graph $K_{\delta, n-\delta}$. This conjecture has drawn the attention of many researchers recently. In this short note, we prove this conjecture.