Algebraic and Analytic Methods in Combinatorics: Lower bounds for incidences
Presenter
March 17, 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
Lots of problems in combinatorics and analysis are connected to upper bounds for incidences: given a set of points and tubes, how much can they intersect? On the other hand, lower bounds for incidences have not been studied much. In this vein, we prove that if you choose `n’ points in the unit square and a line through each point, then there is a nontrivial point-line pair with distance