Introductory Workshop - Graph Theory: Extremal, Probabilistic and Structural: Incidence bounds via extremal graph theory
Presenter
February 11, 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
"Every large system, chaotic as it may be, contains a well-organized subsystem". This phenomenon is truly ubiquitous and manifests itself in different mathematical areas. One of the central problems in extremal combinatorics, which was extensively studied in the last hundred years, is to estimate how large a graph/hypergraph needs to be to guarantee the emergence of such well-organized substructures. In the first part of this talk we will give an introduction to this topic, mentioning some classical results as well as a few applications to other areas of mathematics. We will then discuss a novel combinatorial approach, based on extremal graph theory, to a central problem in discrete geometry: counting incidences, such as point-hyperplane incidences in d-dimensional space. The study of such problems was initiated in the 1990's by Chazelle and it has interesting connections to many other topics, like additive combinatorics and theoretical computer science. This part is a joint work with Milojevic and Tomon.