Induced Subdivisions in Ks,s-Free Graphs With Polynomial Average Degree

In this paper we prove that for every s >= 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 C>0, then G either contains a K-s,K-s or an induced subdivision of H. This is essentially tight and confirms a conjecture of Bonamy, Bousquet, Pilipczuk, Rz & aogon;& zdot;ewski, Thomass & eacute;, and Walczak. A slightly weaker form of this has been independently proved by Bourneuf, Buci & cacute;, Cook, and Davies. We actually prove a much more general result which implies the above (with worse dependence on |H|). We show that for every k >= 2 there is A(k)>0 such that any graph G with average degree s(k)(A) either contains a K-s,K-s or an induced subgraph G 'subset of 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 >= 2 every graph G with average degree at least B(t)k(Omega)(t) must contain either a K-k, an induced K-t,K-t or an induced subdivision of Kk. This is again essentially tight up to the implied constants and answers in a strong form a question of Davies.