We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzazewski, Thomasse, 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) either contains 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, Girao, 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_{s,t} is polynomially chi-bounded. In the case of K_{2,3}, this is the class of theta-free graphs, and answers a question of Davies.

Along the way, we also answer a recent question of McCarty, by showing that if A is a hereditary class of graphs for which there is a polynomial p such that every bipartite K_{s,s}-free graph in A has average degree at most p(s), then more generally, there is a polynomial p' such that every K_{s,s}-free graph in A has average degree at most p'(s).

Our main new tool is an induced variant of the Kovari-Sos-Turan theorem, which we find to be of independent interest.

Joint with: Romain Bourneuf (ENS de Lyon), Matija Bucic (Princeton), James Davies (Cambridge).