Elegant Six-Page Proof Reveals the Emergence of Random Structure

April 27, 2022 5:50 PM

The methods that would eventually lead to [Jinyoung Park and Huy Tuan Pham's] new proof of the Kahn-Kalai conjecture began with a breakthrough on a seemingly unrelated problem. In many ways, the story starts with the sunflower conjecture, a question posed by the mathematicians Paul Erdős and Richard Rado in 1960. The sunflower conjecture considers whether collections of sets can be constructed in ways that resemble the petals of a sunflower. 2500 words from Jordana Cepelewicz for Quanta Magazine.

“This is one of the nice things that happens in mathematics,” [Kahn] said. “Things that people thought were hopeless turn out not only to be not hopeless, but not even hard.”

posted by cgc373 (10 comments total)

Gil Kalai on Benoit's fractals.
posted by No Robots at 6:15 PM on April 27, 2022

Beautifully written article, thanks for sharing!
posted by nfalkner at 7:56 PM on April 27, 2022 [1 favorite]

Thank you for posting this! I passed it along to mrs_goldfish, who takes a professional interest in such things.

"'SIX-PAGE'?!? Nice! ... [clicks on link to pre-print] ... ... mm, okay ... hmmt. ... Huh! ... Surprisingly pretty!"
posted by feral_goldfish at 8:01 PM on April 27, 2022

Just as ice crystals form when the temperature dips below zero degrees Celsius, the emergence of a particular property suddenly becomes extremely likely as more edges get added to the graph. When edges are added to a random graph of N vertices with a probability of less than log(N)/N, for instance, the graph is unlikely to contain a Hamiltonian cycle. But when that probability is adjusted to be just a hair greater than log(N)/N, a Hamiltonian cycle becomes extremely likely.

That log(N)/N thing shows up in strange places — and that metaphor fits the model of a random graph extremely well, considering that the process of freezing, where a random mass of water molecules very abruptly start assuming fixed positions with regard to each other, seems a lot like adding edges to a random graph.
posted by jamjam at 10:40 PM on April 27, 2022 [4 favorites]

As a counter, I feel like "things that people thought would be easy turn out to not only to be not easy, but not even possible" has also popped up quite a lot in the history of mathematics!
posted by Jon Mitchell at 11:40 PM on April 27, 2022 [2 favorites]

So, point of order here: “obvious” and “obvious in hindsight” are not the same thing at all.
posted by mhoye at 5:55 AM on April 28, 2022 [2 favorites]

This was one of those rare stories about advances in higher mathematics that actually made me feel the writer actually understands what they're writing about, and I almost kinda feel like I sort of grasp it too! Good job, writer!
posted by ook at 12:31 PM on April 28, 2022

So, point of order here: “obvious” and “obvious in hindsight” are not the same thing at all.

Sure, but remember, this is mathematics, where the meaning of "trivial" is "between one and a hundred people spent between five years and several centuries struggling to actually prove this, but they eventually did and wrote it all down so we don't have to do that ever again and won't be discussing any of the details in this current proof".
posted by cortex at 10:06 PM on April 28, 2022 [3 favorites]

Great post! I think math is so fascinating but I just don’t get it intuitively, which is frustrating.

Is a line on a graph called an edge because the 2d line represents a 3d (or higher d) edge? If so, I assume vertex means corner.
posted by Don.Kinsayder at 2:59 AM on April 29, 2022

I like to introduce basic graph theory in terms of threads and buttons instead of edges and vertices. It's intuitive to most middle schoolers. Throw down some buttons, pick a pair, roll a die, if it's 4 or more, link them with a thread. When you do that for all of them you have a random graph, and it's the same random graph no matter how you toss the buttons around.

The edges and vertices could be called anything, but one reason to avoid calling edges 'lines' is that lines often have to be straight or live in a plane, and edges don't.
posted by SaltySalticid at 5:37 AM on April 29, 2022 [1 favorite]