Spring 2024

Extremal Combinatorics

  • Time: From March 5th, 2024, every Tuesday and Thursday
    8:30-10:00am (Beijing), 9:30-11:00am(Seoul).
  • Zoom: 346 934 4087, PW: 202402

Announcement

  • There will be a summer research program at ECOPRO in July and August of this year.
  • The Tuesday class on 4/16 will be switched to the same time on Monday April 15.
  • The class on 3/12 will be at 10am-11:30am (Beijing), 11am-12:30pm (Seoul).

Final grade: Homeworks 50%, exam 50%. Please send homework to Zhuo.Wu@warwick.ac.uk

Part 1. Topics

1. Turán problem

  • 3/5 Lecture 1: graph, handshaking lemma, common graph families, subgraph, large degree ⇒ long cycle & large trees, Mantel’s thm, pf1 induction, pf2 max-deg vertex, odd/even town via linear algebra, lower bd construction for Ramsey via probabilistic method. Tablet note
  • 3/7 Lecture 2: Erdős-Szekeres monotone seq via pigeonhole, Sperner’s thm via LYM ineq, pf1 double counting, pf2 probabilistic counting, extremal number, Turán graph, Turán’s thm, pf1 induction, pf2 max-deg vertex, pf3 Zykov’s symmetrization. Tablet note
  • 3/12 Lecture 3: Turán’s thm, pf4 Motzkin-Straus Symmetrization, pf5 probabilistic pf Caro-Wei, first moment method, Erdős-Stone-Simonovits thm pf1. Tablet note
  • 3/14 Lecture 4: a geometric application of Turán’s thm, homomorphism, an embedding lemma bootstrapping $H$-freeness to $H$-hom-freeness, a modern pf2 of Erdős-Stone-Simonovits thm, supersaturation phenomenon, Turán density exists for every graph. Tablet note
  • 3/19 Lecture 5: $r$-uniform $r$-partite hypergraph has Turán density 0, supersaturation pf1 local averaging, supersaturation ⇒ blowups of a graph has the same Turán density ⇒ pf3 Erdős-Simonovits-Stone, Moon-Moser ⇒ supersaturation pf2. Tablet note
  • 3/21 Lecture 6: Füredi perfect stability via degree majorization, Erdős-Simonovits stability from perfect stability and Ruzsa-Szemerédi removal lemma, stability method. Tablet note
  • 3/26 Lecture 7: extremal number of $C_5$ via stability, every maximal $K_r$-free graph contains a wheel-like graph, Brandt’s pf of Andrasfai-Erdős-Sós. Tablet note
  • 3/28 Lecture 8: Bipartite Turán problem, $C_4$ and Sidon-set, Kővári-Sós-Turán, dense constructions of $C_4$-free and $K_{3,3}$-free graphs, Bondy-Simonovits on extremal number of even cycles, pf1 using BFS. Tablet note
  • 4/2 Lecture 9: Regularization, bipartite graph with bounded degree, random zooming. Tablet note
  • 4/4 Lecture 10: Sidorenko’s conjecture, $P_3, C_4$, even cycles, pf2 of even cycle extremal number upper bound using Sidorenko. Tablet note
  • 4/9 Lecture 11: 3-dim cube via supersaturation, grid via rich collection of paths, pf3 of even cycle via Sidorenko and iterative Cauchy-Schwarz. Tablet note

2. Extremal Set Theory

  • 4/11 Lecture 12: Bollobás set-pairs ineq, pf via random permutation, skewed version via exterior algebra, applications: 1. LYM ineq, 2. saturation number. Tablet note
  • 4/15 Lecture 13: Application of Sperner: Littlewood-Offord, Poset, height, width, Dilworth’s thm, pf1 induction, Mirsky’s thm. Tablet note
  • 4/18 Lecture 14: Application of Dilworth: better Ramsey for intersection graph of planar convex sets. Tablet note

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: ecopro@ibs.re.kr, Fax: +82-42-878-9209
Copyright © IBS 2021. All rights reserved.