|
Abstract |
We will introduce the sublinear expander and cover some applications of sublinear expander. Given a graph H, a balanced subdivision of H is a graph obtained from H by subdividing every edge the same number of times. In 1984, Thomason conjectured that for each integer k≥1, high average degree is sufficient to guarantee a balanced subdivision of Kk. Recently, Liu and Montgomery resolved this conjecture. We give an optimal estimate up to an absolute constant factor by showing that there exists c>0 such that for sufficiently large d, every graph with average degree at least d contains a balanced subdivision of a clique with at least cd^{1/2} vertices. It also confirms a conjecture from Verstraëte: every graph of average degree cd^2, for some absolute constant c>0, contains a pair of disjoint isomorphic subdivisions of the complete graph Kd. |
