Premium
Local resilience of almost spanning trees in random graphs
Author(s) -
Balogh József,
Csaba Béla,
Samotij Wojciech
Publication year - 2010
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20345
Subject(s) - combinatorics , mathematics , random graph , bipartite graph , discrete mathematics , lemma (botany) , random regular graph , degree (music) , vertex (graph theory) , bounded function , graph , 1 planar graph , chordal graph , ecology , mathematical analysis , physics , poaceae , acoustics , biology
We prove that for fixed integer D and positive reals α and γ , there exists a constant C 0 such that for all p satisfying p ( n ) ≥ C 0 / n , the random graph G ( n , p ) asymptotically almost surely contains a copy of every tree with maximum degree at most D and at most (1 ‐ α ) n vertices, even after we delete a (1/2 ‐ γ )‐fraction of the edges incident to each vertex. The proof uses Szemerédi's regularity lemma for sparse graphs and a bipartite variant of the theorem of Friedman and Pippenger on embedding bounded degree trees into expanding graphs. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2011