Sperner’s lemma (1928)

Subdivide a triangle and label each vertex 0, 1 or 2, with the corners labelled 0, 1, 2 and each side vertex labelled like one of its side’s endpoints (interior labels are free). Emanuel Sperner proved that an odd number of small triangles carry all three labels. Picture labels 0-1 edges as doors: one enters from the bottom side, and following doors from room to room can only stop in a fully labelled room.

import matplotlib.pyplot as plt
import numpy as np

from mathematicskit.topology import fully_labeled_triangles, random_sperner_labeling, triangle_grid

grid = triangle_grid(12)
counts = [len(fully_labeled_triangles(grid, random_sperner_labeling(grid, seed=s))) for s in range(2000)]
print("fully labelled triangles over 2000 random labellings: all odd?", all(c % 2 == 1 for c in counts))

fully labelled triangles over 2000 random labellings: all odd? True

One labelling, its doors, and its fully labelled triangles

labels = random_sperner_labeling(grid, seed=7)
full = fully_labeled_triangles(grid, labels)
xy = grid.cartesian
fig, axes = plt.subplots(1, 2, figsize=(12, 5.5), width_ratios=(1.2, 1))
ax = axes[0]
ax.triplot(*xy.T, grid.triangles, color="0.75", lw=0.6)
for tri in grid.triangles[full]:
    ax.add_patch(plt.Polygon(xy[tri], color="gold", ec="k", zorder=2))
for tri in grid.triangles:
    for a, b in ((0, 1), (1, 2), (0, 2)):
        if {labels[tri[a]], labels[tri[b]]} == {0, 1}:
            ax.plot(*xy[[tri[a], tri[b]]].T, color="tab:purple", lw=2.5, zorder=1)
for k, color in enumerate(("tab:red", "tab:green", "tab:blue")):
    ax.scatter(*xy[labels == k].T, s=25, color=color, zorder=3, label=f"label {k}")
ax.plot([], [], color="tab:purple", lw=2.5, label="0-1 door")
ax.set_aspect("equal")
ax.axis("off")
ax.legend(loc="upper right", fontsize=8)
ax.set_title(f"{len(full)} fully labelled triangles (gold)")

ax = axes[1]
values, freq = np.unique(counts, return_counts=True)
ax.bar(values, freq, color="tab:orange")
ax.set_xlabel("number of fully labelled triangles")
ax.set_ylabel("labellings")
ax.set_title("always odd")
fig.suptitle("Sperner (1928)")

Text(0.5, 0.98, 'Sperner (1928)')