We prove a conjecture of Bonamy, Bousquet, Pilipczuk, Rzążewski, Thomassé, and Walczak, that for every graph , there is a polynomial such that for every positive integer , every graph of average degree at least contains either as a subgraph or contains an induced subdivision of . 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 and a recent result of Du, Girão, Hunter, McCarty and Scott for graphs with average degree at least singly exponential in .
As an application, we prove that the class of graphs that do not contain an induced subdivision of is polynomially -bounded. In the case of , 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 is a hereditary class of graphs for which there is a polynomial such that every bipartite -free graph in has average degree at most , then more generally, there is a polynomial such that every -free graph in has average degree at most . 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.
This is joint work with Romain Bourneuf (ENS de Lyon), Matija Bucić (Princeton), and James Davies (Cambridge),