Skip to main content
11 of 15
added 376 characters in body
Claus
  • 6.9k
  • 4
  • 25
  • 45

Direct combinatorial link between Sperner's and Tucker's Lemma

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, there seems to be a large class of cases where Sperner's Lemma directly implies Tucker's Lemma, without any additional proof steps. My question: are there any recent results about such a direct combinatorial link?

Edit: As a side comment, there is an interesting consequence from these cases Sperner $\Rightarrow$ Tucker: It is well-known that Tucker $\Rightarrow$ Borsuk-Ulam $\Rightarrow$ Brouwer $\Rightarrow$ Sperner. So if the class of cases Sperner $\Rightarrow$ Tucker is “sufficiently large”, this could establish a meaningful scope of equivalence for all these results.

For clarification, I am adding a 2-dimensional example. It is an example where Tucker’s Lemma follows directly from Sperner’s Lemma, under suitable "compatibility" conditions on the boundary labelling. (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.

Assume the boundary labels can be colored in a way that meets the conditions of Sperner’s Lemma, like in the example. This is the compatibility condition.

Assign the colors to all the Tucker-labelled vertices inside the polygon in the same way, i.e. $1\mapsto \text{orange}$; $2\mapsto \text{blue}$; $-1, -2\mapsto \text{green}$.

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

Because of the 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.

As the example illustrates, the Sperner color labelling seems to be compatible with a large class of Tucker labellings, hence my question about any recent results or ideas in this direction.

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

Claus
  • 6.9k
  • 4
  • 25
  • 45