Summer semester 2024

Discrete Mathematics of Paul Erdős -- NDMI107


  • 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 subset of the following topics:
    Proof of Bertrand's postulate. Erdős's proof of Turán's theorem. Hamilton cycles. Ramsey's theorem and Ramsey numbers. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. Sperner's theorem and the Erdős-Ko-Rado theorem. Van der Waerden's theorem and van der Waerden numbers. Extremal graph theory. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. The Erdős-Rényi random graphs and their evolution.

            
The subject and the instructor, ca.1976


Top of this page   •   Sources   •   Bulletin board   •   Record of the material covered in class   •   Erdős links

Sources:

Additional reading:


Top of this page   •   Sources   •   Bulletin board   •   Record of the material covered in class   •   Erdős links

Bulletin board


Top of this page   •   Sources   •   Bulletin board   •   Record of the material covered in class   •   Erdős links

Record of the material covered in class

Date             Material covered Homeworks
Feb 23Chapter 1 up to and including 1.5.2 Homework 1
Its solution
Mar 11.5.3-1.5.5, 7.1.1-7.1.3
Mar 8pages 175-179 up to and including the proof of Theorem 11.5. Homework 2
Its solution
Mar 1511.1.1. Statement of Theorem 11.11
Mar 22Proof of Theorem 11.11 3.1.3.2 up to the upper bound on R(4,4).
Mar 29Class cancelled
Apr 5
Apr 12
Apr 19
Apr 26
May 3
May 10
May 17
May 24


Top of this page   •   Sources   •   Bulletin board   •   Record of the material covered in class   •   Erdős links


Top of this page   •   Sources   •   Bulletin board   •   Record of the material covered in class   •   Erdős links

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