Past exam of the mathematics course of the University of Cambridge / 2008 / iii / Paper 14 (Combinatorics)

Choose a uniformly random permutation of $[n]$ and take its initial segments. This produces a Uniformly random maximal chain in a Boolean lattice. A fixed $r$-set belongs to this chain with probability $r!(n-r)!/n!={\left(\genfrac{}{}{0ex}{}{n}{r}\right)}^{-1}$. An antichain meets the chain at most once, so taking the expected value of the number of meetings proves the LYM inequality:In particular the Sperner theorem bound follows by multiplying each summand by at most the largest binomial coefficient.

For the vector request, an ordering by ordinary subset need not work: distinct vectors may cancel. Instead, write $s_A={\sum }_{i\in A}{x}_i$ and construct a separated block decomposition for vector subset sums. A block is separated if distinct labeled members have subset sums at distance at least one. We prove that the labeled subsets of $[n]$ can be partitioned into separated blocks, withblocks of size $n-2r+1$, for $0\le r\le \lfloor n/2\rfloor$, with $\left(\genfrac{}{}{0ex}{}{n}{-1}\right)=0$.

For $n=0$ the one subset forms one block. Suppose a block of sums $z_1,\dots ,z_{\ell }$ has already been constructed for $n-1$ vectors, and let $x=x_n$. Choose $z_{\ast }$ minimizing $z_j\cdot x$ in the block. Replace the two copies of the block, with and without the new coordinate, by the following two blocks:The old labels are retained, so these partition the two copies even if equal sums occur in different blocks. Translation preserves separation in the first translated portion, and the second block is a subset of the old separated block. For the new cross pairs, Cauchy-Schwarz inequality givesThus both new blocks are separated. Their sizes are $\ell +1$ and $\ell -1$, omitting an empty block. The resulting size-profile recurrence is $b_{n,r}=b_{n-1,r}+b_{n-1,r-1}$, and Pascal's identity verifies the displayed binomial-difference formula, including the even middle boundary. The total number of blocks telescopes to $\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$.

A signed sum associated with $A=\{i:{ϵ}_i=1\}$ is $2s_A-{\sum }_i{x}_i$. If two signed sums lie in the open ball of radius one, their difference has norm less than two, so their subset sums have distance less than one. At most one can therefore lie in any separated block. Hence the Littlewood-Offord inequality isThe counting is by sign choices, not by distinct numerical values of the sums. The open-ball condition handles the equality-distance boundary correctly.

For the last request take real coefficients. Absorb their signs into the choices ${ϵ}_i$, so all coefficients are positive and at least one. A signed-sum real interval of length four corresponds to a subset-sum real interval of length two. A strict three-member inclusion chain $A⊊B⊊C$ would have $s_C-s_A\ge 2$, which cannot occur in that open real interval. Thus its set family is a k-Sperner family with $k=2$. Every maximal chain in a Boolean lattice meets it at most twice, yielding ${\sum }_r|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})\le 2$. Write $f_r=|{\mathcal{F}}_r|/(\genfrac{}{}{0ex}{}{n}{r})$, so $0\le f_r\le 1$ and ${\sum }_r{f}_r\le 2$. If $B_1\ge B_2$ are the two largest binomial coefficients and $f_{\ast }$ is the fraction at a largest level, then $|\mathcal{F}|\le B_1{f}_{\ast }+B_2(2-f_{\ast })\le B_1+B_2$. This proves the two-level Littlewood-Offord bound:It is the greatest possible number uniformly over choices of coefficients and center. For even $n=2m$, take every coefficient equal to one and center $a=-1$: the real interval $(-3,1)$ contains the sum levels $-2,0$, of multiplicities $\left(\genfrac{}{}{0ex}{}{n}{m-1}\right),\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. For odd $n=2m+1$, take center zero, giving levels $-1,1$, each of multiplicity $\left(\genfrac{}{}{0ex}{}{n}{m}\right)$. These attain the bound. For $n=0$ the only sign choice gives the separate maximum one. Attainment here is at the exhibited centers; it need not hold at every prescribed center.

Assume first $1\le t\le n$, and write $d=n-t$. The sharp nonuniform t-intersecting family bound isWe prove the bound by deriving the needed Kleitman diametric theorem. Identify subsets with binary words, with Hamming distance $|A△B|$. Let $D(n,d)$ be the two expressions above. A set family of Hamming diameter at most $d<n$ has size at most $D(n,d)$, as follows.

First apply downward coordinate compression: delete coordinate $i$ from a member only when its deletion is not already present. This preserves size and cannot increase the Hamming diameter. The only possible increased distance would be between a newly lowered member $A\setminus \{i\}$ and a retained member $B$ containing $i$. The deletion $B\setminus \{i\}$ must have belonged to the old set family, or $B$ would have been lowered too. The old pair $A,B\setminus \{i\}$ has precisely that increased distance, proving it was already allowed. Repeated downward compressions terminate in a down-set.

Next apply all elementary set shifts $S_{ij}$ with $i<j$. They preserve size and Hamming diameter. If shifting one member but retaining the other increased their distance, the retained member must contain $j$ but not $i$; its shifted partner was already present, and the old pair with that partner has the same distance. These shifts preserve the down-set property: a subset of a shifted member either was already present or is obtained by shifting its corresponding old subset. For a retained member, a subset cannot disappear, because the shifted partner of that subset is also a subset of the member or of its retained shifted partner. Repeated shifts terminate, since the sum of the selected coordinate labels decreases whenever a change occurs. We now have a shifted down-set $\mathcal{F}$ of the same size and Hamming diameter.

Split it into sections on $[n-1]$:The first section has Hamming diameter at most $d$. We claim the second has Hamming diameter at most $d-2$. For $X,Y\in {\mathcal{F}}_1$, downward closure gives $X\setminus Y,Y\in {\mathcal{F}}_1$. Compare $(X\setminus Y)\cup \{n\}$ with $Y\in {\mathcal{F}}_0$. Their distance is $|X\cup Y|+1$, so $|X\cup Y|\le d-1<n-1$. Choose $i<n$ outside their union. Shiftedness puts $X\cup \{i\}$ in ${\mathcal{F}}_0$, while $Y\cup \{n\}$ is a member of $\mathcal{F}$. Their distance is $|X△Y|+2$, proving the claim. For $d<2$ this argument forces ${\mathcal{F}}_1$ to be empty.

The induction now giveswhere negative-diameter set families are empty. The equality of the numerical expressions is Pascal's identity. The base case $d=0$ has at most one member. At the boundary $d=n-1$, at most one member of each complementary pair is allowed, giving $2^{n-1}$, which equals $D(n,n-1)$ by binomial symmetry. For the remaining cases $1\le d\le n-2$, both section bounds belong to smaller-dimensional induction cases. This completes the diametric proof.

For a $t$-intersecting set family,so the theorem applies. For $d=2q$, equality is attained by all sets of size at least $n-q$, since two such sets intersect in at least $n-2q=t$ elements. For $d=2q+1$, take all sets of size at least $n-q$, and also all $(n-q-1)$-sets avoiding one fixed point. Two of these smaller sets intersect in at least $2(n-q-1)-(n-1)=t$ points; a smaller and a larger set intersect in at least $t$; two larger sets intersect in at least $t+1$. The size of this set family isso it attains the odd bound. If $t=0$, the full power set is admissible; if $t>n$, the only admissible set family is empty.

Every maximal 1-intersecting set family attains $2^{n-1}$, for $n\ge 1$. Such a set family is an up-set, since adding a superset preserves set intersections. It contains $[n]$ and omits the empty set. It contains at most one member of any complementary pair. If neither of two nonempty complements $A,A^c$ were present, maximality would give a member $B$ disjoint from $A$; upward closure would then include $A^c$, a contradiction. Thus it chooses precisely one member of each complementary pair, as in maximal intersecting families choose one member of every complementary pair.

Not every maximal 2-intersecting set family attains the bound. On four points, let $\mathcal{A}=\{A:\{1,2\}\subseteq A\}$. This set family has four members and is maximal: every missing set meets its member $\{1,2\}$ in at most one point. The sharp bound is $1+4=5$, attained by all sets of size at least three. This proves maximal intersection does not imply maximum size.

All graphs here are finite and simple. For the strong graph product $G⊠H$, two distinct graph vertex pairs are adjacent if in each coordinate the entries are equal or adjacent. Use $G^{⊠m}$ for its strong graph power; the exam's $G^m$ means this product power, not the distance-based graph power. The Shannon capacity of a graph iswhere $\alpha$ is the independence number. Products of independent sets are independent, so $a_{r+s}\ge a_r{a}_s$ for $a_m=\alpha (G^{⊠m})$. To see why the limit exists, fix $r$ and write $m=qr+s$, $0\le s<r$. Then $a_m\ge a_r^q$, using $a_s\ge 1$ and $a_0=1$, so ${\mathrm{liminf}}_m(\log a_m)/m\ge (\log a_r)/r$. Take the supremum over $r$; the reverse upper bound holds termwise. This proves the required form of Fekete lemma. For the empty graph on no graph vertices one sets graph capacity zero separately.

Associativity of the strong product givesAn orthonormal representation of a graph assigns a real unit vector $u_v$ to each graph vertex, with $u_v\perp u_w$ whenever distinct graph vertices $v,w$ are nonadjacent. Adjacent graph vertices need not receive orthogonal vectors. A handle is a unit vector $h$. The handle formulation of the Lovász theta function iswith a zero denominator giving infinity. Representations may use any finite-dimensional Euclidean space. This is the usual Lovász number in its orthonormal-representation formulation.

For an independent set $I$, the vectors $u_v$, $v\in I$, are mutually orthonormal. Directly,If $T={\max }_v|h\cdot u_v{|}^{-2}$ is finite, every summand is at least $1/T$, giving $|I|\le T$. For a strong power, use the vectors and handleTheir norms are one. Nonadjacency of two distinct words means a coordinate has distinct nonadjacent entries, so the corresponding tensor inner product has a zero factor. The handle inner products satisfyApplying the preceding calculation gives $\alpha (G^{⊠m})\le T^m$. Taking roots, then the infimum over representations and handles, provesThis is the tensor-product capacity bound from an orthonormal representation, and the displayed projection calculation supplies Bessel inequality explicitly.

For $C_5$, label graph vertices by $\mathbb{Z}/5\mathbb{Z}$, with edges at differences $\pm 1$. The five wordsare independent in its strong square: a difference $\pm 1$ in the first coordinate produces a nonedge difference $\pm 2$ in the second, while a first-coordinate difference $\pm 2$ is already a nonedge. Hence $c(C_5)\ge \sqrt{5}$.

For the matching upper bound set $\rho =1/\sqrt{5}$, $h=(0,0,1)$, andEach vector is unit. For a nonedge, the angle difference is $\pm 4\pi /5$, andbecause $\cos (4\pi /5)=-(1+\sqrt{5})/4$ and $\rho =1/\sqrt{5}$. Thus these vectors form an orthonormal representation. The handle has $|h\cdot u_j{|}^2=\rho$, giving $\vartheta (C_5)\le 1/\rho =\sqrt{5}$. Together the two bounds prove the pentagon capacity code result

Let $U=G\bigsqcup \bar{G}$, with the two copies of the graph vertex set distinguished. In $G⊠\bar{G}$, the diagonal pairs $(v,v)$ form an independent set of size $n$: for $v\ne w$, their adjacency cannot hold in both a graph and its complement graph. There is another such diagonal set in $\bar{G}⊠G$. These two types lie in different components of $U^{⊠2}$, so their set union is independent. Thuswhich proves the printed bound.

A stronger complement-pair capacity gain will make the strict inequality transparent. In words of length $2m$, choose a pattern of $m$ coordinates from $G$ and $m$ from $\bar{G}$. Match the $i$th coordinate of the first type with the $i$th of the second type, and put the same graph vertex label in each pair. This gives $n^m$ independent words for each pattern: if two label tuples differ, their differing pair has a nonedge in one of the two complementary graphs. Codes belonging to distinct patterns are mutually nonadjacent, since some coordinate lies in different components of the disjoint set union. ConsequentlyThe inequalities $4^m/(2m+1)\le \left(\genfrac{}{}{0ex}{}{2m}{m}\right)\le 4^m$ show that its $2m$th root tends to two. ThereforeThis strengthens, rather than changes, the bound requested in the PDF.

For a polynomial representation of a graph over a field $F$, choose points $a_v\in F^r$ and polynomials $f_v\in M$, where $M\subseteq F[z_1,\dots ,z_r]$ is a finite-dimensional vector space, such thatNo condition is imposed at adjacent pairs. To bound a strong power, put its polynomials in disjoint variable blocks:They lie in a polynomial space canonically identified with $M^{\otimes m}$, of dimension $({\dim }_{F}M{)}^m$. For an independent set of words, evaluation of their polynomials at their associated point tuples is a diagonal matrix with nonzero diagonal: distinct words have a nonedge coordinate, which supplies a zero factor. The polynomials in that independent set are therefore linearly independent, since evaluating any linear relation at each tuple forces its corresponding coefficient to be zero. HenceThis is the polynomial form of the Haemers rank bound, proved here by evaluations and tensor products rather than assumed.

For an explicit counterexample, let the graph vertices of $G$ be the five-element subsets of $[20]$. Join distinct $A,B$ exactly when $|A\cap B|$ is odd. There are $n=\left(\genfrac{}{}{0ex}{}{20}{5}\right)=15504$ graph vertices. Over ${\mathbb{F}}_2$, take $a_B=1_B$ andAt the diagonal $f_A(a_A)=5=1$ in the field. At a distinct nonedge the set intersection is even, so $f_A(a_B)=0$. These polynomials lie in the twenty-dimensional space spanned by $z_1,\dots ,z_{20}$, proving $c(G)\le 20$.

Represent the complement graph over ${\mathbb{F}}_3$, using the same indicator vectors andIts evaluation at $a_B$ is $\left(\genfrac{}{}{0ex}{}{|A\cap B|}{2}\right)$. The diagonal value is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10=1$ modulo three. Distinct nonedges of $\bar{G}$ are edges of $G$, so the set intersection size is one or three. Their evaluations are respectively zero and $\left(\genfrac{}{}{0ex}{}{3}{2}\right)=3=0$ modulo three. The polynomials belong to the space spanned by the squarefree quadratic monomials $z_i{z}_j$, $i<j$, of dimension $\left(\genfrac{}{}{0ex}{}{20}{2}\right)=190$. Therefore $c(\bar{G})\le 190$.

The graph capacity inequalities are real-number bounds regardless of which field supplies the polynomial representation of a graph. Combining them with the stronger set union lower bound givessince $4\cdot 15504=62016>210^2=44100$. This proves nonadditivity of Shannon capacity for the graph just defined, with both individual upper bounds calculated explicitly.