networks
Six degrees, provably
It is 2000 at Cornell, and a thirty-year-old experiment still has no theory: Milgram's letters reached their targets in about six hops, which says short paths exist between almost any two people — but the deeper puzzle is that the letter-holders found those paths using only local knowledge of their own acquaintances. Model both facts. Random graphs give short paths but no way to find them; regular lattices give findability but no short paths. Construct the model in between and prove the sharp result: for exactly which structures can greedy local routing succeed, and at which parameter value does navigability appear and vanish. Peer-to-peer systems, gossip protocols, and decentralized search will be engineered on this theorem — or on folklore, if the theorem is wrong.
Who this problem belongs to
The two figures whose methods fit it best, out of 46 in contention.
Kleinberg published exactly this result in 2000: modeling both of Milgram's facts, short paths exist and they are locally findable, by interpolating between a regular lattice and a random graph via long-range links whose probability decays with a tunable exponent, then proving the sharp threshold at which greedy local routing succeeds or fails as that exponent varies. This is not an adjacent or analogous contribution, it is the literal paper and result the problem describes, down to the institution, the year, and the specific mathematical structure of the theorem. No other carrier in this entire batch can claim direct authorship of this exact navigability result, making this as close to a perfect historical match as the game format allows.
Erdos, with Renyi, essentially founded the mathematical study of random graphs, establishing the very object, a graph where edges appear with some probability, that Kleinberg's model builds on and interpolates away from toward a regular lattice. His probabilistic method for proving existence and threshold results is methodologically the direct ancestor of exactly the kind of sharp phase-transition proof Kleinberg's navigability theorem requires, and his comfort with random-graph phase transitions specifically, connectivity thresholds, giant-component emergence, is precisely the mathematical territory this problem lives in. He did not personally address navigability or Milgram's experiment, since he died in 1996 before Kleinberg's paper, but the entire mathematical toolkit the problem's solution depends on is substantially his own creation.
In the mind map
The same ideas, as concepts rather than history — in John's ML knowledge map.
46 figures are scored on this problem. Draw it in a battle to see where you land.