Induced Subdivisions in <i>K</i> <i>s,s</i>-Free Graphs With Polynomial Average Degree

Abstract In this paper we prove that for every $s\geqslant 2$ and every graph $H$ the following holds. Let $G$ be a graph with average degree $\Omega _{H}(s^{A|H|^{2}})$, for some absolute constant $A&amp;gt;0$, then $G$ either contains a $K_{s,s}$ or an induced subdivision of $H$. This is essentially tight and confirms a conjecture of Bonamy, Bousquet, Pilipczuk, Rz kaŻewski, Thomassé, and Walczak in [2]. A slightly weaker form of this has been independently proved by Bourneuf, Bucić, Cook, and Davies [3]. We actually prove a much more general result, which implies the above (with worse dependence on $|H|$). We show that for every $ k\geqslant 2$ there is $A_{k}&amp;gt;0$ such that any graph $G$ with average degree $s^{A_{k}}$ either contains a $K_{s,s}$ or an induced subgraph $G^{\prime}\subseteq G$ without $C_{4}$’s and with average degree at least $k$. Finally, using similar methods we can prove the following. For every $k,t\geqslant 2$ every graph $G$ with average degree at least $B_{t}k^{\Omega (t)}$ must contain either a $K_{k}$, an induced $K_{t,t}$ or an induced subdivision of $K_{k}$. This is again essentially tight up to the implied constants and answers in a strong form a question of Davies.