Erdős Pál was one of the most influential Hungarian mathematicians. He is famous for his unexpectedly elegant proofs of very difficult problems.
He was born in Budapest, Hungary, in 1913. His parents were both mathematicians. His father introduced him interesting subjects, for example set theory and infinite series. During high school he attended to the competition of KöMaL (a Hungarian mathematical and physical journal for high school students). Later Erdős published several articles in this journal.
He was awarded a doctorate in mathematics at age of 21. In the same year (1934) he had to move to Manchester, England, because of increasing anti-Semitism in Hungary. In 1938 he accepted a position at Princeton University. Then he rejected offers from universities, because it would limit him to focus on mathematical problems and to collaborate with distant colleagues. Instead he traveled from campus to campus, staying with mathematicians and sharing ideas from one place to the next. Over the years he had difficulties with travel restrictions resulting World War II and Cold War.
He published more than 1500 papers with more than 500 collaborators.
Erdős was not only a brilliant problem solver, but had an awesome ability to ask very good questions. He won the Wolf Prize, where his contribution was described as
for his numerous contributions to number theory, combinatorics, probability, set theory, and mathematical analysis, and for personally stimulating mathematicians the world over.
He discovered an elementary proof of prime number theorem, developed the Ramsey theory, he was a pioneer of probabilistic method, investigated combinatorics problems with a new approach, resulting extremal combinatorics. He had little interest in topology, but he gave the first example of a totally disconnected topological space that is not zero-dimensional.
Erdős died 20 September 1996, in Warsaw, Poland, while attending a mathematical conference.
Erdős and graph theory
He published more than 150 papers in this area of mathematics (list of papers).
Among others he wrote about Euler-lines, Hamiltonian cirles, chromatic numbers, matching theorems, decompositions of graphs, spanning trees, bipartite graphs, etc. He was interested in finite and also infinite graphs.
We emphasize three very important ones:
Erdős-Rényi model was the first model for generating random graphs setting an edge between each pair of nodes with the same probability, and independently of the other edges. Erdős-Rényi model does not result a random graph whose degree distribution follows a power law. Nevertheless it was a very important step to models we can use today to simulate or approximate the Internet or World Wide Web, and many other interesting structures of real life.
Probabilistic method is pioneered by Erdős. The basic idea is the following: if we randomly choose a graph (or more generally a mathematical object), and the probability that the chosen one has a prescribed property is more than zero, then this proves the existence of that kind of graphs (or mathematical objects). The proof itself uses probability, but the conclusion is determined for certain. Showing that the probability is less than 1 proves the existence of an object that does not have the prescribed property. The method has now been applied to other parts of mathematics (number theory, linear algebra, real analysis, computer science).
Ramsey theory is the mathematical study of combinatorial objects in which a certain degree of order must occur as the scale of the object becomes large. Ramsey theory is named after Frank Plumpton Ramsey. The theory was subsequently developed extensively by Erdős. A typical (and first) result in Ramsey theory is the party problem.
- Probabilistic method
- Ramsey theory