Zarankiewicz bounds from distal regularity lemma

Abstract

Since Kővári, Sós, and Turán proved upper bounds for the Zarankiewicz problem in 1954, much work has been undertaken to improve these bounds, and some have done so by restricting to particular classes of graphs. In 2017, Fox, Pach, Sheffer, Suk, and Zahl proved better bounds for semialgebraic binary relations, and this work was extended by Do in the following year to arbitrary semialgebraic relations. In this paper, we show that Zarankiewicz bounds in the shape of Do's are enjoyed by all relations satisfying the distal regularity lemma, an improved version of the Szemerédi regularity lemma satisfied by relations definable in distal structures (a vast generalisation of o-minimal structures).