Summer 2022

  • Time: August 1 – 6, Korean time:
    I. Expanders: 9:30am-10:50am;
    II. Topological combinatorics: 11:00am-12:20pm;
    III. Convexity spaces: 2:30pm-3:50pm.
  • Zoom: 819 0982 4573, PW: 202208


  • Time change: on August 4th (Thursday), Convexity spaces will be at 11am, Topological combinatorics will be at 2:30pm.

Sparsifiers and expanders

  • 8/1: Why Laplacian is useful: applications in image processing, analogue of Laplacian operator on Euclidean space.
  • 8/2: Random walks on non-regular graphs, spectral sparsifiers with $O(n\log n)$ edges.
  • 8/3: Spectral sparsifiers with $O(n\log n)$ edges, Interlacing polynomials.
  • 8/4: Spectral sparsifiers with linear many edges.
  • 8/5: Existence of bipartite Ramanujan graphs using 2-covers.
  • 8/6: Existence of bipartite Ramanujan graphs by taking union of perfect matchings.

Topological combinatorics

  • 8/1: Homotopy, Homology, Nerve theorem, good cover, Topological Helly. Tablet note
  • 8/2: Three basic tools in topological combinatorics and their equivalence: Brouwer Fixed-Point Theorem/Sperner’s Lemma/KKM Theorem. Tablet note
  • 8/3: Brouwer implies weak Sperner, and applications of KKM theorem:(p,q)-theorem/Line transversal/Colorful KKM theorem. Tablet note
  • 8/4: Hall’s theorem for hypergraphs, proof based on Sperner’s lemma to an economically hierarchic triangulation of a simplex. Tablet note
  • 8/5: Ryser’s conjecture for tripartite 3-uniform hypergraphs, homology nerve theorem, topological Hall theorem. Tablet note
  • 8/6: Homology nerve theorem, Topological Hall theorem (correction), $d$-collapsible/Leray complexes, Topological colorful Helly theorem, Alexander duality theorem. Tablet note

Convexity spaces

  • 8/1: Examples of convexity spaces: convex lattices sets, subgroups, subtrees, subcubes, invariants abstracting basic properties of Euclidean convexity space: Radon/Carathéodory/Helly. Tablet note
  • 8/2: Radon number of subcubes in $\{0,1\}^n$ is about $\log_2 n$, weak $\varepsilon$-net. Tablet note
  • 8/3: weak $\varepsilon$-net ⇒ Radon, colorful/fractional Helly, Tverberg number. Tablet note
  • 8/4: Helly + Tverberg ⇒ colorful Helly ⇒ fractional Helly, Radon ⇒ fractional Helly, selection ⇒ weak $\varepsilon$-net. Tablet note
  • 8/5: Fractional Helly ⇒ Tverberg using hypergraph matching, fractional Helly + Tverberg ⇒ selection, equivalent formulation of weak $\varepsilon$-net: bounding transversal number via fractional transversal number. Tablet note
  • 8/6: Radon ⇒ weak $\varepsilon$-net in separable convexity space via VC dim. 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:, Fax: +82-42-878-9209
Copyright © IBS 2021. All rights reserved.