Sperner’s Lemma - Statement

States Sperner’s Lemma on a triangulated triangle and lets you color vertices to test the condition interactively.

Consider a triangulation of a triangle. (Below, we show a regular triangulation of an equilateral triangle, but the theorem applies to any triangulation of a triangle.) We color the vertices of the triangle with three colors—say, red, green, and blue—with the following conditions:

1. The vertices of the triangle are colored with the three colors: red, green, and blue.
2. The vertices that lie on the edges of the triangle are colored with one of the colors of the endpoints of that edge—this is crucial.
3. The vertices that lie in the interior of the triangle may be colored with any of the three colors.

Conditions 1 and 2 are often referred to as the Sperner condition.

NoteTheorem: Sperner’s lemma

Any triangulation of a triangle satisfying Sperner’s condition has at least one “rainbow” triangle whose vertices are colored with all three colors: red, green, and blue.

In fact, you always have an odd number of such triangles.

// 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, 20], {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
}

// 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;

  const features = [];
  for (const triangle of subTriangles) {
    const ring = [];
    for (const coord of triangle.coordinates) {
      const c = colored.byKey.get(coord.join(',')).getCoords();
      ring.push([c.x, c.y]);
    }
    ring.push(ring[0]);
    features.push({
      type: "Feature",
      geometry: { type: "Polygon", coordinates: [ring] },
      properties: { fillColor: VM.discreteMath.triangleFillColor(triangle.vertex_colors) }
    });
  }

  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.line([...vertices, vertices[0]], {
        x: "x",
        y: "y",
        stroke: chartColors.ink,
        strokeWidth: 1
      }),
      Plot.geo(
        { type: "FeatureCollection", features },
        {
          fill: d => d.properties.fillColor,
          stroke: chartColors.ink,
          strokeWidth: 1
        }
      ),
      Plot.link(mixedEdges, {
        x1: "x1", y1: "y1", x2: "x2", y2: "y2",
        stroke: "color",
        strokeWidth: 3
      }),
      Plot.dot(
        colored.points,
        {
          x: "x",
          y: "y",
          fill: d => VM.discreteMath.vertexColor(d.color),
          r: 4
        }
      )
    ]
  }));
}

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

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;

    const [a, b, c] = triple;
    this.color = VM.discreteMath.spernerColor(a, b, c);
  }

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

  getColor() {
    return this.color;
  }
}

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

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

  return { points, byKey };
}

subTriangles = {
  const triangles = [];
  for (const coordinates of VM.discreteMath.subTriangleTriples(N)) {
    const vertex_colors = new Set();
    for (const coord of coordinates) {
      vertex_colors.add(colored.byKey.get(coord.join(',')).getColor());
    }
    triangles.push({ coordinates, vertex_colors });
  }
  return triangles;
}

// Edges between differently-colored vertices, in the shared amber/teal/
// purple pair palette (VM.discreteMath.pairColor). Same-color edges are
// skipped entirely to avoid clutter. chartColors is referenced so the
// stored colors are recomputed on a theme toggle.
mixedEdges = {
  chartColors;
  const edges = [];
  for (const { a, b } of VM.discreteMath.triangulationEdges(N)) {
    const pa = colored.byKey.get(a.join(','));
    const pb = colored.byKey.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;
}

numRGBTriangles = {
  let count = 0;
  for (const triangle of subTriangles) {
    if (triangle.vertex_colors.size === 3) count++;
  }
  return count;
}
html`<b>Number of RGB triangles: ${numRGBTriangles}</b>`

Questions

• What is the expected number of such triangles? What about the other colored triangles? Click Regenerate colors a few times at a fixed subdivision count and watch the count above — does it move around a lot, or does it seem to settle near a typical value?

• How to generate a truly random triangulation of a triangle? What is the space of all triangulations of a triangle? How to sample uniformly from this space? How does the number of RGB triangles vary with different triangulations?