- Time: 9:00-10:30am (Beijing), 10:00-11:30am(Seoul)
- Place: IBS ECOPRO B332 (Main building 3rd floor).
- Jul 6 – Jul 10, Entropy method in extremal combinatorics
- Jul 27 – Jul 31, Hypergraphs with Bounded VC-Dimension: Incidences, Zarankiewicz Problems, and Radon-Type Theorems
- Zoom: 3469344087, PW: 202607
Entropy method in extremal combinatorics
Ting-Wei Chao, Massachusetts Institute of Technology
The entropy method has been used in many recent works in extremalcombinatorics. With the help of Shannon entropy, significant progresshas been made on several classical problems, such as the union-closed conjecture and Sidorenko’s conjecture. There are also recent new proofs of classic theorems and their generalizations using entropy, such as the Kruskal-Katona theorem and Turan’s theorem. We will cover the basics of entropy and talk about some applications to graph homomorphism counting problems.
- 7/6 Lecture 1: Basics, bitwise information, and union-closed conjecture NOTE 1
- 7/7 Lecture 2: Graph homomorphism inequalities and Sidorenko’s conjecture NOTE 2
- 7/8 Lecture 3: Shearer’s inequality and its applications NOTE 3
- 7/9 Lecture 4: Friedgut–Kahn theorem and mixture bound (I) NOTE 4
- 7/10 Lecture 5: Mixture bound (II) NOTE 5
Hypergraphs with Bounded VC-Dimension: Incidences, Zarankiewicz Problems, and Radon-Type Theorems
Shakhar Smorodinsky, Ben-Gurion University
The notion of VC-dimension, introduced in statistical learning theory, has become a central tool inmodern combinatorics, discrete geometry, and theoretical computer science. It provides a powerful way to measure the complexity of set systems, or equivalently hypergraphs, and many natural geometric hypergraphs have bounded VC-dimension. In this course, I will discuss the rich combinatorial theory of hypergraphs with bounded VC-dimension and some of its geometric manifestations. We will begin with the Sauer-Shelah-Perles lemma and its basic consequences and then move to epsilon-nets and related sampling and packing phenomena. We will studyextremal questions for graphs and hypergraphs of bounded VC-dimension, including Zarankiewicz-type problems and incidence bounds, together with tools such as the crossing lemma and polynomial partitioning. Further topics will include matchings with low crossing numbers, generalizations of epsilon-nets, and Radon- and Tverberg-type theorems for unions of convex sets.
- 7/27 Lecture 1: Basic definitions: VC-dimension: examples arising in geometry and combinatorics. NOTE 1
- 7/28 Lecture 2: The shatter function, Sauer-Shelah-Perles Lemma. applications to boolean enrichment of hypergraphs. NOTE 2
- 7/29 Lecture 3: Hypergraphs defined by polynomials of bounded degree, Basic convexity and the relation between Radon’s Theorem and VC-dimension of halfspaces, abstract convexity spaces. NOTE 3
- 7/30 Lecture 4: Application of the VC-dimension lens to union of convex sets: Extending Radon and Tverberg theorems to unions of convex sets. NOTE 4
- 7/31 Lecture 5: Epsilon nets and an extension to epsilon-t-nets. Applications to Zarankiewicz problem for bounded VC-dimension graphs. NOTE 5
