English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

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.  Galvin 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}$.

Independent Sets in Graphs with Given Minimum Degree