TY - GEN

T1 - The connectivity threshold for dense graphs

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
Copyright © 2021 by SIAM

PY - 2021

Y1 - 2021

N2 - Consider a random graph model where there is an underlying simple graph G = (V, E), and each edge is sampled independently with probability p ∈ [0, 1]. What is the smallest value of p such that the resulting graph Gp is connected with constant probability? This is a well-studied question for special classes of graphs, such as complete graphs and hypercubes. For instance, when G is the complete graph, we want the connectivity threshold for the Erdős-Rényi G(n, p) model: here the answer is known to be ln n±O(1). However, n the problem is not well-understood for more general graph classes. We first investigate this connectivity threshold problem for “somewhat dense” graphs. We show that for any δ ≥ Oe(√n) and any δ-regular, δ-edge-connected graph G, the random graph Gp for p = ln n+c is connected with δ probability e−e−c ± o(1), generalizing upon the case when G is the complete graph. Our proof also bounds the number of approximate mincuts in such a dense graph, which may be of independent interest. Next, for a general graph G with edge connectivity λ, we define an explicit parameter βG ∈ (0, 2 ln n], based on the number of approximate mincuts, and show that there is a sharp transition in the connectivity of G at p = 1 − exp(βG/λ). Moreover, we show that the width of this transition is an additive O(ln λ/λ) term; this improves upon Margulis' classical result bounding the width of the threshold by O(1/√λ).

AB - Consider a random graph model where there is an underlying simple graph G = (V, E), and each edge is sampled independently with probability p ∈ [0, 1]. What is the smallest value of p such that the resulting graph Gp is connected with constant probability? This is a well-studied question for special classes of graphs, such as complete graphs and hypercubes. For instance, when G is the complete graph, we want the connectivity threshold for the Erdős-Rényi G(n, p) model: here the answer is known to be ln n±O(1). However, n the problem is not well-understood for more general graph classes. We first investigate this connectivity threshold problem for “somewhat dense” graphs. We show that for any δ ≥ Oe(√n) and any δ-regular, δ-edge-connected graph G, the random graph Gp for p = ln n+c is connected with δ probability e−e−c ± o(1), generalizing upon the case when G is the complete graph. Our proof also bounds the number of approximate mincuts in such a dense graph, which may be of independent interest. Next, for a general graph G with edge connectivity λ, we define an explicit parameter βG ∈ (0, 2 ln n], based on the number of approximate mincuts, and show that there is a sharp transition in the connectivity of G at p = 1 − exp(βG/λ). Moreover, we show that the width of this transition is an additive O(ln λ/λ) term; this improves upon Margulis' classical result bounding the width of the threshold by O(1/√λ).

UR - http://www.scopus.com/inward/record.url?scp=85105340501&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85105340501&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:85105340501

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 89

EP - 105

BT - ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

A2 - Marx, Daniel

PB - Association for Computing Machinery

T2 - 32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021

Y2 - 10 January 2021 through 13 January 2021

ER -