pith. machine review for the scientific record. sign in

arxiv: 1311.4147 · v2 · submitted 2013-11-17 · 🧮 math.CO

Recognition: unknown

Maximizing the number of independent sets of a fixed size

Authors on Pith no claims yet
classification 🧮 math.CO
keywords deltaconjecturegraphindependentnumbersetssizeasked
0
0 comments X
read the original 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\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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.