Spanning trees in sparse expanders

arXiv2211.04758MaRDI QIDQ6416652FDOQ6416652

Authors: Jie Han, Donglei Yang 

Publication date: 9 November 2022

Abstract: Given integers $ngeDeltage2$, let $mathcalT(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 $mathcalT(n,Delta)$-universal, namely, it contains all members of $mathcalT(n,Delta)$ as a subgraph simultaneously. In this paper we show that for sufficiently large integer $n$ and all $DeltainmathbbN$, every $(n,d,lambda)$-graph with [ lambdalefrac{d}{2Delta^{5sqrt{log n}}} ] is $mathcalT(n,Delta)$-universal. As an immediate corollary, this implies that Alon's ingenious construction of triangle-free sparse expander is $mathcalT(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 $DeltainmathbbN$, every $(n,Delt{a}^{5sqrtlogn})$-expander is $mathcalT(n,Delta)$-universal. (2).For all $DeltainmathbbN$ with $Deltalecsqrtn$, every $(n,CDelta{n}^{1/2})$-expander is $mathcalT(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.

This page was built for publication: Spanning trees in sparse expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416652)