Generalizations of the Szemerédi-Trotter theorem

DOI10.1007/S00454-016-9759-5MaRDI QIDQ282741zbMATH OpenOpenAlexFDO

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

Publication date 12 May 2016

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

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

zbMATH Keywords

cell decompositionflagspolynomial methodSzemeredi-Trotter incidence theorem

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(4)

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

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)