Two theorems on point-flat incidences

DOI10.1016/J.COMGEO.2020.101681MaRDI QIDQ827305zbMATH OpenOpenAlexFDO

Authors Ben Lund

Publication date 7 January 2021

Published in Computational Geometry (Search for Journal in Brave)

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

zbMATH Keywords

extremal problems in discrete geometryincidence geometry

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Other problems of combinatorial convexity (52A37) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Discrete geometry (52C99)

Abstract: We improve the theorem of Beck giving a lower bound on the number of $k$-flats spanned by a set of points in real space, and improve the bound of Elekes and T'oth on the number of incidences between points and $k$-flats in real space.

Review text

Let \(P \subseteq {\mathbb R}^d\) be a set of \(n\) points. According to \textit{E. Szemerédi} and \textit{W. T. Trotter jun.} [Combinatorica 3, 381--392 (1983; Zbl 0541.05012)], for every \(r>1\) the number of lines containing at least \(r\) points from \(P\) is bounded above by \(O(n^2 r^{-3} + n r^{-1})\). Extending a result of \textit{G. Elekes} and \textit{C. D. Tóth} [in: Proceedings of the 21st annual symposium on computational geometry, SCG 2005, Pisa, Italy, June 6--8, 2005. New York, NY: Association for Computing Machinery (ACM). 16--21 (2005; Zbl 1387.52039)], the author obtains a similar upper bound for the number of \(k\)-flats (i.e.\ \(k\)-dimensional affine subspaces) \(\Gamma\) such that \(|\Gamma \cap P| \ge r\) and at most \(\alpha |\Gamma \cap P|\) points of \(P\) lie on any \((k-1)\)-flat contained in \(\Gamma\), where \(0<\alpha<1\). Moreover, the author improves a result of \textit{J. Beck} [Combinatorica 3, 281--297 (1983; Zbl 0533.52004)], as follows: For any integer \(k\ge 1\) and any \(c_k < 1/2\) there is a constant \(c_k'\) such that either \(c_k n\) points of \(P\) are contained in a single \(k\)-flat, or \(P\) spans \(c_k' n^{k+1}\) \(k\)-flats.

Recommendations

• Extending Erdős-Beck's theorem to higher dimensions
• Incidence theorems for pseudoflats
• An incidence theorem in higher dimensions
• A bichromatic incidence bound and an application
• Incidences of not-too-degenerate hyperplanes

Cites work

• A bichromatic incidence bound and an application
• A Szemerédi-Trotter type theorem in R^4
• Applications of incidence bounds in point covering problems
• Counting facets and incidences
• Essential dimension and the flats spanned by a point set
• Extremal problems in discrete geometry
• Incidences of not-too-degenerate hyperplanes
• Incidences with curves in \(\mathbb{R}^d\)
• Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
• On counting point-hyperplane incidences
• On some problems of elementary and combinatorial geometry
• On the lattice property of the plane and some problems of Dirac, Motzkin and Erdős in combinatorial geometry
• The complexity of many cells in arrangements of planes and related problems
• The Szemerédi-Trotter theorem in the complex plane

Cited in

(11)

• Essential dimension and the flats spanned by a point set
• Nondegenerate spheres in four dimensions
• Extending Erdős-Beck's theorem to higher dimensions
• The largest complete bipartite subgraph in point-hyperplane incidence graphs
• Threshold functions for incidence properties in finite vector spaces
• scientific article; zbMATH DE number 6315496 (Why is no real title available?)
• AN INCIDENCE RESULT FOR WELL-SPACED ATOMS IN ALL DIMENSIONS
• Covering points by hyperplanes and related problems
• On the determinants of matrices with elements from arbitrary sets
• On subsets of lattice cubes avoiding affine and spherical degeneracies
• Incidence theorems for pseudoflats

This page was built for publication: Two theorems on point-flat incidences

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