Unbalanced Zarankiewicz problem for bipartite subdivisions with applications to incidence geometry

Abstract

For a bipartite graph $H$, its linear threshold is the smallest real number $\ddot{I}ƒ$ such that every bipartite graph $G=(U\bigsqcup V,E)$ with unbalanced parts $|V|\gtrsim |U{|}^{\ddot{I}}ƒ$ and without a copy of $H$ must have a linear number of edges $|E|\lesssim |V|$. We prove that the linear threshold of the complete bipartite subdivision graph $K_{s,t}^{\prime }$ is at most $\ddot{I}{ƒ}_s=2-1/s$. Moreover, we show that any $\ddot{I}ƒ<\ddot{I}{ƒ}_s$ is less than the linear threshold of $K_{s,t}^{\prime }$ for sufficiently large $t$ (depending on $s$ and $\ddot{I}ƒ$). Some geometric applications of this result are given: we show that any $n$ points and $n$ lines in the complex plane without an $s$-by-$s$ grid determine $O(n^{4/3-c})$ incidences for some constant $c>0$ depending on $s$; and for certain pairs $(p,q)$, we establish nontrivial lower bounds on the number of distinct distances determined by $n$ points in the plane under the condition that every $p$ points determine at least $q$ distinct distances.

Proof of Theorem 1.1 was simplified