Dense Arrangements are Locally Very Dense. I

DOI10.1137/05062826XzbMATH Open1122.52008arXivmath/0504009OpenAlexW1971661739MaRDI QIDQ5757380FDOQ5757380

Authors: József Solymosi 

Publication date: 6 September 2007

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The Szemer'edi-Trotter theorem gives a bound on the maximum number of incidences between points and lines on the Euclidean plane. In particular it says that $n$ lines and $n$ points determine $O(n^{4/3})$ incidences. Let us suppose that an arrangement of $n$ lines and $n$ points defines $c{n}^{4/3}$ incidences, for a given positive $c.$ It is widely believed that such arrangements have special structure, but no results are known in this direction. Here we show that for any natural number, $k,$ one can find $k$ points of the arrangement in general position such that any pair of them is incident to a line from the arrangement, provided by $ngeq{n}_0(k).$ In a subsequent paper we will establish similar statement to hyperplanes.

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

Recommendations

• On grids in point-line arrangements in the plane
• A Szemerédi-Trotter type theorem in \(\mathbb R^4\)
• Generalizations of the Szemerédi-Trotter theorem
• Sets of rich lines in general position
• Szemerédi-Trotter-type theorems in dimension 3

zbMATH Keywords

regularity lemmapoint-line incidencesSzemerédi-Trotter theorem

Mathematics Subject Classification ID

Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30) Combinatorial complexity of geometric structures (52C45)

Cited In (9)

• The counting lemma for regular k‐uniform hypergraphs
• A structural Szemerédi-Trotter theorem for Cartesian products
• Hasse diagrams with large chromatic number
• On Grids in Point-Line Arrangements in the Plane
• On the structure of pointsets with many collinear triples
• On cliques in three-dimensional dense point-line arrangements
• Depth in an arrangement of hyperplanes
• The constant of point-line incidence constructions
• On grids in point-line arrangements in the plane

This page was built for publication: Dense Arrangements are Locally Very Dense. I

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