Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 109 (Combinatorics)

Every positive integer $m$ has a unique binomial representationDefineThe Kruskal-Katona theorem says that every $r$-uniform family $\mathcal{A}$ of size $m$ hasand the initial segment of length $m$ in colexicographic order attains equality.

We prove the inequality by simultaneous mathematical induction on the ground-set size and on $r$. We use the elementary binomial-shadow arithmetic lemmaTo verify the lemma, greedily remove the largest term $\left(\genfrac{}{}{0ex}{}{q}{r}\right)$ from the binomial representation of $a+b$. If $a$ reaches that term first, apply the induction hypothesis to the remainders; otherwise transfer the excess to $b$. In the crossing case Pascal's identitygives exactly the two terms on the right. This induction also proves uniqueness of the greedy representation.

Choose the largest ground-set element $x$ and splitThe members of the lower shadow that avoid $x$ form $\partial {\mathcal{A}}_0\cup {\mathcal{A}}_1$, while those containing $x$ are the sets $B\cup \{x\}$ with $B\in \partial {\mathcal{A}}_1$. Hence, writing $a=|{\mathcal{A}}_0|$ and $b=|{\mathcal{A}}_1|$,This completes the induction.

Finally, the initial colex segment first contains all $r$-subsets of $[a_r]$, followed recursively by sets containing $a_r+1$ whose remaining elements form the appropriate initial segment at level $r-1$. Its shadow has the same recursive decomposition, and therefore has exactly $f_r(m)$ members. This proves sharpness.

Solved by gpt-5.6-sol high.

Let $c(A)=[n]\setminus A$ and reverse the order of the ground set by $j\mapsto n+1-j$. The resulting bijection sends lexicographic order on $[n{]}^{(r)}$ to colexicographic order on $[n{]}^{(n-r)}$. It also sends the iterated upper shadow of an $r$-uniform family at level $r+1$ to the lower shadow of the corresponding $(n-r)$-uniform family, up to the same harmless reversal of the ground set.

The Kruskal-Katona theorem says that this lower shadow is smallest for an initial colex segment. Undoing the complement and reversal therefore says that the upper shadow of a family of fixed size in $[n{]}^{(r)}$ is smallest for the initial lex segment.

Solved by gpt-5.6-sol high.

The assertion is false. Take $n=6$, $r=3$, andThere are $1+3\cdot 3=10$ members. Its lower shadow consists of the three pairs inside $\{1,2,3\}$ and the nine pairs having one point there and one in $\{4,5,6\}$, so $|\partial \mathcal{A}|=12$. Its upper shadow consists of the twelve four-sets containing at least two points of $\{1,2,3\}$, so $|\nabla \mathcal{A}|=12$. The sum is $24$.

The initial lex segment of length ten is the star of all triples containing $1$; its lower and upper shadows have sizes $15$ and $10$. The initial colex segment consists of all triples in $[5]$; its lower and upper shadows have sizes $10$ and $15$. Both sums are $25$, so neither canonical segment minimizes the sum.

Solved by gpt-5.6-sol high.

The Erdős-Ko-Rado theorem says that if $n\ge 2r$ and $\mathcal{A}\subseteq [n{]}^{(r)}$ is an intersecting family, thenThe star of all $r$-sets containing one fixed point attains equality.

For the shadow proof, let ${\nabla }_{n-r}\mathcal{A}$ be the iterated upper shadow at level $n-r$, and letThese two families are disjoint: if $A\subseteq [n]\setminus B$, then $A$ and $B$ are disjoint. The upper-shadow form of the Kruskal-Katona theorem says that ifthenBut $|{\mathcal{A}}^c|=|\mathcal{A}|$, so disjointness and Pascal's identity would give more thanmembers at level $n-r$, a contradiction.

For the Katona circle method, place $[n]$ in a cyclic order. At most $r$ of its cyclic intervals of length $r$ can belong to an intersecting family. Indeed, after fixing one selected interval, every selected interval starts at one of the $2r-1$ positions at cyclic distance below $r$ from its start; apart from the fixed interval, these positions form $r-1$ pairs whose corresponding intervals are disjoint. Double-count pairs consisting of $A\in \mathcal{A}$ and a cyclic order in which $A$ is consecutive. There are $(n-1)!$ cyclic orders, at most $r$ selected intervals in each, and each $A$ is consecutive in $r!(n-r)!$ cyclic orders. Thereforewhich rearranges to the required bound.

Solved by gpt-5.6-sol high.

Suppose $\mathcal{A},\mathcal{B}\subseteq [n{]}^{(r)}$ are cross-intersecting families. The iterated upper shadow ${\nabla }_{n-r}\mathcal{A}$ is disjoint frombecause $A\subseteq [n]\setminus B$ would mean $A\cap B=\varnothing$. HenceIf $|\mathcal{A}|>\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$, the upper-shadow form of the Kruskal-Katona theorem givesIt follows from Pascal's identity that $|\mathcal{B}|<\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)$. Thus the two sizes cannot both exceed that number.

Solved by gpt-5.6-sol high.

No. Let $n=7$, $r=3$, take $\mathcal{A}=\{\{1,2,3\}\}$, and letThe families are nonempty and cross-intersecting. There aremembers, so

Solved by gpt-5.6-sol high.

Fix a prime number $p>r$. Distinct members of an intersecting $r$-uniform family have intersection size inwhereas every member has size $r\notin L$ modulo $p$. The Frankl-Wilson theorem with $|L|=r-1$ therefore givesFor fixed $r$,This is the asserted asymptotic weakening of the Erdős-Ko-Rado theorem.

Solved by gpt-5.6-sol high.

For $\mathcal{A}$ in the $n$-dimensional Boolean hypercube, the edge-isoperimetric inequality in the discrete cube iswhere $e(\mathcal{A})$ is the number of edges spanned by $\mathcal{A}$. Since the cube is $n$-regular, the equivalent boundary form is

We prove the induced-edge form by induction on $n$. Split the cube according to its last coordinate, and let the two sections have sizes $a\ge b$. At most $b$ edges of $\mathcal{A}$ cross between the sections. The induction hypothesis givesPut $x=b/(a+b)\le 1/2$. The required comparison with $\frac{1}{2}(a+b){\log }_2(a+b)$ is equivalent towhere $H_2$ is the binary entropy function. This follows from concavity because the graph of $H_2$ lies above the chord joining $(0,0)$ to $(1/2,1)$. The induction is complete. Subcubes attain equality when $|\mathcal{A}|$ is a power of two.

Solved by gpt-5.6-sol high.

The statement is false. In the grid graph $[9{]}^2$, take the four-row stripIt has $36=6^2$ vertices, and only the nine edges between rows four and five lie in its edge boundary. The corner square $[6{]}^2$ has six boundary edges along each of its two exposed sides, for a total of twelve. Thus a set of size $t^2$ can have smaller edge boundary than $[t{]}^2$.

Solved by gpt-5.6-sol high.

Apply coordinate compression in a product of paths in both coordinates. Replacing every fiber by an initial interval preserves the number of edges inside that fiber; between two neighboring fibers, the compressed sets span the minimum of their sizes, at least their original intersection size. Repeating the operation therefore never decreases the number of edges spanned and eventually produces a down-set.

Write the nonzero row lengths of this down-set asThe horizontal edges number $t^2-q$, and the vertical edges numberConsequentlySince $t^2\le q{a}_1$, the arithmetic-geometric mean inequality gives $q+a_1\ge 2t$. Henceas required.

Solved by gpt-5.6-sol high.

One uniform form of the Frankl-Wilson theorem is as follows. Let $p$ be prime and let $L\subseteq {\mathbb{F}}_p$ have $s\le \min \{k,n-k\}$ elements. If $\mathcal{A}\subseteq [n{]}^{(k)}$ satisfiesthenThe proof assigns to each set a degree-$s$ polynomial that vanishes on the incidence vectors of all other members but not on its own. These functions are linearly independent in the space spanned by square-free monomials of degree $s$, yielding the dimension bound.

Solved by gpt-5.6-sol high.

Partition the family into complementary pairs $\{A,[4p]\setminus A\}$. Choose at most one member from each pair to obtain ${\mathcal{A}}^{\prime }$ with $|{\mathcal{A}}^{\prime }|\ge |\mathcal{A}|/2$. Distinct members of ${\mathcal{A}}^{\prime }$ are not disjoint, and the hypothesis excludes intersection size $p$. Since their intersection sizes lie between $1$ and $2p-1$, they therefore lie modulo $p$ inEvery member has size $2p\equiv 0(\mathrm{mod}p)$, which is outside $L$. The Frankl-Wilson theorem givesand hence

Solved by gpt-5.6-sol high.

The Borsuk conjecture asserted that every bounded subset of ${\mathbb{R}}^d$ of positive diameter can be partitioned into $d+1$ subsets of strictly smaller diameter. We construct a Kahn-Kalai counterexample to the Borsuk conjecture.

For every $2p$-subset $A$ of $[4p]$, let $v_A\in \{-1,1{\}}^{4p}$ be $1$ on $A$ and $-1$ outside it, and defineBecause $x_A=x_{A^c}$, retain one representative of each complementary pair. The resulting set $X$ has $\frac{1}{2}\left(\genfrac{}{}{0ex}{}{4p}{2p}\right)$ points. For $s=|A\cap B|$,andAll $x_A$ have the same norm, so their distance is largest exactly when this inner product is smallest, namely when $s=p$.

Every smaller-diameter part of $X$ therefore corresponds to a family with no pair having intersection $p$. Part ii bounds such a part by $2\left(\genfrac{}{}{0ex}{}{4p}{p-1}\right)$. Any smaller-diameter partition consequently needs at leastparts. By Stirling formula, this ratio grows like $(27/16{)}^p$ up to a polynomial factor, whereas $d+1=O(p^2)$. For every sufficiently large prime $p$, the required number of parts exceeds $d+1$, disproving the conjecture.

Solved by gpt-5.6-sol high.

Let $D>0$ be the diameter of the bounded set $S$, and choose $x_0\in S$. Then $S\subseteq B(x_0,D)$. It is enough to prove a volumetric covering bound for the unit ball.

Choose a maximal $1/4$-separated set $N$ in $B(0,1)$. The balls of radius $1/8$ centred at points of $N$ are disjoint and lie in $B(0,9/8)$. Comparing volumes givesMaximality means that the balls of radius $1/4$ centred at $N$ cover the unit ball.

After translating and scaling, at most $9^n$ balls of radius $D/4$ cover $S$. Assign each point of $S$ to one covering ball containing it. This gives at most $9^n$ disjoint pieces, each of diameter at most $D/2<D$. Thus the claim holds with the absolute constant $C=9$.

Solved by gpt-5.6-sol high.