Seonghyuk Im (임성혁) gave a talk on the existence of a large complete topological minor in a graph without small dense subgraphs at the Discrete Math Seminar

On November 30, 2021, Seonghyuk Im (임성혁) from KAIST gave a talk at the Discrete Math Seminar on the existence of a large complete topological minor in a graph of bounded average degree when the graph has no small dense subgraphs. The title of his talk was “Large clique subdivisions in graphs without small dense subgraphs“.

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) = \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_{\varepsilon}(G)$ which is the order of the smallest subgraph of $G$ with average degree at least $\varepsilon d(G)$. In fact, they conjectured that for small enough $\varepsilon>0$, every graph $G$ of average degree $d$ contains a clique subdivision of size $\Omega(\min\{d, \sqrt{\frac{c_{\varepsilon}(G)}{\log c_{\varepsilon}(G)}}\})$. We prove that this conjecture holds up to a multiplicative $\min\{(\log\log d)^6,(\log \log c_{\varepsilon}(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.