← Previous: When Seventeen Vanishes Next: Hypercubes on Spheres →

Continuous Graph Coloring & Yellow Pig 17

Relaxing Clusters of Resistance across The Panopticon

🐖 Welcome to The Panopticon

You have entered The Weave—a secret network of sentinels connected by invisible tension fibers. Each sentinel must broadcast a distinct color phase so that no two neighbors transmit on the same frequency. If they do? Resonance collapse. The fiber between them glows red. Your mission: eliminate every conflict across The Weave. But beware: some Weaves are impossible to fully color. In those, stubborn Clusters of Resistance—tightly interconnected cliques—force at least one conflict to survive. Can you find it?

1. The Riddle

For every fixed $q\geq 3$, deciding whether a graph has a proper $q$-coloring is NP-complete. (Two colors are the friendly exception: test whether the graph is bipartite.) So we commit a respectable mathematical prank: map each color to a point on the complex unit circle $S^1$, turning a discrete puzzle into a smooth physics playground.

2. The Physics

We define a potential energy $E(z)$ across The Weave. When two connected sentinels share a phase, their fiber becomes taut—a repulsive force pushes them apart on the circle. Gradient descent rolls the system downhill. Conflict cores fight back. They need not be cliques: the triangle-free Grötzsch graph still demands four colors. Rude!

3. The Yellow Pig Lock

The $q$-th roots of unity $\omega^k=e^{2\pi i k/q}$ are the legal color slots. Every numerical update is projected onto $S^1$, so unit length is enforced exactly. The weight $\lambda$ only controls the root lock: small $\lambda$ lets phases explore the circle; $\lambda=17$ drops the Yellow Pig magnet and yanks them toward exact roots. 🐖

H_q(u,v)=\sum_{j=0}^{q-1}u^{q-1-j}v^j, \qquad E(z)=\sum_{(u,v)\in E}\frac{|H_q(z_u,z_v)|^2}{q^2} +\lambda\sum_{u\in V}|z_u^q-1|^2.

On exact roots, the normalized edge term is an equality detector: it is $1$ when two endpoint colors agree and $0$ when they differ. Away from the roots it is a smooth landscape, not yet a discrete truth oracle. That distinction is where the shenanigans live.

ENERGY / SOLVER FORMULATIONS:

Speyer Planar Obstruction (N=13) Conflicts: 0

Edge Loss: 0.0000 Root Loss: 0.0000 Total: 0.0000

energy_functions.js ✓ Code Valid

Optimizer: The Weave Arena: Init State: Colors (q): 3 Root Weight (λ): 0.05

Snap after a zero-conflict rounded coloring is found

Ready. Rounded conflicts describe the nearest discrete colors; root loss measures whether the phases have reached the roots.

📖 How to Edit Energy Functions & Create Custom Physics

The programming editor allows you to write custom JavaScript potential functions that control how graph vertices interact.

Function Contract: Write function computeEnergy(nodes, edges, q, lambda) returning an object { edge, root, total }.
nodes Array: Contains Complex objects for each node with methods z.add(c), z.sub(c), z.mul(c), z.pow(n), z.sqNorm(), z.norm(), and z.unit().
edges Array: Array of vertex index pairs [u, v] representing graph connections.
Saving & Restoring: Click 💾 Save to LocalStorage to preserve your custom code in your browser, or ↺ Reload Reference Code to reset back to the tutorial default.

📖 Speyer Gadget Proof Walkthrough (Clusters of Resistance)

Step 1 — Remove one suspicious noodle: Delete the outer edge $EI$, but keep all 13 vertices. Triangle $ABC$ must use all three colors. Since color names are arbitrary, rename them so $A=0$, $B=1$, and $C=2$. The Yellow Pig has reduced the investigation to two tiny cases.

First remove EI. The same 13 vertices remain; only one edge is missing.

Branch	D E F G H I J K L M	Verdict
Breakfast	1 2 0 1 0 2 1 2 1 0	$E=I=2$
Second breakfast	2 0 1 0 1 0 2 2 1 0	$E=I=0$

Gadget source: David E. Speyer, “Planar non-3-colorable graphs” .