Extremal Graph Theory Lecture (2026/27)

Past Lectures:

  • 1st class (5 October 2026): Three proofs of Mantel's theorem (induction, the AM–GM inequality, and the Motzkin–Straus discharging argument); Turán's theorem (inductive and structural proofs); every nonempty graph of average degree at least 2t contains every tree on t vertices.
  • 2nd class (12 October 2026): Paths and the Erdős–Gallai theorem; the Erdős–Sós conjecture, now a theorem (Riordan–Scott, Wood) [Only the case where the root of the tree has degree one in Jumping-edge lemma---The whole lemma can be found here: Proof of Therem 5].
  • 3rd class (19 October 2026): Dirac's theorem on Hamiltonian cycles; Moon–Moser and clique supersaturation; the Erdős–Stone–Simonovits theorem (so far assuming the lower-bound on minimum degree).
  • 4th class (26 October 2026): Finish Erdős–Stone–Simonovits (from min degree to average degree assumption); Excluding 4-cycles (upper bound and finite-field construction); the Kővári–Sós–Turán theorem.

Planned lectures:

Tentative plan. Things will change!

  • 5th class (2 November 2026): Triangles versus edges; graph minors and Mader's theorem; Stability of Mantel's and Turán's theorems; Füredi's quantitative bound and (possibly) balancing the parts.
  • 6th class (9 November 2026): Andrásfai–Erdős–Sós degree bound implies bipartite; Erdős–Hajnal–Moon clique saturation construction; Bollobás’s set-pairs inequality; Clique saturation lower-bound.
  • 7th class (16 November 2026): First short test (Lectures 1–6, about 25 minutes); introduction to the probabilistic method.
  • 8th class (23 November 2026): Lovász Local Lemma.
  • 9th class (30 November 2026): Szemerédi's regularity lemma.
  • 10th class (7 December 2026): Applications of Szemerédi's regularity lemma.
  • 11th class (14 December 2026): Second short test (Lectures 7–10, about 25 minutes); ??.
  • 12th class (11 January 2027): ?? Limits Part I.
  • 13th class (18 January 2027): Limits Part II.

Grading:

Two tests during the semester, each giving a grade adjustment from {-0.5, 0, +0.5}. The test will take place at the start of the lecture, i.e. at 10:15.

Oral exam: four subquestions: a definition; an overview; a simpler theorem with a proof; and a more complex theorem with a proof.

masarik<a>mimuw.edu.pl



CENT building room 03.104, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 1650, MIMUW, Banacha 2, Warsaw, 02-097, Poland
Room 8514, Department of Mathematics, Simon Fraser university, 8888 University Drive, Burnaby, V5A 1S6, Canada
Room 320, KAM MFF, Malostranské náměstí 25, Praha 1, 11800, Czech Republic