Generalizations of the Szemerédi-Trotter theorem

DOI10.1007/S00454-016-9759-5zbMATH Open1346.52009arXiv1408.5915OpenAlexW2253180889MaRDI QIDQ282741FDOQ282741

Authors: Saarik Kalia, Noam Solomon, Ben Yang, Micha Sharir 

Publication date: 12 May 2016

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: We generalize the Szemer'edi-Trotter incidence theorem, to bound the number of complete emph{flags} in higher dimensions. Specifically, for each $i=0,1,ldots,d-1$, we are given a finite set $S_i$ of $i$-flats in $R^d$ or in $C^d$, and a (complete) flag is a tuple $(f_0,f_1,ldots,f_{d-1})$, where $f_{i}in{S}_i$ for each $i$ and $f_{i}subset{f}_{i+1}$ for each $i=0,1,ldots,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 $R^3$ such that among the lines incident to a point, at most $O(1)$ of them can be coplanar, (ii) incidences with Legendrian lines in $R^3$, a special class of lines that arise when considering flags that are defined in terms of other groups, and (iii) flags in $R^3$ (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.

Full work available at URL: https://arxiv.org/abs/1408.5915

Recommendations

• A generalization of Szegö's theorem
• On a generalization of Szemerédi's theorem
• ON A GENERALIZATION OF SZEMERÉDI'S THEOREM
• Szasz's theorem and its generalizations
• On a generalization of the Szpilrajn theorem
• Publication:4946892
• A generalisation of Tverberg's theorem
• Generalization of a Classical Theorem of Polya and Szego
• A generalization of Szlam's lemma
• A generalization of a theorem of Tikhonov

zbMATH Keywords

cell decompositionflagspolynomial methodSzemeredi-Trotter incidence theorem

Mathematics Subject Classification ID

Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Cites Work

• On the Erdős distinct distances problem in the plane
• The Szemerédi-Trotter theorem in the complex plane
• Title not available (Why is that?)
• Extremal problems in discrete geometry
• Algebraic methods in discrete analogs of the Kakeya problem
• On lines, joints, and incidences in three dimensions
• Legendrian subvarieties of projective space
• Title not available (Why is that?)
• Point–Line Incidences in Space
• A Szemerédi-Trotter type theorem in \(\mathbb R^4\)

Cited In (4)

• Generalizations of the Sidon-Telyakovskii Theorem
• Dense Arrangements are Locally Very Dense. I
• Incidences of not-too-degenerate hyperplanes
• On a generalization of the Szpilrajn theorem

This page was built for publication: Generalizations of the Szemerédi-Trotter theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q282741)