2014/08/25 by Saarik Kalia, Kalia, Saarik, Micha Sharir +5
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Geometric and Algebraic Topology #Limits and Structures in Graph Theory #math.CO
paper · pdf · doi:10.48550/arxiv.1408.5915
openalex publication_date 2014/08/25 · arxiv created 2015/12/30 · arxiv updated 2015/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We generalize the Szemerédi-Trotter incidence theorem, to bound the number of complete flags in higher dimensions. Specifically, for each i=0,1,…,d-1, we are given a finite set Si of i-flats in \Rd or in \Cd, and a (complete) flag is a tuple (f0,f1,…,fd-1), where fi∈ Si for each i and fi⊂ fi+1 for each i=0,1,…,d-2. Our main result is an upper bound on the number of flags which is tight in the worst case. We also study several other kinds of incidence problems, including (i) incidences between points and lines in \R3 such that among the lines incident to a point, at most O(1) of them can be coplanar, (ii) incidences with Legendrian lines in \R3, a special class of lines that arise when considering flags that are defined in terms of other groups, and (iii) flags in \R3 (involving points, lines, and planes), where no given line can contain too many points or lie on too many planes. The bound that we obtain in (iii) is nearly tight in the worst case. Finally, we explore a group theoretic interpretation of flags, a generalized version of which leads us to new incidence problems.