Large bounded degree trees in expanding graphs (Q2380438): Difference between revisions

Summary: A remarkable result of \textit{J. Friedman} and \textit{N. Pippenger} [``Expanding graphs contain all small trees'', Combinatorica 7, 71--76 (1987; Zbl 0624.05028)] gives a sufficient condition on the expansion properties of a graph to contain all small trees with bounded maximum degree. \textit{P.E. Haxell} [``Tree embeddings'', J. Graph Theory 36, No.\,3, 121--130 (2001; Zbl 0967.05029)] showed that under slightly stronger assumptions on the expansion rate, their technique allows one to find arbitrarily large trees with bounded maximum degree. Using a slightly weaker version of Haxell's result we prove that a certain family of expanding graphs, which includes very sparse random graphs and regular graphs with large enough spectral gap, contains all almost spanning bounded degree trees. This improves two recent tree-embedding results of \textit{N. Alon}, \textit{M. Krivelevich}, and \textit{B. Sudakov} [Combinatorica 27, No.\,6, 629--644 (2007; Zbl 1164.05032)].