Independent sets in graphs with given minimum degree (Q456377)

Summary: The enumeration of independent sets in graphs with various restrictions has been a topic of much interest of late. Let \(i(G)\) be the number of independent sets in a graph \(G\) and let \(i_t(G)\) be the number of independent sets in \(G\) of size \(t\). Kahn used entropy to show that if \(G\) is an \(r\)-regular bipartite graph with \(n\) vertices, then \(i(G)\leq i(K_{r,r})^{n/2r}\). Zhao used bipartite double covers to extend this bound to general \(r\)-regular graphs. \textit{D. Galvin} [Discrete Math. 311, No. 20, 2105--2112 (2011; Zbl 1228.05228)] proved that if \(G\) is a graph with \(\delta(G)\geq \delta\) and \(n\) large enough, then \(i(G)\leq i(K_{\delta,n-\delta})\). In this paper, we prove that if \(G\) is a bipartite graph on \(n\) vertices with \(\delta(G)\geq\delta\) where \(n\geq 2\delta\), then \(i_t(G)\leq i_t(K_{\delta,n-\delta})\) when \(t\geq 3\). We note that this result cannot be extended to \(t=2\) (and is trivial for \(t=0,1)\). Also, we use Kahn's entropy argument and Zhao's extension to prove that if \(G\) is a graph with \(n\) vertices, \(\delta(G)\geq\delta\), and \(\Delta(G)\leq \Delta\), then \(i(G)\leq i(K_{\delta,\Delta})^{n/2\delta}\).