Lemma of Tucker

Illustration of Tucker's lemma in the plane (n = 2): the complementary edge is colored red

The lemma Tucker is a set of combinatorics , which is equivalent to the Borsuk-Ulam is from the topology, established by Albert W. Tucker .

Let T be a triangulation of the closed n-ball that has antipodal symmetry on the edge, the sphere (that is, the simplices of T in yield a triangulation of , in which with the simplex is also ). ${\displaystyle B_{n}}$ ${\displaystyle S^{n-1}}$ ${\displaystyle S^{n-1}}$ ${\displaystyle S^{n-1}}$ ${\displaystyle \sigma }$ ${\displaystyle -\sigma }$

Let also be a numbering of the nodes of T that is on an odd function (i.e. for each node ). ${\displaystyle L\colon V(T)\to \{+1,-1,+2,-2,...,+n,-n\}}$ ${\displaystyle V(T)}$ ${\displaystyle S^{n-1}}$ ${\displaystyle L(-v)=-L(v)}$ ${\displaystyle v\in S^{n-1}}$

According to Tucker's lemma, T with numbering L then contains a complementary edge, that is, an edge with numbering of the associated nodes ${\displaystyle (i,-i)}$

A comparison with the Borsuk-Ulam theorem in the following version shows the analogy:

Borsuk-Ulam's theorem: Let be a continuous mapping such that the function is antipodal on the boundary ( ). Then there is one with . ${\displaystyle f\colon B_{n}\to \mathbb {R} ^{n}}$ ${\displaystyle S^{n-1}}$ ${\displaystyle f(-x)=-f(x)}$ ${\displaystyle x\in B_{n}}$ ${\displaystyle f(x)=0}$

Tucker's lemma follows from Borsuk-Ulam's theorem and vice versa (similar to Brouwer's Fixed Point Theorem from Sperner's lemma and vice versa).

Robert Freund and Michael Todd found a constructive proof of Tucker's lemma, which also provided an algorithm to find the complementary edge.

Ky Fan’s lemma is a generalization of Tucker's lemma:

Ky Fan lemma: The same requirements and definitions apply as Tucker's lemma, except that L is not subject to any restriction on the number of different numbers. If there is no complementary edge, then (T, L) contains an odd number of alternating n-dimensional simplices. A simplex is called alternating if all the numbers of the nodes differ from one another in terms of amount and their signs change.

Since an n-dimensional simplex has (n + 1) nodes, there must be different numbers for an alternating simplex (n + 1), but under the assumptions of Tucker's lemma there are only n numbers with different values. So in this case there is no alternating simplex in (T, L) and Tucker's lemma follows as a corollary to Ky Fan’s lemma.

Web links

• Frederic Meunier, Sperner and Tucker lemmas, 2010, presentation slides, pdf

Individual evidence

1. ^ Tucker, Some topological properties of disk and sphere, Proc. First Canadian Math. Congress, Montreal, 1945, Toronto: University of Toronto Press, 1946, pp. 285-309
2. ↑ Freund, Todd, A constructive proof of Tucker's combinatorial lemma, Journal of Combinatorial Theory, Series A, Volume 30, 1981, pp. 321-325
3. ↑ Ky Fan, A Generalization of Tucker's Combinatorial Lemma with Topological Applications, Annals of Mathematics, Volume 56, 1952, p. 431