Balanced subdivisions of a large clique in graphs with high average degree

Abstract

In 1984, Thomassen conjectured that for every constant $k\in \mathbb{N}$, there exists $d$ such that every graph with average degree at least $d$ contains a balanced subdivision of a complete graph on $k$ vertices, i.e. a subdivision in which each edge is subdivided the same number of times. Recently, Liu and Montgomery confirmed Thomassen's conjecture. We show that for every constant $0<c<1/2$, every graph with average degree at least $d$ contains a balanced subdivision of a complete graph of size at least $\Omega (d^c)$. Note that this bound is almost optimal. Moreover, we show that every sparse expander with minimum degree at least $d$ contains a balanced subdivision of a complete graph of size at least $\Omega (d)$.

arXiv admin note: text overlap with arXiv:2010.15802 by other authors