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 given by
Borsuk-Ulam Theorem: For every continuous mapping , there exists a point with .
Pairs of points are called antipodal.
There are a couple of common illustrative examples for the case . 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 and 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 starting at and going clockwise around . Simultaneously, trace out the path starting at 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, .
We will give the sketch of a proof for Let , and note that our goal is to prove that for some . Note that is antipodal in the sense that for all . Now, if for every , then by compactness there exists an such that for all . Because of this, we may approximate arbitrarily well by a smooth map, and prove that the approximation has a 0. So we will assume that itself is smooth.
Now, define by , i.e. the north/south projection map. Let be a hollow cylinder, and let be given by so that linearly interpolates between and .
Also, let’s define an antipodality on by . Note that is antipodal with respect to , i.e. , because both and are antipodal. For the sake of contradiction, assume that for all .
Now let’s consider the structure of the zero set . Certainly since , and these are h’s only zeros. Here comes the sketchy part: Since is smooth, is also smooth, and thus locally can be approximated by an affine mapping . It follows that if is not empty, then it should be a subspace of dimension at least one. By an arbitrarily small perturbation of the initial , ensuring that is sufficiently generic, we can ensure that is either empty or a subspace of dimension one. Thus locally, should look like a two-sided curve, except at the boundaries and , where (if non-empty) would look like a one-sided curve. But, for instance, cannot contain any Y-shaped branches.
It follows that is a union of closed cycles and paths whose endpoints must lie at the boundaries and . ( is represented by red lines in the cylinder above.) But since there are only two zeros on the sphere, and none on the sphere, must contain a path from to Since is antipodal with respect to , 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 must take the value 0.
Notice that the only important property we used about (other than its smoothness) is that is has a number of zeros which is twice an odd number. If had, e.g. four zeros, then we could have two -symmetric paths emanating from and returning to the bottom. But if has six zeros, then we would again reach a contradiction.