Can I read Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal on EtoBox?

Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal by Julia Böttcher; Yoshiharu Kohayakawa; Anusch Taraz is a Computer Science article available to read on EtoBox.

What is Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal about?

Let Δ ≥ 2 be a fixed integer. We show that the random graph G n,p with p ≥ c(log n/n) 1/Δ is robust with respect to the containment of almost spanning bipartite graphs H with maximum degree Δ and sublinear bandwidth in the following sense. If an adversary deletes arbitrary edges in G n,p such that each vertex loses less than half of its neighbours, then asymptotically almost surely the resulting graph still contains a copy of H.

Who reads Almost Spanning Subgraphs of Random Graphs After Adversarial Edge Removal?

Author

Julia Böttcher; Yoshiharu Kohayakawa; Anusch Taraz

Publisher

Elsevier Science; Elsevier ; Elsevier BV; Amsterdam: Elsevier BV (ISSN 1571-0653)

Published

2009

Language

EN

Field

Computer Science (Physical Sciences)