Analytic view on extremal combinatorics
- Daniel Kráľ (Masaryk University)
Abstract
The theory of combinatorial limits provides analytic tools to represent and study large discrete structures and has led to new views on a wide range of topics in mathematics and computer science. After introducing this rapidly developing area of combinatorics, we focus on several problems from extremal combinatorics, which we will view through lenses of combinatorial limits.
In particular, we will present a counterexample to a conjecture of Lovász concerning finitely forcible optima, which was one of the two most cited conjectures in the theory of combinatorial limits. We will also demonstrate how analytic tools have been successfully used to resolve long standing open problems in extremal combinatorics, such as a 30-year-old conjecture of Erdős and Sós on uniform Turán densities of 3-uniform hypergraphs and a 30-year-old problem on the existence of high chromatic graphs with small Ramsey multiplicity.