From: Douglas Zare <zare@math.columbia.edu>
Subject: Re: An analogue of the Borsuk-Ulam theorem
Date: Fri, 22 Oct 1999 18:26:38 -0400
Newsgroups: sci.math
Keywords: antipodal points in a skeleton of the cube

Douglas Zare wrote:

> Recently, in a mailing list, the following lemma arose:
>
> If n>m, then for any continuous map from the n-cube to R^m there are two
> antipodal points _in the m-skeleton of the cube_ which are sent to the
> same point.
>
> The m-skeleton is the union of faces of dimension at most m, so the
> 1-skeleton is a graph and the (n-1)-skeleton is topologically an
> (n-1)-sphere. If n=m+1, the statement is a version of the Borsuk-Ulam
> theorem.
>
> I mentioned this around the department this afternoon. Before I could
> prove it, a graduate student, A. Champanerkar, did so. Since his method
> and mine (with B. Mangum) are so different, I figure there must be many
> techniques which work.
>
> I look forward to seeing any proofs (or references) from readers of this
> newsgroup. After a few days, I'll post the proofs I know and, depending
> on the discussion in the mailing list, perhaps the application.

First, AC's proof:

Suppose n>m and we have a map from the m-skeleton of the n-cube to R^m such
that no antipodal pair is sent to the same point. If n=m+1, then we apply
the Borsuk-Ulam theorem to get a contradiction. Otherwise, we use this map
to construct a map from the (m+1)-skeleton of the n-cube to R^(m+1) so that
no antipodal pair is sent to one point: Let the first m coordinates of the
new map on the m-skeleton agree with the old map, and let the (m+1)st
coordinate be 0 on the m-skeleton. Let the centers of the (m+1)-cells be
sent to points whose first m coordinates are 0, and extend so that the line
segments connecting the centers of the (m+1)-cells to any point in the
m-skeleton are mapped linearly. Then any antipodal pair of points sent to
the same point must either come from such a pair in the m-skeleton, which
we assumed would not happen, or they would be opposite centers of
(m+1)-cells. We can choose the (m+1)st coordinates of the centers so that
this does not happen.

Next, BM's and my homotopy proof:

Inductively construct maps of the k-sphere into the m-skeleton of the cube
for 0<=k<=m so that these maps are antipodally symmetric. Given such a
symmetric map of the k-sphere with k<m, by the connectivity of the
m-skeleton of the cube there is a map of the k+1-disk into the m-skeleton
whose boundary is the previous map. The union of this map of the disk and
its antipode produce an antipode-preserving map from the (k+1)-sphere to
the m-skeleton. So, one gets an antipode preserving map from S^m to the
m-skeleton.
Composing with the map to R^m must cause two antipodal points of the S^m to
be sent to the same point by the Borsuk-Ulam theorem in R^m, and these
correspond to two antipodal points of the m-skeleton which are sent to the
same point.

These proofs rely on the Borsuk-Ulam theorem in different dimensions: the
first builds up to dimension n-1 and the second builds up to dimension m. I
haven't seen any other proofs, but I am still interested.

The application:

R. Kenyon asked the following on the domino-tiling mailing list: Suppose
one maps the vertices of the n-cube to R^m so that adjacent vertices of the
cube are sent to points of distance at most 1. Is it true that there must
be two antipodal vertices which are sent to points within sqrt(m)?

He proved the stronger bound of sqrt(n) for n<=m by analysis on (Z/2)^n. R.
Chapman proved the case of m=2 (m=1 is easy) using the Borsuk-Ulam theorem
in 2-dimensions.
I should point out that sqrt(m) is the best possible result for n>=m since
that is the distance between antipodal vertices. Using the above
topological lemma, I proved not the desired sqrt(m) but m:

Extend the map on the vertices to the m-skeleton. Use the topological lemma
to produce a point in the m-skeleton such that the distance between
antipodal points is 0. Every point in the m-skeleton is within sqrt(m)/2 of
a vertex, and the gradient of the distance between the images of antipodal
vertices is at most 2sqrt(m), so the nearest vertices to the antipodal pair
in the m-skeleton are sent to points at distance at most m.

At least this involves m rather than n, but one problem is that the
gradient is a weak estimate. Of the vertices of the m-cell, one might hope
that some would have much closer images. However, consider the map of the
unit m-cube to R by the sum of the coordinates. compose with wrapping R
about a circle of circumference 2m. Then the convex hull of the images
includes the center of the circle, which is far away from the vertices, a
distance of c(m) rather than c(sqrt(m)). If this point is the one sent to
the same point as its antipode, then its image will be far from the images
of all of the vertices of that cell, and their antipodes might be just as
far in the other direction.

One could try to get around this by choosing another extension of the map
of the vertices to a map of the m-skeleton, but so far this seems quite
messy. I welcome any help finishing off this problem.

Douglas Zare