On Polynomial Degree-Boundedness

We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph H, there is a polynomial p such that for every positive integer s, every graph of average degree at least p(s) contains either K_s,s as a subgraph or contains an induced subdivision of H. This improves upon a result of Kühn and Osthus from 2004 who proved it for graphs whose average degree is at least triply exponential in s and a recent result of Du, Girão, Hunter, McCarty and Scott for graphs with average degree at least singly exponential in s. As an application, we prove that the class of graphs that do not contain an induced subdivision of K_r,t is polynomially χ-bounded. In the case of K_2,3, this is the class of induced theta-free graphs, and answers a question of Davies. Along the way, we also answer a recent question of McCarty, by showing that if G is a hereditary class of graphs for which there is a polynomial p such that every bipartite K_s,s-subgraph-free graph in G has average degree at most p(s), then more generally, there is a polynomial p′ such that every K_s,s-subgraph-free graph in G has average degree at most p′ (s). Our main new tool is an induced variant of the Kővári-Sós-Turán theorem, which we find to be of independent interest.