Spanning trees in sparse expanders

Abstract

Given integers $n\ge \Delta \ge 2$, let $\mathcal{T}(n,\Delta )$ be the collection of all $n$-vertex trees with maximum degree at most $\Delta$. A question of Alon, Krivelevich and Sudakov in 2007 asks for determining the best possible spectral gap condition forcing an $(n,d,\lambda )$-graph to be $\mathcal{T}(n,\Delta )$-universal, namely, it contains all members of $\mathcal{T}(n,\Delta )$ as a subgraph simultaneously. In this paper we show that for sufficiently large integer $n$ and all $\Delta \in \mathbb{N}$, every $(n,d,\lambda )$-graph with \[ λ\le\frac{d}{2Δ^{5\sqrt{\log n}}} \] is $\mathcal{T}(n,\Delta )$-universal. As an immediate corollary, this implies that Alon's ingenious construction of triangle-free sparse expander is $\mathcal{T}(n,\Delta )$-universal, which provides an explicit construction of such graphs and thus solves a question of Johannsen, Krivelevich and Samotij. Our main result is formulated under a much more general context, namely, the $(n,d)$-expanders. More precisely, we show that there exist absolute constants $C,c>0$ such that the following statement holds for sufficiently large integer $n$. (1).For all $\Delta \in \mathbb{N}$, every $(n,{\Delta }^{5\sqrt{\log n}})$-expander is $\mathcal{T}(n,\Delta )$-universal. (2).For all $\Delta \in \mathbb{N}$ with $\Delta \le c\sqrt{n}$, every $(n,C\Delta n^{1/2})$-expander is $\mathcal{T}(n,\Delta )$-universal. Both results significantly improve a result of Johannsen, Krivelevich and Samotij, and have further implications in locally sparse expanders and Maker-Breaker games that also improve previously known results drastically.

arXiv comment27 pages, 4 figures, comments are welcome