Random graph process and connectivity hitting time

PDF p. 38: Section 7, second paragraph

Assume countable choice. Let $n\ge 1$ be an integer, let $V=\{1,\dots ,n\}$, and put $E=\{\{i,j\}:i,j\in V,i<j\}$ and $N=\mathrm{\mid }E\mathrm{\mid }=n(n-1)\mathrm{/}2$. A graph on $V$ has an edge set contained in $E$; it is connected if every pair of vertices is joined by a finite path of edges. An edge in $E$ that is not in the graph is called missing.

Choose an ordering $(e_1,\dots ,e_N)$ uniformly from the $N!$ orderings of $E$. The random graph process $\{G(n,m){\}}_{m=0}^N$ has vertex set $V$ and edge set $\{e_1,\dots ,e_m\}$ at time $m$, with the empty set at $m=0$. Thus, conditional on any revealed ordering of the first $m<N$ edges, the next edge is uniformly chosen from the missing edges. Its connectivity hitting time is $\tau =\min \{m\in \{0,\dots ,N\}:G(n,m)\text{ is connected}\}$.

Adjacency, degrees, graph Laplacian, and spectral notation

Uniform edge orderings, graph-process times and independent labels

The Axiom of Countable Choice (AC_ω)

Given: An integer $n\ge 1$ and the finite uniform edge ordering under countable choice.

Goal: Verify that the process and its connectivity hitting time are well defined and have the stated transition rule.

1.1 The set $E$ has one element for each pair $i<j$, so it has $N$ elements. Each prefix of an ordering is a subset of $E$ and therefore defines a graph on $V$; the prefix of length zero is empty. By the uniform-order construction, conditional on any specified prefix of length $m<N$, each of the $N-m$ missing edges is next with probability $1\mathrm{/}(N-m)$. Thus the stated transition rule holds. [F1, F2, F3, given]

2.1 At time $N$ every pair of distinct vertices is an edge, so the graph is connected: distinct vertices are joined by a one-edge path, and the one-vertex case is vacuous. Consequently the set of connected times is a nonempty subset of the finite set $\{0,\dots ,N\}$ and has a least element. This establishes $\tau$, including $\tau =0$ when $n=1$. [given, step 1.1] ∎

The process and hitting-time notation are attributed to Expander graphs are globally synchronizing, Section 7, second paragraph. The article is attribution for this formulation, not a premise of the justification.