Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal
- 8 August 2013
- journal article
- research article
- Published by Cambridge University Press (CUP) in Combinatorics, Probability and Computing
- Vol. 22 (5) , 639-683
Abstract
Let Δ ≥ 2 be a fixed integer. We show that the random graph ${\mathcal{G}_{n,p}}$ with $p\gg (\log n/n)^{1/\Delta}$ is robust with respect to the containment of almost spanning bipartite graphsHwith maximum degree Δ and sublinear bandwidth in the following sense: asymptotically almost surely, if an adversary deletes arbitrary edges from ${\mathcal{G}_{n,p}}$ in such a way that each vertex loses less than half of its neighbours, then the resulting graph still contains a copy of all suchH.
Keywords
All Related Versions
This publication has 21 references indexed in Scilit:
- Properly coloured copies and rainbow copies of large graphs with small maximum degreeRandom Structures & Algorithms, 2011
- Local resilience of almost spanning trees in random graphsRandom Structures & Algorithms, 2010
- Local resilience of graphsRandom Structures & Algorithms, 2008
- Proof of the bandwidth conjecture of Bollobás and KomlósMathematische Annalen, 2008
- On the Resilience of Long Cycles in Random GraphsThe Electronic Journal of Combinatorics, 2008
- Sparse universal graphs for bounded‐degree graphsRandom Structures & Algorithms, 2006
- Regular pairs in sparse random graphs IRandom Structures & Algorithms, 2003
- Random Graphs2000
- Szemerédi’s Regularity Lemma for Sparse Graphs1997
- Multicoloured Hamilton CyclesThe Electronic Journal of Combinatorics, 1995