Summer semester 2020

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. Sperner's theorem and the Erdős-Ko-Rado theorem. Turán numbers. Property B and hypergraph colouring. Extremal graph theory. Hamilton cycles. The Friendship Theorem, strongly regular graphs, and Moore graphs of diameter two. Chromatic number of graphs and the probabilistic method. Van der Waerden's theorem and van der Waerden numbers. The Erdős-Szekeres and the Sylvester-Gallai theorems. Delta-systems and Deza's proof of an Erdős-Lovász conjecture. The De Bruijn-Erdős theorem. The Erdős-Rényi random graphs and their evolution. Ramsey's theorem and Ramsey numbers.

            
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
20.2 Proof of Bertrand's postulate up to and including Section 4.
27.2 Proof of Bertrand's postulate concluded. 
5.3 Landau's problems. Sperner's theorem and its proof by Sperner.
12.3 Reading assignment: Extremal set theory.
19.3 Reading assignment: Extremal set theory: First four sections (up to page 18).
26.3 Reading assignment: The last section of Extremal set theory and the first two sections of Extremal graph theory.
2.4 Reading assignment: Extremal graph theory.
9.4 Reading assignment: Extremal graph theory.
16.4 Reading assignment: Extremal graph theory.
23.4 Reading assignment: Hamilton cycles.
30.4 Independent study plans.
7.5 Independent study plans.
14.5 Independent study plans.
21.5 Independent study plans.


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