Sperner’s Lemma - Combinatorial Proof

import { slider } from "@jashkenas/inputs"

viewof N = slider({
  min: 2,
  max: 25,
  step: 1,
  value: 15,
  width: 500,
  title: "Number of subdivisions"
})

equilateral_triangle_vertices = [
  {x: 1, y: 0},
  {x: 0.5, y: Math.sqrt(3) / 2},
  {x: 0, y: 0},
]

barycentric_coords = {
  let result = [];
  for (let i = 0; i <= N; i++) {
    for (let j = 0; j <= N - i; j++) {
      result.push([i, j, N - i - j]);
    }
  }
  return result;
}

centroid = (p1, p2, p3) => ({
  x: (p1.x + p2.x + p3.x) / 3,
  y: (p1.y + p2.y + p3.y) / 3
});

randomChoice = (choices) => choices[Math.floor(Math.random() * choices.length)];

class ColoredPoint {
  constructor(triple, vertices, N) {
    this.barycentricTriple = triple;
    const [A, B, C] = vertices;

    this.x = (triple[0] * A.x + triple[1] * B.x + triple[2] * C.x) / N;
    this.y = (triple[0] * A.y + triple[1] * B.y + triple[2] * C.y) / N;

    this.color = this._assignColor(triple);
  }

  _assignColor([a, b, c]) {
    if (a === 0 && b === 0) return 'red';
    if (b === 0 && c === 0) return 'green';
    if (c === 0 && a === 0) return 'blue';
    if (a === 0) return randomChoice(['red', 'blue']);
    if (b === 0) return randomChoice(['red', 'green']);
    if (c === 0) return randomChoice(['green', 'blue']);
    return randomChoice(['red', 'green', 'blue']);
  }

  getCoords() {
    return { x: this.x, y: this.y };
  }

  getColor() {
    return this.color;
  }
}

coloredPointsMap = {
  const coloredPoints = barycentric_coords.map(triple =>
    new ColoredPoint(triple, equilateral_triangle_vertices, N)
  );

  const map = new Map();
  for (const p of coloredPoints) {
    map.set(p.barycentricTriple.join(','), p);
  }

  return { coloredPoints, coloredPointsMap: map };
}

generateTriangleData = (coordinates, cpMap) => {
  const points = coordinates.map(coord => cpMap.get(coord.join(',')));
  const colors = points.map(p => p.getColor());
  const vertex_colors = new Set(colors);

  let edges = [];
  let special_points = [];

  const computeMidpoint = (a, b) => {
    const c1 = a.getCoords();
    const c2 = b.getCoords();
    return {
      x: (c1.x + c2.x) / 2,
      y: (c1.y + c2.y) / 2
    };
  };

  const isSpecial = (a, b) => a.barycentricTriple[1] === 0 && b.barycentricTriple[1] === 0;

  const RED = 'red', GREEN = 'green', BLUE = 'blue';

  if (vertex_colors.has(RED) && vertex_colors.has(GREEN) && !vertex_colors.has(BLUE)) {
    for (let k = 0; k < 3; k++) {
      const a = points[k], b = points[(k + 1) % 3];
      if (colors[k] !== colors[(k + 1) % 3]) {
        const midpoint = computeMidpoint(a, b);
        edges.push(midpoint);
        if (isSpecial(a, b)) special_points.push(midpoint);
      }
    }
  }

  if (vertex_colors.has(RED) && vertex_colors.has(GREEN) && vertex_colors.has(BLUE)) {
    for (let k = 0; k < 3; k++) {
      const pairs = [
        [k, (k + 1) % 3],
        [k, (k + 2) % 3]
      ];

      for (const [i, j] of pairs) {
        if (colors[i] === RED && colors[j] === GREEN) {
          const a = points[i], b = points[j];
          const midpoint = computeMidpoint(a, b);
          edges.push(midpoint);
          if (isSpecial(a, b)) special_points.push(midpoint);
        }
      }
    }
    const centroidPoint = centroid(...points.map(p => p.getCoords()));
    edges.push(centroidPoint);
    special_points.push(centroidPoint);
  }

  console.log(special_points);
  return { coordinates, vertex_colors, edges, special_points };
}

subTriangles = {
  const triangles = [], trianglesRG = [], trianglesRGB = [];
  const cpMap = coloredPointsMap.coloredPointsMap;

  // Upward
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N - i; j++) {
      const coords = [
        [i, j, N - i - j],
        [i + 1, j, N - i - j - 1],
        [i, j + 1, N - i - j - 1]
      ];
      const data = generateTriangleData(coords, cpMap);
      triangles.push(data);
      if (data.vertex_colors.has('red') && data.vertex_colors.has('green')) {
        data.vertex_colors.has('blue') ? trianglesRGB.push(data) : trianglesRG.push(data);
      }
    }
  }

  // Downward
  for (let i = 0; i < N - 1; i++) {
    for (let j = 0; j < N - i - 1; j++) {
      const coords = [
        [i + 1, j, N - i - j - 1],
        [i + 1, j + 1, N - i - j - 2],
        [i, j + 1, N - i - j - 1]
      ];
      const data = generateTriangleData(coords, cpMap);
      triangles.push(data);
      if (data.vertex_colors.has('red') && data.vertex_colors.has('green')) {
        data.vertex_colors.has('blue') ? trianglesRGB.push(data) : trianglesRG.push(data);
      }
    }
  }

  return { triangles, trianglesRG, trianglesRGB };
}

viewof plotALL = {
  const cpMap = coloredPointsMap.coloredPointsMap;

  const triangleFeatures = (triangles, fillColor) =>
    triangles.map(({ coordinates }) => {
      const pts = coordinates.map(c => cpMap.get(c.join(',')).getCoords());
      return {
        type: "Feature",
        geometry: {
          type: "Polygon",
          coordinates: [[...pts, pts[0]].map(p => [p.x, p.y])]
        },
        properties: { fillColor }
      };
    });

  const makeEdgeLines = triangles =>
    triangles.flatMap(tri =>
      tri.edges.map((pt, i, arr) => {
        const next = arr[(i + 1) % arr.length];
        return Plot.line([pt, next], {
          x: "x",
          y: "y",
          stroke: "black",
          strokeWidth: 5
        });
      })
    );

  const makeSpecialPoints = triangles =>
    triangles.flatMap(tri =>
      tri.special_points
        .map(pt =>
          pt && pt.x !== undefined && pt.y !== undefined
            ? Plot.dot([pt], { x: "x", y: "y", fill: "white", stroke: "black", r: 5 })
            : null
        )
        .filter(Boolean)
    );

  const edgeLines = makeEdgeLines(subTriangles.trianglesRG);
  const edgeLinesRGB = makeEdgeLines(subTriangles.trianglesRGB);
  const special_pointsRG = makeSpecialPoints(subTriangles.trianglesRG);
  const special_pointsRGB = makeSpecialPoints(subTriangles.trianglesRGB);

  return Plot.plot({
    width: 800,
    height: 800,
    x: { label: "x", domain: [0, 1] },
    y: { label: "y", domain: [0, Math.sqrt(3) / 2] },
    marks: [
      Plot.geo(
        { type: "FeatureCollection", features: triangleFeatures(subTriangles.triangles, "white") },
        { fill: d => d.properties.fillColor, stroke: "black", strokeWidth: 1 }
      ),
      Plot.geo(
        { type: "FeatureCollection", features: triangleFeatures(subTriangles.trianglesRG, "rgba(255, 215, 0, 0.7)") },
        { fill: d => d.properties.fillColor, stroke: "black", strokeWidth: 1 }
      ),
      Plot.geo(
        { type: "FeatureCollection", features: triangleFeatures(subTriangles.trianglesRGB, "rgba(0, 0, 0, 0.25)") },
        { fill: d => d.properties.fillColor, stroke: "black", strokeWidth: 1 }
      ),
      ...edgeLines,
      ...edgeLinesRGB,
      Plot.dot(
        coloredPointsMap.coloredPoints.map(d => ({
          ...d,
          title: `(${d.barycentricTriple.join(", ")})`
        })),
        {
          x: "x",
          y: "y",
          fill: "color",
          r: 5,
          title: "title"
        }
      ),
      ...special_pointsRG,
      ...special_pointsRGB
    ]
  });
}

This picture is a combinatorial proof of Sperner’s Lemma.

Imagine each small triangle as a room with three walls. Next we do a trick that I do not know how to motivate: treat each RG edge as a door. Here’s what we observe:

1. RGB triangles have exactly one door.
   
2. RRG and RGG triangles have two doors.
   
3. All other triangles have no doors.

// Create an SVG and draw three triangles with vertex colors and bold RG edges

svg = {
  const width = 600, height = 200;
  const svg = DOM.svg(width, height);
  svg.setAttribute("width", width);
  svg.setAttribute("height", height);
  svg.style.background = "#fff";

  // Triangle definitions: each vertex has [x, y, color]
  const triangles = [
    {
      vertices: [
        [50, 150, "red"],
        [100, 50, "green"],
        [150, 150, "blue"]
      ],
      fill: "lightgray",
      label: "RGB"
    },
    {
      vertices: [
        [250, 150, "red"],
        [300, 50, "red"],
        [350, 150, "green"]
      ],
      fill: "rgba(255, 215, 0, 1)",
      label: "RRG"
    },
    {
      vertices: [
        [450, 150, "red"],
        [500, 50, "green"],
        [550, 150, "green"]
      ],
      fill: "rgba(255, 215, 0, 1)",
      label: "RGG"
    }
  ];

  for (const {vertices, fill, label} of triangles) {
    // Draw triangle fill
    const polygon = document.createElementNS("http://www.w3.org/2000/svg", "polygon");
    polygon.setAttribute("points", vertices.map(v => `${v[0]},${v[1]}`).join(" "));
    polygon.setAttribute("fill", fill);
    polygon.setAttribute("stroke", "black");
    polygon.setAttribute("stroke-width", "1");
    svg.appendChild(polygon);

    // Draw edges with RG edges bolded
    for (let i = 0; i < 3; i++) {
      const [x1, y1, c1] = vertices[i];
      const [x2, y2, c2] = vertices[(i + 1) % 3];

      const isRG = (c1 === "red" && c2 === "green") || (c1 === "green" && c2 === "red");

      const edge = document.createElementNS("http://www.w3.org/2000/svg", "line");
      edge.setAttribute("x1", x1);
      edge.setAttribute("y1", y1);
      edge.setAttribute("x2", x2);
      edge.setAttribute("y2", y2);
      edge.setAttribute("stroke", "black");
      edge.setAttribute("stroke-width", isRG ? "4" : "1");
      if (isRG) edge.setAttribute("stroke-dasharray", "8,4"); // dotted line
      svg.appendChild(edge);
    }

    // Draw vertices with colors
    for (const [x, y, color] of vertices) {
      const circle = document.createElementNS("http://www.w3.org/2000/svg", "circle");
      circle.setAttribute("cx", x);
      circle.setAttribute("cy", y);
      circle.setAttribute("r", 5);
      circle.setAttribute("fill", color);
      svg.appendChild(circle);
    }

    // Add label
    const [lx, ly] = vertices[1]; // top vertex
    const text = document.createElementNS("http://www.w3.org/2000/svg", "text");
    text.setAttribute("x", lx);
    text.setAttribute("y", ly - 10);
    text.setAttribute("text-anchor", "middle");
    text.setAttribute("font-size", "12");
    text.setAttribute("font-family", "sans-serif");
    text.textContent = label;
    svg.appendChild(text);
  }

  return svg;
}

In other words, we can identify RGB triangles as the rooms with an odd number of doors. Sperner’s Lemma, then, can be restated in a more visual way:

If Sperner’s condition holds, there is at least one room with an odd number of doors.

We’ll prove a related version of this statement.

---

Picture all the possible paths that can be formed by stepping through these RG doors — the black lines in the diagram represent all of these paths.

• The yellow triangles have paths that enter through one door and exit through another — like hallways.
  
• The RGB triangles have only one door, so they are endpoints — there’s no way to pass through.

Using simple logic, we can deduce the following:

1. No two paths intersect.
   
2. Some paths form closed loops.
   
3. Paths that do not form loops must have two endpoints, so the total number of endpoints is even.
   
4. The only possible endpoints are:
   1. An RG door on the outer boundary of the big triangle
      
   2. An RGB triangle

This is where Sperner’s condition comes in — it controls which boundary edges are allowed.

Putting this all together gives us a key result:

Theorem 1 The sum of the number of RG boundary edges, and the number of RGB triangles must be even.

From this, we immediately get:

Theorem 2 The number of RGB triangles is odd if and only if the number of RG edges on the boundary is odd.

So to conclude the proof, all that remains is to show: The number of RG boundary edges is odd. This final step uses induction. The proof itself is short, but there’s a subtle trick — it’s easy to overlook unless you write it out carefully. Give it a shot!

 

viewof M = slider({
  min: 1,
  max: 25,
  step: 1,
  value: 5,
  width: 500,
  title: "Number of subdivisions"
})

viewof plot = {
  const colors = Array.from({length: M + 1}, (_, i) => {
    if (i === 0) return "red";
    if (i === M) return "green";
    return Math.random() < 0.5 ? "red" : "green";
  });
  const x = d3.scaleLinear().domain([0, M]).range([20, 580]);
  const svg = d3.create("svg").attr("width", 600).attr("height", 100);
  let boldCount = 0;

  for (let i = 0; i < M; i++) {
    const c1 = colors[i], c2 = colors[i + 1];
    const bold = c1 !== c2;
    if (bold) boldCount++;
    svg.append("line")
      .attr("x1", x(i)).attr("x2", x(i + 1))
      .attr("y1", 50).attr("y2", 50)
      .attr("stroke", "black")
      .attr("stroke-width", bold ? 6 : 1);
  }

  svg.selectAll("circle")
    .data(colors)
    .join("circle")
    .attr("cx", (_, i) => x(i))
    .attr("cy", 50)
    .attr("r", 5)
    .attr("fill", d => d)
    .attr("stroke", "black");

  svg.append("text")
    .attr("x", 150).attr("y", 15)
    .text(`Number of RG edges: ${boldCount}`)
    .attr("font-size", 20);

  return svg.node();
}

 

Questions

The app at the top of this page demonstrates the proof by dividing a triangle uniformly into smaller triangles. However, Sperner’s Lemma is much more general: it applies to any triangulation of a triangle, as long as the vertices are colored according to Sperner’s condition. The proof itself never relies on the triangulation being uniform — so it holds for any triangulation. That said, the app is harder to generalize for arbitrary triangulations.

• How does one generate random triangulations?

One natural approach is to use Delaunay triangulations, but how random are these triangulations? Once you have such a triangulation, the next step is:

• How do you efficiently loop through all the triangles?

While this isn’t a research question, implementing a general Sperner’s Lemma checker on arbitrary triangulations would be a neat exercise, combining computational geometry with combinatorics.