Algebraic and Analytic Methods in Combinatorics: Independent Sets in H-free Hypergraphs
Presenter
March 21, 2025
Keywords:
- extremal combinatorics
- extremal graph theory
- probabilistic combinatorics
- discrete geometry
- additive combinatorics
- combinatorial geometry
- incidence geometry
- arithmetic progressions
- Discrete analysis
MSC:
- 05C25 - Graphs and abstract algebra (groups rings fields
- etc.) [See also 20F65]
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C50 - Graphs and linear algebra (matrices eigenvalues etc.)
- 05D40 - Probabilistic methods in extremal combinatorics including polynomial methods (combinatorial Nullstellensatz etc.)
- 52C35 - Arrangements of points flats hyperplanes (aspects of discrete geometry) [See also 14N20 32S22]
Abstract
It is a fundamental question in Ramsey theory to determine the smallest possible independence number of an H-free hypergraph on n vertices. In the case of graphs, the problem was famously solved for H=K3 by Kim and for H=K4 (up to a logarithmic factor) by Mattheus-Verstraete in 2023. Even C4 and K5 remain wide open. We study the problem for 3-uniform hypergraphs and conjecture a full classification: the minimum independence number is poly(n) if and only if H is contained in the iterated blowup of the single-edge hypergraph. We prove this conjecture for all H with at most two tightly connected components. Based on joint work with Conlon, Fox, Gunby, Mubayi, Suk, Verstraete, and Yu.