Large bounded degree trees in expanding graphs

zbMath1184.05022MaRDI QIDQ2380438

Martin Pei, Wojciech Samotij, József Balogh, Béla Csaba

Publication date: 26 March 2010

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/233109

zbMATH Keywords

spectral gapsparse random graphsbounded maximum degreeexpansion propertiessmall treesspanning bounded degree trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Random graphs (graph-theoretic aspects) (05C80) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items (18)

The vertex size-Ramsey number ⋮ Rolling backwards can move you forward: On embedding problems in sparse expanders ⋮ Global maker-breaker games on sparse graphs ⋮ Rainbow trees in uniformly edge‐colored graphs ⋮ Cycle Factors and Renewal Theory ⋮ Embedding Graphs into Larger Graphs: Results, Methods, and Problems ⋮ Sparse multipartite graphs as partition universal for graphs with bounded degree ⋮ Random perturbation of sparse graphs ⋮ Cycle lengths in expanding graphs ⋮ Local resilience of almost spanning trees in random graphs ⋮ Universality of random graphs and rainbow embedding ⋮ Universality for bounded degree spanning trees in randomly perturbed graphs ⋮ An improved upper bound on the density of universal random graphs ⋮ Optimal threshold for a random graph to be 2-universal ⋮ Spanning trees in random graphs ⋮ Unnamed Item ⋮ The Approximate Loebl--Komlós--Sós Conjecture I: The Sparse Decomposition ⋮ Sharp threshold for the appearance of certain spanning trees in random graphs

This page was built for publication: Large bounded degree trees in expanding graphs