Random Structures and Algorithms · 2010 · 71 citations · 15 references
Natural SciencesComputer ScienceMathematicsCombinatoricsProbability TheoryStochastic ProcessesGraph TheoryProbabilistic CombinatoricsExpander GraphsExpansion In GraphsExpansion In Random GraphsRandom Graph ModelsRandom Graph TheoryRandom GraphsResilienceSparse Random Graphs
Abstract 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
15
Some Theorems on Abstract Graphs
G. A. Dirac · Proceedings of the London Mathematical Society · 1952 · 1.6K citations
Hamiltonian circuits in random graphs
L. Pósa · Discrete Mathematics · 1976 · 468 citations
Expanding graphs contain all small trees
Joel Friedman, Nicholas Pippenger · COMBINATORICA · 1987 · 186 citations
Benny Sudakov, Van H. Vu · Random Structures and Algorithms · 2008 · 93 citations