Summer 2023

  • Time: 9:00-10:30am (Beijing), 10-11:30am(Seoul)
  • July 17-21, The method of hypergraph containers.
    @ IBS Science Culture Center, S221 (2nd floor), Daejeon, South Korea.
  • July 24-30, Graph limits and flag algebras.
    @ Dongmingzhu Building 112, Shandong University, Jinan, China.
  • Zoom: 346 934 4087, PW: 202307

The method of hypergraph containers

  • 7/17 Lecture 1: Classical results about triangle-free graphs – Mantel’s and Ramsey’s theorems (without proofs); the binomial random graph $G_{n,p}$; Mantel’s and Ramsey’s theorems relative to a (random) graph; the Erdős–Kleitman–Rothschild theorem on the number of triangle-free graphs and the structure of a random triangle-free graph (without proof); Hoeffding’s theorem (aka Chernoff’s bound); maximal triangle-free graphs; a weak container theorem for triangle-free graphs; the supersaturation theorem of Erdős and Simonovits (without proof); derivation of an upper bound on the number of triangle-free graphs from the weak container theorem for triangle-free graphs and the supersaturation theorem
  • 7/18 Lecture 2: Proof of the Erdős–Simonovits supersaturation theorem; proof of the random analogue of Mantel’s theorem (for $p \gg n^{-1/2} \log n$); Ramsey multiplicity; proof of the random analogue of Ramsey’s theorem for triangles (for $p \gg n^{-1/2} \log n$); necessary conditions on the edge probability $p$ for random analogues of Mantel’s theorem and Ramsey’s theorem for triangles
  • 7/19 Lecture 3: Container theorem for triangle-free graphs; proof of Mantel’s theorem relative to $G_{n,p}$ under the optimal assumption $p \gg n^{-1/2}$; Simonovits’s stability theorem for triangle-free graphs (Füredi’s proof); the triangle-removal lemma of Ruzsa and Szemerédi (without proof); stability theorem for almost-triangle-free graphs; proof of Simonovits’s stability theorem relative to $G_{n,p}$
  • 7/20 Lecture 4: Independent sets in hypergraphs; the general hypergraph container theorem; derivation of the container theorem for triangle-free graphs; optimality of assumptions in the hypergraph container theorem on the example of the general Turán problem in random graphs; the existence of induced Ramsey graphs via the hypergraph container theorem
  • 7/21 Lecture 5: The $(4,3)$-problem – subsets of points in general position in point sets without collinear $4$-tuples; a randomised construction of such n-element sets whose largest subsets in general position has no more than $n^{5/6+o(1)}$ points (the Balogh–Solymosi theorem)

Graph limits and flag algebras

  • 7/24 Lecture 1: convergence of graph sequences, limits of dense graphs, graphons, cut distance
    Note Exercise
  • 7/25 Lecture 2: definition of flag algebras
    Note Exercise
  • 7/26 Lecture 3: proof of Mathel’s theorem using flag algebras, setting a semidefinite programming for automatic flag algebras proofs
  • 7/27 Lecture 4: rounding the numerical solution, using Flagmatic for computations in flag algebras, example usage of flag algebras for oriented graphs
  • 7/25 Lecture 5: applications of flag algebras, differential method

IBS Extremal Combinatorics and Probability Group
기초과학연구원 수리및계산과학연구단 극단 조합 및 확률 그룹
대전 유성구 엑스포로 55 (우) 34126
IBS Extremal Combinatorics and Probability Group (ECOPRO)
Institute for Basic Science (IBS)
55 Expo-ro Yuseong-gu Daejeon 34126 South Korea
E-mail:, Fax: +82-42-878-9209
Copyright © IBS 2021. All rights reserved.