Seonghyuk Im (임성혁), Large clique subdivisions in graphs without small dense subgraphs

What is the largest number $f(d)$ where every graph with average degree at least $d$ contains a subdivision of $K_{f(d)}$? Mader asked this question in 1967 and $f(d)=\mathrm{\Theta }(\sqrt{d})$ was proved by Bollobás and Thomason and independently by Komlós and Szemerédi. This is best possible by considering a disjoint union of $K_{d,d}$. However, this example contains a much smaller subgraph with the almost same average degree, for example, one copy of $K_{d,d}$.

In 2017, Liu and Montgomery proposed the study on the parameter $c_{\epsilon }(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\epsilon d(G)$. In fact, they conjectured that for small enough $\epsilon >0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $\mathrm{\Omega }(min\{d,\sqrt{\frac{c_{\epsilon }(G)}{\log c_{\epsilon }(G)}}\})$. We prove that this conjecture holds up to a multiplicative $min\{(\log \log d{)}^6,(\log \log c_{\epsilon }(G){)}^6\}$-term.

As a corollary, for every graph $F$, we determine the minimum size of the largest clique subdivision in $F$-free graphs with average degree $d$ up to multiplicative polylog$(d)$-term.

This is joint work with Jaehoon Kim, Youngjin Kim, and Hong Liu.