3
$\begingroup$

Consider a triangulated polygon in the 2-dimensional plane, where each vertex is labelled green, blue, or orange. Sperner's Lemma asserts that a fully-colored triangle exists in the triangulation, if the boundary vertices a suitably labelled.

Looking at the close combinatorial link between Sperner's Lemma and Tucker's Lemma (Direct combinatorial link between Sperner's and Tucker's Lemma?), I am interested in structural results about the boundary labelling for Sperner's Lemma.

To specify my question, I am using an example of a Sperner labelling of the boundary vertices (not showing the triangulation and inside vertices). enter image description here

It is not obvious at first sight that this is a valid Sperner labelling. But the number of color-changes (e.g. from blue to green) is uneven, so the conditions of Sperner's Lemma are met. This can best be seen in the diagram on the right which just shows the color changes.

How is this complex labelling example related to the minimum base case? Base case means when the boundary has the minimum labelling with just three color-changes: enter image description here

My working hypothesis is that every valid Sperner labelling of the boundary follows from the minimum base case in a unique way: by adding layers of even-numbered color changes. This is of key interest when studying the link with Tucker's Lemma which requires an antipodally symmetric boundary labelling.

For clarification of this idea, the example from above decomposes into three layers. Starting from the (uneven) base layer and adding two (even) layers of color-changes: enter image description here

I have searched for results in combinatorics and topology in that direction, but could not find anything. Would someone by able to point me to a good reference?

$\endgroup$

1 Answer 1

3
$\begingroup$

For an answer, see discussion of the degree of the Sperner boundary labelling in the Musin (2014) article https://arxiv.org/pdf/1405.7513.pdf

If the pdf link does not work try https://arxiv.org/abs/1405.7513

Effectively, a valid Sperner boundary labelling is a piecewise linear automorphism on the boundary with odd degree.

$\endgroup$
1
  • $\begingroup$ Thanks a lot for a great reference. Exactly what I was looking for. $\endgroup$
    – Claus
    Jul 18, 2020 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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