Kneser conjecture

Lecture 6: Borsuk-Ulam and some combinatorial applications

~ James ~ 1 Comment

Now we’ll move away from spectral methods, and into a few lectures on topological methods.  Today we’ll look at the Borsuk-Ulam theorem, and see a stunning application to combinatorics, given by Lovász in the late 70’s.  A great reference for this material is Matousek’s book, from which I borrow heavily.  I’ll also discuss why the Lovász-Kneser theorem arises in theoretical CS.

The Borsuk-Ulam Theorem

We begin with a statement of the theorem.  We will think of the n-dimensional sphere as the subset of {\mathbb R^{n+1}} given by

{S^n = \left\{ (x_1, \ldots, x_{n+1}) : x_1^2 + \cdots + x_{n+1}^2 = 1\right\}.}

Borsuk-Ulam Theorem: For every continuous mapping {f : S^n \to \mathbb R^n} , there exists a point {x \in S^n} with {f(x)=f(-x)} .

Pairs of points {x,-x \in S^n} are called antipodal.

There are a couple of common illustrative examples for the case {n=2} .  The theorem says that if you take the air out of a basketball, crumple it (no tearing), and flatten it out, then there are two points directly on top of each other which were antipodal before.  Another common example states that at every point in time, there must be two points on the earth which both have exactly the same temperature and barometric pressure (assuming, of course, that these two parameters vary continuously over the surface of the eath).

The n=1 case is completely elementary.  For the rest of the lecture, let’s use {N = (0,0,\ldots,1)} and {S=(0,0,\ldots,-1)} to denote the north and south poles (the dimension will be obvious from context).  To prove the n=1 case, simply trace out the path in {\mathbb R} starting at {f(N)} and going clockwise around {S^1} .  Simultaneously, trace out the path starting at {f(S)} and going counter-clockwise at the same speed.  It is easy to see that eventually these two paths have to collide:  At the point of collision, {f(x)=f(-x)} .

We will give the sketch of a proof for {n \geq 2.}   Let {g(x)=f(x)-f(-x)} , and note that our goal is to prove that {g(x)=0} for some {x \in S^n} .  Note that {g} is antipodal in the sense that {g(x)=-g(-x)} for all {x \in S^n} .  Now, if {g(x) \neq 0} for every {x} , then by compactness there exists an {\epsilon > 0} such that {\|g(x)\| > \epsilon} for all {x \in S^n} .  Because of this, we may approximate {g} arbitrarily well by a smooth map, and prove that the approximation has a 0.  So we will assume that {g} itself is smooth.

Now, define {h : S^n \to \mathbb R^n} by {h(x_1, \ldots, x_{n+1}) = (x_1, \ldots, x_n)} , i.e. the north/south projection map.  Let {X = S^n \times [0,1]} be a hollow cylinder, and let {F : X \to \mathbb R^n} be given by {F(x,t)=t g(x) + (1-t)h(x)} so that {F} linearly interpolates between {g} and {h} .

Also, let’s define an antipodality on {X} by {\nu(x,t) = (-x,t)} .  Note that {F} is antipodal with respect to {\nu} , i.e. {F(\nu(x,t))=-F(x,t)} , because both {g} and {h} are antipodal.  For the sake of contradiction, assume that {g(x) \neq 0} for all {x \in S^n} .

Now let’s consider the structure of the zero set {Z = F^{-1}(0)} .  Certainly {(N,0), (S,0) \in Z} since {h(N)=h(S)=0} , and these are h’s only zeros.  Here comes the sketchy part:  Since {g} is smooth, {F} is also smooth, and thus locally {F} can be approximated by an affine mapping {F_{\mathrm{loc}} : \mathbb R^{n+1} \to \mathbb R^n} .  It follows that if {F_{\mathrm{loc}}^{-1}(0)} is not empty, then it should be a subspace of dimension at least one.  By an arbitrarily small perturbation of the initial {g} , ensuring that {F} is sufficiently generic, we can ensure that {F_{\mathrm{loc}}^{-1}(0)} is either empty or a subspace of dimension one.  Thus locally, {F^{-1}(0)} should look like a two-sided curve, except at the boundaries {t=0} and {t=1} , where {F^{-1}(0)} (if non-empty) would look like a one-sided curve.  But, for instance, {F^{-1}(0)} cannot contain any Y-shaped branches.

It follows that {Z} is a union of closed cycles and paths whose endpoints must lie at the boundaries {t=0} and {t=1} .  ({Z} is represented by red lines in the cylinder above.)  But since there are only two zeros on the {t=0} sphere, and none on the {t=1} sphere, {Z} must contain a path {\gamma} from {(N,0)} to {(S,0).}   Since {F} is antipodal with respect to {\nu} , {\gamma} must also satisfy this symmetry, making it impossible for the segment initiating at N to ever meet up with the segment initiating at S.  Thus we arrive at a contradiction, implying that {g} must take the value 0.

Notice that the only important property we used about {h} (other than its smoothness) is that is has a number of zeros which is twice an odd number.  If {h} had, e.g. four zeros, then we could have two {\nu} -symmetric paths emanating from and returning to the bottom.  But if {h} has six zeros, then we would again reach a contradiction.

Continue reading →