{"id":"arxiv/2608.28354","url":"https://arxiv.org/abs/2608.28354","tags":["math.CO","cs.CC","cs.DM","math.MG"],"score":0,"title":"Discrepancy of geometric incidences","domain":"math.CO","source":"arxiv","authors":["Azem Adibelli","István Tomon"],"reviews":0,"subject":"math.CO","summary":"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^{\\frac12-\\frac{1}{2(D+1)}-\\varepsilon}$ for some $\\varepsilon=\\varepsilon(D,k)>0$. This gives a polynomial improvement over the straightforward VC-dimension bound $\\tilde O(n^{\\frac12-\\frac{1}{2(D+1)}})$. In the opposite direction, we…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-28","reactions":{}}