Local resilience of almost spanning trees in random graphs

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

Research output: Contribution to journalArticlepeer-review

Abstract

We prove that for fixed integer D and positive reals α and γ, there exists a constant C0 such that for all p satisfying p(n) ≥ C0/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.

Original languageEnglish (US)
Pages (from-to)121-139
Number of pages19
JournalRandom Structures and Algorithms
Volume38
Issue number1-2
DOIs
StatePublished - Jan 2011

Keywords

  • Random graphs
  • Resilience
  • Tree embedding

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Computer Graphics and Computer-Aided Design
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Local resilience of almost spanning trees in random graphs'. Together they form a unique fingerprint.

Cite this