Past exam of the mathematics course of the University of Cambridge / 2025 / iii / Paper 109 / 4

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.