Discrete mathematics of Paul Erdős

Discrete mathematics of Paul Erdős Summer semester 2025

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 prefix of the following ordered set of topics:
Sylvester-Gallai theorem and De Bruijn-Erdős theorem. Ramsey's theorem and Ramsey numbers. Erdős's refinement of Turán's theorem. Hamilton cycles. The Erdős-Rényi random graphs and their evolution. Van der Waerden's theorem and van der Waerden numbers. Erdős's proof of Bertrand's postulate.

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

Date	Material covered	Homeworks
20.2	2.2 and 2.3 till Lemma 2.7 and the first paragraph of its proof. Near-pencils and projective planes of order k.
27.2	... continued till the end of 2.4.1.	HW1 assigned.
6.3	2.4.3, 2.4.4, 2.4.2. 3.1 and 3.2 till just before Theorem 3.4.
13.3	3.3. Theorem 3.7. 2.1.	HW2 assigned.
20.3	The remainder of 3.4. The remainder of 3.2. 3.5.
27.3	3.6. 7.1.1, 7.1.2, 7.1.3.	HW3 assigned.
3.4	11.1. 11.1.1.
10.4	11.2. Pages 151-152.	HW4 assigned.
17.4	10.1. 10.1.1. 10.1.4. 10.1.2 up to (10.2).
24.4	The remainder of 10.1.2. 10.1.3 up to (10.4).	HW5 assigned
Tuesday 29.4 9:00--10:30	A.1.1. Robbins's refinement of Stirling's formula on top of page 196. From (10.4) to the end of the proof of (10.5).
1.5	No classes: national holiday.
Tuesday 6.5 9:00--10:30	Proof of (10.6).
8.5	No classes: national holiday.
15.5	10.2 up to and including proof of (10.17).
22.5	The remainder of Section 10.2. Section 10.3.