Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 13 / 1

The Lusternik-Schnirelmann-Borsuk theorem has the following two equivalent covering formulations. For every integer $d\ge 0$, a cover of the sphere $S^d$ by $d+1$ closed sets has a member containing an antipodal pair. The same assertion holds with open sets in place of closed sets. Thus $d+1$ antipodal-pair-free open sets, or $d+1$ antipodal-pair-free closed sets, cannot cover $S^d$. The dimension-zero case simply says that one set covering the two-point sphere contains both points.

Here is why the two versions agree. A finite open cover of a compact metric space admits a closed shrinking that still covers: sufficiently small closed balls subordinate to the open cover can be grouped according to their containing open member. Applying the closed version to that shrinking proves the open version. Conversely, if a nonempty closed subset $C$ of $S^d$ avoids antipodal pairs, compactness gives positive distance between $C$ and $-C$. A sufficiently small open neighbourhood of $C$ still avoids antipodal pairs. Enlarge each member of a hypothetical closed counterexample in this way; the open version rules it out. Empty members cause no difficulty.

Another common equivalent formulation is the Borsuk-Ulam theorem: every continuous $f:S^d\to {\mathbb{R}}^d$ has $f(x)=f(-x)$ for some $x$, or, equivalently, every continuous odd function $g:S^d\to {\mathbb{R}}^d$ has a zero. For example, if $d+1$ antipodal-pair-free open sets covered $S^d$, a subordinate partition of unity $({\varphi }_1,\dots ,{\varphi }_{d+1})$ would give the odd functionIt cannot vanish, since some ${\varphi }_i(x)>0$, whereas antipodal-pair-freeness forces ${\varphi }_i(-x)=0$. In the other direction, if an odd function $g:S^d\to {\mathbb{R}}^d$ never vanishes, choose $d+1$ vectors $u_i$ forming a regular simplex centred at the origin in ${\mathbb{R}}^d$. For $d\ge 1$, the open sets $\{x:u_i\cdot g(x)>0\}$ cover $S^d$ and none contains an antipodal pair, contradicting the covering theorem.

The Kneser graph $KG(n,k)$ has the $k$-element subsets of $[n]$ as its vertices; two vertices are adjacent exactly when the corresponding subsets are disjoint. The Lovász theorem on Kneser graphs determines its chromatic number. A graph colouring is therefore a partition of the $k$-sets into intersecting families.

First construct a graph colouring with $d+2=n-2k+2$ colours. If a $k$-set meets $[d+1]$, give it the colour of its least element. Give every remaining $k$-set colour $d+2$. Two sets with one of the first $d+1$ colours share that colour's element. The last colour consists of $k$-sets in a $(2k-1)$-element ground set, so it too is an intersecting family. Thus $\chi (KG(n,k))\le d+2$.

For the converse we establish the Gale hemisphere lemma explicitly, using a signed moment curve. Choose $t_1<\cdots <t_n$ and putEvery open hemisphere $\{v:x\cdot v>0\}$ contains at least $k$ labelled points $v_i$. To see this, put $p(t)=x_0+x_{1}t+\cdots +x_d{t}^d$. It is a nonzero polynomial of polynomial degree at most $d$. First suppose none of the $p(t_i)$ vanishes. Write $b_i=\mathrm{sgn}((-1{)}^{i}p(t_i))$. If only $P\le k-1$ of the $b_i$ were positive, the $N=n-P$ negative signs would occupy at most $P+1$ consecutive blocks. There would be at leastadjacent pairs with both $b_i,b_{i+1}$ negative. Each such pair forces $p(t_i)$ and $p(t_{i+1})$ to have opposite signs. The intermediate value theorem would give $d+1$ distinct roots of a polynomial, a contradiction.

If $p$ vanishes at $z$ of the sample points, then $z\le d$. A Lagrange interpolation polynomial $q$ of polynomial degree at most $z-1$ can be chosen with $(-1{)}^{i}q(t_i)<0$ at all those points. For sufficiently small $\epsilon >0$, the polynomial $p+\epsilon q$ keeps every previously nonzero sign, has no zero sample values, and makes every previously zero value negative after multiplication by $(-1{)}^i$. Its positive count is exactly the positive count of $p$, so the preceding argument proves the open hemisphere assertion also in this case. For $d=0$, the labelled points alternate between the two points of $S^0$; distinct labels, rather than distinct positions, are what is needed.

Suppose now that $KG(n,k)$ had a graph colouring with at most $d+1$ colours, padding the palette with unused colours if necessary. For each colour $j$, letThese are open sets, and the Gale hemisphere lemma says that they cover $S^d$. If both $x$ and $-x$ belonged to $U_j$, two $k$-sets of colour $j$ would lie in opposite open hemispheres. They would be disjoint, hence adjacent in the Kneser graph, contradicting the graph colouring. The Lusternik-Schnirelmann-Borsuk theorem excludes this cover. Therefore the lower bound matches the explicit colouring:

Use the identification of two-element subsets of $[n]$ with the edges of the complete graph $K_n$. A colour class in the Kneser graph $KG(n,2)$ is an intersecting two-element set family, so its edges must pairwise meet.

Such a class is contained either in a star graph or in a triangle in a graph. Indeed, if not all edges have a common vertex, take two meeting edges $ab,ac$. An edge not containing $a$ must then be $bc$. Any further edge meeting all three of $ab,ac,bc$ is one of these three. Classes with at most two edges already lie in a star graph.

Assume that a graph colouring used $c\le n-3$ colours. Classify $s$ classes as stars and the remaining $t=c-s$ classes as triangles. Delete a chosen centre of each star class, leaving $m\ge n-s\ge t+3$ vertices. Every edge between those remaining vertices must belong to a triangle class, of which each covers at most three edges. HenceButa contradiction. Thus $\chi (KG(n,2))\ge n-2$. For the matching upper bound, assign a two-set the colour of its smaller element if that element is at most $n-3$, and otherwise give it colour $n-2$. The last class comprises the three pairs on the last three elements, an intersecting family. Consequently an entirely combinatorial argument gives