Discrepancy of geometric incidences

Abstract

We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every n-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most D and degree at most k has discrepancy at most n^{1/2−1/(2(D+1))−ε} for some ε=ε(D,k)>0. This gives a polynomial improvement over the straightforward VC-dimension bound Õ(n^{1/2−1/(2(D+1))}). In the opposite direction, we construct n-point sets in ℝ^d whose discrepancy with respect to hyperplanes is Ω̃(n^{1/2−1/(d+1)}), extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.

A combinatorial approach to point-flat incidences over finite fields
Ben Lund, Tao Zhang
arXiv27 Sep 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
Lengths and incidences in Poisson hypersphere and spherical splitting tessellations
Daniel Hug, Christoph Thäle
arXiv7 Sep 2026PreprintCC BY 4.0Full textProbabilityarXiv
Hyperplane Incidences and Distance Sets in Higher Dimensions
Marianna Csornyei, D. M. Stull
arXiv30 Sep 2026PreprintCC BY 4.0Full textAnalysis & PDEs Combinatorics & discrete mathematicsarXiv
Optimal discrepancy for triangles
Gleb Smirnov
arXiv16 Oct 2026PreprintCC BY 4.0Full textCombinatorics & discrete mathematics ProbabilityarXiv
A Sharp Distributional Lower Bound for Planar Discrepancy
Aicke Hinrichs
arXiv21 Oct 2026PreprintCC BY 4.0Full textAlgebra & number theoryarXiv

Cite

BibTeX RIS

BibTeX

@misc{adibelli2026discrepancy,
  title = {{Discrepancy of geometric incidences}},
  author = {Azem Adibelli and István Tomon},
  howpublished = {arXiv},
  year = {2026},
  month = aug,
  doi = {10.48550/arxiv.2608.28354},
  eprint = {2608.28354},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2608.28354},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Discrepancy of geometric incidences
AU  - Azem Adibelli
AU  - István Tomon
PY  - 2026
DA  - 2026/08/28
PB  - arXiv
DO  - 10.48550/arxiv.2608.28354
UR  - https://arxiv.org/abs/2608.28354
AB  - We study the combinatorial (red-blue) discrepancy of finite point sets with respect to hyperplanes and, more generally, bounded-complexity affine algebraic sets. We prove that every n-point set in a real Euclidean space admits a red-blue coloring for which every affine algebraic set of dimension at most D and degree at most k has discrepancy at most n^1/2−1/(2(D+1))−ε for some ε=ε(D,k)>0. This gives a polynomial improvement over the straightforward VC-dimension bound Õ(n^1/2−1/(2(D+1))). In the opposite direction, we construct n-point sets in ℝ^d whose discrepancy with respect to hyperplanes is Ω̃(n^1/2−1/(d+1)), extending the point-line discrepancy lower bound of Chazelle and Lvov. We present further applications of our methods in communication complexity, concerning separation between randomized communication cost and deterministic communication cost with access to equality oracle.
ER  -

Abstract

Related

Cite