Rainbow subdivisions of cliques

Abstract

We show that for every integer $m\ge 2$ and large $n$, every properly edge-coloured graph on $n$ vertices with at least $n(\log n{)}^{53}$ edges contains a rainbow subdivision of $K_m$. This is sharp up to a polylogarithmic factor. Our proof method exploits the connection between the mixing time of random walks and expansion in graphs.

22 pages, journal version