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 -