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 $\delta$. They further conjectured that when $n\ge 2\delta$ and $t\ge 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.

5 pages

References in corpus (1)

• The Number of Independent Sets in a Regular Graph

Cited by in corpus (8)

• Supersaturation for subgraph counts
• Tree densities in sparse graph classes
• Many cliques with few edges and bounded maximum degree
• Extremal graphs with local covering conditions
• Tight bounds on the coefficients of partition functions via stability
• A simple proof of the Gan-Loh-Sudakov conjecture
• Maximizing the density of $K_t$'s in graphs of bounded degree and clique number
• Many cliques in bounded-degree hypergraphs