Past exam of the mathematics course of the University of Cambridge / 2005 / iii / Paper 10 (Extremal Combinatorics)

Identify the discrete cube $Q_n$ with the subsets of $[n]$, with hypercube graph adjacency given by changing one element. Write $N[A]$ for the closed graph neighbourhood and $\partial A=N[A]\setminus A$ for the external vertex boundary. The simplicial order on the discrete cube first orders by set size and then by lexicographic order, with the smallest differing coordinate belonging to the earlier set.

Harper theorem states that, for every set family $A\subseteq Q_n$,Here is the simplicial section compression proof. Induct on $n$, the one-dimensional case being immediate. Split $A$ by a coordinate into sections $A_0,A_1\subseteq Q_{n-1}$. Its neighbourhood sections areReplace $A_0,A_1$ by equally large simplicial initial segments $I_0,I_1$. By induction $|N[I_j]|\le |N[A_j]|$. Also the neighbourhood of a simplicial initial segment is itself a simplicial initial segment: at its last occupied level the extra vertices form the upper shadow of a lexicographic initial segment, again lexicographically initial. Consequently the compressed unions have sizes $\max \{|N[I_0]|,|I_1|\}$ and $\max \{|N[I_1]|,|I_0|\}$, no larger than the original unions. The compression preserves $|A|$ and cannot increase $|N[A]|$.

Repeat in every coordinate until all sections are initial. Every nontrivial compression strictly decreases the sum of the global simplicial positions, so the process terminates. To describe the terminal families for simplicial section compression, suppose an earlier absent vertex $S$ precedes a later present vertex $T$. They cannot share a coordinate value: otherwise they lie in the same compressed section, contradicting its initiality. Thus $T=[n]\setminus S$. No vertex can lie strictly between them in the order, since it would make another absent/present pair that is not complementary. Hence the terminal family is either $C(|A|)$ or that segment with its last vertex $S$ exchanged for its immediate complementary successor $T$.

For odd $n=2m+1$, that exceptional exchange crosses the middle levels: $S=\{m+2,\dots ,2m+1\}$ and $T=\{1,\dots ,m+1\}$. For $m\ge 1$, all sets of size at most $m+1$ remain in the neighbourhood after the exchange, since an $(m+1)$-set has at least two lower neighbours and only one was removed. The new $T$ can only add vertices of size $m+2$.

For even $n=2m$, the only consecutive complementary pair in one level is $S=\{1,m+2,\dots ,2m\}$ and $T=\{2,\dots ,m+1\}$. The original segment contains all sets below size $m$ and all $m$-sets containing 1. For $m\ge 2$, its neighbourhood contains all sets of size at most $m$ and all $(m+1)$-sets containing 1; every such upper set still has an included lower neighbour after the single removal. The new $T$ can only add further neighbours. The cases $n=1,2$ follow directly, with the exceptional families related to the initial ones by a graph automorphism. Thus neither exception improves the neighbourhood, completing the induction.

For the half-cube vertex-boundary extrema, if $n=2m+1$, the initial half cube is all sets of size at most $m$; its boundary is the next level, of size $\left(\genfrac{}{}{0ex}{}{2m+1}{m+1}\right)$. If $n=2m$, it contains all levels below $m$ and the $m$-sets containing 1. The boundary consists of the $m$-sets avoiding 1 and the $(m+1)$-sets containing 1, giving $2\left(\genfrac{}{}{0ex}{}{2m-1}{m}\right)=\left(\genfrac{}{}{0ex}{}{2m}{m}\right)$.

No boundary can exceed the $2^{n-1}$ vertices outside a half cube. Taking all vertices of even Hamming weight attains that bound, because every odd-weight vertex is adjacent to one of them. Therefore, for $n\ge 1$,

Always true. Simplicial initial segments are nested: $C(k)\subseteq C(l)$ when $k\le l$. Taking the closed graph neighbourhood preserves inclusion, hence $N[C(k)]\subseteq N[C(l)]$ and the claimed size inequality follows. No extremal theorem is needed for this step.

False. The simplicial vertex boundaries need not increase below half volume. In $Q_3$,Both closed graph neighbourhoods consist of all vertices except $\{1,2,3\}$, so both have size seven. Their external vertex boundaries therefore have sizesalthough $3<4=2^{3-1}$. Adding a vertex already in the neighbourhood can reduce the external vertex boundary without enlarging the neighbourhood.

False. Complementary-size simplicial vertex boundaries can be asymmetric. Use $n=7$, $k=63$ and $l=65$, so $k+l=128$.

There are 64 sets of size at most three. The initial segment $C(63)$ contains all of them except the last triple $\{5,6,7\}$. Every four-set has another included triple, so its external vertex boundary is that missing triple together with all $\left(\genfrac{}{}{0ex}{}{7}{4}\right)=35$ four-sets: $|\partial C(63)|=36$.

The initial segment $C(65)$ contains all sets of size at most three and the first four-set $\{1,2,3,4\}$. Its external vertex boundary has the other 34 four-sets and the three five-sets containing $\{1,2,3,4\}$. Thuscontradicting the proposed inequality.

The standard simplicial decomposition of a sphere $F^n$ is the boundary of the cross-polytope with vertices $\pm e_1,\dots ,\pm e_{n+1}$, identified radially with $S^n$. A face chooses distinct coordinate indices and one sign for each; it never contains an antipodal pair.

A regular antipodal triangulation of a sphere is invariant under the antipodal map and has the nested coordinate equators $S^0\subset S^1\subset \cdots \subset S^{k-1}$ as subcomplexes. In particular each equator separates its sphere into two triangulated hemispheres. These conditions are preserved by barycentric subdivision.

For a simplicial map $f:F\to F^n$, a positive alternating simplex of dimension $j$ has distinct image labelsThe opposite alternating pattern is negative; all other simplices, including collapsed images, are neutral.

To prove the antipodal alternating-simplex parity lemma, let $p_j$ count positive $j$-simplices in the equatorial $S^j$. There is exactly one positive vertex in $S^0$, so $p_0=1$. A $j$-simplex has an odd number of positive alternating facets precisely when it is positive or negative alternating. Indeed an alternating sequence has exactly one positive alternating deletion; a nonalternating sequence has either zero or two. For a collapsed image, a positive facet can occur only when exactly one label is repeated; deleting either copy gives two such facets.

Count incidences of positive $(j-1)$-faces with $j$-simplices in one closed hemisphere. Interior faces contribute twice and equatorial faces once. The count modulo two is therefore $p_{j-1}$. It is also the number of positive or negative $j$-simplices in that hemisphere modulo two. Because $f$ is antipodal, each alternating pair $\sigma ,-\sigma$ has one positive and one negative member, with one member in each hemisphere. ThusInduction gives odd $p_k$, proving the existence of a positive $k$-simplex. In particular, an antipodal simplicial map $F\to F^{k-1}$ is impossible: a positive $k$-simplex would require $k+1$ distinct coordinate labels but only $k$ are available.

The Borsuk-Ulam theorem states that every continuous map $g:S^k\to {\mathbb{R}}^k$ has some $x$ with $g(x)=g(-x)$. First rule out a continuous antipodal map $h:S^k\to S^{k-1}$ for $k\ge 1$. By uniform continuity, take a sufficiently fine regular barycentric subdivision so that endpoints of each edge have images less than $2/\sqrt{k}$ apart. Label a vertex by $\mathrm{sgn}(h_i)e_i$, where $i$ is the smallest index maximizing $|h_i|$. Since $h$ is unit length, this maximum is at least $1/\sqrt{k}$; two adjacent vertices cannot have opposite labels. The labels therefore define an antipodal simplicial map to $F^{k-1}$, contradicting the preceding result.

If the stated Borsuk-Ulam theorem failed, the mapwould be just such a continuous antipodal map. This proves the required version; $k=0$ is immediate.

For the Kneser conjecture, equivalently Lovász theorem on Kneser graphs, the claim isThe Kneser graph joins disjoint $r$-subsets of $[N]$. Let $d=N-2r+1$. Colour each $r$-set by its least element in $[d]$ when it has one, and otherwise by one final colour. A colour class indexed by $i$ is an intersecting family because all its members contain $i$; the final class lies in a $(2r-1)$-set and is also intersecting. This proves the upper bound $d+1$.

For the lower bound, first deduce the open-cover Lusternik-Schnirelmann-Borsuk theorem. An open cover $U_0,\dots ,U_d$ of $S^d$ admits a continuous partition of unity ${\varphi }_0,\dots ,{\varphi }_d$ subordinate to it. Apply the Borsuk-Ulam theorem to $({\varphi }_1,\dots ,{\varphi }_d)$. Equal values at $x,-x$ and ${\sum }_i{\varphi }_i=1$ make all values equal. At least one common value is positive, so some $U_i$ contains an antipodal pair.

Now suppose the $r$-sets could be coloured with only $d$ colours, each an intersecting family. Choose $N$ points $v_1,\dots ,v_N\in S^d$ such that every $d+1$ of their vectors are linearly independent. For example, normalize $(1,t_i,\dots ,t_i^d)$ for distinct real $t_i$; the Vandermonde determinant proves this property. The general-position hemisphere count says that at most $d$ points lie on any equator. Since $N-d=2r-1$, at least one of the opposite open hemispheres determined by $x,-x$ contains an $r$-set of the labelled points.

Let $U_i$ be the open set of directions whose positive open hemisphere contains an $r$-set of colour $i$. It contains no antipodal pair, as such a pair would give two disjoint sets of that colour. The compact set $K=S^d\setminus {\bigcup }_{i=1}^d{U}_i$ also contains no antipodal pair: otherwise each of the two opposite hemispheres would have at most $r-1$ points, contradicting the count $2r-1$.

If $K$ is nonempty, compactness gives a positive set distance between $K$ and $-K$; an open neighbourhood $U_0$ of radius less than half that set distance still has no antipodal pair. If $K$ is empty, take $U_0=\varnothing$. In either case $U_0,U_1,\dots ,U_d$ is an open cover with no member containing an antipodal pair, contradicting the Lusternik-Schnirelmann-Borsuk theorem. Hence at least $d+1$ colours are required.

Use the uniform Frankl-Wilson theorem: if $p$ is a prime number, $L\subseteq {\mathbb{F}}_p$ has $s$ distinct residues, $s\le \min \{r,n-r\}$, and an $r$-uniform set family $\mathcal{F}$ has distinct-member intersection sizes in $L$ modulo $p$ while $r\mathrm{mod}p\notin L$, thenHere is a polynomial method in combinatorics proof. For each $A\in \mathcal{F}$, form the intersection polynomialover ${\mathbb{F}}_p$, and use multilinear reduction on the Boolean cube so its degree is at most $s$. At the characteristic vector of $B\in \mathcal{F}$, this evaluates to zero for $A\ne B$ and is nonzero for $A=B$. Consequently these evaluation functions are linearly independent.

The low-degree evaluation rank on a uniform layer bounds their space by $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. To justify that step without division by a possibly zero residue, form the integer incidence matrix with rows $T\subseteq [n]$, $|T|\le s$, columns $r$-sets $B$, and entries $1_{T\subseteq B}$. Over the rational numbers, a row with $|T|=j$ equals ${\left(\genfrac{}{}{0ex}{}{r-j}{s-j}\right)}^{-1}$ times the sum of the rows of all $s$-sets containing $T$. Thus its rational matrix rank is at most $\left(\genfrac{}{}{0ex}{}{n}{s}\right)$. Every larger minor is an integer determinant equal to zero and stays zero modulo $p$, so the same upper bound holds over ${\mathbb{F}}_p$. This proves the theorem.

For the forbidden midpoint problem, split $\mathcal{A}$ according to whether its members contain coordinate 1. Leave the containing half unchanged; complement every member of the avoiding half. Both resulting families consist of $2p$-sets containing 1, and complementation preserves their internal intersection sizes becauseWithin either transformed family, distinct intersections lie between 1 and $2p-1$ and are not $p$. Their residues are therefore in $L=\{1,\dots ,p-1\}$, whereas the set-size residue is $2p\equiv 0$. Apply the Frankl-Wilson theorem to each half and add:The factor 2 comes from splitting into two families. The unsplit family can contain disjoint sets, whose intersection residue zero equals the set-size residue and prevents this direct application. Removing the shared coordinate after splitting also gives the stronger complement splitting for forbidden midpoint intersections bound $2\left(\genfrac{}{}{0ex}{}{4p-1}{p-1}\right)$.

For the construction, fix a $(p+1)$-set $B$ and let $R=[4p]\setminus B$, of size $3p-1$. The fixed-core construction avoiding midpoint intersections isTwo members of $\mathcal{F}$ intersect in at least $p+1$ points; the same is true for two complements. An intersection across the two halves has size $|X\setminus Y|\le p-1$. No intersection is $p$. The halves are disjoint because one contains all of $B$ and the other none, so

The uniform covers theorem says that if a multiset $\mathcal{C}$ of coordinate subsets covers every coordinate exactly $k$ times, then a Euclidean body $S\subseteq {\mathbb{R}}^n$ satisfieswhere $S_A$ is its coordinate projection of a Euclidean body. Work with bounded Borel bodies, whose projections are Lebesgue measurable sets; an empty-coordinate projection has measure one.

Prove the theorem by induction on dimension, with the one-dimensional case immediate. Slice at the last coordinate, writing $S_t\subseteq {\mathbb{R}}^{n-1}$. The subsets $A\setminus \{n\}$ still cover each remaining coordinate $k$ times, so induction givesFor $A$ not containing $n$, the projected slice is contained in $S_A$, giving a constant bound. For $A$ containing $n$, its measure is the slice measure $f_A(t)$ of $S_A$. Exactly $k$ members of $\mathcal{C}$ contain $n$, counted with multiplicity. Integrate and apply Hölder's inequality to those $k$ factors:Fubini's theorem identifies $\int f_A=|S_A|$, completing the proof. Exact covering is needed for real volumes, which may be smaller than one.

The Bollobas--Thomason box theorem states that there is an axis-parallel box $B$ with $|B|=|S|$ and $|B_A|\le |S_A|$ for every nonempty coordinate subset $A$. Use the logarithmic linear program for the box theorem: if its side lengths are $b_i=e^{x_i}$, maximize ${\sum }_i{x}_i$ subject toThe linear program is feasible by choosing all $x_i$ sufficiently negative and is bounded above by the full-set constraint. Its dual minimizes ${\sum }_A{\lambda }_A\log |S_A|$ subject to ${\lambda }_A\ge 0$ and ${\sum }_{A\ni i}{\lambda }_A=1$ for each $i$: precisely a fractional uniform cover.

The dual feasible polytope is nonempty, bounded and defined by integer coefficients, so an optimal extreme point has rational coordinates. Multiply its weights by a common denominator $k$. The resulting integer uniform cover and the uniform covers theorem giveThus the dual optimum is at least $\log |S|$; weight one on $A=[n]$ attains equality. Strong duality gives a primal optimum ${\sum }_i{x}_i=\log |S|$. The corresponding box has the required volume and projected-volume bounds, proving the theorem.

For the Loomis–Whitney theorem, take the box supplied by the Bollobas--Thomason box theorem. Each side length occurs in exactly $n-1$ projections omitting one coordinate, soThis is the Loomis--Whitney inequality.

For the three projection areas of a volume-one body, necessity is $1=|S{|}^2\le abc$. Conversely suppose $abc\ge 1$ and setThe box $[0,x]\times [0,y]\times [0,z]$ has projected areas $a,b,c$ and volume $V=\sqrt{abc}\ge 1$. Inside it retain the three slabsFor $t>0$, each projection is the full corresponding rectangle, since the slab in the omitted coordinate supplies every point of that projection. The volume is $V[1-(1-t{)}^3]$. Chooseto make the volume one. This is a compact connected union of three positive-thickness boxes. Hence the complete answer is