Structure of cell decompositions in Extremal Szemerédi-Trotter examples

2023/03/30 by Nets Hawk Katz, Katz, Nets, Olivine Silier +1 · 1 citation
Mathematics · #Analytic and geometric function theory #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Dynamics and Fractals

paper · pdf · doi:10.48550/arxiv.2303.17186

openalex publication_date 2023/03/30 · openalex created_date 2023/04/05 · openalex updated_date 2026/07/28

Abstract

The symmetric case of the Szemerédi-Trotter theorem says that any configuration of N lines and N points in the plane has at most O(N^4/3) incidences. We describe a recipe involving just O(N^1/3) parameters which sometimes (that is, for some choices of the parameters) produces a configuration of N point and N lines. (Otherwise, we say the recipe fails.) We show that any near-extremal example for Szemerédi Trotter is densely related to a successful instance of the recipe. We obtain this result by getting structural information on cell decompositions for extremal Szemerédi-Trotter examples. We obtain analogous results for unit circles.

Cited by

• More pointsets with many rich lines

Related

• On the structure of extremal point-line arrangements
• Structural Szemerédi-Trotter for Lattices and their Generalizations
• More pointsets with many rich lines
• On cliques in three-dimensional dense point-line arrangements
• A structural Szemerédi-Trotter Theorem for Cartesian Products