Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-25T17:33:36.496Z 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: [email protected])
BENNY SUDAKOV
Affiliation:
Department of Mathematics, Princeton University, Princeton, NJ 08540, USA and Institute for Advanced Study, Princeton, NJ 08540, USA (e-mail: [email protected])
VAN H. VU
Affiliation:
Theory Group, Microsoft Research, Redmond, WA 98052, USA (e-mail: [email protected]; Web: http://www.math.ucsd.edu/˜vanvu)
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

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

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)