Random regular graphs

DefinitionRegular simple graphs on a labelled vertex set#✓fully proved

For natural numbers \(n\) and \(d\), the finite set of all \(d\)-regular simple graphs on the vertex set \(\{0, \dots, n - 1\}\); the uniformly random \(d\)-regular graph on \(n\) vertices is uniform on this set. It is empty when \(nd\) is odd or \(1 \le n \le d\).

noncomputable def regularGraphs (n d : ℕ) : Finset (SimpleGraph (Fin n)) :=
  Finset.univ.filter fun G => G.IsRegularOfDegree d

Used by 1

Used byDeviation probability of the independence ratio of a random regular graph

DefinitionDeviation probability of the independence ratio of a random regular graph#✓fully proved

For natural numbers \(n\) and \(d\) and real numbers \(c\) and \(\varepsilon\), the probability that the independence ratio \(\alpha(G)/n\) of a uniformly random \(d\)-regular simple graph \(G\) on the vertex set \(\{0, \dots, n - 1\}\) differs from \(c\) by more than \(\varepsilon\), where \(\alpha(G)\) is the independence number of \(G\): the number of \(d\)-regular simple graphs \(G\) on this vertex set with \(|\alpha(G)/n - c| > \varepsilon\) divided by the number of all \(d\)-regular simple graphs on it, or \(0\) when there is no \(d\)-regular simple graph on it. For \(n = 0\) the ratio \(\alpha(G)/n\) is read as \(0\).

noncomputable def ratioDeviationProb (n d : ℕ) (c ε : ℝ) : ℝ :=
  ((regularGraphs n d).filter fun G => ε < |(G.indepNum : ℝ) / n - c|).card /
    (regularGraphs n d).card

Uses 1 · Used by 1

Statement usesRegular simple graphs on a labelled vertex set

Used byBollobás's question on the independence ratio of random regular graphs

DefinitionBollobás's question on the independence ratio of random regular graphs#✓fully proved

The statement that for every integer \(d \ge 1\) there is a real number \(c\) such that, for every \(\varepsilon > 0\), the probability that the independence ratio \(\alpha(G)/n\) of a uniformly random \(d\)-regular simple graph \(G\) on the vertex set \(\{0, \dots, n - 1\}\) differs from \(c\) by more than \(\varepsilon\) tends to \(0\) as \(n \to \infty\). Here \(\alpha(G)\) is the independence number of \(G\), the largest size of an independent set of vertices, and the probability is taken to be \(0\) for the \(n\) with no \(d\)-regular simple graph on \(n\) vertices.

The question whether this holds is due to Bollobás and is Question 18 in Abért's list of problems.

def independenceRatioConverges : Prop :=
  ∀ d : ℕ, 1 ≤ d → ∃ c : ℝ, ∀ ε : ℝ, 0 < ε →
    Tendsto (fun n : ℕ => ratioDeviationProb n d c ε) atTop (𝓝 0)

Uses 1 · Used by 1

Statement usesDeviation probability of the independence ratio of a random regular graph

Used byThe independence ratio of random regular graphs converges

TheoremThe independence ratio of random regular graphs converges#●ready to prove

For every integer \(d \ge 1\) there is a real number \(c\) such that, for every \(\varepsilon > 0\), the probability that the independence ratio \(\alpha(G)/n\) of a uniformly random \(d\)-regular simple graph \(G\) on the vertex set \(\{0, \dots, n - 1\}\) differs from \(c\) by more than \(\varepsilon\) tends to \(0\) as \(n \to \infty\). Here \(\alpha(G)\) is the independence number of \(G\), the largest size of an independent set of vertices, and the probability is taken to be \(0\) for the \(n\) with no \(d\)-regular simple graph on \(n\) vertices.

public theorem_wanted independenceRatioConverges_holds : independenceRatioConverges

Sources

• M. Abért, Some questions (2010), Question 18 (B. Bollobás), https://www.renyi.hu/~abert/questions.pdf; resolution: M. Bayati, D. Gamarnik and P. Tetali, Combinatorial approach to the interpolation method and scaling limits in sparse random graphs, Ann. Probab. 41 (2013), no. 3, 1803-1826, DOI 10.1214/12-AOP816, arXiv:0912.2444, Theorem 3: for every r and every model of §2 (independent sets included, H(G) = size of a largest independent set) there is H(r) with lim N^{-1} H(G(N, r)) = H(r) w.h.p. (N along Nr even); §1: G(N, r) is chosen uniformly from the r-regular graphs on N nodes and the result resolves the question whether |I_N|/N converges in probability; §2: results proved w.h.p. for the configuration model carry over to simple regular graphs, https://arxiv.org/abs/0912.2444.

Uses 1

Statement usesBollobás's question on the independence ratio of random regular graphs

DefinitionProportion of regular graphs with nonsingular adjacency matrix#✓fully proved

For natural numbers \(d\) and \(n\), this is the real number obtained by dividing the number of \(d\)-regular simple graphs on the vertex set \(\{0, 1, \ldots, n-1\}\) whose adjacency matrix has nonzero determinant over \(\mathbb{Q}\) by the number of all \(d\)-regular simple graphs on that vertex set; it is \(0\) when there is no \(d\)-regular simple graph on that vertex set. It is the probability that the adjacency matrix of the uniformly random \(d\)-regular graph \(G(n, d)\) is nonsingular.

Nonsingularity over \(\mathbb{Q}\) is the same as nonsingularity over \(\mathbb{R}\).

noncomputable def nonsingularFraction (d n : ℕ) : ℝ :=
  (Nat.card {G : SimpleGraph (Fin n) // G.IsRegularOfDegree d ∧ (G.adjMatrix ℚ).det ≠ 0} : ℝ) /
    Nat.card {G : SimpleGraph (Fin n) // G.IsRegularOfDegree d}

Used by 1

Used byVu's problem on nonsingular adjacency matrices of random regular graphs

DefinitionVu's problem on nonsingular adjacency matrices of random regular graphs#✓fully proved

This is the statement that for every natural number \(d \ge 3\), the probability that the adjacency matrix of the uniformly random \(d\)-regular simple graph on \(n\) labeled vertices is nonsingular tends to \(1\) as \(n \to \infty\), where \(n\) runs over the natural numbers with \(nd\) even. Here the probability is the proportion of the \(d\)-regular simple graphs on \(\{0, 1, \ldots, n-1\}\) whose adjacency matrix has nonzero determinant over \(\mathbb{Q}\).

The restriction to \(nd\) even is natural: \(d\)-regular graphs on \(n\) vertices exist only for such \(n\).

def regularGraphAdjacencyNonsingular : Prop :=
  ∀ d : ℕ, 3 ≤ d →
    Tendsto (fun n => nonsingularFraction d n) (atTop ⊓ 𝓟 {n | Even (n * d)}) (𝓝 1)

Uses 1 · Used by 1

Statement usesProportion of regular graphs with nonsingular adjacency matrix

Used byNonsingularity of adjacency matrices of random regular graphs

TheoremNonsingularity of adjacency matrices of random regular graphs#●ready to prove

For every natural number \(d \ge 3\), the probability that the adjacency matrix of the uniformly random \(d\)-regular simple graph on \(n\) labeled vertices has nonzero determinant (over \(\mathbb{Q}\), equivalently over \(\mathbb{R}\)) tends to \(1\) as \(n \to \infty\) along the natural numbers \(n\) with \(nd\) even.

Huang proved more: for every fixed \(d \ge 3\) there is \(c > 0\) such that the adjacency matrix of a random \(d\)-regular directed or undirected graph on \(n\) vertices is singular with probability at most \(n^{-c}\) for all large \(n\), in the configuration model and, by contiguity, in the uniform model.

public theorem_wanted regularGraphAdjacencyNonsingular_holds : regularGraphAdjacencyNonsingular

Sources

• V. Vu, problem (1) of the problem session, in Combinatorics, Oberwolfach Reports 11 (2014), Report 01/2014, pp. 84-85, DOI 10.4171/OWR/2014/01; resolution: J. Huang, Invertibility of adjacency matrices for random d-regular graphs, Duke Math. J. 170 (2021), no. 18, 3977-4032, DOI 10.1215/00127094-2021-0006, arXiv:1807.06465, Theorem 1.3: for fixed d ≥ 3, P(A is singular in R) ≤ n^(-c) for n sufficiently large (directed and undirected d-regular graphs); Section 1.1: by a contiguity argument the results hold for the uniform model, https://arxiv.org/abs/1807.06465.

Uses 1

Statement usesVu's problem on nonsingular adjacency matrices of random regular graphs

5 fully proved2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.