- Time: 9:00-10:30am (Beijing), 10:00-11:30am(Seoul)
- Place: IBS ECOPRO B332 (Main building 3rd floor).
- Jul 28 – Aug 1, Around removal lemmas
- Aug 4 – 8, Introduction to Boolean analysis
- Zoom: 3469344087, PW: 2025
Around removal lemmas
Lior Gishboliner, University of Toronto, Canada
The removal lemma for a graph (or hypergraph) property $\mathcal{P}$ states that if a graph $G$ is $\varepsilon$-far from satisfying $\mathcal{P}$, then a random sample of $f(\varepsilon)$ vertices of $G$ is likely to not satisfy $\mathcal{P}$. Such results are useful both in combinatorics and theoretical computer science, where they correspond to property testing algorithms. Removal lemmas are typically proved using a regularity lemma, which leads to very poor bounds on $f(\varepsilon)$. A central problem is to understand for which properties $\mathcal{P}$ we can take $f(\varepsilon)$ to be polynomial in $\varepsilon$. The goal of this course is to give an overview of regularity and removal lemmas and present the tools used in the study of this question, including some recent results.
- 7/28 Lecture 1: Szemeredi’s regularity lemma and the counting lemma, proof of the triangle removal lemma. NOTE 1
- 7/29 Lecture 2: Behrend’s construction, the $H$-removal lemma is polynomial if and only if $H$ is bipartite (Alon’s theorem). NOTE 2
- 7/30 Lecture 3: The induced removal lemma. VC-dimension, the Sauer-Shelah lemma. NOTE 3-4
- 7/31 Lecture 4: Ultra-strong regularity for graphs of bounded VC-dimension, the infinite removal lemma, property testing.
- 8/1 Lecture 5: Testing bipartiteness, testing for large independent sets, hypergraph regularity and VC-dimension.. NOTE 5
Introduction to Boolean analysis
Yuval Filmus, Technion, Israel
Boolean function analysis studies Boolean functions on the Boolean cube and other domains from a spectral perspective. Motivated initially by social choice theory, it has seen many applications in combinatorics and theoretical computer science. We will cover the basic definitions and results, and see some classical applications as well as some more recent ones.
- 8/4 Lecture 1: Introduction and linearity testing
- 8/5 Lecture 2: KKL theorem
- 8/6 Lecture 3: Hypercontractivity
- 8/7 Lecture 4: Biased Fourier analysis
- 8/8 Lecture 5: Global hypercontractivity, Bourgain’s booster theorem and Erdős-Ko-Rado
