file.pdf (228.17 kB)
Download file

Maximizing the Number of Independent Sets of a Fixed Size

Download (228.17 kB)
journal contribution
posted on 01.01.2014, 00:00 by Wenyang Gan, Po-Shen Loh, Benny Sudakov

Let it (G) be the number of independent sets of size t in a graph G. Engbers and Galvin asked how large it (G) could be in graphs with minimum degree at least δ. They further conjectured that when n ≥ 2δ and t ≥ 3, it (G) is maximized by the complete bipartite graph Kδ,n−δ . This conjecture has recently drawn the attention of many researchers. In this short note, we prove this conjecture.

History

Publisher Statement

© Cambridge University Press

Date

01/01/2014

Usage metrics

Exports