Uniform edge orderings, graph-process times and independent labels

Assume countable choice. Let $n\ge 1$ be an integer, $V=\{1,\dots ,n\}$, and let $E=\{\{i,j\}:i,j\in V,i<j\}$ be the set of possible edges, with $N=\mathrm{\mid }E\mathrm{\mid }=\left(\genfrac{}{}{0px}{}{n}{2}\right)$. A graph here is the vertex set $V$ together with a subset of $E$; it is connected if each pair of vertices is joined by a finite path of edges. Give the set $\mathrm{\Omega }$ of the $N!$ orderings $(e_1,\dots ,e_N)$ of $E$ its power-set sigma-algebra and the uniform probability law. For $0\le m\le N$, define $G(n,m)$ to have edge set $\{e_1,\dots ,e_m\}$. For $0\le m\le N$, the joint prefix map $R_m:\mathrm{\Omega }\to E^m$ sends an ordering to $(e_1,\dots ,e_m)$; the finite target $E^m$ has the discrete topology and hence its full power set as its Borel sigma-algebra. For $m=0$, $E^0$ is the singleton consisting of the empty tuple. Its edge-revelation filtration is ${\mathcal{F}}_m=\sigma (R_m)=\{R_m^{-1}(B):B\subseteq E^m\}$, also written $\sigma (e_1,\dots ,e_m)$, extended by ${\mathcal{F}}_m={\mathcal{F}}_N$ for $m>N$. Define the connectivity time $\tau =\min \{m:G(n,m)\text{ is connected}\}$. A discrete stopping time is a map whose event $\{\tau \le m\}$ belongs to ${\mathcal{F}}_m$ for every $m\ge 0$.

Equivalently for the order process, assign to each edge an independent random label $U_e$ uniform on $[0,1)$ and order edges by increasing label, breaking ties using a fixed deterministic edge order. For $p\in [0,1]$, put an edge in the threshold graph $G_p$ exactly when $U_e\le p$. Here uniform means $\mathbb{P}(U_e\in [a,b))=b-a$ for $0\le a\le b\le 1$, and independence means that probabilities of simultaneous coordinate events factor. Almost surely the labels are distinct, and their ordering has the uniform law above. At each fixed $p$, the edge indicators of $G_p$ are independent with inclusion probability $p$.

For a sequence of random processes indexed by $n$, an event holds with high probability if its probability tends to one as $n\to \mathrm{\infty }$. A simultaneous assertion after connectivity means that the single event $\{G(n,m)\text{ has the property for every }m\in \{\tau ,\dots ,N\}\}$ holds with high probability. This is stronger than separate high-probability assertions at deterministic times, even when the latter are restricted to times at or after $\tau$. No monotonicity of a graph property such as synchronization is asserted by this definition.

Given: An integer $n\ge 1$, the finite edge set and the uniform permutation and label constructions in the definition, under countable choice.

Goal: Verify the laws, the coupling, the stopping-time assertion, and the stated distinction of quantifiers.

1.1 There are $N!$ edge orderings. For a fixed $m$-edge set, exactly $m!(N-m)!$ orderings put precisely that set first, so $G(n,m)$ is uniform among the $\left(\genfrac{}{}{0px}{}{N}{m}\right)$ graphs with $m$ edges. Conditional on any specified first $m<N$ edges in their revealed order, each missing edge is next in exactly $(N-m-1)!$ of the $(N-m)!$ compatible orderings. Thus it is selected with probability $1\mathrm{/}(N-m)$. For $N=0$ the unique empty ordering gives the same statements where applicable. [F1, algebra]

1.2 For $N>0$, use the $N$-fold product of normalized Lebesgue measure on $[0,1)$, indexed by $E$; for $N=0$ use the one-point probability space. Product rectangles show that the coordinate labels are independent and have the stated uniform law. A threshold event is a coordinate event of probability $p$, including the endpoints $p=0,1$; therefore all threshold indicators are independent. Strict ordering events are Borel, since they are defined by finitely many strict coordinate inequalities. [F3, F4, given]

1.3 Each $R_m$ has a finite discrete target, so ${\mathcal{F}}_m$ is a sigma-algebra of events by [F6]. Truncating a prefix of length $m+1$ to length $m$ shows that ${\mathcal{F}}_m\subseteq {\mathcal{F}}_{m+1}$. For each $m\le N$, the event that $G(n,m)$ is connected is the inverse image under $R_m$ of the set of prefixes whose edge set joins every pair of vertices by a path, and thus belongs to ${\mathcal{F}}_m$. Connectivity persists when edges are added, because every existing path remains a path. The complete graph is connected: distinct vertices have a one-edge path, and each vertex has a length-zero path to itself. Thus $\tau \le N$, including when $n=1$, and $\{\tau \le m\}$ is exactly the event that $G(n,m)$ is connected for $m\le N$; for $m>N$ it is the whole space. Hence $\tau$ is a bounded stopping time for the stated filtration. [F2, F5, F6, given]

1.4 For $n\ge 2$, a disconnected graph on $V$ has at least $n-1$ missing edges. Indeed, choose a vertex and let $S$ be the vertices reachable from it by paths. Disconnectedness makes $S$ nonempty and proper, and there is no edge from $S$ to its complement: such an edge would extend a path to a vertex outside $S$. If $s=\mathrm{\mid }S\mathrm{\mid }$, at least $s(n-s)\ge n-1$ edges are therefore missing, since $s(n-s)-(n-1)=(s-1)(n-s-1)\ge 0$. Consequently every graph with at most $n-2$ missing edges is connected. In the given process this proves $\tau \le a_n:=N-n+2$ deterministically. The set $L_n=\{a_n,\dots ,N\}$ contains $n-1$ indices, all at or after the actual connectivity time. [F5, given, algebra]

2.1 Divide $[0,1)$ into $k$ equal half-open intervals. The probability that a specified pair of distinct labels falls in the same interval is $1\mathrm{/}k$, by independence and the interval lengths. A finite union bound gives probability at most $\left(\genfrac{}{}{0px}{}{N}{2}\right)\mathrm{/}k$ that any pair shares an interval. The tie event is contained in this event for every $k$, so it has probability zero. [F3, F4, F7, step 1.2, algebra]

2.2 Write $S_n$ for the simultaneous event in the definition and $B_{n,m}=\{m<\tau \}\cup \{G(n,m)\text{ has the property}\}$ for the assertion at a deterministic index $0\le m\le N$, restricted to times at or after connectivity. Then $S_n={\bigcap }_{m=0}^N{B}_{n,m}$, so $\mathbb{P}(B_{n,m})\ge \mathbb{P}(S_n)$ for each such index, including any deterministic choice depending on $n$. Thus simultaneous high probability implies each of these deterministic-time assertions. [given, step 1.3]

3.1 On the event that all labels occupy different intervals, each ordered list of distinct interval indices has probability $k^{-N}$, and relabeling its coordinates gives equally many lists for each of the $N!$ strict edge orders. Hence the probabilities of any two strict edge orders differ by at most $\left(\genfrac{}{}{0px}{}{N}{2}\right)\mathrm{/}k$. Letting $k$ grow shows that all strict orders have equal probability. They are disjoint and, by step 2.1, their union has probability one; each therefore has probability $1\mathrm{/}N!$. The deterministic tie-breaking rule changes nothing outside a null event, establishing the coupling to the uniform permutation process. The case $N=0$ is immediate. [F1, step 1.2, step 2.1, algebra]

4.1 On the finite space $\mathrm{\Omega }\times L_n$, use the uniform law, so each pair has mass $1\mathrm{/}(N!(n-1))$. Its ordering coordinate retains the original graph-process law. For subsets $A\subseteq \mathrm{\Omega }$ and $B\subseteq L_n$, the probability of $A\times B$ is $\mathrm{\mid }A\mathrm{\mid }\mathrm{\mid }B\mathrm{\mid }\mathrm{/}(N!(n-1))$, the product of its marginal probabilities. Hence the index coordinate $J$ is uniform on $L_n$ and independent of the ordering. Define a time-indexed property to hold at $m$ exactly when $m\mathrm{\ne }J$; equivalently, sample the graph property that its edge count differs from $J$. For each deterministic index $m$, its failure probability is $\mathbb{P}(J=m)\le 1\mathrm{/}(n-1)$, which tends to zero. Since $J\ge \tau$ by step 1.4, the simultaneous post-connectivity assertion fails for every outcome, at the index $m=J$. This proves the strict quantifier distinction on the stated graph process with an independently sampled property. No monotonicity of synchronization follows from the process construction or the definitions. [F1, F3, step 2.2, step 1.4, algebra] ∎