Skip to main content
deleted 75 characters in body; edited tags
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45

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, without any additional proof steps. My question: are there any recent results about such a direct combinatorial link for arbitrary dimension?

Edit: As a side comment, there is an interestinga 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. It is an example where, and a proof why Tucker’s Lemma follows directly from Sperner’s Lemma, with "compatible" boundary labellings. (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 in a waysuch that meetsthey 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)

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, without any additional proof steps. My question: are there any recent results about such a direct combinatorial link for arbitrary dimension?

Edit: As a side comment, there is an interesting 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. It is an example where Tucker’s Lemma follows directly from Sperner’s Lemma, with "compatible" boundary labellings. (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 in a way that meets 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, see 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)

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)

added 38 characters in body; edited title
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45

Direct combinatorial link between Sperner's andLemma implies Tucker's Lemma - simple combinatorial proof

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, it seemsI find that Sperner's Lemma directly implies Tucker's Lemma in two dimensions, without any additional proof steps. My question: are there any recent results about such a direct combinatorial link for arbitrary dimension?

Edit: As a side comment, there is an interesting 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. It is an example where Tucker’s Lemma follows directly from Sperner’s Lemma, with "compatible" boundary labellings. (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.

AssumeColor the boundary labels can be colored in a way that meets 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 compatiblevalid Sperner labelling always exists, see proof in the answer below.

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 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)

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, it seems 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 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. It is an example where Tucker’s Lemma follows directly from Sperner’s Lemma, with "compatible" boundary labellings. (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.  Edit: In the two-dimensional case, such a compatible labelling always exists, see the answer below.

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 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)

Sperner's Lemma implies Tucker's Lemma - simple combinatorial proof

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, without any additional proof steps. My question: are there any recent results about such a direct combinatorial link for arbitrary dimension?

Edit: As a side comment, there is an interesting 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. It is an example where Tucker’s Lemma follows directly from Sperner’s Lemma, with "compatible" boundary labellings. (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 in a way that meets 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, see 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)

deleted 47 characters in body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
added 376 characters in body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
added 70 characters in body; edited title
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
added 70 characters in body; edited title
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
edited body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
improved diagram for clarification
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
correct description for Tucker: antipodally symmetric
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
added 54 characters in body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
Minor tidying
Source Link
LSpice
  • 12.9k
  • 4
  • 45
  • 69
Loading
edited tags
Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
added 31 characters in body
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading
Source Link
Claus
  • 6.9k
  • 4
  • 25
  • 45
Loading