Course description: Paul Erdős (1913-- 1996) was an outstanding, prolific, influential, legendary mathematician. We will study a selection of his results in number theory, geometry, Ramsey theory, extremal combinatorial problems, and graph theory that laid the foundations of discrete mathematics before it matured into the rich and vibrant discipline of today. From time to time we will stray from his own work to the work of his confrères and disciples, but we shall never escape the gravitational pull of the great man. At a leisurely pace, we shall cover a prefix of the following ordered set of topics: Sylvester-Gallai theorem and De Bruijn-Erdős theorem. Ramsey's theorem and Ramsey numbers. Hamilton cycles. The Erdős-Rényi random graphs and their evolution. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. Van der Waerden's theorem and van der Waerden numbers. Chromatic number. Extremal set theory. Erdős's proof of Bertrand's postulate. Extremal graph theory.

The subject and the instructor, ca.1976

• Instructor: Vašek Chvátal
  • Email:     c h v a t a l (at) k a m (dot) m f f (dot) c u n i (dot) c z
    
  • Office hours: by appointment

• Classes: Thursdays 10:40 -- 12:10 in S221 (the 2nd floor hallway of KAM)

• Text: The Discrete Mathematical Charms of Paul Erdős (also at Megabooks and at Amazon)

• Prerequisities: Ease with the notation of elementary set theory and with matrix descriptions of systems of linear equations. Elementary calculus: Taylor expansions of the exponential and the logarithm, L'Hopital's rule.
• Grading scheme: 50% homeworks, 50% final exam
  

Sources:

• Collected Papers of Paul Erdős up to 1989
• The MacTutor History of Mathematics archive

Additional reading:

• Xiaomin Chen's proof of a conjecture of mine.
• The Search for a Finite Projective Plane of Order 10 by C. W. H. Lam
• Andrew Suk's breakthrough on the Happy End Theorem.

• Correct answers are not necessarily unique.

Erdős quotations Property is a nuisance. There will be plenty of time to rest in the grave. A theorem a day means promotion and pay; a theorem a year and you're out on your ear. Another roof, another proof. Favourites of Erdős, often attributed to him, but originating elsewhere A mathematician is a machine for turning coffee into theorems. (Alfréd Rényi) Chebyshev said it and I say it again: There is always a prime between n and 2n. (Nathan Fine) Websites dedicated to Erdős Erdős site from Zentralblatt für Mathematik Erdős page from the Mathematical Institute in Budapest References and links to information about Erdős from the Erdős Number Project. Articles on Erdős Two Places at Once (A Remembrance of Paul Erdős) by János Pach Paul Erdős (1913 -- 1996) by László Babai and Joel Spencer The Mathematics of Paul Erdős by László Babai, Carl Pomerance, and Pétér Vértesi Reminiscences of Paul Erdős (1913-1996) by Melvin Henriksen Remembering Paul Erdős by Aleksandar Ivić Biography from MacTutor Obituaries from The New York Times and The Washington Post Two films on Erdős by George Csicsery N is a Number: A Portrait of Paul Erdős (1993) Erdős 100 Plus (a DVD compilation of ten videos totaling 180 minutes) A book on Erdős Bruce Schechter, My Brain is Open : The Mathematical Journeys of Paul Erdős , Simon & Schuster, 1998.

Vašek Chvátal's front page at KAM
Vašek Chvátal's front page at Concordia