Structural Szemerédi-Trotter for Lattices and their Generalizations

2023/09/29 by Dasu, Shival, Sheffer, Adam, Shen, Junxuan
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2310.00191

Abstract

We completely characterize point--line configurations with Θ(n^4/3) incidences when the point set is a section of the integer lattice. This can be seen as the main special case of the structural Szemerédi-Trotter problem. We also derive a partial characterization for several generalizations: (i) We rule out the concurrent lines case when the point set is a Cartesian product of an arithmetic progression and an arbitrary set. (ii) We study the case of a Cartesian product where one or both sets are generalized arithmetic progression. Our proofs rely on deriving properties of multiplicative energies.

Related

• A structural Szemerédi-Trotter Theorem for Cartesian Products
• Structure of cell decompositions in Extremal Szemerédi-Trotter examples
• On the structure of extremal point-line arrangements
• Sharp Szemerédi-Trotter Constructions in the Plane
• The constant of point-line incidence constructions