Sách Large bounded degree trees in expanding graphs

Abstract
A remarkable result of Friedman and Pippenger [4] gives a sufficient condition
on the expansion properties of a graph to contain all small trees with bounded
maximum degree. Haxell [5] 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 ran-
dom graphs and regular graphs with large enough spectral gap, contains all almost
spanning bounded degree trees. This improves two recent tree-embedding results of
Alon, Krivelevich and Sudakov [1].