Sperner’s lemma

Let ABC be a triangle, and let S be the set of vertices of some triangulation T of ABC. Let f be a mapping of S into a three-element set, say {1,2,3}=T (indicated by red/green/blue respectively in the figure), such that:

  • any point P of S, if it is on the side AB, satisfies f(P){1,2}

  • similarly if P is on the side BC, then f(P){2,3}

  • if P is on the side CA, then f(P){3,1}

(It follows that f(A)=1,f(B)=2,f(C)=3.) Then some (triangular) simplex of T, say UVW, satisfies

f(U)=1  f(V)=2  f(W)=3.

We will informally sketch a proof of a stronger statement: Let M (resp. N) be the number of simplexes satisfying (1) and whose vertices have the same orientation as ABC (resp. the opposite orientation). Then M-N=1 (whence M>0).

The proof is in the style of well-known proofs of, for example, Stokes’s theorem in the plane, or Cauchy’s theorems about a holomorphic functionMathworldPlanetmath.

Define an antisymmetric function d:T×T by


Let’s define a “circuit” of size n as an injectivePlanetmathPlanetmath mapping z of the cyclic group /n into V such that z(n) is adjacent to z(n+1) for all n in the group.

Any circuit z has what we will call a contour integral Iz, namely


Let us say that two vertices P and Q are equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath if f(P)=f(Q).

There are four steps:

1) Contour integrals are added when their corresponding circuits are juxtaposed.

2) A circuit of size 3, hitting the vertices of a simplex PQR, has contour integral

  • 0 if any two of P, Q, R are equivalent, else

  • +3 if they are inequivalent and have the same orientation as ABC, else

  • -3

3) If y is a circuit which travels around the perimeter of the whole triangle ABC, and with same orientation as ABC, then Iy=3.

4) Combining the above results, we get


where the sum contains one summand for each simplex PQR.

Remarks: In the figure, M=2 and N=1: there are two “red-green-blue” simplexes and one blue-green-red.

With the same hypotheses as in Sperner’s lemma, there is such a simplex UVW which is connectedPlanetmathPlanetmath (along edges of the triangulation) to the side AB (resp. BC,CA) by a set of vertices v for which f(v){1,2} (resp. {2,3}, {3,1}). The figure illustrates that result: one of the red-green-blue simplexes is connected to the red-green side by a red-green “curve”, and to the other two sides likewise.

The original use of Sperner’s lemma was in a proof of Brouwer’s fixed point theorem in two dimensionsMathworldPlanetmathPlanetmathPlanetmath.

Title Sperner’s lemma
Canonical name SpernersLemma
Date of creation 2013-03-22 13:44:33
Last modified on 2013-03-22 13:44:33
Owner mathcam (2727)
Last modified by mathcam (2727)
Numerical id 12
Author mathcam (2727)
Entry type Theorem
Classification msc 55M20