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

Given a set of points P and a set of regions O, an incidence is a pair (p, o) ∈ P × O such that p ∈ o. 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.