Couple the process with independent uniform edge labels, and expose . A spanning-tree union bound excludes components of orders through , and a cut bound excludes orders up to . The graph has one large component and at most isolated vertices, with at least one isolated vertex. Before , the probability of any new edge between those isolated vertices is . All have joined the large component by by the isolated-vertex threshold in the Erdős-Rényi model. Throughout this window the only obstruction to connectivity is an isolated vertex, establishing the equality of hitting times.
Articles by others on the same topic
There are currently no matching articles.