Paul Erdos

Life and career

For most of the last four decades of his life, Paul Erdős owned a suitcase, a plastic bag, and no home. He would arrive at a colleague's door, announce that his brain was open, work for a few days or weeks, co-author a paper, and move on to the next mathematician. He had no permanent position, no bank account worth speaking of, and no possessions to store. He had, by the end, something on the order of fifteen hundred papers and five hundred co-authors — more of both than any mathematician in history — and a style of doing mathematics that turned out to be exactly the style computer science would need.

He was born in Budapest in 1913 to two mathematics teachers. Days before his birth, his two young sisters died of scarlet fever, and his mother, understandably, kept him out of school and close to home for much of his childhood; his father spent six years as a prisoner of war in Siberia. He was calculating with negative numbers and independently rediscovering prime facts before he was ten. At the University of Budapest he studied under Lipót Fejér and, at nineteen, produced an elementary proof of Bertrand's postulate — that there is always a prime between $n$ and $2n$ — a result Chebyshev had proved with analytic machinery. Erdős's proof used counting. That preference, for arguments that are elementary but ingenious rather than heavy but routine, defined his career.

He took his doctorate in 1934 at twenty-one and left immediately for a fellowship in Manchester, which almost certainly saved his life. He was Jewish and Hungary was moving rapidly toward alliance with Nazi Germany; most of his extended family was murdered in the Holocaust, and his father died during the war. He spent the war years in the United States, at Princeton and elsewhere, and never afterward settled anywhere.

The 1949 elementary proof of the prime number theorem, arrived at in parallel and partly in collaboration with Atle Selberg, was the most celebrated and most painful episode of his career: the two men's accounts of who owed what to whom diverged, the collaboration collapsed acrimoniously, and Selberg received a Fields Medal in 1950 while Erdős received the Cole Prize the following year. Erdős later received the Wolf Prize, in 1983, and characteristically gave nearly all of the money away.

His itinerancy was partly forced. During the McCarthy period he travelled to Hungary and was subsequently denied a re-entry visa to the United States, spending years working in Israel and around Europe before the restriction lapsed in the 1960s. After that he moved continuously among Hungary, Israel, the United States, and anywhere a conference or a colleague could be found. Ron Graham at Bell Labs managed his correspondence, his money, and a filing cabinet of his affairs.

He had a private vocabulary that his collaborators adopted: children were *epsilons*, women *bosses*, men *slaves*, a mathematician who had stopped proving theorems had *died* and one who had died had *left*. God, whose existence he was uncommitted about but whose obstruction he complained of constantly, was the Supreme Fascist, and kept a Book containing the perfect proof of every theorem — the highest praise Erdős could give a proof was that it came straight from the Book. He posted cash bounties on open problems, from ten dollars to several thousand depending on difficulty, and the outstanding ones are still being claimed and paid from his estate.

He worked, for decades, with the assistance of amphetamines — a fact he was open about, and the subject of a well-known bet with Graham in which Erdős abstained for a month, won the money, and complained that mathematics had been set back by thirty days. He died in Warsaw in 1996, aged 83, at a combinatorics conference, which is where he would have chosen. The Erdős number, measuring collaborative distance from him, is his most widely known monument and a fair one: his central innovation was arguably social as much as mathematical.

Key contributions

**The probabilistic method.** This is the contribution that matters most to a data-science audience, and it is startlingly simple in outline: to prove that an object with property $P$ exists, define a probability distribution over candidate objects and show that a random draw has $P$ with positive probability. No construction is required. The canonical example is Erdős's 1947 lower bound on Ramsey numbers: colour the edges of $K_n$ red or blue uniformly at random; the expected number of monochromatic $k$-cliques is $\binom{n}{k}2^{1-\binom{k}{2}}$; if that is less than one, some colouring has none, so $R(k,k) > 2^{k/2}$ roughly. The proof is a paragraph, and more than seventy-five years later nobody has substantially improved the bound by any method, constructive or otherwise.

The method's descendants are everywhere in theoretical computer science and in machine learning. Randomized algorithms are the probabilistic method made executable. The Lovász Local Lemma, which handles the case where bad events are mostly independent, gives the existence of satisfying assignments and underlies Moser–Tardos constructive algorithms. Existence proofs for expander graphs, error-correcting codes achieving Shannon's bound, and restricted-isometry matrices in compressed sensing all take the same shape: random works, and we cannot yet exhibit anything explicit that works as well. The Johnson–Lindenstrauss lemma — that a random projection preserves pairwise distances — is a probabilistic-method argument, and it is the foundation of random-projection dimensionality reduction and locality-sensitive hashing.

**Random graph theory (with Alfréd Rényi).** The 1959–60 papers introduce $G(n,p)$ and $G(n,m)$ and establish the phenomenon that makes the theory important: *thresholds*. As $p$ increases, graph properties do not appear gradually but switch on sharply. Connectivity has threshold $\log n / n$. The appearance of a giant component has threshold $1/n$, and the transition — the "double jump," from all components of size $O(\log n)$ below the threshold, to a unique component of size $\Theta(n)$ above — is a genuine phase transition in the physicists' sense. Erdős and Rényi had no application in mind whatsoever. The framework is now the null model against which every empirical network is compared, the source of the percolation-threshold analysis of network robustness, and the direct ancestor of the phase-transition analysis of random constraint satisfaction problems.

**Extremal and additive combinatorics.** The Erdős–Ko–Rado theorem on intersecting set families; the Erdős–Szekeres theorem, that any sequence of $(r-1)(s-1)+1$ reals contains a monotone subsequence of length $r$ or $s$, and the related "happy ending" problem on convex position; the Erdős–Stone theorem, which essentially settles the extremal density question for graphs of chromatic number at least three; the Erdős–Gallai results on degree sequences; the distinct-distances problem, which stood for six decades until Guth and Katz nearly settled it in 2010; the discrepancy conjecture, resolved by Terence Tao in 2015 with help from a crowdsourced Polymath project. The Erdős–Turán conjecture on arithmetic progressions in dense sets is the direct provocation behind Szemerédi's theorem and, through it, the Green–Tao theorem.

**Problem-posing as a discipline.** Erdős's habit of formulating precise, hard, cheaply stated problems and putting money on them is a genuine methodological contribution. A remarkable share of modern combinatorics and additive number theory traces to a question he asked and priced.

In battle

Erdős carries 100 problems at a mean of 36.7, with seven dominant cells and twenty-six at 20 or below. He is a mid-range generalist with one enormously deep specialty and a large blind zone.

His categories are led by **networks** (61.6 across 14 problems) — his single strongest showing over a substantial problem count — with **search** (51.5), **experimental-design** (48.0), and **computability** (47.7 across 16) behind it.

The peak is **P093 — The random graph's threshold** at 98, where the matrix's verdict is unequivocal: this is not analogous to his work, it *is* his work, down to the detail that Erdős and Rényi had no application in view. The cluster around it is the whole $G(n,p)$ programme deployed against modern network science: **P034 — Phase transition at the threshold** (88), the random-SAT and percolation analogue of the double jump; **P271 — Robust to failure, fragile to attack** (85), which is percolation on a degree sequence and is answered by exactly his machinery; **P089 — Six degrees, provably** (82), small-world diameter bounds in random graphs; **P268 — Who will know whom next year?** (82), link prediction against a random-graph null; and **P270 — Choose the first hundred believers** (72), influence seeding on a graph. **P269 — Frequencies without interference** (87) is graph colouring — extremal combinatorics proper. **P050 — Twenty questions with a liar** (95) is Rényi–Ulam search with errors, a combinatorial search problem that sits directly in his and Rényi's shared territory.

The weaknesses cluster into two kinds. The first is anything statistical or learned: **regression** 15.0, **testing** 14.0, **classification** 11.0, with floor cells at **P139 — Regression when the outcome is censored** (6), **P243 — Name what you've never trained on** (5, zero-shot transfer), **P260 — The sentence in a single vector** (8), **P088 — Attention replaces recurrence** (8), and **P201 — The dice make it learnable** (8). Erdős used probability constantly, but as a *proof technique* over finite discrete structures, never as a model of data. He did no estimation, no inference from samples, no function approximation. The distinction is worth teaching: probabilistic reasoning and statistics are not the same discipline, and Erdős is the cleanest illustration on the board.

The second is engineering. **Systems** at 7.0 is his lowest category, and his single floor cell is **P080 — The software that may not fail** (4) — the Apollo guidance computer's overload handling. The matrix's note is blunt about why: there is nothing in counting arguments and existence proofs that bears on interrupt scheduling, and it scores that honestly rather than manufacturing a bridge. His **optimization** average of 36.4 across 13 problems is the interesting middle: he supplies the existence results and threshold behaviour that randomized algorithms rest on, but he never designed an algorithm to run, and problems that ask for a working procedure rather than a proof that one exists reward him only partially.

Play Erdős on graphs, thresholds, colourings, extremal bounds, and any question where the winning move is "consider a random one." Keep him away from anything with data in it.