Tucker's lemma

Remarks

Tucker's lemma is a combinatorial form of the Borsuk–Ulam theorem. To derive the lemma from Borsuk–Ulam, send a vertex with label $\pm i$ to $\pm e_i$ and extend linearly on simplices to a map $f \colon B^n \to \R^n$. With no complementary edge, the image of $f$ avoids $0$. Then $f / \norm{f}$ restricts to an odd map from the boundary sphere $S^{n-1}$ to $S^{n-1}$ that extends over the ball, which is impossible. Conversely, applying the lemma to finer and finer triangulations proves the Borsuk–Ulam theorem. There are also constructive path-following proofs, which give algorithms to find a complementary edge.

Example: for $n = 1$, subdivide $[-1, 1]$ into intervals and label the vertices by $\pm 1$ with $\lambda(-1) = -\lambda(1)$. Moving from $-1$ to $1$ the label changes sign, so some interval of the subdivision has endpoints labelled $1$ and $-1$.

The antipodal condition on the boundary is needed: if every vertex gets the label $1$, no edge is complementary.

Going deeper

For a student

Tucker's lemma is to the Borsuk–Ulam theorem what Sperner's lemma is to the Brouwer fixed-point theorem. Because it is finite and combinatorial, it is the usual route to applications of Borsuk–Ulam in combinatorics, such as necklace splitting and Kneser's conjecture, and to algorithms for them.