Erase

what this is

A spanning tree of a grid is a set of paths that joins every point to every other, with no loop anywhere, so that between any two points there is exactly one way. A grid this size has more spanning trees than there are atoms in anything; this page holds one of them, chosen so that every one of them was equally likely. That is not easy to do, and for most of a century nobody could. In 1996 David Wilson found the way, and it is what you watched: start a random walk anywhere outside the tree, let it wander until it hits the tree, erase its loops in the order it made them, keep what is left. Repeat from anywhere. The result is not merely a spanning tree; it is a uniformly random one, and Wilson proved that the order you start the walks in, and the place you start the tree from, make no difference at all.

The thread you see wandering is the walk with its loops already taken out. A random walk on a plane crosses itself constantly; each time it does, the loop it closed is gone, and the thread snaps back to the crossing. What survives is a loop-erased random walk, and Lawler, Schramm and Werner proved in 2004 that its paths have dimension exactly five fourths. They are not lines and not areas. It is why the light has so far to go: on this grid the mean distance from the root to a point, along the tree, is 1,081.2 steps, and the mean distance as the crow flies is 109.7. Ten times further by the only road there is.

This is the twin of Topple. The number of spanning trees of any graph is a determinant, which Kirchhoff knew in 1847, and Dhar showed in 1990 that the same determinant counts the stable states of a sandpile that the sandpile can return to. Majumdar and Dhar then gave the map between the two, the burning bijection, and it is the reason the sandpile has theorems at all: every exact number Topple was held to was counted here, on trees. The page does the counting both ways on a grid small enough to count, and gets the same number.

the gates

Six checks were fixed in the project notes before any code existed, with tolerances and the direction an honest error would lean, and run headless against the engine the page draws from.

• 1 · uniform, root at a corner: all 192 trees of the 3 by 3, chi-square under 241.1
  Held: the determinant gave 192; 38,400 samples saw 192 of 192, chi-square 198.3 on 191 degrees of freedom.
• 2 · uniform, root at the centre
  Held: 192 of 192, chi-square 224. A second seed gave 196.1 and 216.1.
• 3 · the five fourths, exponent within 1.20 to 1.30, any error low
  Held: 1.2596 from walks to the boundary on grids of 128, 256 and 512; a second seed gave 1.2531. The notes said a short grid would read low; it read high by a hundredth, which is within the noise of four hundred walks, so the declared direction was not tested and that is recorded rather than claimed.
• 4 · census of the page grid, exactly
  Held: 78,156 vertices, 78,155 parent edges, the root reached from every vertex, none counted twice, grown by the same budgeted stepping the page uses (32,701 walks, 435,375 steps, 235,238 erased).
• 5 · moving the root leaves the tree unchanged, exactly
  Held: 50 reroots in a row, identical edge set each time, and the distances the light travels by equal to the depth counted by hand at every vertex.
• 6 · the twin: recurrent sandpile states on the same small grid, exactly
  Held: of 2,592 stable configurations, 192 pass Dhar's burning test, the number gate 1 sampled against.

Reported and not gated, because no exact value exists at this size: from a root at the centre the farthest vertex is 2,032 steps away along the tree and the mean is 1,081.2, against a mean straight-line distance of 109.7.

the picture

Every vertex is drawn to its parent and nothing else. The tone is the tree distance from the root, so the root glows and the light runs out along the branches and dies in the far twigs; the thread in flight is the one thing on the page that is not yet part of the tree. Once the tree is complete, fronts of light leave the root at a fixed speed in tree distance and take the only road there is, which is why a front arrives at two neighbouring points minutes apart in tree time. Moving the root reverses one path of parent pointers and recomputes the distances; the tree is the same tree. Monochrome, procedural, no paid instruments.