Induced subdivisions in $K_{s,s}$-free graphs with polynomial average degree

Abstract

In this paper we prove that for every $s\ge 2$ and every graph $H$ the following holds. Let $G$ be a graph with average degree ${\Omega }_H(s^{C|H{|}^2})$, for some absolute constant $C>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ążewski, Thomassé, and Walczak. A slightly weaker form of this has been independently proved by Bourneuf, Bucić, 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\ge 2$ there is $C_k>0$ such that any graph $G$ with average degree $s^{C_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\ge 2$ every graph $G$ with average degree at least $C_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.

24 pages, comments welcome!

Cited by in corpus (1)

• Induced subdivisions with pinned branch vertices