On the Number of Incidences When Avoiding an Induced Biclique in Geometric Settings

Given a set of points P and a set of regions 𝒪, an incidence is a pair ( p , θ) ∈ P × 𝒪 such that p ∈ ø. We obtain a number of new results on a classical question in combinatorial geometry: What is the number of incidences (under certain restrictive conditions)? We prove a bound of O ( kn (log n / log log n ) d -1 ) on the number of incidences between n points and n axis-parallel boxes in ℝ d , if no k boxes contain k common points, that is, if the incidence graph between the points and the boxes does not contain K k , k as a subgraph. This new bound improves over previous work, by Basit, Chernikov, Starchenko, Tao, and Tran (2021), by more than a factor of log d n for d > 2. Furthermore, it matches a lower bound implied by the work of Chazelle (1990), for k = 2, thus settling the question for points and boxes. We also study several other variants of the problem. For halfspaces, using shallow cuttings, we get a linear bound in two and three dimensions. We also present linear (or near linear) bounds for shapes with low union complexity, such as pseudodisks and fat triangles. * The full version of the paper can be accessed at https://arxiv.org/abs/2112.14829