Hostname: page-component-74656f9884-8rzl6 Total loading time: 0 Render date: 2026-11-06T00:32:30.003Z Has data issue: false hasContentIssue false
  • English
  • Français

A Sharp Threshold for Network Reliability

Published online by Cambridge University Press:  09 October 2002

MICHAEL KRIVELEVICH ,
BENNY SUDAKOV  and
VAN H. VU
MICHAEL KRIVELEVICH
Affiliation:
Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Tel Aviv University, Tel Aviv 69978, Israel (e-mail: krivelev@math.tau.ac.il)
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08540, USA and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: bsudakov@math.princeton.edu)
VAN H. VU
Affiliation:
Theory Group, Microsoft Research, Redmond, WA 98052, USA (e-mail: vanvu@ucsd.edu; Web: http://www.math.ucsd.edu/˜vanvu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Given a graph G on n vertices with average degree d, form a random subgraph Gp by choosing each edge of G independently with probability p. Strengthening a classical result of Margulis we prove that, if the edge connectivity k(G) satisfies k(G) [Gt] d/log n, then the connectivity threshold in Gp is sharp. This result is asymptotically tight.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 5 , September 2002 , pp. 465 - 474
Copyright
2002 Cambridge University Press