Uniform random regular graph convention

PDF p. 7: Section 1.3, Friedman discussion; PDF p. 9: Section 1.5, Hamiltonian random regular graphs

Let $n$ be a positive integer and $d$ a nonnegative integer. Put $V=\{1,\dots ,n\}$. A simple graph on $V$ has as its edges a set of unordered pairs of distinct vertices; its degree at a vertex is the number of edges incident to that vertex. It is $d$-regular if every vertex has degree $d$. Let ${\mathcal{G}}_{n,d}$ be the set of all such graphs on the labelled vertex set $V$.

When ${\mathcal{G}}_{n,d}$ is nonempty, a uniformly random $d$-regular graph on $n$ vertices is a random element of ${\mathcal{G}}_{n,d}$ under the uniform law: each graph has probability $1\mathrm{/}\mathrm{\mid }{\mathcal{G}}_{n,d}\mathrm{\mid }$, and an event $E\subseteq {\mathcal{G}}_{n,d}$ has probability $\mathrm{\mid }E\mathrm{\mid }\mathrm{/}\mathrm{\mid }{\mathcal{G}}_{n,d}\mathrm{\mid }$. An order $n$ is feasible for $d$ when ${\mathcal{G}}_{n,d}$ is nonempty.

For fixed $d$, limits as $n\to \mathrm{\infty }$ in this model run through feasible orders. A sequence of events $E_n\subseteq {\mathcal{G}}_{n,d}$ holds with high probability if, for every $\epsilon >0$, there is an $N$ such that $\mathbb{P}(E_n)>1-\epsilon$ for every feasible $n\ge N$.

Adjacency, degrees, graph Laplacian, and spectral notation

The uniform probability space on a nonempty finite set

Asymptotic quantifiers and uniform parameter ranges

Given: A positive integer $n$ and a nonnegative integer $d$; for the probability law suppose that $n$ is feasible, and for the limit keep $d$ fixed.

Goal: Verify that the stated graph law and asymptotic convention are well defined.

1.1 There are finitely many unordered pairs of distinct vertices, so there are finitely many possible edge sets and ${\mathcal{G}}_{n,d}$ is finite. For a simple graph, each incident edge contributes exactly one to the adjacency row sum, so its degree and regularity agree with [F1]. At a feasible order the outcome set is nonempty; [F2] therefore gives the stated uniform probabilities for every event. [given, F1, F2]

2.1 For every positive integer $k$, take $k$ disjoint blocks of $d+1$ vertices and include every edge within each block and no edge between blocks. Every vertex has exactly $d$ neighbors, including when $d=0$, so $n=k(d+1)$ is feasible. Thus feasible orders are unbounded. The displayed quantifier condition is exactly convergence of the event probabilities to one along those orders, as in [F3]. This establishes the convention. [given, F3, construct, step 1.1] ∎

The article discusses uniformly chosen regular graphs and high-probability conclusions in Sections 1.3 and 1.5, and explicitly considers the limit as $n$ grows in Section 5. Its citation is attribution for that usage; the argument above uses the stated mathematical suppliers.