Tucker's lemma

In mathematics, Tucker's lemma is a combinatorial analog of the Borsuk–Ulam theorem, named after Albert W. Tucker.

In this example, where n=2, the red 1-simplex has vertices which are labelled by the same number with opposite signs. Tucker's lemma states that for such a triangulation at least one such 1-simplex must exist.

Let T be a triangulation of the closed n-dimensional ball ${\displaystyle B_{n}}$. Assume T is antipodally symmetric on the boundary sphere ${\displaystyle S_{n-1}}$. That means that the subset of simplices of T which are in ${\displaystyle S_{n-1}}$ provides a triangulation of ${\displaystyle S_{n-1}}$ where if σ is a simplex then so is −σ. Let ${\displaystyle L:V(T)\to \{+1,-1,+2,-2,...,+n,-n\}}$ be a labeling of the vertices of T which is an odd function on ${\displaystyle S_{n-1}}$, i.e, ${\displaystyle L(-v)=-L(v)}$ for every vertex ${\displaystyle v\in S_{n-1}}$. Then Tucker's lemma states that T contains a complementary edge - an edge (a 1-simplex) whose vertices are labelled by the same number but with opposite signs.[1]

Proofs

The first proofs were non-constructive, by way of contradiction.[2]

Later, constructive proofs were found, which also supplied algorithms for finding the complementary edge.[3][4] Basically, the algorithms are path-based: they start at a certain point or edge of the triangulation, then go from simplex to simplex according to prescribed rules, until it is not possible to proceed any more. It can be proved that the path must end in a simplex which contains a complementary edge.

An easier proof of Tucker's lemma uses the more general Ky Fan lemma, which has a simple algorithmic proof.

The following description illustrates the algorithm for ${\displaystyle n=2}$.[5] Note that in this case ${\displaystyle B_{n}}$ is a disc and there are 4 possible labels: ${\displaystyle -2,-1,1,2}$, like the figure at the top-right.

Start outside the ball and consider the labels of the boundary vertices. Because the labeling is an odd function on the boundary, the boundary must have both positive and negative labels:

• If the boundary contains only ${\displaystyle \pm 1}$ or only ${\displaystyle \pm 2}$, there must be a complementary edge on the boundary. Done.
• Otherwise, the boundary must contain ${\displaystyle (+1,-2)}$ edges. Moreover, the number of ${\displaystyle (+1,-2)}$ edges on the boundary must be odd.

Select an ${\displaystyle (+1,-2)}$ edge and go through it. There are three cases:

• You are now in a ${\displaystyle (+1,-2,+2)}$ simplex. Done.
• You are now in a ${\displaystyle (+1,-2,-1)}$ simplex. Done.
• You are in a simplex with another ${\displaystyle (+1,-2)}$ edge. Go through it and continue.

The last case can take you outside the ball. However, since the number of ${\displaystyle (+1,-2)}$ edges on the boundary must be odd, there must be a new, unvisited ${\displaystyle (+1,-2)}$ edge on the boundary. Go through it and continue.

This walk must end inside the ball, either in a ${\displaystyle (+1,-2,+2)}$ or in a ${\displaystyle (+1,-2,-1)}$ simplex. Done.

Run-time

The run-time of the algorithm described above is polynomial in the triangulation size. This is considered bad, since the triangulations might be very large. It would be desirable to find an algorithm which is logarithmic in the triangulation size. However, the problem of finding a complementary edge is PPA-complete even for ${\displaystyle n=2}$ dimensions. This implies that there is not too much hope for finding a fast algorithm.[6]

Equivalent results

There are several fixed-point theorems which come in three equivalent variants: an algebraic topology variant, a combinatorial variant and a set-covering variant. Each variant can be proved separately using totally different arguments, but each variant can also be reduced to the other variants in its row. Additionally, each result in the top row can be deduced from the one below it in the same column.[7]

Algebraic topology	Combinatorics	Set covering
Brouwer fixed-point theorem	Sperner's lemma	Knaster–Kuratowski–Mazurkiewicz lemma
Borsuk–Ulam theorem	Tucker's lemma	Lusternik–Schnirelmann theorem

See also

• Topological combinatorics

References

1. Matoušek, Jiří (2003), Using the Borsuk–Ulam Theorem, Springer-Verlag, pp. 34–45, ISBN 3-540-00362-2
2. Tucker, Albert W. (1946), "Some topological properties of disk and sphere", Proc. First Canadian Math. Congress, Montreal, 1945, Toronto: University of Toronto Press, pp. 285–309, MR 0020254
3. Freund, Robert M.; Todd, Michael J. (1981), "A constructive proof of Tucker's combinatorial lemma", Journal of Combinatorial Theory, Series A, 30 (3): 321–325, doi:10.1016/0097-3165(81)90027-3, MR 0618536
4. Freund, Robert M.; Todd, Michael J. (1980), A constructive proof of Tucker's combinatorial lemma
5. Meunier, Frédéric (2010), Sperner and Tucker lemmas (PDF), Algorithms and Pretty Theorems Blog, pp. 46–64, retrieved 25 May 2015
6. Aisenberg, James; Bonet, Maria Luisa; Buss, Sam (2015), 2-D Tucker is PPA complete, ECCC TR15-163
7. Nyman, Kathryn L.; Su, Francis Edward (2013), "A Borsuk–Ulam equivalent that directly implies Sperner's lemma", American Mathematical Monthly, 120 (4): 346–354, doi:10.4169/amer.math.monthly.120.04.346, MR 3035127