Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 12 (Combinatorics)

For $1\le r\le n$ and a rank-$r$ uniform set family $\mathcal{F}$, let $\partial \mathcal{F}$ be its lower shadow. Count pairs $(B,A)$ with $A\in \mathcal{F}$, $B\subset A$ and $|B|=r-1$. Every $A$ contributes $r$ pairs, whereas each shadow member lies in at most $n-r+1$ rank-$r$ sets. ThusThis is the Local LYM inequality. Complementation gives the upper-shadow form $|\nabla \mathcal{F}|/\left(\genfrac{}{}{0ex}{}{n}{r+1}\right)\ge |\mathcal{F}|/(\genfrac{}{}{0ex}{}{n}{r})$ for $r<n$.

To deduce the LYM inequality, let $\mathcal{A}$ be an antichain, ${\mathcal{A}}_r$ its rank-$r$ part, and $U_r$ all rank-$r$ sets containing some member of $\mathcal{A}$. For $r\ge 1$,The union is disjoint because an antichain member cannot contain a smaller member; every other set of $U_r$ contains a rank-$(r-1)$ superset of its smaller witnessing member. Apply the upper local inequality and put $u_r=|U_r|/(\genfrac{}{}{0ex}{}{n}{r})$:Since $u_0=|{\mathcal{A}}_0|$ and $u_n\le 1$, summing givesThus the deduction uses the local inequality explicitly, rather than quoting a separate maximal-chain argument.

Let $M=\left(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor }\right)$, the largest rank size. The LYM sum is at least $|\mathcal{A}|/M$, proving the Sperner theorem bound. If $|\mathcal{A}|=M$, equality forces all its members onto ranks with binomial coefficient $M$. For even $n$, there is only the middle rank, so the family is that whole rank.

For $n=2m+1$, only ranks $m,m+1$ are possible, each of size $M$. Let $\mathcal{B}={\mathcal{A}}_{m+1}$. Antichainness gives ${\mathcal{A}}_m\cap \partial \mathcal{B}=\varnothing$, and local LYM gives $|\partial \mathcal{B}|\ge |\mathcal{B}|$. Since the two antichain parts together have size $M$, equality must hold. The inclusion graph between these ranks is $(m+1)$-regular on each side. Its edges from $\mathcal{B}$ already number $(m+1)|\mathcal{B}|$, so equality leaves no edge from $\partial \mathcal{B}$ to the complementary upper vertices.

The graph is connected: exchanging one element between two $m$-sets joins them through their $(m+1)$-element union, and successive exchanges connect all lower vertices; every upper vertex has a lower neighbour. Consequently $\mathcal{B}$ is either empty or the entire upper rank. This connectedness of adjacent-level incidence in a Boolean lattice excludes mixed extremizers. HenceThere is one choice for even $n$ and two for odd $n$. For $n=0$, the sole maximum family is $\{\varnothing \}$, agreeing with this description.

Proceed by induction on the ground-set size, starting with the one-element chain $\{\varnothing \}$ in the Boolean lattice on no coordinates. Suppose a symmetric chain decomposition of a Boolean lattice on $[n]$ has been constructed. Write one of its chains asOn adjoining the new coordinate $v=n+1$, replace its two copies byand, when nonempty,The first chain has endpoint ranks $r,n-r+1$, summing to $n+1$. The second has endpoint ranks $r+1,n-r$, also summing to $n+1$. Both are saturated chains, increasing rank by one at every step. If the original chain was a singleton, the second chain is omitted.

These new chains are disjoint: the first contains every old set without $v$ and just the last old set with $v$; the second contains precisely the remaining old sets with $v$. Thus together they cover both lifted copies of the old chain. Different old chains have disjoint copies, so performing this construction for each yields a partition of all subsets of $[n+1]$ into symmetric chains. This completes the induction and proves a symmetric chain partition exists for every $n$.

Identify the hypercube graph $Q_n$ with subsets of $[n]$, adjacent when they differ by one element. Write $N(\mathcal{F})$ for a family's closed vertex neighbourhood. The simplicial order on the discrete cube orders first by size and then, within a rank, by lexicographic order: the least element of a symmetric difference belongs to the earlier set. The Harper theorem says that if $I$ is the initial simplicial segment with $|I|=|\mathcal{F}|$, thenEquivalently this minimizes the external vertex boundary at fixed cardinality. This is the vertex-isoperimetric assertion, distinct from the edge version in Question 3.

Here is the deduction of Kruskal-Katona theorem. For a family $\mathcal{B}\subseteq [n{]}^{(k)}$, adjoin every lower rank and set $\mathcal{D}=[n{]}^{(<k)}\cup \mathcal{B}$. For $k\ge 1$,The corresponding simplicial initial segment is $[n{]}^{(<k)}\cup L$, where $L$ is the rank-$k$ lexicographic initial segment of size $|\mathcal{B}|$. Canceling the common lower-rank count in Harper's inequality gives $|\nabla \mathcal{B}|\ge |\nabla L|$. The rank-zero case is immediate by considering its two possible families.

To turn upper shadows into lower shadows, let $\rho (i)=n+1-i$ and $T(B)=\rho ([n]\setminus B)$. This bijection reverses inclusion and changes rank $k$ to $n-k$. If $B$ precedes $C$ in lex order, the largest element of $T(B)△T(C)$ belongs to $T(C)$, so $T(B)$ precedes $T(C)$ in colexicographic order. Also $T(\nabla \mathcal{B})=\partial (T\mathcal{B})$. Hence applying the upper-shadow conclusion to the transformed family proveswhere $C$ is the colex initial segment of the same size and rank as $\mathcal{A}$. This is the Kruskal-Katona lower-shadow theorem. A colex segment's shadow is itself a colex segment: split its sets by their largest element, giving a full initial block of the preceding ground set followed by an initial block with the new largest element. The same description holds one rank lower. Iteration therefore shows that colex segments minimize shadows at every lower rank. This proves the Harper theorem implies the Kruskal-Katona theorem deduction, including the necessary complement and coordinate reversal.

The Erdős-Ko-Rado theorem states that for $1\le r\le n/2$, every intersecting family $\mathcal{A}\subseteq [n{]}^{(r)}$ satisfiesThe family of all $r$-sets containing a fixed point attains the bound. We use the standard convention of positive ranks here.

For the first proof, let $\mathcal{B}$ be the complements of members of $\mathcal{A}$, at rank $k=n-r\ge r$, and let $\mathcal{S}$ be its rank-$r$ lower shadow. It is disjoint from $\mathcal{A}$, since $A\subseteq [n]\setminus A^{\prime }$ would make two family members disjoint. Suppose $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$. The colex rank-$k$ segment of that size contains every $k$-set on $[n-1]$ and at least one set containing $n$. Its rank-$r$ shadow therefore contains all $\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$ old $r$-sets and at least one new $r$-set containing $n$. The iterated Kruskal-Katona bound givesThen $|\mathcal{A}|+|\mathcal{S}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n}{r}\right)$, impossible for disjoint subfamilies of rank $r$. This proves the Erdős-Ko-Rado theorem from shadows.

For the second proof use the Katona circle method. In any cyclic ordering of the $n$ points, an intersecting collection of length-$r$ intervals has at most $r$ members. To prove this, rotate one selected interval to end at position $n$, so it occupies $n-r+1,\dots ,n$. Intervals ending at $r,\dots ,n-r$ miss it and cannot be selected. Among the remaining endpoints other than $n$, pair $j$ with $j+n-r$ for $1\le j\le r-1$. The two intervals in each pair are disjoint because $n\ge 2r$, so at most one can be selected. Including the fixed interval gives at most $1+(r-1)=r$.

Now count pairs consisting of a family member and a permutation in which it is a cyclic interval. A fixed $r$-set has $nr!(n-r)!$ such permutations: choose its final position, its internal order, and the order of the remaining points. Each of the $n!$ permutations contributes at most $r$ family intervals by the proved cyclic interval intersection bound. ThusThis is the required cyclic-ordering proof, with its interval lemma established explicitly.

Always true, for the ordinary positive-rank intersecting-family convention. The Erdős-Ko-Rado theorem bounds the family's size by $\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. In lexicographic order, the first exactly that many rank-$r$ sets are all those containing one. Therefore the initial segment of the given size is contained in that star and any two members intersect at one. This proves that lexicographic initial segments preserve ordinary intersection. Empty families cause no exception. If rank zero is admitted, its layer has just one set and replacement by either initial segment changes nothing, so all three preservation assertions at that rank hold trivially.

False in general. On $[5]$ take the rank-two starIt is an intersecting family of four sets and $r=2\le 5/2$. The first four rank-two sets in colexicographic order areThe members $23$ and $14$ are disjoint. Thus colexicographic replacement can destroy intersection, despite its shadow-minimizing property.

False in general. Take $n=8$, $r=4$, andIt is a Frankl family with $\left(\genfrac{}{}{0ex}{}{4}{3}\right)\left(\genfrac{}{}{0ex}{}{4}{1}\right)+\left(\genfrac{}{}{0ex}{}{4}{4}\right)=17$ members. Two members each use at least three of the first four points, so they share at least two of those points. Hence it is t-intersecting with $t=2$, and $r=n/2$.

The first fifteen rank-four sets in lexicographic order are precisely those containing $1,2$. The sixteenth is $1345$, which intersects the earlier set $1278$ only at one. Therefore the lex initial segment of size seventeen is not two-intersecting. This proves that lexicographic replacement can destroy two-intersection; an ordinary intersecting bound cannot justify preservation of higher-order intersection.

Use binary encoding $b(S)={\sum }_{i\in S}{2}^{i-1}$ for vertices of the hypercube graph, and write $I_m=\{S:b(S)<m\}$. Let $e(\mathcal{A})$ count edges with both endpoints in a family. The exact edge-isoperimetric theorem for binary initial segments, due to Harper, Lindsey, Bernstein and Hart, iswhere $s_2(j)$ is the number of ones in the binary expansion. Equivalently,The equality for $I_m$ follows by assigning each internal edge to its larger endpoint: each one-bit of that endpoint can be cleared, giving an earlier endpoint still in $I_m$. This is the exact extremal statement, stronger than the logarithmic entropy bound.

We prove it by induction on $n$. The case $n=1$ follows by checking sizes zero, one and two. Fix a coordinate $i$ and delete it from the two sections ${\mathcal{A}}_0,{\mathcal{A}}_1$. The edge count splits asReplace each section by a binary initial segment of the same size. By induction its internal edges cannot decrease. The two replacement segments are nested, so their intersection size is the smaller section size, at least the previous intersection size. Thus this section compression in binary order cannot decrease $e(\mathcal{A})$.

Repeatedly perform any nontrivial section compression. The sum ${\sum }_{S\in \mathcal{A}}b(S)$ strictly decreases each time: in a fixed section, the original numerical order is exactly the numerical order after deleting its fixed coordinate. This nonnegative integer potential ensures termination at a family compressed in every coordinate section.

Classify such a terminal family. If an absent vertex $S$ precedes a present vertex $T$, they cannot agree in any coordinate, because their common section is compressed and its earlier vertex would then have to be present. Hence $T=[n]\setminus S$. There can be no vertex strictly between them: if present, it would also have to be the complement of $S$; if absent, it would have to be the complement of $T$. Thus they are consecutive complementary binary integers, forcingNo other inversion is possible for the same reason. Therefore a terminal family is either a binary initial segment or the sole exceptional formThis exception has size $2^{n-1}$. For $n\ge 2$, compared with the half-cube $I_{2^{n-1}}$, it removes a vertex of internal degree $n-1$ and adds a vertex joined only to the retained empty set. Its edge count is thus $e(I_{2^{n-1}})-(n-1)+1\le e(I_{2^{n-1}})$. The $n=1$ case was already handled. Since compression never decreased edges, every original family has at most the initial segment's edge count. This proves the theorem, including the exceptional terminal configuration rather than assuming all compressed families are initial segments.

For the remaining requests it is useful to obtain the entropy proof of cube edge-isoperimetry, including its equality cases. Inductively a family of size $m$ satisfiesIndeed let the two sections have sizes $a\ge b\ge 0$, $m=a+b>0$. Their internal edges are bounded inductively and the crossing edges are at most $b$, soHere $0{\log }_{2}0=0$ and $H_2(t)=-t{\log }_{2}t-(1-t){\log }_2(1-t)$ is the binary entropy function. Its concavity and its endpoint values at zero and one-half give $H_2(t)\ge 2t$ for $0\le t\le 1/2$. This proves the bound, starting from the zero-dimensional cube.

Define the isoperimetric number of a graph bySince every cube vertex has degree $n$, the internal-edge bound giveswhen $|A|\le 2^{n-1}$. A coordinate half-cube has one crossing edge per vertex, attaining ratio one. Hence, for $n\ge 1$,

Now establish the equality cases of entropy cube edge-isoperimetry. Strict concavity of $H_2$ makes $H_2(t)>2t$ for $0<t<1/2$. Equality in the internal-edge bound therefore requires either one section to be empty, or two equal-size sections. In the equal-size case equality in the crossing bound forces the sections to coincide; each section must also attain its inductive internal-edge bound. Induction gives exactly coordinate subcubes: the empty-section case fixes the coordinate, and the coincident-section case frees it. Conversely every coordinate subcube attains that bound.

At size $m=2^{n-1}$, an edge boundary of size $m$ means $e(A)=\frac{1}{2}m(n-1)=\frac{1}{2}m{\log }_{2}m$, so these equality cases apply. The subcube has dimension $n-1$ and fixes precisely one coordinate. ThereforeThese $2n$ coordinate half-cubes are the only extremizers of the requested size.

The uniform modular Frankl-Wilson theorem states the following. Let $p$ be prime, let $L\subseteq {\mathbb{F}}_p$ have size $s$, and let $\mathcal{F}$ be a rank-$k$ family on $[N]$, with $0\le s\le \min \{k,N-k\}$. Assume $k\mathrm{mod}p\notin L$ and $|A\cap B|\mathrm{mod}p\in L$ for every distinct $A,B\in \mathcal{F}$. ThenThe restrictions concern distinct pairs; the diagonal size residue is explicitly excluded from $L$.

For each member $A$, over ${\mathbb{F}}_p$ form the intersection polynomialAt the characteristic vector $1_B$, its value vanishes when $B\ne A$ and is nonzero when $B=A$. Thus these functions are linearly independent on the whole rank-$k$ layer: evaluate any linear relation at each family member in turn. Replacing every positive power of $z_i$ by $z_i$ preserves all Boolean evaluations, so the functions are restrictions of multilinear polynomials of degree at most $s$.

We need the sharp low-degree evaluation rank on a uniform layer, not the larger whole-cube dimension ${\sum }_{j\le s}\left(\genfrac{}{}{0ex}{}{N}{j}\right)$. Let $M$ be the integer incidence matrix with rows indexed by subsets $S$ of size at most $s$, columns by rank-$k$ sets $B$, and entries $1_{S\subseteq B}$. Over the rationals, if $|S|=j\le s$, thenThis coefficient counts the possible $T$ inside each containing column set and is positive because $s\le k$. Consequently the degree-$s$ rows span all rows over $\mathbb{Q}$, giving rank at most $\left(\genfrac{}{}{0ex}{}{N}{s}\right)$. Every larger square minor is therefore the integer zero. Reducing those minors modulo $p$ shows the rank over ${\mathbb{F}}_p$ is also at most $\left(\genfrac{}{}{0ex}{}{N}{s}\right)$. This transfer avoids dividing by a binomial coefficient that might vanish modulo $p$. The independent functions $f_A$ lie in this row space, so their number is at most its rank. This proves the theorem in full.

For the requested forbidden-intersection application, split $\mathcal{A}$ into sets containing coordinate one and sets avoiding it. In the first part, delete one. Distinct original sets have intersection size between one and $2p-1$, excluding $p$. Their reduced intersections therefore lie between zero and $2p-2$, excluding $p-1$, so their residues belong to $L=\{0,\dots ,p-2\}$. The reduced set size is $2p-1$, whose residue is $p-1\notin L$. Frankl-Wilson on the ground set of size $4p-1$ bounds this part by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

For the avoiding part, first complement every set. The complements contain one, retain size $2p$, and satisfyDelete one and apply the same argument. The complement splitting for forbidden midpoint intersections yields the stronger boundThe split is essential: a family may contain complementary pairs with intersection zero, preventing direct use of $L=\{1,\dots ,p-1\}$ on the original layer.

The Borsuk conjecture asserted that a bounded subset of ${\mathbb{R}}^d$ of positive diameter can be partitioned into $d+1$ subsets of strictly smaller diameter. Here is the Kahn-Kalai counterexample to the Borsuk conjecture, implemented by balanced cut vectors. For each $X\in [4p{]}^{(2p)}$, define $v_X\in {\mathbb{R}}^{\left(\genfrac{}{}{0ex}{}{4p}{2}\right)}$ whose coordinate indexed by an unordered pair $\{i,j\}$ is one when exactly one endpoint lies in $X$, and zero otherwise. Complementary sets give the same cut. Choose the representative with $1\in X$, obtaining exactlydistinct points: a cut determines its two parts, and fixing the side containing one removes its only ambiguity. Every cut has $(2p{)}^2=4p^2$ occupied coordinates, so all points lie in the affine hyperplane with coordinate sum $4p^2$. Its dimension isWe can identify this hyperplane isometrically with ${\mathbb{R}}^d$; no claim of full affine span is needed.

For two side sets with $t=|X\cap Y|$, their symmetric difference has $4p-2t$ points. The two cuts disagree exactly on pairs with one endpoint in that symmetric difference, giving the balanced cut-vector distance formulaThe diameter is $2p$, attained exactly when $t=p$; such pairs exist even among representatives containing one. Thus a smaller-diameter part contains no pair with side intersection $p$. Since all representative sets already contain one, deleting that common coordinate and applying the preceding Frankl-Wilson argument bounds each part by $\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$. There is no extra factor two at this step. This is the cut construction described in the original Kahn-Kalai paper; the distance and part-size calculations above give the required justification directly.

An explicit choice is $p=13$. The point set lies in dimensionThe exact counts areTheir ratio requires at least $\lceil M/B\rceil =1562$ smaller-diameter parts, exceeding $d+1=1326$. In particular,Rescaling the point set to diameter one changes none of these partition counts. Therefore the Borsuk counterexample in dimension 1325 is fully explicit. This is a concrete dimension, not a claim that it is the smallest possible counterexample dimension.