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.