Past exam of the mathematics course of the University of Cambridge / 2004 / iii / Paper 11 / 6

Use discrete Shannon entropy with base-two logarithms. The standard facts needed are the chain rule for information entropy, conditioning reduces entropy, nonnegativity of conditional entropy, and the fact that a uniform distribution on $M$ outcomes has Shannon entropy ${\log }_{2}M$.

Order the coordinates by their indices and put $h_j=H(X_j\mid X_1,\dots ,X_{j-1})\ge 0$. Applying the chain rule within a coordinate subset $A$ and then adding the missing earlier conditioning coordinates givesOn summing over the family, coordinate $j$ occurs at least $k$ times. Since each $h_j$ is nonnegative,This proves Shearer's inequality without any independence assumption on the coordinates. For countable alphabets, apply the finite-valued assertion to refining finite coordinate partitions; the standard monotone approximation of Shannon entropy gives the same result with extended values. Differential entropy is not the Shannon entropy intended here.

For the graph application, let its bipartition be $U,V$, with degrees $a$ on $U$ and $b$ on $V$, where $a,b\ge 1$. Choose an independent set uniformly from all $i(G)$ such sets, and let $X$ be its vertex-indicator vector. Then $H(X)={\log }_{2}i(G)$. For $v\in V$ put $Y_v=X_{N(v)}$ and $q_v=\mathrm{Pr}(Y_v=0)$.

Each vertex of $U$ belongs to exactly $a$ of these neighbourhoods. Shearer's inequality therefore gives $H(X_U)\le a^{-1}{\sum }_{v\in V}H(Y_v)$. Conditional on $X_U$, a vertex of $V$ is forced absent if any neighbor was selected, and otherwise is a free fair binary choice. There are no edges within $V$, and the conditional independent-set distribution is uniform on all these free choices. Henceand

There are $2^b$ possible neighborhood patterns. Give the zero pattern weight $w_0=2^a$ and every other pattern weight one. For its distribution $(p_y)$, concavity of the logarithm, or Jensen's inequality, givesThis establishes the local weighted-entropy estimate rather than just counting neighborhood patterns.

Edge counting gives $a|U|=b|V|$; together with $|U|+|V|=n$, it yields $|V|/a=n/(a+b)$. Exponentiating the Shannon entropy estimate proves the independent-set bound for biregular graphs:The complete bipartite graph $K_{b,a}$ has exactly $2^a+2^b-1$ independent sets, since one chooses a subset of one side and subtracts the double-counted empty set. Disjoint unions of such components attain equality. If exactly one degree parameter is zero, edge counting forces the graph to be edgeless and the displayed bound equals $2^n$, so it remains valid. If $a=b=0$, the denominator is undefined; the edgeless graph has exactly $2^n$ independent sets.