Large bounded degree trees in expanding graphs

J́ozsef Balogh, B́ela Csaba, Martin Pei, Wojciech Samotij

Research output: Contribution to journalArticlepeer-review

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 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 Alon, Krivelevich and Sudakov [1].

Original languageEnglish (US)
Pages (from-to)1-9
Number of pages9
JournalElectronic Journal of Combinatorics
Volume17
Issue number1
DOIs
StatePublished - 2010

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Large bounded degree trees in expanding graphs'. Together they form a unique fingerprint.

Cite this