The connectivity threshold for dense graphs

Anupam Gupta, Euiwoong Lee, Jason Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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/λ).

Original languageEnglish (US)
Title of host publicationACM-SIAM Symposium on Discrete Algorithms, SODA 2021
EditorsDaniel Marx
PublisherAssociation for Computing Machinery
Pages89-105
Number of pages17
ISBN (Electronic)9781611976465
StatePublished - 2021
Event32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021 - Alexandria, Virtual, United States
Duration: Jan 10 2021Jan 13 2021

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Conference

Conference32nd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2021
Country/TerritoryUnited States
CityAlexandria, Virtual
Period1/10/211/13/21

ASJC Scopus subject areas

  • Software
  • General Mathematics

Fingerprint

Dive into the research topics of 'The connectivity threshold for dense graphs'. Together they form a unique fingerprint.

Cite this