17
$\begingroup$

Sperner’s Lemma is often called the "combinatorial analog" of Brouwer’s Fixed Point Theorem, and similarly Tucker’s Lemma is often called the combinatorial analog of Borsuk–Ulam’s Theorem.

We can fairly directly show Borsuk–Ulam implies Brouwer, but it seems no direct combinatorial proof is known between Tucker's and Sperner's Lemma. (see a related discussion from 2013/2014 with links to good articles at Sperner's lemma and Tucker's lemma.)

To my surprise, I find that Sperner's Lemma directly implies Tucker's Lemma in two dimensions. My question: are there any recent results about such a direct combinatorial link for arbitrary dimension?

Edit: As a side comment, there is a striking consequence from Sperner $\Rightarrow$ Tucker: It is well-known that Tucker $\Rightarrow$ Borsuk-Ulam $\Rightarrow$ Brouwer $\Rightarrow$ Sperner. So Sperner $\Rightarrow$ Tucker could establish a meaningful scope of equivalence for all these results.

For clarification, I am adding a 2-dimensional example, and a proof why Tucker’s Lemma follows directly from Sperner’s Lemma. (This example only shows the boundary labelling, not the triangulation and the inside vertices).

enter image description here

Take a triangulated polygon with vertices labelled -2, -1, 1, or 2, and antipodally symmetric labelling on its boundary, satisfying the conditions of Tucker’s Lemma.

Color the boundary labels such that they meet the conditions of Sperner’s Lemma, like in the example, i.e. $1\mapsto \text{orange}$; $2\mapsto \text{blue}$; $-1, -2\mapsto \text{green}$. Assign the colors to all the Tucker-labelled vertices inside the polygon in the same way

Edit: In the two-dimensional case, such a valid Sperner labelling always exists. Please see the proof in the answer below.

Here is why this Sperner color labelling directly implies Tucker's Lemma:

Because of the valid Sperner coloring of the boundary, a 3-colored Sperner triangle must exist. But this 3-colored triangle either has a complementary green–orange edge $(-1,1)$ or a complementary green–blue edge $(-2,2)$. In other words, the existence of the complementary edge follows directly from Sperner’s Lemma, proving Tucker’s Lemma.

In the two-dimensional case, the Sperner color labelling is always compatible with the Tucker labelling, hence my question about any recent results or ideas in this direction for arbitrary dimensions.

(for a related question see this post Structure of boundary labelling in Sperner‘s Lemma)

$\endgroup$
3
  • $\begingroup$ Version 15 of this question. $\endgroup$ – Gerry Myerson Jun 11 '20 at 22:19
  • $\begingroup$ Adding a link to an article from Kathryn Nyman and Francis Edward Su (2013) where they show that Fan’s 1952 lemma on labelled triangulations of the n-sphere is equivalent to the Borsuk-Ulam theorem, and that it also implies Sperner’s Lemma. Thus giving a combinatorial version of Borsuk-Ulam $\Rightarrow$ Brouwer jstor.org/stable/10.4169/… $\endgroup$ – Claus Dollinger Jun 14 '20 at 12:48
  • $\begingroup$ Adding a really good 2019 article link, looking at origins and history of Sperner’s Lemma and how it links to Alexander’s Lemma. Alexander’s Lemma is a stronger result and was actually found two years earlier, in 1926. Great modern exposition, quite surprising historical details, and a cohomological interpretation: Nicolai Ivanov arXiv:1909.00940 $\endgroup$ – Claus Dollinger Jun 14 '20 at 13:37
3
$\begingroup$

Just to close the loop on this. I now found a simple proof that an antipodally symmetric labelling of the boundary always has a valid Sperner coloring (in two dimensions). This means Tucker’s Lemma actually follows directly from Sperner’s Lemma with a combinatorial argument. This is quite a surprise to me, because in the literature, Tucker’s Lemma/Borsuk-Ulam Theorem is generally considered stronger, in the sense that it implies Sperner’s Lemma/Brouwer’s Fixed Point Theorem.

Here is the proof about the compatible labelling, a proof by induction over antipodally symmetric pairs of boundary vertices. It assumes the coloring from the OP questions above.

For the remainder of the proof, we exclude all the cases with a complementary edge on the boundary, as there is nothing more to prove (complementary edge exists).

In the diagrams, the lines do not indicate the triangulation; the lines just indicate the antipodally symmetric pair of vertices.

Induction Base Case($2n=4$): This case obviously allows for a valid Sperner coloring, i.e. a Sperner triangle and hence a complementary edge exists inside the triangulated polygon. enter image description here

Induction Step from $2n$ to $2n+2$: Assume that the boundary has a valid Sperner coloring for its $2n$ antipodally symmetric labelled vertices. Valid Sperner coloring means that the number of color changes on the boundary is uneven (i.e. uneven number of boundary edges with endpoints of different color). Now we include another pair of antipodally symmetric pair of boundary vertices, to arrive at $2n+2$ vertices with valid Sperner coloring. When including a new pair, we have to insert it in-between two existing pairs of vertices. There are just four different cases to consider:

enter image description here enter image description here

For case A, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1 or 2 on one side, as in the diagram. But this does not add any color change to the boundary, i.e. the boundary just keeps its valid Sperner coloring. An analoguous argument works for case B. enter image description here

For case C, because we don’t allow for complementary edges on the boundary, we can only include an antipodally symmetric labelled pair of vertices with 1, 2, or -2 on one side, as in the diagram. But if it is 1, it does not not add any color change to the boundary. And if it is 2 or -2, it just adds an even number of color changes to the boundary. In both cases, the number of color changes remains uneven, i.e. the Sperner coloring of the boundary remains valid.An analoguous argument works for case D. enter image description here

Conclusion of Induction: So we have shown that a valid Sperner coloring for $2n$ antipodally symmetric labelled vertices implies that the Sperner coloring is also valid for $2n+2$ antipodally symmetric labelled vertices vertices. So starting from $2n=4$, it is valid for all $2n$, which concludes the proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.