Post

In 1947, Paul Erdős, the itinerant Hungarian mathematician, introduced what would become one of math’s most powerful tools. He wanted to prove that a certain kind of object existed — in this case, a network made of interconnected nodes. But strangely, his proof didn’t specify how to build it. Instead, he showed that if you consider all networks and select one at random, the chances that you’ll… Source

In 1947, Paul Erdős, the itinerant Hungarian mathematician, introduced what would become one of math’s most powerful tools. He wanted to prove that a certain kind of object existed — in this case, a network made of interconnected nodes. But strangely, his proof didn’t specify how to build it. Instead, he showed that if you consider all networks and select one at random, the chances that you’ll…

Source

Erdős’ approach, known as the probabilistic method, was simple but revolutionary. Before its development, “if I’m telling you that certain objects exist, you would tell me, ‘Show me,’” said Benny Sudakov , a mathematician at the Swiss Federal Institute of Technology Zurich. “But certain objects are so unusual that it’s hard for us to grasp that they exist at all.”

Erdős’ technique overcame this difficulty, demonstrating that randomness could be used in ways mathematicians had never imagined. “It was just astounding that you would use randomness,” said Joel Spencer of New York University. “Now, that’s the baseline.”

Today, the probabilistic method is used across mathematics and computer science — to figure out if a number is prime, to design better circuits, or to clean up data without introducing biases.

Researchers have strengthened the technique in various ways. But the original focus of the probabilistic method — the question about networks that Erdős sought to answer — has seen very little progress. For eight decades, mathematicians were unable to significantly improve on the solution that Erdős came up with.

Imagine a network of nodes — a graph — in which every pair of nodes is connected by an edge.