1913 – 1996 • The Wandering Mathematician
The most prolific mathematician in history, who published over 1,500 papers with 500+ collaborators, inventing the probabilistic method and making mathematics the most social of enterprises.
Paul Erdos was born on March 26, 1913 in Budapest, Hungary. Both his parents were high school mathematics teachers. His two older sisters died of scarlet fever just days before his birth, making his parents fiercely protective.
A prodigy, he could multiply three-digit numbers in his head by age three and independently discovered negative numbers by age four. His mother, Anna, was devoted to his education and remained his closest companion until her death in 1971.
At age 17, he entered the University of Budapest. By 20, he had published an elegant new proof of Chebyshev's theorem (that there is always a prime between n and 2n), which brought him international attention.
He received his doctorate in 1934, then left Hungary due to rising anti-Semitism. He would never again have a permanent home, spending his life traveling between mathematical colleagues worldwide.
At age 20, published a beautiful elementary proof that a prime exists between n and 2n (Bertrand's postulate). This established his reputation and began his lifelong love of prime number theory.
Pioneered the probabilistic method in combinatorics: to prove a combinatorial object exists, show a random construction has positive probability. This became one of the most powerful tools in discrete mathematics.
With Atle Selberg, gave an "elementary" proof of the prime number theorem (no complex analysis). The priority dispute that followed was one of the rare bitter episodes in Erdos's life.
Lived out of two suitcases, traveling constantly between collaborators. Published over 1,500 papers, won the Wolf Prize (1983) and the Cole Prize (1951), and inspired the concept of the Erdos number.
Budapest's mathematical culture, centered on the journal KoMaL and the Eotvos competitions, produced a remarkable generation. Erdos, Turan, Gallai, and Szekeres grew up solving problems together in the city parks.
This problem-solving tradition, emphasizing concrete problems over grand theories, shaped Erdos's mathematical identity throughout his life.
In the mid-20th century, combinatorics was often dismissed as "mere counting." Erdos, along with contemporaries like Turan, Ramsey, and later Szemerédi, transformed it into a deep, central branch of mathematics.
The rise of computer science made Erdos's combinatorial and graph-theoretic work unexpectedly relevant, and fields he helped create (Ramsey theory, extremal graph theory) became cornerstones of theoretical CS.
Hungarian Tradition Combinatorics Analytic Number Theory
The probabilistic method proves the existence of mathematical objects with desired properties by showing that a random object has the property with positive probability.
Key insight: if P(X has property P) > 0, then an object with property P must exist, even if we cannot construct one explicitly.
Erdos used this to prove results in graph coloring, Ramsey theory, number theory, and combinatorial geometry that seemed intractable by deterministic methods. The method has since become a standard tool across mathematics and computer science.
Erdos proved R(k,k) >= 2^(k/2) by showing a random 2-coloring of edges of a complete graph avoids monochromatic cliques of size k with positive probability. This lower bound remains essentially the best known after 75+ years.
Using the probabilistic method, Erdos showed graphs with high girth (no short cycles) can still have high chromatic number, refuting the intuition that "locally tree-like" graphs should be easy to color.
With Lovasz, Erdos proved a powerful extension: if bad events are mostly independent and individually unlikely, they can all be simultaneously avoided. This "local lemma" has become one of the most important tools in combinatorics.
Probabilistic existence proofs often lead to efficient algorithms: if random objects usually have a property, a deterministic algorithm can find one. This "derandomization" paradigm is central to theoretical computer science.
Erdos co-authored papers with 511 people, the most collaborators in the history of mathematics. These collaborators have Erdos number 1; their co-authors have Erdos number 2; and so on.
The Erdos number concept, introduced half-jokingly, became a cultural phenomenon and an early example of social network analysis. Most active mathematicians have Erdos number at most 5 or 6.
The collaboration graph revealed the "small world" property of the mathematical community and anticipated the study of social networks by decades.
Erdos published more papers than any mathematician in history. He worked in number theory, combinatorics, graph theory, probability, set theory, approximation theory, and more. His breadth was matched only by Euler.
Erdos imagined God keeping a book of the most elegant proofs. "You don't have to believe in God, but you have to believe in The Book." The posthumous collection "Proofs from THE BOOK" (Aigner & Ziegler) became a bestseller.
He posed thousands of problems, many with cash prizes ($25 to $10,000). These "Erdos problems" drove research in combinatorics and number theory for decades. Many remain open and are actively pursued today.
Erdos showed that mathematics could be a deeply collaborative enterprise. His model of open problem-posing and itinerant collaboration anticipated modern open-source and crowdsourced research.
Erdos was the principal developer of Ramsey theory: the study of conditions under which order must appear in large enough structures. "Complete disorder is impossible."
He proved foundational bounds on Ramsey numbers and showed they grow at least exponentially. The Erdos-Szekeres theorem (1935) on monotone subsequences is a classic of the field.
With Turan, Gallai, and others, Erdos developed extremal graph theory: what is the maximum number of edges a graph can have without containing a particular subgraph?
The Erdos-Stone theorem (1946) gives the asymptotic answer for any forbidden subgraph with chromatic number >= 3. It is considered the fundamental theorem of extremal graph theory.
Ramsey Numbers Extremal Problems Szemerédi Regularity
Erdos was the supreme problem-poser and problem-solver, favoring elegant short proofs over grand theoretical frameworks.
Identify a clean, concrete problem
Discuss with the right co-author
Find the "Book" proof
Pose new problems suggested by the solution
His mathematical vocabulary was unique: "epsilons" (children), "bosses" (wives), "Sam" (USA), "Joe" (USSR), "noise" (music), "poison" (alcohol). He lived for mathematics and little else.
In 1948, Erdos and Selberg collaborated on an elementary proof of the prime number theorem. But Selberg felt his fundamental lemma was the key contribution and wanted to publish alone. The resulting priority dispute was one of the ugliest in modern mathematics.
During the McCarthy era, Erdos was denied re-entry to the US after visiting Hungary (1954). He was suspected of communist sympathies. He spent years unable to visit American collaborators, deeply affecting his mathematical life.
Erdos owned almost nothing: two suitcases, a few changes of clothes. He gave away prize money. He was cared for by a network of mathematical friends who housed and fed him as he traveled the world proving theorems.
Erdos relied on amphetamines for decades to maintain his prodigious output. When friend Ron Graham bet him $500 he couldn't stop for a month, Erdos won the bet but complained: "You've set mathematics back a month."
The Erdos-Renyi random graph model (1959) is the foundation of network science, used to study the internet, social networks, epidemiology, and biological networks.
The probabilistic method directly yields randomized algorithms. Derandomization techniques convert these into efficient deterministic algorithms for optimization, satisfiability, and network design.
Probabilistic arguments show good error-correcting codes exist, guiding the search for practical codes. The Lovasz Local Lemma has direct applications to code construction.
Random graph theory underpins methods for genome assembly, protein interaction networks, and phylogenetic analysis. Erdos-Renyi thresholds model phase transitions in biological systems.
Ramsey-theoretic and extremal combinatorial results provide bounds in communication complexity and cryptographic protocols.
Random graph and probabilistic method ideas appear in the analysis of neural network architectures, random feature models, and compressed sensing.
Paul Hoffman (1998). A warm, entertaining biography capturing Erdos's eccentric personality and his mathematical world.
Aigner & Ziegler (1998, 6th ed. 2018). A collection of the most elegant proofs in mathematics, inspired by Erdos's concept of "The Book." A joy to read.
Alon & Spencer (2016, 4th ed.). The standard textbook on the technique Erdos pioneered. Graduate-level but accessible to anyone with combinatorics background.
Bruce Schechter (1998). Another engaging biography, with more mathematical detail than Hoffman's book and a focus on Erdos's collaborations.
"A mathematician is a device for turning coffee into theorems."
— Paul Erdos (often attributed to Alfréd Rényi)1913 – 1996