An incidence theorem in higher dimensions (Q452010): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(8 intermediate revisions by 6 users not shown) | |||
Property / author | |||
Property / author: Terence C. Tao / rank | |||
Property / author | |||
Property / author: Terence C. Tao / rank | |||
Normal rank | |||
Property / review text | |||
The Szemerédi-Trotter theorem [\textit{E. Szemerédi} and \textit{W.~T. Trotter, jun.}, Combinatorica 3, 381--392 (1983; Zbl 0541.05012)] gives a ``big O'' upper bound for the number of incidences between a set of points and a set of lines in terms of their respective cardinalities. The article under review gives an upper bound for the number of incidences between points and \(k\)-dimensional real algebraic varieties of bounded degree under the assumption of some ``pseudoline-type axioms''. This bound is only ``almost tight'' because of an \(\varepsilon\)-loss in an exponent. The authors conjecture that one can get rid of this loss but also concede that their methods of the proof (induction on the number of points and the polynomial ham sandwich theorem) do not easily give such an improvement. The article contains a number of corollaries to the main theorem, also from seemingly remote areas, a simpler proof for a cheaper result, and a good discussion of history and relevance of Szemerédi-Trotter type theorems. | |||
Property / review text: The Szemerédi-Trotter theorem [\textit{E. Szemerédi} and \textit{W.~T. Trotter, jun.}, Combinatorica 3, 381--392 (1983; Zbl 0541.05012)] gives a ``big O'' upper bound for the number of incidences between a set of points and a set of lines in terms of their respective cardinalities. The article under review gives an upper bound for the number of incidences between points and \(k\)-dimensional real algebraic varieties of bounded degree under the assumption of some ``pseudoline-type axioms''. This bound is only ``almost tight'' because of an \(\varepsilon\)-loss in an exponent. The authors conjecture that one can get rid of this loss but also concede that their methods of the proof (induction on the number of points and the polynomial ham sandwich theorem) do not easily give such an improvement. The article contains a number of corollaries to the main theorem, also from seemingly remote areas, a simpler proof for a cheaper result, and a good discussion of history and relevance of Szemerédi-Trotter type theorems. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Hans-Peter Schröcker / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 51B05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 51A05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 14J99 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6084049 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Szemerédi-Trotter type incidence theorems | |||
Property / zbMATH Keywords: Szemerédi-Trotter type incidence theorems / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
sum-product bounds | |||
Property / zbMATH Keywords: sum-product bounds / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56454604 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2144337080 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1103.2926 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Applications of a new space-partitioning technique / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Crossing-Free Subgraphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Incidences between points and circles in three and higher dimensions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Refined bounds on the number of connected components of sign conditions on a variety / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of cells defined by a family of polynomials on a variety / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the multilinear restriction and Kakeya conjectures / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Research Problems in Discrete Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximate subgroups of linear groups. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4203817 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Additive and Multiplicative Structure in Matrix Spaces / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the number of sums and products / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4410009 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Incidences of not-too-degenerate hyperplanes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3533739 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4846449 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algebraic methods in discrete analogs of the Kakeya problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Erdős distinct distances problem in the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4143433 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Definability and fast quantifier elimination in algebraically closed fields / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Geometric incidence theorems via Fourier analysis / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Simple proofs of classical theorems in discrete geometry via the Guth-Katz polynomial partitioning technique / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a problem of K. Zarankiewicz / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Incidence theorems for pseudoflats / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4530626 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Betti Numbers of Real Varieties / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The red book of varieties and schemes. Includes the Michigan lectures (1974) on ``Curves and their Jacobians''. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5792748 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Repeated angles in the plane and related problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the Number of Incidences Between Points and Curves / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5302610 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The complexification and degree of a semi-algebraic set. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3344468 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the affine Bezout inequality / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Point–Line Incidences in Space / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3602878 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinct distances in homogeneous sets in Euclidean space / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Distinct distances in homogeneous sets / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5186278 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Generalized ''sandwich'' theorems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Crossing Numbers and Hard Erdős Problems in Discrete Geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4410025 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Extremal problems in discrete geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The sum-product phenomenon in arbitrary rings / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4542029 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5511997 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Szemerédi-Trotter theorem in the complex plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4250346 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An improved bound on the number of point-surface incidences in three dimensions / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 17:33, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An incidence theorem in higher dimensions |
scientific article |
Statements
An incidence theorem in higher dimensions (English)
0 references
19 September 2012
0 references
The Szemerédi-Trotter theorem [\textit{E. Szemerédi} and \textit{W.~T. Trotter, jun.}, Combinatorica 3, 381--392 (1983; Zbl 0541.05012)] gives a ``big O'' upper bound for the number of incidences between a set of points and a set of lines in terms of their respective cardinalities. The article under review gives an upper bound for the number of incidences between points and \(k\)-dimensional real algebraic varieties of bounded degree under the assumption of some ``pseudoline-type axioms''. This bound is only ``almost tight'' because of an \(\varepsilon\)-loss in an exponent. The authors conjecture that one can get rid of this loss but also concede that their methods of the proof (induction on the number of points and the polynomial ham sandwich theorem) do not easily give such an improvement. The article contains a number of corollaries to the main theorem, also from seemingly remote areas, a simpler proof for a cheaper result, and a good discussion of history and relevance of Szemerédi-Trotter type theorems.
0 references
Szemerédi-Trotter type incidence theorems
0 references
sum-product bounds
0 references
0 references
0 references