Skip to content
All apps

First-passage percolation

About this app

Fire on a random grid: the front becomes round, fastest routes merge into trees, and almost surely there is no route that is fastest and infinite in both directions (bigeodesic). openai/math, family 212.

The model

In first-passage percolation (Hammersley–Welsh 1965) every edge of the square lattice gets an independent random passage time. Think of a forest fire spreading from a spark, always along the fastest route. The burnt region grows linearly and, divided by time, takes on a fixed convex limit shape. Fastest routes to distant points merge into trees. It was open whether a bigeodesic exists: a route infinite in both directions whose every piece is fastest. An AI-generated preprint in github.com/openai/math (family 212) claims that almost surely there is none. According to the catalogue this theorem is not formalised, and the preprint is not peer-reviewed.

What the app shows

A lattice of 201 × 201 nodes with exponential or uniform passage times; the spread is computed exactly with Dijkstra’s algorithm. In the “fire front” view the front grows, and a dashed curve shows the limit shape estimated from this sample against a circle and a diamond. “Path trees” shows how the fastest routes from 25 starting points to a distant target merge. “Bigeodesic” computes fastest routes between opposite points at growing distance.

Try it yourself

In the fire-front view, move the pointer over the lattice: the line is the fastest route there, and a click pins it. In the bigeodesic experiment, click to choose a direction and watch whether the route still passes through the centre box as the opposite points move apart. Statistics over 12 directions and 4 random lattices show how the share of routes through the centre falls with distance. A simulation only sees finitely many edges; the theorem comes from the proof alone.

Frequently asked questions

What is first-passage percolation?
First-passage percolation is a model of spreading through a random medium. Each edge of a lattice gets a random passage time, and the time from x to y is the sum along the fastest route. It can model fires, infections or fluids in porous material.
What is a bigeodesic?
A bigeodesic is a route that continues infinitely in both directions and is the fastest connection on every finite piece. Furstenberg asked whether such routes exist in first-passage percolation. In physics this corresponds to non-trivial ground states of a polymer in a random environment.
Do bigeodesics exist in first-passage percolation?
It was expected that in the plane there are almost surely no bigeodesics. An AI-generated preprint in the catalogue github.com/openai/math (family 212) claims a proof for independent, identically distributed weights without atoms under a mild moment condition. According to the catalogue this theorem is not formalised in Lean, and the preprint has not yet been peer-reviewed.
What can I try out in this app?
You let a fire burn across a random lattice, watch the limit shape grow and trace fastest routes with the pointer. In the path-tree view, routes from 25 starting points merge. The bigeodesic experiment shows with statistics how routes between distant opposite points avoid the centre.

Subject: Open problems, solved by AI

More from Open problems, solved by AI

A VisuApp by heyprof: interactive, free in your browser, no sign-up. What is a VisuApp? · All apps