\documentclass[12pt]{article} \usepackage{e-jc} % preamble (fold) \usepackage{amsmath,amssymb,amsthm} \usepackage{graphicx} \newtheorem{problem}{Problem} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{porism}[theorem]{Porism} \newtheorem{conjecture}{Conjecture} {\theoremstyle{definition} \newtheorem{claim}{Claim} \newtheorem{remark}{Remark} \newtheorem*{definition}{Definition} \newtheorem{example}{Example} \newtheorem*{algorithm}{Algorithm} } \newcommand{\K}{K_{\delta,n-\delta}} \newcommand{\Kdd}{K_{\delta,\Delta}} \newcommand{\de}{\delta} \newcommand{\De}{\Delta} \newcommand{\I}{\mathcal{I}} \newcommand{\J}{\mathcal{J}} \newcommand{\Lt}{\Lambda_t} \newcommand{\X}{\mathbf{X}} \newcommand{\Y}{\mathbf{Y}} \newcommand{\Z}{\mathbf{Z}} \newcommand{\Q}{\mathbf{Q}} \newcommand{\A}{\mathcal{A}} \newcommand{\R}{\mathbb{R}} \newcommand{\wo}{\setminus} \newcommand{\up}[1]{\left\lceil{#1}\right\rceil} \newcommand{\down}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\abs}[1]{\left|{#1}\right|} \newcommand{\rabs}[1]{\bigl|{#1}\bigr|} \newcommand{\card}{\#} \newcommand{\set}[1]{\left\{{#1}\right\}} \newcommand{\setof}[2]{\left\{{#1}\,:\,{#2}\right\}} \newcommand{\of}{\subseteq} \newcommand{\powerset}{\mathcal{P}} \newcommand{\st}{^{\rm st}} \newcommand{\intersect}{\bigcap} \newcommand{\union}{\bigcup} \newcommand{\symd}{\bigtriangleup} \newcommand{\adj}{\sim} \newcommand{\nadj}{\not\adj} \newcommand{\disj}{\cup} \newcommand{\nset}[1][n]{\left[{#1}\right]} \newcommand{\0}{\emptyset} \newcommand{\1}{\mathds{1}} \newcommand{\given}{\mid} \renewcommand{\P}{\mathbb{P}} \newcommand{\E}{\mathbb{E}} \DeclareMathOperator{\iso}{iso} \DeclareMathOperator{\range}{range} \DeclareGraphicsRule{*}{mps}{*}{} \title{Independent sets in graphs with given minimum degree} \author{James Alexander\thanks{Supported by The Margaret and Herman Sokol Graduate Summer Research Fellowship.}\\ \small Montclair State University\\[-0.8ex] \small\tt alexanderj1@mail.montclair.edu\\ \and Jonathan Cutler\\ \small Montclair State University\\[-0.8ex] \small\tt jonathan.cutler@montclair.edu\\ \and Tim Mink\\ \small Montclair State University\\[-0.8ex] \small\tt minkt1@mail.montclair.edu } \date{\dateline{2011}{2012}\\ \small Mathematics Subject Classifications: 05C69, 05C30, 05C35} % preamble (end) \begin{document} \maketitle \begin{abstract} 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 $\de(G)\geq \de$ and $n$ large enough, then $i(G)\leq i(\K)$. In this paper, we prove that if $G$ is a bipartite graph on $n$ vertices with $\de(G)\geq\de$ where $n\geq 2\de$, then $i_t(G)\leq i_t(\K)$ 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, $\de(G)\geq\de$, and $\De(G)\leq \De$, then $i(G)\leq i(\Kdd)^{n/2\de}$. \end{abstract} \section{Introduction} % (fold) \label{sec:introduction} The study of independent sets in various classes of graphs has been a topic of much recent interest. For a graph $G$, we let $\I(G)$ be the set of independent sets of $G$ and $i(G)=\abs{\I(G)}$. Kahn \cite{K01} made a breakthrough on these problems when he proved the following result with a beautiful entropy argument. \begin{theorem}[Kahn]\label{thm:kahn} If $G$ is an $r$-regular bipartite graph on $n$ vertices with $r\geq 1$, then \[ i(G)\leq i(K_{r,r})^{n/2r}=\left(2^{r+1}-1\right)^{n/2r}. \] \end{theorem} In fact, Kahn proved a stronger result for weighted independent sets. Galvin and Tetali \cite{GT} generalized Theorem~\ref{thm:kahn} to homomorphisms and, in the process, extended Kahn's weighted independent sets result. Zhao \cite{Z} extended Theorem~\ref{thm:kahn} to all $r$-regular graphs using the bipartite double cover of a graph. Given a graph $G$, define the \emph{bipartite double cover} of $G$, denoted $G\times K_2$, to be the graph with vertex set $V(G)\times \set{0,1}$ with $(u,i)\sim (v,j)$ if and only if $uv\in E(G)$ and $i\neq j$. The key lemma of Zhao \cite{Z} was the following. \begin{lemma}[Zhao]\label{lem:zhao} If $G$ is any graph, then \[ i(G)^2\leq i(G\times K_2), \] with equality if and only if $G$ is bipartite. \end{lemma} The problem of maximizing the number of independent sets among graphs in other classes has also been well-studied. If we consider graphs on $n$ vertices and $m$ edges, then the answer follows from the Kruskal-Katona theorem \cite{K63,K68}. Define the \emph{lex graph} with $n$ vertices and $m$ edges, denoted $L(n,m)$, to be the graph with vertex set $[n]$ and edge set consisting of an initial segment of size $m$ of $\binom{[n]}2$ under the lexicographic ordering. (Recall that for distinct sets $A,B\subset \mathbb{Z}$, we say $A0$. There is a $n(\de)$ such that if $n\geq n(\de)$ and $G$ is a graph with $n$ vertices and minimum degree at least $\de$, then \[ i(G)\leq i(\K), \] with equality if and only if $G=\K$. \end{theorem} In the same paper, Galvin conjectured the following. \begin{conjecture}[Galvin]\label{conj:galvin} If $G$ is a graph on $n$ vertices with minimum degree at least $\de$, where $n$ and $\de$ satisfy $n\geq 2\de$, then \[ i(G)\leq i(\K). \] \end{conjecture} One of the main results of this paper is a ``level sets'' version of this conjecture for bipartite graphs. We let $\I_t(G)=\setof{I\in \I(G)}{\abs{I}=t}$ and $i_t(G)=\abs{\I_t(G)}$. Note that $i_2(G)=\binom{n}2-e(G)$, and so maximizing $i_2(G)$ corresponds to minimizing $e(G)$. Thus, if we are interested in maximizing $i_2(G)$ where $G$ is a graph with $n$ vertices and minimum degree $\de$, we simply want to make $G$ ``as regular as possible'' and so, it is not the case in general that $i_2(G)\leq i_2(\K)$ for $G$ a graph with $n$ vertices and minimum degree $\de$. Galvin \cite{G11} was able to prove that $K_{1,n-1}$ is the unique maximizer for $i_t(G)$ with $t\geq 3$ among graphs with minimum degree one. We conjecture that this is true for all $\de$. \begin{conjecture}\label{conj:level} Let $n$, $\de$, and $t$ be positive integers with $n\geq 2\de$ and $t\geq 3$. If $G$ is a graph on $n$ vertices with minimum degree at least $\de$, then \[ i_t(G)\leq i_t(\K), \] with equality if and only if $G=\K$. \end{conjecture} The main result of this paper is to prove Conjecture~\ref{conj:level} for bipartite graphs. \begin{theorem}\label{thm:main} Let $n$, $\de$, and $t$ be positive integers with $n\geq 2\de$ and $t\geq 3$. If $G$ is a bipartite graph on $n$ vertices and minimum degree at least $\de$, then \[ i_t(G)\leq i_t(\K), \] with equality if and only if $G=\K$. \end{theorem} Even among bipartite graphs it is, in general, not the case that $\K$ maximizes the number of independent sets of size two. If $n\geq 2\de+2$, we know that $K_{\de+1,n-\de-1}$ has fewer edges (and thus more independent sets of size two) than $\K$. In Section~\ref{sec:main}, we will prove Theorem~\ref{thm:main} along with some related results. For example, we can prove that the bipartite case of Conjecture~\ref{conj:galvin} follows from the above. \begin{corollary}\label{cor:allind} Suppose $n$ and $\de$ are positive integers with $n\geq 2\de$. If $G$ is an $n$-vertex bipartite graph with minimum degree at least $\delta$, then $i(G) \leq i(K_{\delta,n-\delta})$ with equality if and only if $G=\K$. \end{corollary} In a related question, one might hope to get a bound on the number of independent sets in a graph in terms of its minimum \emph{and maximum} degrees. The following conjecture was made by Kahn; see \cite{GZ}. We let $\iso(G)$ be the number of isolated vertices in a graph $G$. \begin{conjecture}[Kahn] If $G$ is any graph, then \[ i(G)\leq 2^{\iso(G)} \prod_{uv\in E(G)} \left(2^{d(u)}+2^{d(v)}-1\right)^{\frac{1}{d(u)d(v)}}. \] \end{conjecture} In Section~\ref{sec:diff}, we modify the entropy proof of Kahn \cite{K01} to get the following. \begin{theorem}\label{thm:kdd} If $G$ is a bipartite graph with bipartition $(A,B)$ such that $\de(G)\geq\de\geq 1$, then \[ i(G)\leq \prod_{v\in A} \left(2^{\de}+2^{d(v)}-1\right)^{1/\de}. \] \end{theorem} From this, it is easy to derive a general bound for $i(G)$ using Zhao's extension. \begin{corollary} If $G$ is a graph on $n$ vertices with $\de(G)\geq\de\geq 1$ and $\De(G)\leq \De$, then \[ i(G)\leq i(\Kdd)^{n/2\de}=(2^\de+2^\De-1)^{n/2\de}. \] \end{corollary} \begin{proof} The result follows from applying Theorem~\ref{thm:kdd}, then Lemma~\ref{lem:zhao}. \end{proof} While this result does give a bound for non-regular graphs, it does not seem to be sharp except when $G$ is regular (and so reduces to Theorem~\ref{thm:kahn}). In particular, it would nice to get a bound that would imply Conjecture~\ref{conj:galvin} in general. We conjecture the following. \begin{conjecture}\label{conj:ours} If $G$ is a graph on $n$ vertices with minimum degree at least $\de\geq 1$ and maximum degree at most $\De$, then \[ i(G)\leq i(\Kdd)^{\up{\frac{n}{\de+\De}}}=(2^\de+2^\De-1)^{\up{\frac{n}{\de+\De}}}. \] \end{conjecture} We are able to prove a slightly stronger result in the case when $\de=1$ and do so at the end of Section~\ref{sec:diff}. We adopt the convention that $K_{1,-1}$ is the null graph, so $i(K_{1,-1})=1$, and $K_{1,0}=K_1$, so $i(K_{1,0})=2$. Also, for an integer $w$ and a graph $G$, we write $wG$ for the disjoint union of $w$ copies of $G$. \begin{theorem}\label{thm:deone} If $n$ and $\De$ are integers with $1\leq\De\leq n-1$ and $q$ and $r$ are defined to be the unique integers such that $n=q(\De+1)+r$ and $0\leq r<\De+1$, then for any graph $G$ on $n$ vertices with $\de(G)\geq 1$ and $\De(G)\leq \De$, it is the case that \[ i(G)\leq i\left(qK_{1,\De}\cup i(K_{1,r-1})\right) = \left(2^\De+1\right)^q \down{2^{r-1}+1}. \] \end{theorem} \section{Proof of Theorem~\ref{thm:main} and related results} % (fold) \label{sec:main} In this section, we begin by proving Theorem~\ref{thm:main}. \begin{proof}[Proof of Theorem~\ref{thm:main}] Let $G$ be any $n$-vertex bipartite graph of minimum degree at least $\de$ with bipartition $G=A\cup B$. We may assume, without loss of generality, that $\abs{A}\leq \abs{B}$. We know that $\abs{A}\geq \de$, for if not, the vertices of $B$ could not satisfy the minimum degree requirement. Define the integer $c$ so that $\abs{A}=\de+c$. Thus, $\abs{B}=n-\de-c$ and $0\leq c\leq \frac{n-2\de}2$ since $\abs{A}\leq \abs{B}$. We know that independent sets in $G$ can be partitioned into those contained entirely in $A$, those contained entirely in $B$, and those containing vertices from both $A$ and $B$. Let $\Lt=\setof{I\in \I_t(G)}{I\cap A, I\cap B\neq \emptyset}$. So, as $A$ and $B$ are themselves independent sets, we have \[ i_t(G)=\binom{\abs{A}}t+\binom{\abs{B}}t+\abs{\Lt}=\binom{\de+c}t+\binom{n-\de-c}t+\abs{\Lt}. \] Our first goal will be to bound $\abs{\Lt}$. To this end, note that \begin{align} \abs{\Lt}&=\sum_{j=1}^{t-1} \abs{\setof{I\in \I_t(G)}{\abs{I\cap B}=j}} \nonumber\\ &=\sum_{j=1}^{t-1} \frac{1}{j}\sum_{b\in B} \abs{\setof{(b,I)}{I\in \I_t(G),\ \abs{I\cap B}=j,\ b\in I}}.\label{eqn:lt} \end{align} If $I\in \I_t(G)$ is such that $\abs{I\cap B}=j$ and $b\in I$ for some $b\in B$, then the vertices of $I\cap A$ cannot be in the neighborhood of $b$ and so, since $d(b)\geq \de$, there are at most $\abs{A}-\de=c$ vertices in $A$ from which to choose the $t-j$ vertices of $I\cap A$. Further, the vertices of $(I\cap B)\setminus \set{b}$ must not be in any of the neighborhoods of the vertices in $I\cap A$. The union of these neighborhoods must have size at least $\de$ and so there are at most $n-2\de-c-1$ vertices left to choose the $j-1$ vertices of $(I\cap B)\setminus \set{b}$. Thus, from (\ref{eqn:lt}), we have \begin{align} \nonumber \abs{\Lt}&=\sum_{j=1}^{t-1} \frac{1}{j}\sum_{b\in B} \abs{\setof{(b,I)}{I\in \I_t(G),\ \abs{I\cap B}=j,\ b\in I}}\\ \nonumber &\leq \sum_{j=1}^{t-1} \frac{1}{j}\sum_{b\in B} \binom{c}{t-j}\binom{n-2\de-c-1}{j-1}\\ &=\frac{n-\de-c}{n-2\de-c}\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{n-2\de-c}{j}.\label{eqn:lambat} \end{align} We will now use this bound on $\Lt$ to show that if $t\geq 3$, then the difference $i_t(\K)-i_t(G)$ is nonnegative. Using (\ref{eqn:lambat}), we see \begin{align*} i_t(\K)-i_t(G)&\geq \binom{n-\de}t+\binom{\de}t-\binom{n-\de-c}t-\binom{\de+c}t\\ & \qquad \qquad\qquad\qquad -\frac{n-\de-c}{n-2\de-c}\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{n-2\delta-c}{j}\\ &=\sum_{j=0}^{t} \binom{c}{t-j}\binom{n-\delta-c}{j}+\binom{\delta}{t}-\binom{n-\delta-c}t-\sum_{j=0}^{t} \binom{c}{t-j}\binom{\delta}{j}\\ &\qquad\qquad\qquad\qquad-\frac{n-\de-c}{n-2\de-c}\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{n-2\de-c}{j}\\ % &=\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{n-\delta-c}{j}-\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{\delta}{j}\\ % &\qquad\qquad\qquad\qquad-\frac{n-\de-c}{n-2\de-c}\sum_{j=1}^{t-1} \binom{c}{t-j}\binom{n-2\de-c}{j}\\ &=\sum_{j=1}^{t-1} \binom{c}{t-j}\left[\binom{n-\de-c}j-\binom{\de}j-\frac{n-\de-c}{n-2\de-c}\binom{n-2\de-c}{j}\right], \end{align*} where the first equality follows from Vandermonde's identity. Expanding and applying this again to the above, we have \begin{align} \nonumber \hspace{3em}&\hspace{-3em}i_t(\K)-i_t(G)\\ \nonumber &\geq\sum_{j=1}^{t-1} \binom{c}{t-j}\left[\sum_{l=1}^{j-1}\binom{\de}{l}\binom{n-2\de-c}{j-l}-\frac{\delta}{n-2\delta-c}\binom{n-2\de-c}{j}\right]\\ \nonumber &=-\binom{c}{t-1}\delta+ \binom{c}{t-2}\left[\delta(n-2\delta-c)-\frac{\delta}{n-2\delta-c}\binom{n-2\de-c}{2}\right]\\ &\qquad +\sum_{j=3}^{t-1} \binom{c}{t-j}\left[\sum_{l=1}^{j-1}\binom{\de}{l}\binom{n-2\de-c}{j-l}-\frac{\delta}{n-2\delta-c}\binom{n-2\de-c}{j}\right],\label{eqn:mess} \end{align} where the second equality holds because $t\geq 3$. We then note that \begin{align} \sum_{l=1}^{j-1}\binom{\de}{l}\binom{n-2\de-c}{j-l}&\geq \de\binom{n-2\de-c}{j-1}> \frac{\delta}{n-2\delta-c}\binom{n-2\de-c}{j}.\label{eqn:strict} \end{align} So, to show that $i_t(\K)-i_t(G)\geq 0$, it suffices to show that \[ \binom{c}{t-2}\left[\delta(n-2\delta-c)-\frac{\delta}{n-2\delta-c}\binom{n-2\de-c}{2}\right]-\binom{c}{t-1}\delta\geq 0. \] We have that the left hand side of the above is equal to \[ \delta\binom{c}{t-1}\left[\frac{t-1}{c-t+2}\left(\frac{n-2\delta-c+1}{2}\right)-1\right]\geq\delta\binom{c}{t-1}\left[\frac{(t-1)(c+1)}{2(c-t+2)}-1\right]. \] Further, since $t\geq 3$, we have $2(c-t+2)\leq 2(c-1)\leq (t-1)(c+1)$, and so the above expression is nonnegative. To show that $\K$ is the unique maximizer of $i_t(G)$, we note that in (\ref{eqn:strict}), the inequality is strict and so $i_t(G)>i_t(\K)$ unless $c=0$. This, in turn, implies that $G=\K$ since the only bipartite graph with $\abs{A}=\de$ satisfying the minimum degree condition is $\K$. \end{proof} \begin{remark} We note that in the case $t=2$, the equation (\ref{eqn:mess}) would become \begin{align} i_2(\K)-i_2(G)&\geq c\left[(n-\delta-c)-\delta-\frac{n-\delta-c}{n-2\delta-c}(n-2\delta-c)\right] = -c\delta, \label{eqn:two} \end{align} which makes sense, for any graph with less edges than $K_{\delta,n-\delta}$ should have more independent sets of size $2$. In particular, $e(K_{\delta,n-\delta})-e(G) \leq (n-\delta)\delta - (n-\delta-c)\delta = c\delta$ for any $G$ with minimum degree at least $\delta$. \end{remark} Theorem~\ref{thm:main} has several implications, some of which we present here. To begin, we prove that it implies Conjecture~\ref{conj:galvin} for bipartite graphs. In fact, it gives a bound on the independence polynomial for bipartite graphs with given minimum degree. For a graph $G$, we let the \emph{independence polynomial of $G$}, denoted $P(G,x)$, be the generating function for independent sets in $G$, i.e., \[ P(G,x)=\sum_{t=0}^{\alpha(G)} i_t(G) x^t, \] where $\alpha(G)$ is the independence number of $G$. We are able to show, as a corollary of the proof of Theorem~\ref{thm:main}, that $\K$ maximizes $P(G,x)$ for all $x\geq 1$. \begin{porism} If $G$ is an $n$-vertex bipartite graph with minimum degree at least $\delta$ where $n \geq 2\delta$, then $P(G,x) \leq P(\K,x)$ for all $x\geq 1$ with equality if and only if $G=\K$. \end{porism} \begin{proof} Recall that we assume that $G$ has bipartition $A\cup B$ with $\abs{A}\leq \abs{B}$. We again define the integer $c$ so that $\abs{A}=\de+c$. So, $\abs{B}=n-\de-c$ and $0\leq c\leq \frac{n-2\de}2$. Using the first two terms on the right hand side of (\ref{eqn:mess}) and also the bound in (\ref{eqn:two}), we see that \begin{align*} P(K_{\delta,n-\delta})-P(G,x) &= \sum_{t=0}^{\infty}(i_{t}(\K)-i_{t}(G))x^{t}\\ &\geq -c \delta x^{2}+\sum_{t=3}^{\infty}\left[-\delta\binom{c}{t-1}+\delta\binom{c}{t-2}\frac{n-2\delta-c+1}{2}\right]x^{t} \\ &=\sum_{t=2}^{\infty}-\delta\binom{c}{t-1}x^{t}+\sum_{t=2}^{\infty}\delta\frac{n-2\delta-c+1}{2}\binom{c}{t-1}x^{t+1}\\ &=\sum_{t=2}^{\infty}\delta\binom{c}{t-1}\left(-1+\frac{n-2\delta-c+1}{2}x\right)x^{t}. \end{align*} If $c=0$, then $\binom{c}{t-1}=0$, each term in the sum is zero. If $c \geq 1$, then each coefficient is at least $\delta\binom{c}{t-1}(-1+\frac{c+1}{2}x)$ as $c \leq \frac{n-2\delta}{2}$, which is clearly non-negative when $c,x \geq 1$. \end{proof} Letting $x=1$, Corollary~\ref{cor:allind} follows immediately. The next result of this section proves the level set version of Conjecture~\ref{conj:galvin} when $n=2\de$. \begin{theorem} If $G$ is any $2\delta$-vertex graph with minimum degree at least $\delta$, then $i_{t}(G) \leq i_{t}(\K)=i_t(K_{\de,\de})$ for all $t\geq 0$. \end{theorem} \begin{proof} We show this by induction on $t$. We have that $i_{1}(G) = i_{1}(K_{\delta,\delta})$ trivially. Assume that $i_{t}(G) \leq i_{t}(K_{\delta,\delta})$. Let $\J_t(G)=\setof{(v,I)}{v\in I,\ I\in \I_t(G)}$. Then we have \[ (t+1)i_{t+1}(G)=\abs{\J_{t+1}(G)}\leq (n-\de-t)i_t(G). \] So, \[ i_{t+1}(G)\leq \frac{n-\de-t}{t+1}i_t(G)\leq \frac{n-\de-t}{t+1} i_t(K_{\de,\de})= i_{t+1}(K_{\de,\de}), \] where the second inequality is by induction and the last step follows from $n=2\de$. \end{proof} We get the following corollary immediately. \begin{corollary} If $G$ is any $2\de$-vertex graph with minimum degree at least $\delta$, then for any $x\geq 0$, we have $P(G,x) \leq P(K_{\delta,\delta},x)$. \end{corollary} % section main (end) \section{A different bound} % (fold) \label{sec:diff} In this section, we prove a weak version of Conjecture~\ref{conj:ours} based on Kahn's entropy proof of Theorem~\ref{thm:kahn}. In fact, we use ideas from Galvin and Tetali's extension of Theorem~\ref{thm:kahn} to general homomorphisms \cite{GT}. The proof uses entropy methods and so we begin this section with a reminder of some basic facts about entropy. A more detailed introduction can be found in, for example, \cite{GP}. Throughout this section, all logarithms are base two. \begin{definition} The \emph{entropy} of a random variable $\X$ is defined by \[ H(\X)=\sum_{x} \P(\X=x)\log \frac{1}{\P(\X=x)}. \] For random variables $\X$ and $\Y$, the \emph{conditional entropy of $\X$ given $\Y$} is defined by \[ H(\X\given \Y)=\E(H(\X\given \Y=y))=\sum_{y} \P(\Y=y)H(\X\given \Y=y), \] where \[ H(\X\given \Y=y)=\sum_{x} \P(\X=x\given \Y=y)\log \frac{1}{\P(\X=x\given \Y=y)}. \] \end{definition} Entropy has some natural, and useful, properties, some of which we include in the following theorem. These results can all be found in, e.g., \cite{GP}. \begin{theorem}\label{thm:entprop}\ \begin{enumerate} \item If $\X$ is a random variable, then \[ H(\X)\leq \log\abs{\range(\X)} \] with equality if and only if $\X$ is uniform on its range. \item If $\X=(\X_1,\X_2,\ldots,\X_n)$ is a random sequence, then \[ H(\X)=H(\X_1)+H(\X_2\given \X_1)+\cdots+H(\X_n\given \X_1,\X_2,\ldots,\X_{n-1}). \] \item If $\X$, $\Y$, and $\Z$ are random variables, then \[ H(\X\given \Y,\Z)\leq H(\X\given \Y). \] \item If $\X$, $\Y$, and $\Z$ are random variables such that $\Y$ determines $\Z$, i.e., there is a function $f$ such that $f(\Y)=\Z$, then \[ H(\X\given \Y)\leq H(\X\given \Z). \] \end{enumerate} \end{theorem} Part (2) of the theorem is usually called the chain rule, and we will call part (1) the uniform bound and part (3) the information loss bound. We also make use of the following lemma, known as Shearer's Lemma \cite{CGFS}. If $\X=(\X_1,\X_2,\ldots,\X_n)$ is a random sequence and $A\of [n]$, we write $\X_A$ for the random sequence $(\X_a)_{a\in A}$. \begin{theorem}[Shearer] Let $\X=(\X_1,\X_2,\ldots,\X_n)$ be a random sequence and $\A$ be a collection of subsets of $[n]$ such that each element $i\in [n]$ is in at least $k$ elements of $\A$. Then \[ H(\X)\leq \frac{1}{k} \sum_{A\in \A} H(\X_A). \] \end{theorem} With the preliminaries of entropy out of the way, we will now prove Theorem~\ref{thm:kdd}. \begin{proof}[Proof of Theorem~\ref{thm:kdd}] Let $G=(V,E)$ be a bipartite graph with bipartition $(A,B)$ with $\abs{A}\leq \abs{B}$, so that $\abs{A}\leq n/2$. Choose an independent set $I$ uniformly from $I(G)$ and define a random vector $\X=(\X_v)_{v\in V}$ where $\X_v=1$ if $v\in I$ and $\X_v=0$ if $v\not\in I$. Since $I$ is chosen uniformly, we know that $H(\X)=\log i(G)$. We have \begin{align*} H(\X) &= H(\X_B)+H(\X_A\given \X_B)\\ &\leq \sum_{v\in A} \left[\frac{1}{\delta} H(\X_{N(v)})+H(\X_v\given \X_{N(v)})\right]\\ &=\frac{1}{\de}\sum_{v\in A} \left[H(\X_{N(v)})+\de H(\X_v\given \X_{N(v)})\right], \end{align*} where the first equality is the chain rule and the first inequality is by the information loss bound and Shearer's lemma with $\mathcal{A}=\setof{N(v)}{v\in A}$. We then note that if there is a vertex $w\in N(v)$ such that $\X_w=1$, then $\X_v$ must be $0$. We let $\Q_v=\setof{\X_w}{w\in N(v)}$ and, for $R\of \set{0,1}$, $q_v(R)=\P(\Q_v=R)$. Also, for $R\of \set{0,1}$, let $s_v(R)$ be the number of $R$-labelings of the vertices in $N_v$ in which all elements of $R$ are used (i.e., the number of surjections from $N_v$ to $R$) and $t_v(R)$ be the number of possible values of $\X_v$ given that $\Q_v=R$. Thus, $s_v(\set{0})=s_v(\set{1})=1$ and $s_v(\set{0,1})=2^{d(v)}-2$. We also have that $t_v(\set{0,1})=t_v(\set{1})=1$ and $t_v(\set{0})=2$. We then see that \begin{align} \nonumber \hspace{5em}&\hspace{-5em}\frac{1}{\de}\sum_{v\in A} \left[H(\X_{N(v)}+\de H(\X_v\given \X_{N(v)}))\right]\\ \nonumber &= \frac{1}{\de}\sum_{v\in A} \left[H(\Q_v)+H(\X_{N(v)}\given \Q_v)+\de H(\X_v\given \X_{N(v)}))\right]\\ \nonumber &\leq \frac{1}{\de} \sum_{v\in A} \sum_{\emptyset\neq R\of\set{0,1}} \biggl[q_v(R)\log \frac{1}{q_v(R)}+ q_v(R)H(\X_{N(v)}\given \Q_v=R)\\ %\nonumber &\qquad\qquad+ q_v(R)\de H(\X_v\given \X_{N(v)},\ \Q_v=R)\biggr]\label{eqn:condent} \\ %&\qquad\qquad \\ \nonumber &\leq \frac{1}{\de}\sum_{v\in A}\sum_{\emptyset\neq R\of\set{0,1}} \biggl[q_v(R)\log \frac{1}{q_v(R)} %\\ \nonumber %&\qquad\qquad + q_v(R)\log s_v(R) + q_v(R)\de \log t_v(R)\biggr]\\ \nonumber &= \frac{1}{\de}\sum_{v\in A}\sum_{\emptyset\neq R\of\set{0,1}} q_v(R)\log \frac{s_v(R)t_v(R)^{\de}}{q_v(R)}\\ \label{eqn:jen} &\leq \frac{1}{\de}\sum_{v\in A} \log\left[\sum_{\emptyset\neq R\of\set{0,1}} s_v(R)t_v(R)^{\de}\right]\\ \nonumber &= \frac{1}{\de} \sum_{v\in A} \log\left(2^{\de}+2^{d(v)}-1\right), \end{align} where we used the uniform bound on entropy repeatedly, the definition of conditional entropy and, since $\Q_v$ is determined by $\X_{N(v)}$, Theorem~\ref{thm:entprop} (4) for (\ref{eqn:condent}), and Jensen's inequality for (\ref{eqn:jen}). \end{proof} \begin{remark} We note that this argument can be generalized to homomorphisms into any image graph just as Galvin and Tetali proved \cite{GT}. This gives an upper bound on the number of homomorphisms to any image graph from a graph with given minimum and maximum degree. \end{remark} We conclude the paper by proving a slightly stronger version of the $\de=1$ case of Conjecture~\ref{conj:ours}, i.e., Theorem~\ref{thm:deone}. \begin{proof}[Proof of Theorem~\ref{thm:deone}] Let $G$ be a graph with minimum degree at least one and maximum degree at most $\De$. Form a graph $G'$ by removing edges from $G$ until every edge is incident to a vertex of degree one. Note that $i(G)\leq i(G')$ and also that $G'$ must be the disjoint union of stars. That is, \[ G'=\bigcup_{i=1}^k K_{1,n_i}, \] where $k+\sum_i n_i=n$. Suppose that $G'$ has two components that are not $K_{1,\De}$'s, i.e., there are $1\leq s