Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 / 3 / i / Solution

The Balister-Bollobas inequality says that if $r_i$ is the coordinate multiplicity in a multiset $\mathcal{A}$, and $L_j=\{i:r_i\ge j\}$, then ${\sum }_{j}H(X_{L_j})\le {\sum }_{A\in \mathcal{A}}H(X_A)$. More generally, each union-intersection compression decreases the entropy sum, by entropy submodularity.

For an exact $k$-cover define $A^{-}=[\min A-1]$ and $A^{+}=[\max A-1]\setminus A$. Compressing the family of $A\cup A^{-}$ gives the nested family of all $A^{-}$ together with $k$ full sets. Rearranging the resulting bound gives the upper Madiman-Tetali inequality. Conversely, compressing the family of all $A^{+}$ together with $k$ full sets gives the nested family of $A\cup A^{+}$, yielding the lower bound. In conditional-entropy notation these areThe coordinate multiplicities agree in each compression, because $\mathcal{A}$ is an exact $k$-cover. An equivalent proof expands the chain rule for information entropy contributions $h_i=H(X_i\mid X_{[i-1]})$ and uses conditioning reduces entropy. It also gives the upper inequality for arbitrary fractional covers and the lower inequality for fractional packings.