Does triangulation have to be finite for Sperner's Lemma to Apply? I'm a little confused about a proof I read for Sperner's Lemma. The context was described as follows: Assume we have a n-dimensional simplex that is partitioned into smaller simplices that are either disjoint or share a full face. Sperner's Lemma states that a proper coloring of such a simplical subdivision must contain a simplex whose vertices share no colors in common, and in particular, there must be an odd number of such simplices (mod n).

Kathryn Sanchez

Kathryn Sanchez

Answered question

2022-09-05

Does triangulation have to be finite for Sperner's Lemma to Apply?
I'm a little confused about a proof I read for Sperner's Lemma. The context was described as follows: Assume we have a n-dimensional simplex that is partitioned into smaller simplices that are either disjoint or share a full face. Sperner's Lemma states that a proper coloring of such a simplical subdivision must contain a simplex whose vertices share no colors in common, and in particular, there must be an odd number of such simplices (mod n).
However, I'm a little confused by the proofs I've seen for the 1-dimension and 2-dimension cases. If we have the simplex as a line segment, it doesn't seem obvious to me that if we have a non-finite number of vertices in the interior of the segment that there need be an odd number of line segments that have differently colored endpoints; couldn't there be an infinite number of such segments? Similarly, the proof I saw for the 2d case seems to use the handshake lemma, which only applies to finite graphs.

Answer & Explanation

Konner Parker

Konner Parker

Beginner2022-09-06Added 12 answers

Step 1
In Sperner's Lemma we consider an n-dimensional simplex that is partitioned into smaller n-dimensional simplices that are either disjoint or share a full face. Let us call it a regular partition. The finiteness of such a partition is an additional requirement - but an essential one.
In fact there are infinite regular partitions. Here is an example:
Step 2
Consider the 1-simplex [-1,1] and partition it into [-1,0] and [ 1 n + 1 , 1 n ], n N .
But here is the problem: There exist Sperner coloring functions producing infinitely many 1-simplices whose vertices are colored by 2 colors, and it does not make sense to say that there is an odd number of such simplices.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?