Sperner’s Lemma - Combinatorial Proof

Proves Sperner’s Lemma with the ‘doors’ argument: a path that must exit through an odd number of bicolored edges.

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

// VM is the shared utility library, loaded globally via _includes/head-scripts.html (js/**). This page uses VM.discreteMath.barycentricTriples, VM.discreteMath.subTriangleTriples, VM.discreteMath.spernerColor, VM.discreteMath.triangulationEdges, VM.discreteMath.pairColor, VM.discreteMath.triangleFillColor, VM.discreteMath.vertexColor.
VM = window.VM

vmTheme = Generators.observe(notify => VM.plotting.onThemeChange(notify))
chartColors = VM.plotting.colors(vmTheme)

viewof N = {
  const slider = Inputs.range([2, 25], {step: 1, value: 15, label: "Number of subdivisions"})
  slider.classList.add("ojs-fill")
  return slider
}

// Referenced (but otherwise unused) inside coloredPoints below so that
// clicking the button re-runs the random color assignment without moving
// the slider.
viewof regenerate = {
  const button = Inputs.button("Regenerate colors", {value: 0, reduce: v => v + 1})
  button.classList.add("ojs-auto")
  return button
}

// === Main Plot ===
// A diagram, not a graph: no axes, and a height chosen so the unit-wide
// equilateral triangle is drawn to scale (Plot stretches y to fill
// whatever height it is given otherwise).
viewof mainPlot = {
  const width = 800;
  const margin = 20;
  const height = (width - 2 * margin) * Math.sqrt(3) / 2 + 2 * margin;
  return Plot.plot(VM.plotting.plotOptions({
    width,
    height,
    margin,
    grid: false,
    x: { domain: [0, 1], axis: null },
    y: { domain: [0, Math.sqrt(3) / 2], axis: null },
    marks: [
      Plot.geo(
        { type: "FeatureCollection", features: triangleFeatures(triangles.all, cpMap) },
        { fill: d => d.properties.fillColor, stroke: chartColors.ink, strokeWidth: 1 }
      ),
      Plot.link(mixedEdgeFeatures(N, cpMap), {
        x1: "x1", y1: "y1", x2: "x2", y2: "y2",
        stroke: "color",
        strokeWidth: 3
      }),
      ...makeEdgeLines(triangles.rg, chartColors),
      ...makeEdgeLines(triangles.rgb, chartColors),
      Plot.dot(
        coloredPointsWithTitle,
        {
          x: "x",
          y: "y",
          fill: d => VM.discreteMath.vertexColor(d.color),
          r: 4,
          title: "title"
        }
      ),
      ...makeSpecialPoints(triangles.rg, chartColors),
      ...makeSpecialPoints(triangles.rgb, chartColors)
    ]
  }));
}

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

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

isEdgeBoundary = (a, b) => {
  for (let i = 0; i < 3; i++) {
    if (a.barycentricTriple[i] === 0 && b.barycentricTriple[i] === 0) return true;
  }
  return false;
}

// === Color Assignment Class ===
class ColoredPoint {
  constructor(triple, vertices, N) {
    this.barycentricTriple = triple;
    const [A, B, C] = vertices;
    const [a, b, c] = triple;

    this.x = (a * A.x + b * B.x + c * C.x) / N;
    this.y = (a * A.y + b * B.y + c * C.y) / N;

    this.color = VM.discreteMath.spernerColor(a, b, c);
  }

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

  getColor() {
    return this.color;
  }
}

classifyTriangle = (vertexColors) => {
  const set = new Set(vertexColors);
  return {
    isRG: set.has('red') && set.has('green') && !set.has('blue'),
    isRGB: set.has('red') && set.has('green') && set.has('blue'),
    vertexColors: set
  }
}

getTriangleEdges = (points, classification) => {
  const edges = [];

  if (classification.isRG) {
    for (let k = 0; k < 3; k++) {
      const a = points[k], b = points[(k + 1) % 3];
      if (a.getColor() !== b.getColor()) {
        edges.push({ point: midpoint(a, b), source: [a, b] });
      }
    }
  }

  if (classification.isRGB) {
    for (let k = 0; k < 3; k++) {
      const pairs = [[k, (k + 1) % 3], [k, (k + 2) % 3]];
      for (const [i, j] of pairs) {
        if (points[i].getColor() === 'red' && points[j].getColor() === 'green') {
          edges.push({ point: midpoint(points[i], points[j]), source: [points[i], points[j]] });
        }
      }
    }
    edges.push({ point: centroid(points[0].getCoords(), points[1].getCoords(), points[2].getCoords()), source: null });
  }

  return edges;
}

getSpecialPoints = (edges, classification) => {
  const specials = [];

  for (const edge of edges) {
    if (!edge.source) continue;
    const [a, b] = edge.source;
    if (isEdgeBoundary(a, b)) specials.push(edge.point);
  }

  if (classification.isRGB) {
    for (const edge of edges) {
      if (edge.source === null) {
        specials.push(edge.point);
        break;
      }
    }
  }

  return specials;
}

generateTriangleData = (coordinates, cpMap) => {
  const points = [];
  for (const coord of coordinates) points.push(cpMap.get(coord.join(',')));

  const colors = [];
  for (const p of points) colors.push(p.getColor());
  const vertex_colors = new Set(colors);

  const classification = classifyTriangle(vertex_colors);
  const edgesWithSource = getTriangleEdges(points, classification);
  const special_points = getSpecialPoints(edgesWithSource, classification);

  const edges = [];
  for (const e of edgesWithSource) edges.push(e.point);

  return { coordinates, vertex_colors, classification, edges, special_points };
}

triangleFillColor = tri => {
  if (tri.classification.isRGB) return VM.discreteMath.triangleFillColor(tri.vertex_colors);
  if (tri.classification.isRG) return VM.plotting.alpha('warn', 0.3);
  return 'none';
}

triangleFeatures = (triangles, cpMap) => {
  const features = [];
  for (const tri of triangles) {
    const pts = [];
    for (const c of tri.coordinates) pts.push(cpMap.get(c.join(',')).getCoords());

    const ring = [];
    for (const p of pts) ring.push([p.x, p.y]);
    ring.push(ring[0]);

    features.push({
      type: "Feature",
      geometry: { type: "Polygon", coordinates: [ring] },
      properties: { fillColor: triangleFillColor(tri) }
    });
  }
  return features;
}

// Edges between differently-colored vertices, in the shared amber/teal/
// purple pair palette (VM.discreteMath.pairColor). Distinct from the
// ink-colored "door" path below -- this is a general structural layer, not
// specific to RG doors.
mixedEdgeFeatures = (N, cpMap) => {
  const edges = [];
  for (const { a, b } of VM.discreteMath.triangulationEdges(N)) {
    const pa = cpMap.get(a.join(','));
    const pb = cpMap.get(b.join(','));
    const color = VM.discreteMath.pairColor(pa.getColor(), pb.getColor());
    if (!color) continue;
    const ca = pa.getCoords();
    const cb = pb.getCoords();
    edges.push({ x1: ca.x, y1: ca.y, x2: cb.x, y2: cb.y, color });
  }
  return edges;
}

// The "door" path through each RG/RGB room, in the page's ink color (the
// palette snapshot is passed in from the plot cell, which re-runs on a
// theme toggle).
makeEdgeLines = (triangles, colors) => {
  const lines = [];
  for (const tri of triangles) {
    for (let i = 0; i < tri.edges.length; i++) {
      const pt = tri.edges[i];
      const next = tri.edges[(i + 1) % tri.edges.length];
      lines.push(Plot.line([pt, next], { x: "x", y: "y", stroke: colors.ink, strokeWidth: 5 }));
    }
  }
  return lines;
}

// Path endpoints: a hollow ring, filled with the halo color (white on
// light, the page background on dark) rather than a literal white.
makeSpecialPoints = (triangles, colors) => {
  const dots = [];
  for (const tri of triangles) {
    for (const pt of tri.special_points) {
      if (pt && pt.x !== undefined && pt.y !== undefined) {
        dots.push(Plot.dot([pt], { x: "x", y: "y", fill: colors.halo, stroke: colors.ink, r: 4 }));
      }
    }
  }
  return dots;
}

// === Define Base Triangle Vertices ===
vertices = [
  {x: 1, y: 0},
  {x: 0.5, y: Math.sqrt(3) / 2},
  {x: 0, y: 0},
]

coloredPoints = {
  regenerate;
  const points = [];
  for (const triple of VM.discreteMath.barycentricTriples(N)) {
    points.push(new ColoredPoint(triple, vertices, N));
  }
  return points;
}

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

coloredPointsWithTitle = {
  const arr = [];
  for (const d of coloredPoints) {
    arr.push({ ...d, title: `(${d.barycentricTriple.join(", ")})` });
  }
  return arr;
}

generateAllTriangles = (N, cpMap) => {
  const all = [], rg = [], rgb = [];

  for (const coordinates of VM.discreteMath.subTriangleTriples(N)) {
    const data = generateTriangleData(coordinates, cpMap);
    all.push(data);
    if (data.vertex_colors.has('red') && data.vertex_colors.has('green')) {
      if (data.vertex_colors.has('blue')) {
        rgb.push(data);
      } else {
        rg.push(data);
      }
    }
  }

  return { all, rg, rgb };
}

triangles = generateAllTriangles(N, cpMap);

Imagine each small triangle as a room with three walls. 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.

(In the plot above, RRG/RGG triangles are shaded a much fainter amber than in the diagram below, so the rainbow triangles stay the visual focus; every other non-rainbow triangle is left unfilled. Mixed-color edges still get a colored line, the same convention used on the other Sperner’s lemma pages.)

// The three room types, each drawn with its vertex colors; the fill is
// resolved from the palette when the marks are built, not stored here.
doorExamples = [
  {
    label: "RGB",
    vertices: [
      {x: 50, y: 150, color: "red"},
      {x: 100, y: 50, color: "green"},
      {x: 150, y: 150, color: "blue"}
    ]
  },
  {
    label: "RRG",
    vertices: [
      {x: 250, y: 150, color: "red"},
      {x: 300, y: 50, color: "red"},
      {x: 350, y: 150, color: "green"}
    ]
  },
  {
    label: "RGG",
    vertices: [
      {x: 450, y: 150, color: "red"},
      {x: 500, y: 50, color: "green"},
      {x: 550, y: 150, color: "green"}
    ]
  }
]

// Builds the marks for the RGB/RRG/RGG example diagram: one filled polygon
// per example triangle (the shared rainbow purple for RGB, a solid amber
// for the two-door rooms -- stronger than the faint amber in the main
// plot, since here nothing competes with it), a bold dashed line on each
// RG ("door") edge, a colored dot per vertex, and a label above each
// triangle. chartColors is referenced so the fills are recomputed on a
// theme toggle.
doorExampleMarks = {
  chartColors;
  const fills = [];
  const doors = [];
  const dots = [];
  const labels = [];

  for (const tri of doorExamples) {
    const { vertices, label } = tri;

    const vertexColors = [];
    for (const v of vertices) vertexColors.push(v.color);
    let fill = VM.discreteMath.triangleFillColor(vertexColors);
    if (fill === 'none') fill = VM.plotting.alpha('warn', 0.9);

    const ring = [];
    for (const v of vertices) ring.push([v.x, v.y]);
    ring.push(ring[0]);
    fills.push({
      type: "Feature",
      geometry: { type: "Polygon", coordinates: [ring] },
      properties: { fill }
    });

    for (let i = 0; i < 3; i++) {
      const a = vertices[i], b = vertices[(i + 1) % 3];
      const isRG = (a.color === "red" && b.color === "green") || (a.color === "green" && b.color === "red");
      if (isRG) doors.push({ x1: a.x, y1: a.y, x2: b.x, y2: b.y });
    }

    for (const v of vertices) dots.push(v);

    const top = vertices[1];
    labels.push({ x: top.x, y: top.y, text: label });
  }

  return { fills, doors, dots, labels };
}

viewof doorExamplePlot = Plot.plot(VM.plotting.plotOptions({
  width: 600,
  height: 200,
  margin: 10,
  grid: false,
  x: { domain: [0, 600], axis: null },
  y: { domain: [200, 0], axis: null },
  marks: [
    Plot.geo(
      { type: "FeatureCollection", features: doorExampleMarks.fills },
      { fill: d => d.properties.fill, stroke: chartColors.ink, strokeWidth: 1 }
    ),
    Plot.link(doorExampleMarks.doors, {
      x1: "x1", y1: "y1", x2: "x2", y2: "y2",
      stroke: chartColors.ink, strokeWidth: 4, strokeDasharray: "8,4"
    }),
    Plot.dot(doorExampleMarks.dots, { x: "x", y: "y", fill: d => VM.discreteMath.vertexColor(d.color), stroke: chartColors.ink, r: 4 }),
    Plot.text(doorExampleMarks.labels, { x: "x", y: "y", text: "text", dy: -10, fontSize: 12 })
  ]
}))

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.

Following the Doors

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

• The amber 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.

Putting this all together gives us a key result:

NoteTheorem: Doors plus RGB triangles is even

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

From this, we immediately get:

NoteTheorem: RGB triangles share parity with the boundary

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:

NoteConjecture: Odd number of RG boundary edges

The number of RG boundary edges is odd.

Sperner’s condition implies that the only RG boundary edges must appear on the bottom edge (the edge running from the red vertex to the green vertex — the blue vertex can’t be an endpoint of an RG edge), which reduces the problem to the following.

NoteConjecture: Odd number of RG edges on the bottom

The number of RG boundary edges on the bottom edge is odd.

This has a short, elegant proof — but it’s also easy to think you’ve proven it when you haven’t, so rather than writing it out, here it is as a genuine exercise. Try each step before opening the next.

TipExercise

Prove the conjecture above: the bottom edge is a sequence of points colored red or green, starting red and ending green (by Sperner’s condition, no blue is possible there). Call the sequence of colors \(x_0, x_1, \dots, x_M\), read left to right.

1. Encode each color as a number: \(x_i = 0\) if the \(i\)-th point is red, \(x_i = 1\) if it’s green. What are \(x_0\) and \(x_M\)?
2. An RG edge is an index \(i\) with \(x_i \neq x_{i+1}\). Write the total number of RG edges as a sum involving the \(x_i\) — without an absolute value or a case split. (Consider working modulo 2.)
3. Combine steps 1 and 2 to conclude the number of RG edges is odd.

Try it below: click Regenerate colors a few times and check that the count is always odd, no matter how the interior points are colored.

viewof M = {
  const slider = Inputs.range([1, 25], {step: 1, value: 5, label: "Number of subdivisions"})
  slider.classList.add("ojs-fill")
  return slider
}

// Referenced (but otherwise unused) inside boundaryColors below so that
// clicking the button re-randomizes the interior colors without moving
// the slider.
viewof boundaryRegenerate = {
  const button = Inputs.button("Regenerate colors", {value: 0, reduce: v => v + 1})
  button.classList.add("ojs-auto")
  return button
}

viewof boundaryPlot = Plot.plot(VM.plotting.plotOptions({
  width: 600,
  height: 100,
  margin: 20,
  grid: false,
  x: { domain: [0, M], axis: null },
  y: { domain: [0, 1], axis: null },
  marks: [
    Plot.link(boundaryEdges.segments, {
      x1: "x1", y1: 0.5, x2: "x2", y2: 0.5,
      stroke: chartColors.ink, strokeWidth: d => d.bold ? 6 : 1
    }),
    Plot.dot(boundaryEdges.points, { x: "x", y: 0.5, fill: d => VM.discreteMath.vertexColor(d.color), stroke: chartColors.ink, r: 5 }),
    Plot.text([{ x: M / 2, y: 0.9, text: `Number of RG edges: ${boundaryEdges.boldCount}` }], {
      x: "x", y: "y", text: "text", fontSize: 16
    })
  ]
}))

boundaryColors = {
  boundaryRegenerate;
  const colors = [];
  for (let i = 0; i <= M; i++) {
    if (i === 0) {
      colors.push('red');
    } else if (i === M) {
      colors.push('green');
    } else {
      colors.push(Math.random() < 0.5 ? 'red' : 'green');
    }
  }
  return colors;
}

boundaryEdges = {
  const points = [];
  for (let i = 0; i <= M; i++) points.push({ x: i, color: boundaryColors[i] });

  const segments = [];
  let boldCount = 0;
  for (let i = 0; i < M; i++) {
    const bold = boundaryColors[i] !== boundaryColors[i + 1];
    if (bold) boldCount++;
    segments.push({ x1: i, x2: i + 1, bold });
  }

  return { points, segments, boldCount };
}

Questions

• Design an app for visualizing this proof for any triangulation of a triangle, not just uniform subdivisions. How would you generate random triangulations? How would you efficiently loop through all the triangles?

• This proof generalizes to an \(n\)-simplex for any \(n\). For \(n=1\), we recover the case of a line segment. For \(n=2\), we have Sperner’s lemma. What is the statement for \(n=3\)? How would you visualize it?

  • For \(n=2\), the case of a line segment can be thought of as an intermediate value theorem: if a continuous function \(f\) has \(f(a) < 0\) and \(f(b) > 0\), then there is a point \(c \in (a, b)\) with \(f(c) = 0\). Do you see it? What is the analogous statement for \(n=3\)?