Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 15 (Combinatorial Probability)

Use the uniform probability measure on the Boolean hypercube. In the Fourier-Walsh transform convention ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, write $f={\sum }_S{\alpha }_S{\chi }_S$ with ${\alpha }_S=\mathbb{E}[f{\chi }_S]$. For the indicator $f$, Parseval's identity givesThe flip-probability influence satisfies ${\beta }_i=4{\sum }_{S\ni i}{\alpha }_S^2$, and summing gives ${\sum }_{S\ne \varnothing }|S|{\alpha }_S^2=\frac{1}{4}{\sum }_i{\beta }_i$.

For $p=1+\delta \in (1,2)$, Beckner's inequality says $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_p$. Apply it to the discrete derivative of a Boolean function in coordinate $i$, viewed on the other $n-1$ coordinates. Its nonzero magnitude is $1/2$ and occurs with probability ${\beta }_i$, soSumming over $i$ gives the hypercontractive weighted influence bound

By the Cauchy-Schwarz inequality, ${\sum }_i{\beta }_i\le \sqrt{n{\sum }_i{\beta }_i^2}<\lambda$. The total influence identity in part (i) therefore gives $\boxed{\sum _{S\ne \varnothing }|S|{\alpha }_S^2<\lambda /4}$.

The Holder inequality gives ${\sum }_i{\beta }_i^{2/p}\le n^{1-1/p}({\sum }_i{\beta }_i^2{)}^{1/p}<{\lambda }^{2/p}{n}^{1-2/p}$. Substitute this into the hypercontractive weighted influence bound and multiply by $\delta$ to obtainas required. The version with ${\delta }^{|S|-1}$ is slightly stronger and will also be useful below.

Put $v=t(1-t)$. The assertion is trivial when $v=0$. Otherwise suppose it fails and set $L=\log n$, $\lambda =vL$, $\gamma =3\log L/L$, $\delta =1-\gamma$, $p=2-\gamma$ and $b=L/3$, with natural logarithms. For large $n$ these parameters lie in their required ranges. The high-level Fourier weight isFor $1\le s<b$, let $M_n=\max [s{\delta }^{s-1}{]}^{-1}$. The logarithm of this expression is a convex function of real $s$, so its maximum on $[1,b]$ is at an endpoint. Also ${\delta }^{1-b}/b\to 3$, since $-(b-1)\log (1-\gamma )=\log L+o(1)$. Hence $M_n$ is bounded. The stronger inequality in part (ii) givesDivide by $v$. Because $0<v\le 1/4$ and $2/p>1$, the factor $v^{2/p-1}$ is at most one. The remaining factor is $L^{2/p}{e}^{-\gamma L/p}=L^{-1/2+o(1)}\to 0$. Thus the low-level weight is $o(v)$ uniformly in $t$. Adding both parts contradicts ${\sum }_{S\ne \varnothing }{\alpha }_S^2=v$ for sufficiently large $n$. This proves the squared-influence logarithmic lower bound

The uniform cover inequality states that for a positive-volume body $K\subset {\mathbb{R}}^n$ and a multiset $\mathcal{A}$ in which each coordinate occurs exactly $k$ times, $\boxed{|K{|}^k\le \prod _{A\in \mathcal{A}}|K_A|}$, where $K_A$ is its coordinate projection and volumes use the corresponding dimensions.

To deduce the box theorem, maximize ${\sum }_i{x}_i$ subject to ${\sum }_{i\in A}{x}_i\le \log |K_A|$ for every nonempty $A\subseteq [n]$. This linear program is feasible and bounded above by the full-set constraint. Its dual minimizes ${\sum }_A{\lambda }_A\log |K_A|$ over nonnegative weights with ${\sum }_{A\ni i}{\lambda }_A=1$. For rational weights, clearing denominators gives an exact uniform cover, so the uniform cover inequality bounds that dual objective below by $\log |K|$. The same holds for all feasible weights by density of rational points in the rational constraint polyhedron. Strong duality makes the primal optimum at least $\log |K|$, while the full-set constraint makes it at most that value. An optimal solution therefore gives $b_i=e^{x_i}>0$ withThe axis-aligned box with these side lengths has the required volume and projection volumes.

Use the lexicographic embedding of a sumset: choose the least tuple $(s_1,\dots ,s_n)\in {\prod }_i{S}_i$ representing each distinct sum, and let $B$ be the set of those tuples. Then $|B|=|S|$. If two projections onto $A$ had the same partial sum but different tuples, replacing the larger projected tuple by the smaller one inside its full representative would preserve that full sum and improve its lexicographic order. This is impossible. Thus the summation map is injective on the projection $B_A$, giving $|B_A|\le |S_A|$.

Replace every integer tuple of $B$ by the closed unit cube centered there. Their interiors are disjoint, and each coordinate projection is a union of unit cubes indexed by $B_A$, so the resulting body has volume $|B|$ and projected volume $|B_A|$. Apply the box theorem to obtainThe empty-set case uses $S_{\varnothing }=\{0\}$ and the empty product one.

Translate each two-element set by its smaller element to write $S_i=\{0,s_i\}$ with $s_i>0$. Translation does not affect any sumset cardinality. The pair-sum hypothesis forces the $s_i$ to be distinct, since equal values would give only three pair sums. Relabel so $s_1<\cdots <s_n$.

The distinct-positive-integer subset-sum lower bound has a short inductive proof. Suppose the first $n-1$ values have sum $P$, their largest subset sum. Adding $s_n$ creates the $n$ distinct sums $P+s_n$ and $P+s_n-s_i$ for $1\le i<n$. They are all above $P$, since $s_n>s_i$, and hence are all new. Starting with one sum for no elements and adding $1,2,\dots ,n$ new sums givesEquality is attained by $S_i=\{0,i\}$. Their subset sums fill every integer from zero to $n(n+1)/2$, by induction on $n$, and each pair of distinct positive values has four different pair sums. Thus the bound is best possible for every $n$.

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.

Choose an independent set uniformly and let $X_i$ indicate whether it contains vertex $i$. Then $H(X)={\log }_{2}i(G)$. Put $P_i=N(i)\cap [i-1]$ and $b_i=|P_i|$. Form a multiset containing every nonempty $P_i$ and $b_i$ copies of singleton $\{i\}$. Each coordinate $j$ occurs exactly $d_j$ times: in $d_j-b_j$ later-neighbor sets and in $b_j$ singleton copies.

For a set $A$ in this multiset, weight it by $1/{\min }_{j\in A}{d}_j$. These weights form a fractional cover, since each of the $d_j$ occurrences of $j$ has weight at least $1/d_j$. Apply the upper Madiman-Tetali inequality. Since every $j\in P_i$ precedes $i$, one has $d_j\ge d_i$; enlarging that set's weight to $1/d_i$ and removing conditioning only enlarges its nonnegative contribution. For singleton terms retain the useful conditioning on $P_i$. ThusFor $b_i>0$, let $q_i=\mathbb{P}(X_{P_i}=0)$. Every nonzero neighbor assignment forces $X_i=0$, while the all-zero assignment allows at most two values. The maximum entropy on a finite alphabet givesThe last inequality is the binary entropy maximization formula, or the log-sum inequality, with group sizes $2^{b_i}$ and $2^{b_i}-1$. If $b_i=0$ the whole term is zero, also agreeing with the formula. Exponentiating proves the degree-ordered independent-set entropy bound

Take $G=K_{d,d}$ for any $d\ge 1$, ordering one part before the other. Every degree is $d$; the first $d$ vertices have $b_i=0$, the last $d$ have $b_i=d$. The bound is therefore $(2^{d+1}-1{)}^{d/d}=2^{d+1}-1$. An independent set lies entirely in one part, giving $2^d+2^d-1$ possibilities after subtracting the twice-counted empty set. Hence equality holds. Disjoint unions of such ordered components give further equality examples.

Choose $X$ uniformly among the $n$ vertices. For each covering graph use a proper binary coloring, and fill the color of an absent vertex with an independent random color having the same law as the color of a uniform vertex of that graph, as in the question's construction. Write $h_i$ for that color information entropy, so $h_i\le 1$. The marginal distribution of $Y_i$ is precisely this color law, and the variables $Y_i$ are conditionally independent given $X$: present colors are deterministic and absent colors use independent dummy draws. ThereforeAny two distinct vertices are joined in some $G_i$ and have different forced colors there. They cannot both be compatible with the same observed color vector, so $H(X\mid Y_1,\dots ,Y_{\ell })=0$. The mutual information identity now givesand hence $\boxed{\sum _i|G_i|\ge n{\log }_{2}n}$.

For each $G_i$, choose a proper coloring minimizing its color information entropy $h_i$, so its coloring entropy weight is $w(G_i)=|G_i|h_i$. A minimizing coloring exists: up to relabeling there are only finitely many partitions of its finite vertex set into color classes. Use independent dummy colors with the same marginal law as before. The marginal and conditional-entropy calculations in part (i) remain valid for any number of colors. Also any pair of vertices is joined in some covering graph and hence receives different forced colors there, so the full color vector still determines $X$. Thus

Use the same random variables for the edge cover of $G$. For a fixed color vector, any two compatible candidate vertices cannot be adjacent: an edge in a covering graph would force different colors at that coordinate. Thus the compatible candidates form an independent set and there are at most $\alpha$ of them. By the maximum entropy on a finite alphabet, $H(X\mid Y_1,\dots ,Y_{\ell })\le {\log }_2\alpha$.

Consequently the mutual information is at least ${\log }_{2}n-{\log }_2\alpha$, while the marginal and conditional-entropy bounds from part (i) make it at most $n^{-1}{\sum }_{i}w(G_i)$. The entropy weight of a graph cover bound follows: