Paul Erdős: The Wandering Mathematician

Born into Mathematics

Paul Erdős (pronounced "AIR-dish") was born on 26 March 1913 in Budapest, Hungary, to Lajos and Anna Erdős. Both parents were high school mathematics teachers. Paul's two older sisters had died of scarlet fever just days before his birth, a tragedy that made his mother fiercely protective of him throughout her life.

Erdős was a prodigy. At the age of three, he could multiply three-digit numbers in his head. At four, he discovered negative numbers on his own by contemplating what happens when you subtract a larger number from a smaller one. His mother, afraid of infectious diseases in school, kept him at home for much of his childhood, educating him herself.

By his teenage years, Erdős was already a known figure in the vibrant Budapest mathematical community, contributing problems and solutions to KöMaL, the famous Hungarian mathematics journal for students.

---

Early Career

Erdős entered the University of Budapest at seventeen and earned his doctorate at twenty-one (1934), writing a thesis on prime numbers that gave an elegant proof of Chebyshev's theorem: for every integer $n \geq 1$, there exists a prime $p$ with $n < p \leq 2n$. This result, known as Bertrand's postulate, had been proved before, but Erdős's proof was remarkable for its simplicity and elegance.

With the rise of fascism in Hungary, Erdős left for a postdoctoral fellowship in Manchester, England. He would never again have a permanent home. His parents, who were Jewish, survived the Holocaust, but many of his relatives did not — four of his mother's five siblings were killed.

---

The Wandering Mathematician

Erdős's lifestyle was unlike that of any other mathematician — or perhaps any other person. He owned almost nothing: a suitcase of clothes, a small bag of mathematical papers, and his brain. He had no permanent home, no regular position, and no interest in money, possessions, or conventional career advancement.

Instead, Erdős traveled constantly, appearing at the doorstep of mathematicians around the world with the greeting: "My brain is open." He would stay for a few days, collaborate intensively on problems, and then move on to the next colleague. His hosts provided food and lodging; Erdős provided mathematical brilliance.

He donated most of the prize money he received to charity or offered it as prizes for solving mathematical problems he posed.

---

The Erdős Number

Erdős collaborated with more mathematicians than anyone in history — over 500 coauthors across approximately 1,500 published papers. This led to the concept of the Erdős number, a measure of collaborative distance:

• Erdős himself has Erdős number 0
• A mathematician who coauthored a paper with Erdős has Erdős number 1
• A mathematician who coauthored with someone of Erdős number 1 has Erdős number 2
• And so on

The Erdős number has become a playful but widely recognized measure in the mathematical community. Most active research mathematicians have an Erdős number of 5 or less.

---

Major Mathematical Contributions

Erdős made fundamental contributions to combinatorics, graph theory, number theory, approximation theory, set theory, and probability. His work is characterized by deceptively simple-sounding problems that reveal deep mathematical truths.

The Probabilistic Method

Perhaps Erdős's most influential contribution to mathematical methodology is the probabilistic method — a technique for proving the existence of mathematical objects by showing that a random construction produces them with positive probability.

As a classic example, Erdős proved a lower bound on the Ramsey number $R(k, k)$ using the probabilistic method. Color the edges of the complete graph $K_n$ red and blue independently at random, each with probability $1/2$. The expected number of monochromatic $k$-cliques is:

$\binom{n}{k} \cdot 2^{1 - \binom{k}{2}}$

If this is less than 1, then there exists a 2-coloring with no monochromatic $k$-clique, proving:

$R(k, k) > 2^{k/2}$

This result, published in 1947, was revolutionary. The probabilistic method has since become one of the most powerful tools in combinatorics.

The Erdős–Rényi Model of Random Graphs

Together with Alfréd Rényi, Erdős founded the theory of random graphs. In the Erdős–Rényi model $G(n, p)$, a graph on $n$ vertices is formed by including each possible edge independently with probability $p$.

Their fundamental discovery was the existence of sharp thresholds: many graph properties appear suddenly as $p$ crosses a critical value. For example, the threshold for the appearance of a giant connected component is $p = 1/n$:

• If $p < (1-\varepsilon)/n$, the largest component has $O(\log n)$ vertices with high probability.
• If $p > (1+\varepsilon)/n$, there is a unique giant component of size $\Theta(n)$.

This work laid the foundation for the modern theory of complex networks and has applications in epidemiology, computer science, and social network analysis.

The Erdős–Kac Theorem

The Erdős–Kac theorem (1940) is one of the most beautiful results in probabilistic number theory. Let $\omega(n)$ denote the number of distinct prime factors of $n$. Hardy and Ramanujan had shown that $\omega(n)$ is typically about $\ln \ln n$. Erdős and Kac proved a much more precise result:

In other words, the number of prime factors of a random integer follows a normal distribution — the central limit theorem applies to prime factorization. Erdős called this result "the fundamental theorem of probabilistic number theory."

The Erdős–Selberg Dispute

In 1948–1949, Erdős and Atle Selberg independently found an elementary proof of the prime number theorem — one that uses no complex analysis. This was a major achievement, as the prime number theorem had previously been thought to require analytic methods essentially. A dispute arose over credit and priority that strained the relationship between the two mathematicians for years.

Combinatorial Number Theory

Erdős proved numerous results in combinatorial and additive number theory. With Paul Turán, he proved the Erdős–Turán conjecture on arithmetic progressions (partial results) and developed extremal graph theory. The Erdős–Gallai theorem characterizes degree sequences of simple graphs: a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ is the degree sequence of a simple graph if and only if the sum is even and for each $k$:

$\sum_{i=1}^{k} d_i \leq k(k-1) + \sum_{i=k+1}^{n} \min(d_i, k)$

---

Erdős's Language

Erdős developed a distinctive private vocabulary that became famous in mathematical circles:

• "The Book" — God's book containing the most elegant proofs of all theorems
• "epsilon" — a small child
• "boss" — a wife
• "slave" — a husband
• "captured" — married
• "liberated" — divorced
• "to preach" — to give a mathematical lecture
• "the SF" — the "Supreme Fascist," Erdős's tongue-in-cheek name for God

---

Death and Legacy

Paul Erdős died on 20 September 1996, at the age of 83, of a heart attack while attending a mathematics conference in Warsaw, Poland. He was working on mathematics until the very end.

Erdős's influence on mathematics is vast. He essentially created or co-created the fields of probabilistic combinatorics, extremal graph theory, and probabilistic number theory. His problems — many still open — continue to drive research. The book Proofs from THE BOOK (by Aigner and Ziegler), inspired by Erdős's concept of God's book of perfect proofs, has become a classic.

---

References

• Hoffman, P., The Man Who Loved Only Numbers: The Story of Paul Erdős, Hyperion, 1998.
• Schechter, B., My Brain Is Open: The Mathematical Journeys of Paul Erdős, Simon & Schuster, 1998.
• Aigner, M. and Ziegler, G., Proofs from THE BOOK, Springer, 6th edition, 2018.
• Alon, N. and Spencer, J., The Probabilistic Method, Wiley, 4th edition, 2016.
• Wikipedia — Paul Erdős
• MacTutor — Paul Erdős
• The Erdős Number Project