Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: Refined Absorption: A New Proof of the Existence Conjecture
Presenter
February 13, 2025
Keywords:
- extremal graph theory
- random graphs
- probabilistic methods
- structural graph theory
- Ramsey theory
MSC:
- 05C35 - Extremal problems in graph theory [See also 90C35]
- 05C55 - Generalized Ramsey theory [See also 05D10]
- 05C75 - Structural characterization of families of graphs
- 05C80 - Random graphs (graph-theoretic aspects) [See also 60B20]
- 05D40 - Probabilistic methods in extremal combinatorics
- including polynomial methods (combinatorial Nullstellensatz
- etc.)
Abstract
The study of combinatorial designs has a rich history spanning nearly two centuries. In a recent breakthrough, the notorious Existence Conjecture for Combinatorial Designs dating back to the 1800s was proved in full by Keevash via the method of randomized algebraic constructions. Subsequently Glock, Kühn, Lo, and Osthus provided an alternate purely combinatorial proof of the Existence Conjecture via the method of iterative absorption. We introduce a novel method of “refined absorption” for designs and use it to provide a new alternate proof of the Existence Conjecture. The method can also be applied in a black-box fashion to many other design theory problems, including proving the High Girth Existence Conjecture and finding sufficiently spread distributions on designs. Joint work with Luke Postle and Tom Kelly.