Introduction
Motivation from random matrix theory
Consider a sequence of possibly random matrices A ∈ M n ( C ) A \in M_n(\mathbb{C}) A ∈ M n ( C ) of growing dimension n → ∞ n \to\infty n → ∞ . In many situations, we are interested in the asymptotics as n → ∞ n \to\infty n → ∞ of the spectral radius of A A A defined as
ϱ ( A ) = max { ∣ λ ∣ : λ ∈ σ ( A ) } . \varrho(A) = \max\{|\lambda| : \lambda\in\sigma(A)\}. ϱ ( A ) = max { ∣ λ ∣ : λ ∈ σ ( A )} .
The spectral radius is upper bounded by the operator norm:
ϱ ( A ) ≤ ∥ A ∥ o p = sup x ≠ 0 ∥ A x ∥ 2 ∥ x ∥ 2 . \varrho(A) \le\lVert A\rVert_{\mathrm{op}} = \sup_{x \ne0} \frac{\lVert Ax\rVert_2}{\lVert x\rVert_2}. ϱ ( A ) ≤ ∥ A ∥ op = x = 0 sup ∥ x ∥ 2 ∥ A x ∥ 2 .
In particular, for any integer k ≥ 1 k \ge1 k ≥ 1 , we have ϱ ( A ) k = ϱ ( A k ) ≤ ∥ A k ∥ o p \varrho(A)^k = \varrho(A^k) \le\lVert A^k\rVert_{\mathrm{op}} ϱ ( A ) k = ϱ ( A k ) ≤ ∥ A k ∥ op . Gelfand’s theorem asserts that this upper bound is asymptotically sharp in the sense that
ϱ ( A ) = lim k → ∞ ∥ A k ∥ o p 1 / k . \varrho(A) = \lim_{k \to\infty} \lVert A^k\rVert_{\mathrm{op}}^{1/k}. ϱ ( A ) = k → ∞ lim ∥ A k ∥ op 1/ k .
This limit is, however, not uniform over the dimension n n n , and this formula may not be very useful in high dimensions.
The trace method is a classical general strategy to upper bound the spectral radius of random matrices; see the monographs [1 , 2 , 38 ] . A foundational application to the extreme eigenvalues of symmetric random matrices is due to Füredi and Komlós [21 ] . It starts with the following chain of inequalities:
ϱ ( A ) 2 k = ϱ ( A k ) 2 ≤ ∥ A k ∥ o p 2 = ∥ A k ( A k ) ∗ ∥ o p ≤ tr ( A k ( A k ) ∗ ) . \varrho(A)^{2k} = \varrho(A^k)^2 \le\lVert A^k\rVert_{\mathrm{op}}^2 = \lVert A^k(A^k)^*\rVert_{\mathrm{op}} \le\operatorname{tr}\left(A^k(A^k)^*\right). ϱ ( A ) 2 k = ϱ ( A k ) 2 ≤ ∥ A k ∥ op 2 = ∥ A k ( A k ) ∗ ∥ op ≤ tr ( A k ( A k ) ∗ ) .
Then, we may expand the trace as a sum of products of matrix entries and, for many sequences of random matrices A A A , we may derive a probabilistic upper bound on the growth rate of trace powers of the form: tr ( A k ( A k ) ∗ ) ≤ n ( 1 + ϵ k ) 2 k ρ + 2 k \operatorname{tr}\left(A^k(A^k)^*\right) \le n(1+\epsilon_k)^{2k}\rho_+^{2k} tr ( A k ( A k ) ∗ ) ≤ n ( 1 + ϵ k ) 2 k ρ + 2 k for some ρ + > 0 \rho_+ > 0 ρ + > 0 and where ϵ k \epsilon_k ϵ k goes to 0 0 0 as k → ∞ k \to\infty k → ∞ . Therefore, we find that ϱ ( A ) ≤ n 1 / 2 k ( 1 + ϵ k ) ρ + \varrho(A) \le n^{1/2k}(1+\epsilon_k)\rho_+ ϱ ( A ) ≤ n 1/2 k ( 1 + ϵ k ) ρ + . If this holds for k ≫ log n k \gg\log n k ≫ log n , we then deduce that ϱ ( A ) ≤ ( 1 + O ( max ( ϵ k , log n / k ) ) ) ρ + \varrho(A) \le(1+O(\max(\epsilon_k,\log n/k)))\rho_+ ϱ ( A ) ≤ ( 1 + O ( max ( ϵ k , log n / k ))) ρ + .
For example, if A = X / n A = X/\sqrt{n} A = X / n with ( X i j ) (X_{ij}) ( X ij ) independent, centered, variance 1 1 1 and uniformly bounded support, it follows from Geman [23 ] , one of the earliest appearances of this method, that for some c 1 > 0 c_1 > 0 c 1 > 0 , E tr ( A k ( A k ) ∗ ) ≤ n k c 1 \mathbb{E}\operatorname{tr}(A^k(A^k)^*) \le n k^{c_1} E tr ( A k ( A k ) ∗ ) ≤ n k c 1 for k ≤ n 1 / c 1 k \le n^{1/c_1} k ≤ n 1/ c 1 , leading to ϱ ( A ) ≤ 1 + O ( n − c 2 ) \varrho(A) \le1 + O(n^{-c_2}) ϱ ( A ) ≤ 1 + O ( n − c 2 ) with high probability for some c 2 > 0 c_2 > 0 c 2 > 0 . Since then, there have been numerous improvements and further examples of such successful computations in random matrix theory; see, for example [37 , 40 , 3 , 5 ] . If A A A is a normal matrix (that is if A A ∗ = A ∗ A AA^* = A^*A A A ∗ = A ∗ A ), then the same strategy gives also a lower bound. Indeed, for normal matrices, we have ρ ( A ) = ∥ A ∥ o p \rho(A) = \|A\|_{\mathrm{op}} ρ ( A ) = ∥ A ∥ op and thus
ρ ( A ) 2 k = ∥ ( A A ∗ ) k ∥ o p ≥ 1 n tr ( ( A A ∗ ) k ) . \rho(A)^{2k} = \|(AA^*)^k\|_{\mathrm{op}} \ge\frac{1}{n}\operatorname{tr}\left((AA^*)^k\right). ρ ( A ) 2 k = ∥ ( A A ∗ ) k ∥ op ≥ n 1 tr ( ( A A ∗ ) k ) .
In particular, any lower bound of the form tr ( ( A A ∗ ) k ) ≥ n ( 1 − ϵ k ) 2 k ρ − 2 k \operatorname{tr}\left((AA^*)^k\right) \ge n(1-\epsilon_k)^{2k}\rho_-^{2k} tr ( ( A A ∗ ) k ) ≥ n ( 1 − ϵ k ) 2 k ρ − 2 k now gives ρ ( A ) ≥ ( 1 − ϵ k ) ρ − \rho(A) \ge(1-\epsilon_k)\rho_- ρ ( A ) ≥ ( 1 − ϵ k ) ρ − . Note that for the lower bound, there is no need to let k → ∞ k \to\infty k → ∞ jointly with n → ∞ n \to\infty n → ∞ . If ρ + = ρ − \rho_+ = \rho_- ρ + = ρ − , then we have obtained an asymptotic equivalent to ρ ( A ) \rho(A) ρ ( A ) with a controlled error.
In the non-normal case, however, it is not straightforward to extend this strategy to get a lower bound. The usual route takes the following detour. We first prove that the empirical distribution of the eigenvalues of A A A converges weakly to a compactly supported measure μ \mu μ on C \mathbb{C} C . Then, we observe that it implies that lim inf n → ∞ ρ ( A ) ≥ ρ − \liminf_{n\to\infty}\rho(A) \ge\rho_- lim inf n → ∞ ρ ( A ) ≥ ρ − with ρ − = sup { ∣ λ ∣ : λ ∈ supp ( μ ) } \rho_- = \sup\{|\lambda| : \lambda\in\operatorname{supp}(\mu)\} ρ − = sup { ∣ λ ∣ : λ ∈ supp ( μ )} .
For example, if A = X / n A = X/\sqrt{n} A = X / n with ( X i j ) (X_{ij}) ( X ij ) iid centered entries of variance 1 1 1 , then, in probability, the empirical distribution of eigenvalues converges weakly to the uniform measure on the unit disc; see [8 ] for a survey. Together with the upper bound ρ ( A ) ≤ 1 + o ( 1 ) \rho(A) \le1 + o(1) ρ ( A ) ≤ 1 + o ( 1 ) from [9 ] , we thus get in probability, lim n ρ ( A ) = 1 \lim_{n}\rho(A) = 1 lim n ρ ( A ) = 1 in this case.
Proving the weak convergence of the empirical distribution of eigenvalues is usually not an easy task, and one might wonder if a more direct and quantitative approach exists. One goal of this work is to illustrate one such possible approach. It still relies on the trace powers, but now it exploits its trace fluctuations for large powers . More precisely, we write:
ρ ( A ) ≥ 1 n ∑ i = 1 n ∣ λ i ( A ) ∣ ≥ ∣ 1 n ∑ i = 1 n λ i ( A ) ∣ = ∣ 1 n tr ( A ) ∣ . \rho(A) \ge\frac{1}{n}\sum_{i=1}^{n}|\lambda_i(A)| \ge\left|\frac{1}{n}\sum_{i=1}^{n}\lambda_i(A)\right| = \left|\frac{1}{n}\operatorname{tr}(A)\right|. ρ ( A ) ≥ n 1 i = 1 ∑ n ∣ λ i ( A ) ∣ ≥ n 1 i = 1 ∑ n λ i ( A ) = n 1 tr ( A ) .
Hence for any integer k ≥ 1 k \ge1 k ≥ 1 ,
ρ ( A ) ≥ ∣ 1 n tr ( A k ) ∣ 1 / k . (1) \rho(A) \ge\left|\frac{1}{n}\operatorname{tr}(A^k)\right|^{1/k}. \tag*{(1)} ρ ( A ) ≥ n 1 tr ( A k ) 1/ k . (1)
For fixed k k k , at first order in n n n , this lower bound may be crude. For example, if ρ ( A ) = O ( 1 ) \rho(A) = O(1) ρ ( A ) = O ( 1 ) and if the empirical distribution of eigenvalues of A A A converges to a radial measure μ \mu μ on C \mathbb{C} C then for any integer k ≥ 1 k \ge1 k ≥ 1 ,
lim n → ∞ 1 n tr ( A k ) = ∫ C λ k d μ ( λ ) = 0. \lim_{n\to\infty}\frac{1}{n}\operatorname{tr}(A^k) = \int_{\mathbb{C}}\lambda^k\,\mathrm{d}\mu(\lambda) = 0. n → ∞ lim n 1 tr ( A k ) = ∫ C λ k d μ ( λ ) = 0.
As we discussed above, this case notably happens if A = X / n A = X/\sqrt{n} A = X / n with ( X i j ) (X_{ij}) ( X ij ) i.i.d. centered entries of variance 1 1 1 . On the other hand, for this random matrix, under a proper moment condition on X i j X_{ij} X ij , for any fixed k ≥ 1 k \ge1 k ≥ 1 , it is well-known [35 , 32 ] that, as n → ∞ n \to\infty n → ∞ ,
tr ( A k ) k ⟹ Z , \frac{\operatorname{tr}(A^k)}{\sqrt{k}} \Longrightarrow Z, k tr ( A k ) ⟹ Z ,
where Z Z Z is a Gaussian variable of unit variance. Moreover, central limit theorems for linear eigenvalue statistics have been established for analytic test functions in real elliptic ensembles [33 ] , and for sufficiently smooth test functions in non-Hermitian matrices with i.i.d. entries [13 , 12 ] .
More quantitatively, for any random matrix model A A A , assume that we can prove that weakly, along a sequence k = k n k = k_n k = k n with k ≫ log n k \gg\log n k ≫ log n ,
tr ( A k ) ( 1 + ϵ k ) k ρ − k ⟹ Z , \frac{\operatorname{tr}(A^k)}{(1+\epsilon_k)^k\rho_-^k} \Longrightarrow Z, ( 1 + ϵ k ) k ρ − k tr ( A k ) ⟹ Z ,
where ρ − > 0 \rho_- > 0 ρ − > 0 and Z Z Z is a random variable such that P ( Z = 0 ) = 0 \mathbb{P}(Z=0)=0 P ( Z = 0 ) = 0 . Then, ∣ Z ∣ 1 / k ≥ 1 − O ( log n / k ) |Z|^{1/k} \ge1 - O(\log n/k) ∣ Z ∣ 1/ k ≥ 1 − O ( log n / k ) with high probability. We thus get from (1) that, with high probability,
ρ ( A ) ≥ ( 1 + ϵ k ) ( 1 − O ( log n k ) ) ρ − . \rho(A) \ge(1+\epsilon_k)\left(1-O\left(\frac{\log n}{k}\right)\right)\rho_-. ρ ( A ) ≥ ( 1 + ϵ k ) ( 1 − O ( k log n ) ) ρ − .
Therefore, the fluctuations of trace powers provide a lower bound on the spectral radius. To our knowledge, this strategy has not been used so far. In the present work, we follow this strategy for the study of the spectral gap of the simple random walk on a random directed graph sampled according to the configuration model, which we define below.
Model and motivation from spectral theory of Markov chains
For integer n ≥ 1 n \ge1 n ≥ 1 , prescribe non-negative integers ( d i + , d i − ) i = 1 n (d_i^+,d_i^-)_{i=1}^n ( d i + , d i − ) i = 1 n such that
∑ i d i + = ∑ i d i − = N . \sum_i d_i^+ = \sum_i d_i^- = N. i ∑ d i + = i ∑ d i − = N .
If N ≥ 1 N \ge1 N ≥ 1 , we consider a random directed multigraph G G G on [ n ] [n] [ n ] sampled from the configuration model. It is defined as follows. Attach d i + d_i^+ d i + outgoing half-edges, called heads , and d i − d_i^- d i − incoming half-edges, called tails , to vertex i i i . Write E + ( i ) E^+(i) E + ( i ) and E − ( i ) E^-(i) E − ( i ) for these two sets, and use bold letters e \mathbf{e} e and f \mathbf{f} f for heads and tails, respectively. The unions
E + = ⨆ i = 1 n E + ( i ) , E − = ⨆ i = 1 n E − ( i ) E^+ = \bigsqcup_{i=1}^n E^+(i), \qquad E^- = \bigsqcup_{i=1}^n E^-(i) E + = i = 1 ⨆ n E + ( i ) , E − = i = 1 ⨆ n E − ( i )
both have cardinality N N N . Choose arbitrary labels [ N ] [N] [ N ] for each of E + E^+ E + and E − E^- E − , sample a uniform permutation σ ∈ S N \sigma\in S_N σ ∈ S N , and let σ : E + → E − \sigma:E^+ \to E^- σ : E + → E − also denote the induced bijection: the head with label a a a is matched to the tail with label σ ( a ) \sigma(a) σ ( a ) . In other words, σ : E + → E − \sigma:E^+ \to E^- σ : E + → E − is a uniform bijection. If e ∈ E + ( i ) \mathbf{e} \in E^+(i) e ∈ E + ( i ) and σ ( e ) ∈ E − ( j ) \sigma(\mathbf{e}) \in E^-(j) σ ( e ) ∈ E − ( j ) , we place one directed edge i → j i \to j i → j .
Write G G G for the resulting directed configuration multigraph; loops and parallel edges are allowed. Assuming min i d i + ≥ 1 \min_i d_i^+ \ge1 min i d i + ≥ 1 , for i , j ∈ [ n ] i,j \in[n] i , j ∈ [ n ] , the ( i , j ) (i,j) ( i , j ) -entry of the transition probability matrix of G G G is
P ( i , j ) = # { e ∈ E + ( i ) : σ ( e ) ∈ E − ( j ) } d i + . (2) P(i,j) = \frac{\#\{\mathbf{e} \in E^+(i):\sigma(\mathbf{e}) \in E^-(j)\}}{d_i^+}. \tag*{(2)} P ( i , j ) = d i + # { e ∈ E + ( i ) : σ ( e ) ∈ E − ( j )} . (2)
We order the eigenvalues of P P P by modulus, including multiplicity:
λ 1 = 1 , ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣ . \lambda_1 = 1, \qquad|\lambda_2| \ge\cdots\ge|\lambda_n|. λ 1 = 1 , ∣ λ 2 ∣ ≥ ⋯ ≥ ∣ λ n ∣.
The matrix P P P is the Markov transition kernel of the simple random walk on G G G . It is non-reversible on a directed graph. The spectral gap of P P P is 1 − ∣ λ 2 ∣ 1-|\lambda_2| 1 − ∣ λ 2 ∣ . It measures the asymptotic mixing rate to equilibrium; we refer to [31 , 27 ] . For example, if P P P is aperiodic and irreducible, it admits a unique invariant probability measure π \pi π and then, for any probability measure μ \mu μ on [ n ] [n] [ n ] ,
lim t → ∞ ∥ μ P t − π ∥ T V 1 / t ≤ ∣ λ 2 ∣ , \lim_{t \to\infty} \lVert\mu P^t-\pi\rVert_{\mathrm{TV}}^{1/t} \le|\lambda_2|, t → ∞ lim ∥ μ P t − π ∥ TV 1/ t ≤ ∣ λ 2 ∣ ,
where for a signed measure ν \nu ν , its total variation is ∥ ν ∥ T V = ( 1 / 2 ) ⋅ ∑ i ∣ ν ( i ) ∣ \lVert\nu\rVert_{\mathrm{TV}}=(1/2)\cdot\sum_i|\nu(i)| ∥ ν ∥ TV = ( 1/2 ) ⋅ ∑ i ∣ ν ( i ) ∣ . The invariant measure π \pi π of P P P defined in (2) and its mixing time were studied in [7 ] . The study of the spectrum of P P P was initiated by Coste [15 ] , where an upper bound on ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ was computed using the trace method outlined above. In this work, we prove a matching lower bound for ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ ; see Remark 1.2 below.
Main results
Define
Δ = max i { d i + , d i − } , δ = min i d i + and ρ = 1 N ∑ i = 1 n d i − d i + . \Delta= \max_i\{d_i^+,d_i^-\}, \qquad\delta= \min_i d_i^+ \qquad\text{and}\qquad\rho= \sqrt{\frac{1}{N}\sum_{i=1}^n\frac{d_i^-}{d_i^+}}. Δ = i max { d i + , d i − } , δ = i min d i + and ρ = N 1 i = 1 ∑ n d i + d i − .
We assume that for all sufficiently large integers n n n ,
δ ≥ 2 and δ ρ ≥ 1. (3) \delta\ge2 \qquad\text{and}\qquad\delta\rho\ge1. \tag*{(3)} δ ≥ 2 and δ ρ ≥ 1. (3)
The condition δ ρ ≥ 1 \delta\rho\ge1 δ ρ ≥ 1 is satisfied when the out-degree sequence is concentrated. For example, since ρ ≥ 1 / Δ \rho\ge1/\sqrt{\Delta} ρ ≥ 1/ Δ , the condition δ ρ ≥ 1 \delta\rho\ge1 δ ρ ≥ 1 is implied by the assumption δ 2 ≥ Δ \delta^2 \ge\Delta δ 2 ≥ Δ . Similarly, let κ = min i d i − / d i + ∈ [ 0 , 1 ] \kappa= \min_i d_i^- / d_i^+ \in[0,1] κ = min i d i − / d i + ∈ [ 0 , 1 ] and d = N / n d = N/n d = N / n be the average in/out-degree. Then ρ ≥ κ / d \rho\ge\sqrt{\kappa/d} ρ ≥ κ / d and the condition δ ρ ≥ 1 \delta\rho\ge1 δ ρ ≥ 1 is implied by the assumption κ δ 2 ≥ d \kappa\delta^2 \ge d κ δ 2 ≥ d .
We finally consider another parameter of the degree sequence. Set
β 3 = 1 N ∑ i = 1 n d i − ( d i + ) 2 \beta_3 = \frac{1}{N}\sum_{i=1}^{n}\frac{d_i^-}{(d_i^+)^2} β 3 = N 1 i = 1 ∑ n ( d i + ) 2 d i −
and consider some θ ≥ 0 \theta\ge0 θ ≥ 0 such that
β 3 ≤ e − θ ρ 3 (4) \beta_3 \le e^{-\theta}\rho^3 \tag*{(4)} β 3 ≤ e − θ ρ 3 (4)
Indeed, if (3) holds, then 1 / d i + ≤ 1 / δ ≤ ρ 1/d_i^+ \le1/\delta\le\rho 1/ d i + ≤ 1/ δ ≤ ρ and thus (4) holds for θ = 0 \theta= 0 θ = 0 . More is true: we will show in Lemma 2.11 that θ = ( δ − δ ) / Δ > 0 \theta= (\delta-\sqrt{\delta})/\Delta> 0 θ = ( δ − δ ) /Δ > 0 always satisfies (4) . If G G G is out-degree regular, that is if d i + = d d_i^+ = d d i + = d for all i i i , then ρ = 1 / d \rho= 1/\sqrt{d} ρ = 1/ d , β 3 = 1 / d 2 \beta_3 = 1/d^2 β 3 = 1/ d 2 and thus we may take θ = ( log d ) / 2 \theta= (\log d)/2 θ = ( log d ) /2 .
We prove the following lower bound on the second eigenvalue of P P P provided that θ \theta θ in (4) is not too small and that Δ \Delta Δ is not too large.
Theorem 1.1. Assume (3) –(4) with log Δ = o ( log n log log n ) \log\Delta= o\left(\frac{\log n}{\log\log n}\right) log Δ = o ( l o g l o g n l o g n ) and θ ≥ log Δ / ( log n ) 1 + o ( 1 ) \theta\ge\sqrt{\log\Delta}/(\log n)^{1+o(1)} θ ≥ log Δ / ( log n ) 1 + o ( 1 ) . We have
P { ∣ λ 2 ∣ ≥ ( 1 − ε n ) ρ } ⟶ 1 , (5) \mathbb{P}\{|\lambda_2| \ge(1-\varepsilon_n)\rho\} \longrightarrow1, \tag*{(5)} P { ∣ λ 2 ∣ ≥ ( 1 − ε n ) ρ } ⟶ 1 , (5) for any sequence ε n → 0 \varepsilon_n \to0 ε n → 0 such that
ε n ≫ log Δ ⋅ log log n log n . (6) \varepsilon_n \gg\log\Delta\cdot\frac{\log\log n}{\log n}. \tag*{(6)} ε n ≫ log Δ ⋅ log n log log n . (6)
As pointed out below (4) , since θ ≥ ( 2 − 2 ) / Δ \theta\ge(2-\sqrt{2})/\Delta θ ≥ ( 2 − 2 ) /Δ in the worst case, the condition on θ \theta θ in Theorem 1.1 is automatically satisfied if Δ ≤ ( log n ) 1 + o ( 1 ) \Delta\le(\log n)^{1+o(1)} Δ ≤ ( log n ) 1 + o ( 1 ) and (3) holds.
Remark 1.2 (A matching upper bound). When Δ = O ( 1 ) \Delta= O(1) Δ = O ( 1 ) , Coste [15 ] proves that, with high probability, ∣ λ 2 ∣ ≤ max { ρ , 1 / δ } + o ( 1 ) |\lambda_2| \le\max\{\rho,1/\delta\}+o(1) ∣ λ 2 ∣ ≤ max { ρ , 1/ δ } + o ( 1 ) , where δ = min { d i + , d i − : i ∈ [ n ] } \delta= \min\{d_i^+,d_i^-:i\in[n]\} δ = min { d i + , d i − : i ∈ [ n ]} . A close inspection of the proof in [15 ] shows that δ \delta δ can be replaced by the minimum out-degree δ \delta δ . The same argument therefore yields the sharper bound ∣ λ 2 ∣ ≤ max { ρ , 1 / δ } + o ( 1 ) |\lambda_2| \le\max\{\rho,1/\delta\}+o(1) ∣ λ 2 ∣ ≤ max { ρ , 1/ δ } + o ( 1 ) . Under assumption (3) , this upper bound reduces to ρ + o ( 1 ) \rho+o(1) ρ + o ( 1 ) and matches our lower bound.
As explained above, we prove Theorem 1.1 by establishing the following central limit theorem for the traces of powers of P P P . This is our main technical contribution.
Theorem 1.3. Assume (3) –(4) with Δ = n o ( 1 ) \Delta= n^{o(1)} Δ = n o ( 1 ) and some θ > 0 \theta> 0 θ > 0 . Let t = t n t=t_n t = t n be an integer sequence such that
1 ≪ t ≪ ( log n ) 2 log ( Δ ) log log n and θ − 2 + o ( 1 ) ≤ t . (7) 1 \ll t \ll\frac{(\log n)^2}{\log(\Delta)\log\log n}
\qquad\text{and}\qquad
\theta^{-2+o(1)} \le t. \tag*{(7)} 1 ≪ t ≪ log ( Δ ) log log n ( log n ) 2 and θ − 2 + o ( 1 ) ≤ t . (7) Then, we have
tr P t − 1 t ρ t ⟹ N ( 0 , 1 ) . \frac{\operatorname{tr} P^t-1}{\sqrt{t}\rho^t} \Longrightarrow\mathcal{N}(0,1). t ρ t tr P t − 1 ⟹ N ( 0 , 1 ) .
Proof of Theorem 1.1 with Theorem 1.3. Since the conclusion becomes stronger when ε n \varepsilon_n ε n is decreased, we may assume without loss of generality that
ε n ≤ log Δ ( log log n ) 2 log n . (8) \varepsilon_n \le\frac{\log\Delta(\log\log n)^2}{\log n}. \tag*{(8)} ε n ≤ log n log Δ ( log log n ) 2 . (8)
The trace identity gives
∣ tr P t − 1 ∣ = ∣ ∑ i = 2 n λ i t ∣ ≤ ( n − 1 ) ∣ λ 2 ∣ t . |\operatorname{tr} P^t-1| = \left|\sum_{i=2}^{n}\lambda_i^t\right| \le(n-1)|\lambda_2|^t. ∣ tr P t − 1∣ = i = 2 ∑ n λ i t ≤ ( n − 1 ) ∣ λ 2 ∣ t .
Take t = ⌊ 2 ( log n ) / ε n ⌋ t=\lfloor2(\log n)/\varepsilon_n\rfloor t = ⌊ 2 ( log n ) / ε n ⌋ where ε n \varepsilon_n ε n satisfies (6) , (8) , and ε n = o ( 1 ) \varepsilon_n=o(1) ε n = o ( 1 ) . Then the two conditions in (7) hold. Also, we have, for sufficiently large n n n ,
ε n t ≥ log n . \varepsilon_n t \ge\log n. ε n t ≥ log n .
Hence, for sufficiently large n n n , ( 1 − ε n ) t ≤ e − ε n t ≤ n − 1 (1-\varepsilon_n)^t \le e^{-\varepsilon_n t} \le n^{-1} ( 1 − ε n ) t ≤ e − ε n t ≤ n − 1 . Therefore
P ( ∣ λ 2 ∣ ≤ ( 1 − ε n ) ρ ) ≤ P ( ∣ tr P t − 1 ∣ t ρ t ≤ n − 1 t ( 1 − ε n ) t ) ≤ P ( ∣ tr P t − 1 ∣ t ρ t ≤ 1 t ) ≤ P ( ∣ tr P t − 1 ∣ t ρ t ≤ ε ) \begin{aligned}
\mathbb{P}(|\lambda_2| \le(1-\varepsilon_n)\rho) \le\mathbb{P}\left(\frac{|\operatorname{tr} P^t-1|}{\sqrt{t\rho^t}} \le\frac{n-1}{\sqrt{t}}(1-\varepsilon_n)^t\right) \\
&\le\mathbb{P}\left(\frac{|\operatorname{tr} P^t-1|}{\sqrt{t\rho^t}} \le\frac{1}{\sqrt{t}}\right) \le\mathbb{P}\left(\frac{|\operatorname{tr} P^t-1|}{\sqrt{t\rho^t}} \le\varepsilon\right)
\end{aligned} P ( ∣ λ 2 ∣ ≤ ( 1 − ε n ) ρ ) ≤ P ( t ρ t ∣ tr P t − 1∣ ≤ t n − 1 ( 1 − ε n ) t ) ≤ P ( t ρ t ∣ tr P t − 1∣ ≤ t 1 ) ≤ P ( t ρ t ∣ tr P t − 1∣ ≤ ε )
for any ε > 0 \varepsilon>0 ε > 0 when n n n is sufficiently large. For every fixed ε > 0 \varepsilon>0 ε > 0 , Theorem 1.3 therefore gives
lim sup n → ∞ P { ∣ λ 2 ∣ ≤ ( 1 − ε n ) ρ } ≤ P { ∣ Z ∣ ≤ ε } , Z ∼ N ( 0 , 1 ) . \limsup_{n\to\infty}\mathbb{P}\{|\lambda_2| \le(1-\varepsilon_n)\rho\} \le\mathbb{P}\{|Z| \le\varepsilon\}, \qquad Z\sim\mathcal{N}(0,1). n → ∞ lim sup P { ∣ λ 2 ∣ ≤ ( 1 − ε n ) ρ } ≤ P { ∣ Z ∣ ≤ ε } , Z ∼ N ( 0 , 1 ) .
Letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 , and using that the Gaussian distribution has no atom at zero, we prove (5) . □
Central limit theorems for traces and cycle counts at lengths up to the diameter scale log d − 1 ( n ) \log_{d-1}(n) log d − 1 ( n ) have been established for random d d d -regular graphs and digraphs in [19 , 26 , 16 ] , using Poisson approximations of cycle counts and Gaussian limits for Poisson random variables with diverging means. Beyond the graph diameter scale, Garmo [22 ] obtained weighted Poisson limits for normalized cycle count fluctuations in fixed-degree random regular graphs. Theorem 1.3 holds with t ≫ log Δ n t\gg\log_{\Delta} n t ≫ log Δ n , beyond the range covered by previous results. As we can see in the proof above, reaching this scale is essential for obtaining the sharp spectral lower bound via (1) .
Proof overview
A natural approach to proving Theorem 1.3 is by the moment method. However, as in the proofs of Alon’s second eigenvalue conjecture [20 , 6 ] , tangles (see Definition 2.3) can dominate the moments when t ≫ log n t\gg\log n t ≫ log n . To illustrate this obstruction, consider the directed configuration model with d i + = d i − = d d_i^+=d_i^-=d d i + = d i − = d for a fixed d ≥ 2 d\ge2 d ≥ 2 , so that ρ = d − 1 / 2 \rho=d^{-1/2} ρ = d − 1/2 . Let Ω \Omega Ω be the event that vertices 1, 2 are each isolated with d d d self-loops. Counting matchings gives for some constant C d C_d C d depending only on d d d ,
P ( Ω ) = ( d ! ) 2 ( n d − 2 d ) ! ( n d ) ! ≥ C d n − 2 d . \mathbb{P}(\Omega)=(d!)^2\frac{(nd-2d)!}{(nd)!}\ge C_dn^{-2d}. P ( Ω ) = ( d ! ) 2 ( n d )! ( n d − 2 d )! ≥ C d n − 2 d .
On Ω \Omega Ω , we have tr P t ≥ 2 \operatorname{tr}P^t\ge2 tr P t ≥ 2 and when t ≫ log n t\gg\log n t ≫ log n ,
E ( tr P t − 1 t ρ t ) 2 ≥ d t t P ( Ω ) ≥ C d d t t n 2 d → ∞ . \mathbb{E}\left(\frac{\operatorname{tr}P^t-1}{\sqrt{t\rho^t}}\right)^2\ge\frac{d^t}{t}\mathbb{P}(\Omega)\ge C_d\frac{d^t}{tn^{2d}}\to\infty. E ( t ρ t tr P t − 1 ) 2 ≥ t d t P ( Ω ) ≥ C d t n 2 d d t → ∞.
Thus, when t ≫ log n t\gg\log n t ≫ log n in Theorem 1.3, the normalized trace converges in distribution to a standard Gaussian, even though its second moment diverges. The isolated vertices with d d d self-loops are examples of the tangles creating this issue.
To overcome this obstruction, we use the tangle-free path decomposition of [6 , 15 ] and apply the moment method to a modified trace. Pairs of traces following the same directed cycle of length t t t give the Gaussian moments, while all other paths have relatively negligible total contribution. On a high-probability tangle-free event, the modified trace agrees with tr P t − 1 \operatorname{tr}P^t-1 tr P t − 1 up to a negligible scalar correction after normalization. This transfers the Gaussian limit to the original trace and completes the proof.
Obstruction to lower bounds on ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣
As stressed above, the Markov chain P P P is non-reversible, which in linear algebra terms means that P ≠ P ∗ P\ne P^* P = P ∗ where the adjoint is taken with respect to the invariant measure. A consequence of non-reversibility is that there are no known simple lower bounds on ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ ; see [30 ] for relations between graph expansion and spectral gap.
The failure of a deterministic Alon-Boppana bound for d d d -regular digraphs is illustrated by the de Bruijn digraphs. For integer s ≥ 1 s\ge1 s ≥ 1 , the digraph D B ( d , s ) DB(d,s) D B ( d , s ) has vertex set V ( D B ( d , s ) ) = [ d ] s V(DB(d,s))=[d]^s V ( D B ( d , s )) = [ d ] s and edge set E ( D B ( d , s ) ) = { ( a 1 , … , a s ) ⟶ ( a 2 , … , a s , t ) : a i , t ∈ [ d ] } E(DB(d,s))=\{(a_1,\ldots,a_s)\longrightarrow(a_2,\ldots,a_s,t):a_i,t\in[d]\} E ( D B ( d , s )) = {( a 1 , … , a s ) ⟶ ( a 2 , … , a s , t ) : a i , t ∈ [ d ]} . It is an aperiodic d d d -regular digraph on d s d^s d s vertices, but all of its nontrivial eigenvalues vanish [18 , 34 ] .
Further relations to previous works and extensions
As mentioned above, the simple random walk on the directed configuration model was previously studied in [7 , 15 ] . Some of the techniques developed in this work build upon a refinement of the trace method developed in [6 , 15 ] .
Despite the lack of general Alon-Boppana-type lower bounds for ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ , there have been some recent works on such lower bounds for adjacency or non-backtracking operators of sparse random digraphs based on limiting spectral distributions [36 , 25 , 29 , 17 , 4 , 28 ] .
Notably, a special case of the directed configuration model is the random d d d -regular digraph (when d i + = d i − = d d_i^+=d_i^-=d d i + = d i − = d for all i ∈ [ n ] i\in[n] i ∈ [ n ] ). It was recently proved in [25 ] that, in probability, the empirical distribution of eigenvalues of P P P converges weakly to the oriented Kesten-McKay law. This implies ∣ λ 2 ( P ) ∣ ≥ 1 / d − o ( 1 ) |\lambda_2(P)|\ge1/\sqrt{d}-o(1) ∣ λ 2 ( P ) ∣ ≥ 1/ d − o ( 1 ) with high probability for random d d d -regular digraphs. Our present work gives a quantitative estimate on this lower bound.
There are several other closely related sparse random matrices which could also be studied with our techniques. The simpler model of this form is the anisotropic random walk on a directed random Schreier graph: that is, A = ∑ i = 1 d p i S i A=\sum_{i=1}^d p_iS_i A = ∑ i = 1 d p i S i where S i S_i S i are independent uniform permutation matrices of size n n n and ∑ i p i = 1 \sum_i p_i=1 ∑ i p i = 1 , p i ≥ 0 p_i\ge0 p i ≥ 0 . It follows from [10 , 11 ] that ∣ λ 2 ( A ) ∣ ≤ ( 1 + o ( 1 ) ) ∥ p ∥ 2 |\lambda_2(A)|\le(1+o(1))\|p\|_2 ∣ λ 2 ( A ) ∣ ≤ ( 1 + o ( 1 )) ∥ p ∥ 2 . An easy adaptation of the present work gives the matching lower bound.
More generally, in [11 ] and [39 ] , the authors study random sparse bistochastic matrices of the form Q S QS QS and p Q + ( 1 − p ) S pQ+(1-p)S pQ + ( 1 − p ) S , respectively, where S S S is a uniform permutation matrix, Q Q Q is a bistochastic matrix, and 0 < p < 1 0<p<1 0 < p < 1 . They establish sharp upper bounds on ∣ λ 2 ∣ |\lambda_2| ∣ λ 2 ∣ . It would be interesting to investigate the corresponding lower bounds with the techniques presented in this work.
Proof of the main result
It remains to prove Theorem 1.3 . Our proof uses the tangle-free trace method developed in [6 , 15 ] .
Estimates on a random matching
For a random permutation from S N S_N S N , define a matching matrix M M M such that
M e f = 1 { σ ( e ) = f } , M ‾ e f = M e f − N − 1 . M_{ef}=\mathbf{1}_{\{\sigma(e)=f\}},\qquad\overline{M}_{ef}=M_{ef}-N^{-1}. M e f = 1 { σ ( e ) = f } , M e f = M e f − N − 1 .
Consider a sequence of half-edges γ = ( γ 1 , … , γ 2 k ) \gamma=(\gamma_1,\ldots,\gamma_{2k}) γ = ( γ 1 , … , γ 2 k ) , with γ 2 t − 1 ∈ E + \gamma_{2t-1}\in E^+ γ 2 t − 1 ∈ E + and γ 2 t ∈ E − \gamma_{2t}\in E^- γ 2 t ∈ E − . The distinct oriented edges in the sequence form the set
E γ = { { γ 2 t − 1 , γ 2 t } : 1 ≤ t ≤ k } . E_\gamma=\{\{\gamma_{2t-1},\gamma_{2t}\}:1\le t\le k\}. E γ = {{ γ 2 t − 1 , γ 2 t } : 1 ≤ t ≤ k } .
Since E + E^+ E + and E − E^- E − are disjoint, each element of E γ E_\gamma E γ specifies one head and one tail. We call such a pair an edge ; it need not belong to the sampled matching. For e = { e , f } ∈ E γ e=\{e,f\}\in E_\gamma e = { e , f } ∈ E γ , its multiplicity is
# { t ∈ [ k ] : γ 2 t − 1 = e , γ 2 t = f } . \#\{t\in[k]:\gamma_{2t-1}=e,\ \gamma_{2t}=f\}. # { t ∈ [ k ] : γ 2 t − 1 = e , γ 2 t = f } .
The edge is called single when this number is one. It is consistent when
e ∩ e ′ = ∅ for any e ′ ∈ E γ , e ′ ≠ e . e\cap e'=\varnothing\qquad\text{for any }e'\in E_\gamma,\ e'\ne e. e ∩ e ′ = ∅ for any e ′ ∈ E γ , e ′ = e .
Distinct edges sharing a head or a tail cannot both belong to the same matching, and we call them inconsistent .
A factor M e f M_{ef} M e f is called raw , and a factor M ‾ e f \overline{M}_{ef} M e f is called centered . We have the following estimate for the expectation of a mixed product for edges in a random matching.
Lemma 2.1. Let 1 ≤ k ≤ N 1\le k\le\sqrt{N} 1 ≤ k ≤ N and 0 ≤ k 0 ≤ k 0\le k_0\le k 0 ≤ k 0 ≤ k . Let γ = ( γ 1 , … , γ 2 k ) \gamma=(\gamma_1,\ldots,\gamma_{2k}) γ = ( γ 1 , … , γ 2 k ) be a sequence of half-edges such that γ 2 t − 1 ∈ E + \gamma_{2t-1}\in E^+ γ 2 t − 1 ∈ E + and γ 2 t ∈ E − \gamma_{2t}\in E^- γ 2 t ∈ E − for every 1 ≤ t ≤ k 1\le t\le k 1 ≤ t ≤ k . Put a = ∣ E γ ∣ a=|E_\gamma| a = ∣ E γ ∣ . Among the edges occurring at positions t ≤ k 0 t\le k_0 t ≤ k 0 , let a 1 a_1 a 1 count the consistent single edges and b b b the inconsistent single edges, with
multiplicities taken in the whole sequence γ \gamma γ . When k 0 = 0 k_0=0 k 0 = 0 , put a 1 = b = 0 a_1=b=0 a 1 = b = 0 and interpret the empty product as one. We have for some constant C > 0 C>0 C > 0 ,
∣ E ∏ t = 1 k 0 M γ 2 t − 1 γ 2 t ∏ t = k 0 + 1 k M γ 2 t − 1 γ 2 t ∣ ≤ C 2 b N a ( 3 k N ) a 1 . (9) \left|\mathbb{E}\prod_{t=1}^{k_0}M_{\gamma_{2t-1}\gamma_{2t}}\prod_{t=k_0+1}^{k}M_{\gamma_{2t-1}\gamma_{2t}}\right|\leq\frac{C\,2^b}{N^a}\left(\frac{3k}{\sqrt{N}}\right)^{a_1}. \tag*{(9)} E t = 1 ∏ k 0 M γ 2 t − 1 γ 2 t t = k 0 + 1 ∏ k M γ 2 t − 1 γ 2 t ≤ N a C 2 b ( N 3 k ) a 1 . (9)
When k 0 = k k_0=k k 0 = k , assume all edges are consistent, and every edge has multiplicity at least two, then
∣ E ∏ t = 1 k M γ 2 t − 1 γ 2 t − 1 ( N ) a ∣ ≤ 2 k N ⋅ ( N ) a . (10) \left|\mathbb{E}\prod_{t=1}^{k}M_{\gamma_{2t-1}\gamma_{2t}}-\frac{1}{(N)_a}\right|\leq\frac{2k}{N\cdot(N)_a}. \tag*{(10)} E t = 1 ∏ k M γ 2 t − 1 γ 2 t − ( N ) a 1 ≤ N ⋅ ( N ) a 2 k . (10)
where ( N ) a = N ( N − 1 ) ⋯ ( N − a + 1 ) (N)_a=N(N-1)\cdots(N-a+1) ( N ) a = N ( N − 1 ) ⋯ ( N − a + 1 ) .
Proof. For k 0 ≥ 1 k_0\geq1 k 0 ≥ 1 , (2.1) is [6 Proposition 28] , see also [14 ] for the connection to Weingarten calculus. For k 0 = 0 k_0=0 k 0 = 0 , an inconsistent product is zero, whereas a consistent product has expectation ( N ) a − 1 (N)_a^{-1} ( N ) a − 1 . Since a ≤ k ≤ N a\leq k\leq\sqrt{N} a ≤ k ≤ N ,
0 ≤ log N a ( N ) a = ∑ h = 0 a − 1 − log ( 1 − h / N ) ≤ ∑ h = 0 a − 1 h N − a + 1 ≤ a ( a − 1 ) 2 ( N − a + 1 ) ≤ 1 2 , (11) 0\leq\log\frac{N^a}{(N)_a}=\sum_{h=0}^{a-1}-\log(1-h/N)\leq\sum_{h=0}^{a-1}\frac{h}{N-a+1}\leq\frac{a(a-1)}{2(N-a+1)}\leq\frac{1}{2}, \tag*{(11)} 0 ≤ log ( N ) a N a = h = 0 ∑ a − 1 − log ( 1 − h / N ) ≤ h = 0 ∑ a − 1 N − a + 1 h ≤ 2 ( N − a + 1 ) a ( a − 1 ) ≤ 2 1 , (11)
so (2.1) holds in this case as well. For (2.2), let h 1 , … , h a ≥ 2 h_1,\ldots,h_a\geq2 h 1 , … , h a ≥ 2 be the multiplicities, so ∑ i = 1 a h i = k \sum_{i=1}^{a}h_i=k ∑ i = 1 a h i = k . For a matching indicator M e f M_{ef} M e f ,
( M e f − N − 1 ) h = α h M e f + ( − N − 1 ) h , where α h = ( 1 − N − 1 ) h − ( − N − 1 ) h . (M_{ef}-N^{-1})^h=\alpha_hM_{ef}+(-N^{-1})^h,\qquad\text{where }\alpha_h=(1-N^{-1})^h-(-N^{-1})^h. ( M e f − N − 1 ) h = α h M e f + ( − N − 1 ) h , where α h = ( 1 − N − 1 ) h − ( − N − 1 ) h .
For N ≥ 2 N\geq2 N ≥ 2 , we have α h ∈ [ 0 , 1 ] \alpha_h\in[0,1] α h ∈ [ 0 , 1 ] and 1 − α h ≤ h / N 1-\alpha_h\leq h/N 1 − α h ≤ h / N . The following elementary inequality holds:
0 ≤ 1 − ∏ i = 1 a α h i ≤ ∑ i = 1 a ( 1 − α h i ) ≤ k N . (12) 0\leq1-\prod_{i=1}^{a}\alpha_{h_i}\leq\sum_{i=1}^{a}(1-\alpha_{h_i})\leq\frac{k}{N}. \tag*{(12)} 0 ≤ 1 − i = 1 ∏ a α h i ≤ i = 1 ∑ a ( 1 − α h i ) ≤ N k . (12)
Let { e t , f t } \{e_t,f_t\} { e t , f t } , 1 ≤ t ≤ a 1\leq t\leq a 1 ≤ t ≤ a be the distinct edges. Then
E [ ∏ t = 1 a M e t , f t h t − 1 ( N ) a ] = E ∏ t = 1 a ( α h t M e t f t + ( − N − 1 ) h t ) − 1 ( N ) a . \mathbb{E}\left[\prod_{t=1}^{a}M_{e_t,f_t}^{h_t}-\frac{1}{(N)_a}\right]=\mathbb{E}\prod_{t=1}^{a}\left(\alpha_{h_t}M_{e_tf_t}+(-N^{-1})^{h_t}\right)-\frac{1}{(N)_a}. E [ t = 1 ∏ a M e t , f t h t − ( N ) a 1 ] = E t = 1 ∏ a ( α h t M e t f t + ( − N − 1 ) h t ) − ( N ) a 1 .
In the product E ∏ t = 1 a ( α h t M e t f t + ( − N − 1 ) h t ) \mathbb{E}\prod_{t=1}^{a}(\alpha_{h_t}M_{e_tf_t}+(-N^{-1})^{h_t}) E ∏ t = 1 a ( α h t M e t f t + ( − N − 1 ) h t ) , the term selecting all a a a indicator random variables contributes 1 ( N ) a ∏ i = 1 a α h i \frac{1}{(N)_a}\prod_{i=1}^{a}\alpha_{h_i} ( N ) a 1 ∏ i = 1 a α h i , and from (2.4),
∣ 1 ( N ) a ∏ i = 1 a α h i − 1 ( N ) a ∣ ≤ k N ( N ) a . \left|\frac{1}{(N)_a}\prod_{i=1}^{a}\alpha_{h_i}-\frac{1}{(N)_a}\right|\leq\frac{k}{N(N)_a}. ( N ) a 1 i = 1 ∏ a α h i − ( N ) a 1 ≤ N ( N ) a k .
Since h t ≥ 2 h_t\geq2 h t ≥ 2 , each term taking ( a − j ) (a-j) ( a − j ) indicators and j j j scalars contributes at most
1 ( N ) a − j ⋅ N − 2 j ≤ 1 ( N ) a N − j \frac{1}{(N)_{a-j}}\cdot N^{-2j}\leq\frac{1}{(N)_a}N^{-j} ( N ) a − j 1 ⋅ N − 2 j ≤ ( N ) a 1 N − j
in absolute value. The total approximation error is at most
∣ E ∏ t = 1 k M γ 2 t − 1 γ 2 t − 1 ( N ) a ∣ ≤ k N ( N ) a + 1 ( N ) a ∑ j = 1 a ( a j ) N − j = 1 ( N ) a ( k N + ( 1 + N − 1 ) a − 1 ) ≤ 2 k N ⋅ ( N ) a , \begin{aligned}
\left|\mathbb{E}\prod_{t=1}^{k}M_{\gamma_{2t-1}\gamma_{2t}}-\frac{1}{(N)_a}\right|
\leq\frac{k}{N(N)_a}+\frac{1}{(N)_a}\sum_{j=1}^{a}\binom{a}{j}N^{-j} \\
&=\frac{1}{(N)_a}\left(\frac{k}{N}+(1+N^{-1})^a-1\right)\leq\frac{2k}{N\cdot(N)_a},
\end{aligned} E t = 1 ∏ k M γ 2 t − 1 γ 2 t − ( N ) a 1 ≤ N ( N ) a k + ( N ) a 1 j = 1 ∑ a ( j a ) N − j = ( N ) a 1 ( N k + ( 1 + N − 1 ) a − 1 ) ≤ N ⋅ ( N ) a 2 k ,
where in the last inequality, we use a ≤ k / 2 a\leq k/2 a ≤ k /2 .
Tangle-freeness and telescoping decomposition
The matching estimate Lemma 2.1 applies to arbitrary half-edge sequences. To use it for powers of P P P , we now impose the vertex adjacency condition that makes such a sequence a path.
Definition 2.2 (Path). For t ≥ 1 t \ge1 t ≥ 1 , a path of length t t t from u u u to v v v is a sequence γ = ( e 1 , f 1 , … , e t , f t ) \gamma= (\mathbf{e}_1,\mathbf{f}_1,\ldots,\mathbf{e}_t,\mathbf{f}_t) γ = ( e 1 , f 1 , … , e t , f t ) for which there are vertices v 0 , … , v t v_0,\ldots,v_t v 0 , … , v t satisfying
v 0 = u , v t = v , e s ∈ E + ( v s − 1 ) , f s ∈ E − ( v s ) , 1 ≤ s ≤ t . v_0 = u,\qquad v_t = v,\qquad\mathbf{e}_s \in E^{+}(v_{s-1}),\qquad\mathbf{f}_s \in E^{-}(v_s),\qquad1 \le s \le t. v 0 = u , v t = v , e s ∈ E + ( v s − 1 ) , f s ∈ E − ( v s ) , 1 ≤ s ≤ t . Vertices and half-edges may repeat. The path is defined before sampling σ \sigma σ ; it is realized when σ ( e s ) = f s \sigma(\mathbf{e}_s) = \mathbf{f}_s σ ( e s ) = f s for every s s s . Write P t ( u , v ) \mathcal{P}^t(u,v) P t ( u , v ) for the set of all these potential paths, without requiring their edges to be realized or consistent.
The support G ( γ ) G(\gamma) G ( γ ) is the directed multigraph with vertex set { v 0 , … , v t } \{v_0,\ldots,v_t\} { v 0 , … , v t } and one edge v s − 1 → v s v_{s-1} \to v_s v s − 1 → v s for each distinct pair ( e s , f s ) (\mathbf{e}_s,\mathbf{f}_s) ( e s , f s ) . Repeated uses of the same pair give only one support edge; distinct pairs with the same endpoints give parallel edges. Loops are allowed. Connectivity, cycles, and degrees are computed after forgetting orientations but keeping all loops and parallel edges. In particular, a loop contributes two to the degree, and one to each of the in- and out-degrees.
Definition 2.3 (Genus and tangle-free paths). For a connected multigraph H H H , its genus is
g ( H ) = ∣ E ( H ) ∣ − ∣ V ( H ) ∣ + 1. g(H) = |E(H)| - |V(H)| + 1. g ( H ) = ∣ E ( H ) ∣ − ∣ V ( H ) ∣ + 1. The graph H H H is tangle-free if g ( H ) ≤ 1 g(H) \le1 g ( H ) ≤ 1 (a tree or a connected graph with one cycle), and is a tangle if g ( H ) ≥ 2 g(H) \ge2 g ( H ) ≥ 2 . A path γ \gamma γ is tangle-free when its support G ( γ ) G(\gamma) G ( γ ) is tangle-free, and tangled otherwise. For integer t ≥ 1 t \ge1 t ≥ 1 , write T t ( u , v ) ⊆ P t ( u , v ) \mathcal{T}^t(u,v) \subseteq\mathcal{P}^t(u,v) T t ( u , v ) ⊆ P t ( u , v ) for the tangle-free paths of length t t t from u u u to $v.
Let d e + d_{\mathbf{e}}^{+} d e + denote the out-degree of the vertex carrying the head e \mathbf{e} e . Define the degree weight of a path γ = ( e s , f s ) s = 1 t \gamma= (\mathbf{e}_s,\mathbf{f}_s)_{s=1}^t γ = ( e s , f s ) s = 1 t by
ω ( γ ) = ∏ s = 1 t ( d e s + ) − 1 . \omega(\gamma) = \prod_{s=1}^{t}(d_{\mathbf{e}_s}^{+})^{-1}. ω ( γ ) = s = 1 ∏ t ( d e s + ) − 1 .
The ordinary and centered weights of a single step are
A ( e , f ) = M e f d e + , A ‾ ( e , f ) = M ‾ e f d e + . A(\mathbf{e},\mathbf{f}) = \frac{M_{\mathbf{e}\mathbf{f}}}{d_{\mathbf{e}}^{+}},\qquad\underline{A}(\mathbf{e},\mathbf{f}) = \frac{\underline{M}_{\mathbf{e}\mathbf{f}}}{d_{\mathbf{e}}^{+}}. A ( e , f ) = d e + M ef , A ( e , f ) = d e + M ef .
The usual path expansion gives
P t ( u , v ) = ∑ γ ∈ P t ( u , v ) ∏ s = 1 t A ( e s , f s ) . P^t(u,v) = \sum_{\gamma\in\mathcal{P}^t(u,v)} \prod_{s=1}^{t} A(\mathbf{e}_s,\mathbf{f}_s). P t ( u , v ) = γ ∈ P t ( u , v ) ∑ s = 1 ∏ t A ( e s , f s ) .
Restricting the sum to tangle-free paths defines two matrices P ( t ) P^{(t)} P ( t ) and P ‾ ( t ) \underline{P}^{(t)} P ( t ) such that
P ( t ) ( u , v ) = ∑ γ ∈ T t ( u , v ) ∏ s = 1 t A ( e s , f s ) , P^{(t)}(u,v) = \sum_{\gamma\in\mathcal{T}^t(u,v)} \prod_{s=1}^{t} A(\mathbf{e}_s,\mathbf{f}_s), P ( t ) ( u , v ) = γ ∈ T t ( u , v ) ∑ s = 1 ∏ t A ( e s , f s ) ,
P ‾ ( t ) ( u , v ) = ∑ γ ∈ T t ( u , v ) ∏ s = 1 t A ‾ ( e s , f s ) . \underline{P}^{(t)}(u,v) = \sum_{\gamma\in\mathcal{T}^t(u,v)} \prod_{s=1}^{t} \underline{A}(\mathbf{e}_s,\mathbf{f}_s). P ( t ) ( u , v ) = γ ∈ T t ( u , v ) ∑ s = 1 ∏ t A ( e s , f s ) .
Set P ( 0 ) = P ‾ ( 0 ) = I n P^{(0)} = \underline{P}^{(0)} = I_n P ( 0 ) = P ( 0 ) = I n .
Let B + ( u , ℓ ) B^{+}(u,\ell) B + ( u , ℓ ) be the subgraph of G G G induced by the vertices reachable from u u u by a directed path of length at most ℓ \ell ℓ . The graph G G G is ℓ \ell ℓ -tangle-free if every B + ( u , ℓ ) B^{+}(u,\ell) B + ( u , ℓ ) is tangle-free. Let H ℓ \mathcal{H}_{\ell} H ℓ be the event that G G G is ℓ \ell ℓ -tangle-free. Then
P ℓ = P ( ℓ ) on H ℓ . P^{\ell} = P^{(\ell)} \qquad\text{on } \mathcal{H}_{\ell}. P ℓ = P ( ℓ ) on H ℓ .
The following lemma extends the local tangle-free estimate in [15 Proposition 2.3] to growing Δ \Delta Δ , using the exploration argument of [7 Section 3.2] .
Lemma 2.4 (Tangle-freeness). If Δ = n o ( 1 ) \Delta= n^{o(1)} Δ = n o ( 1 ) and ℓ ≤ ⌈ α log Δ n ⌉ \ell\le\lceil\alpha\log_{\Delta} n\rceil ℓ ≤ ⌈ α log Δ n ⌉ for a fixed 0 < α < 1 / 4 0 < \alpha< 1/4 0 < α < 1/4 , then G G G is ℓ \ell ℓ -tangle-free with high probability.
Proof. Starting with a fixed vertex, explore the reachable vertices in order of directed distance, revealing all outgoing heads at vertices of distance at most ℓ \ell ℓ , including those at distance ℓ \ell ℓ . This reveals every edge of its ℓ \ell ℓ -neighborhood and uses at most
Δ ∑ j = 0 ℓ Δ j ≤ 2 Δ ℓ + 1 \Delta\sum_{j=0}^{\ell}\Delta^j \le2\Delta^{\ell+1} Δ j = 0 ∑ ℓ Δ j ≤ 2 Δ ℓ + 1
matching pairs. Since 2 Δ ℓ + 1 ≤ n α + o ( 1 ) = o ( N ) 2\Delta^{\ell+1} \le n^{\alpha+o(1)} = o(N) 2 Δ ℓ + 1 ≤ n α + o ( 1 ) = o ( N ) , this number is at most N / 2 N/2 N /2 for sufficiently large n n n . A collision occurs when the chosen tail is attached to an already discovered vertex. A tangle requires at least two collisions. The collision estimate in [7 Lemma 5] , followed by a union bound over the n n n initial vertices, gives
P { G is not ℓ -tangle-free } ≤ n 2 Δ 2 ( 2 Δ ℓ + 1 ) 4 ( N / 2 ) 2 ≤ 32 Δ 4 ℓ + 6 n ≤ n 4 α − 1 + o ( 1 ) . \mathbb{P}\{G\text{ is not }\ell\text{-tangle-free}\} \le n\frac{2\Delta^2(2\Delta^{\ell+1})^4}{(N/2)^2} \le\frac{32\Delta^{4\ell+6}}{n} \le n^{4\alpha-1+o(1)}. P { G is not ℓ -tangle-free } ≤ n ( N /2 ) 2 2 Δ 2 ( 2 Δ ℓ + 1 ) 4 ≤ n 32 Δ 4 ℓ + 6 ≤ n 4 α − 1 + o ( 1 ) .
Since 0 < α < 1 / 4 0 < \alpha< 1/4 0 < α < 1/4 , the lemma follows. □
For 1 ≤ k ≤ ℓ 1 \le k \le\ell 1 ≤ k ≤ ℓ , let R ℓ , k ( u , v ) R^{\ell,k}(u,v) R ℓ , k ( u , v ) be the set of tangled paths whose first ( k − 1 ) (k-1) ( k − 1 ) steps and the last ( ℓ − k ) (\ell-k) ( ℓ − k ) steps are separately tangle-free. The k k k -th edge joins these two tangle-free paths. Define
R ℓ , k ( u , v ) = ∑ γ ∈ R ℓ , k ( u , v ) ( ∏ s < k A ( e s , f s ) ) 1 d e k + ( ∏ s > k A ( e s , f s ) ) . R^{\ell,k}(u,v)=\sum_{\gamma\in R^{\ell,k}(u,v)}
\left(\prod_{s<k}A(e_s,f_s)\right)\frac{1}{d_{e_k}^{+}}
\left(\prod_{s>k}A(e_s,f_s)\right). R ℓ , k ( u , v ) = γ ∈ R ℓ , k ( u , v ) ∑ ( s < k ∏ A ( e s , f s ) ) d e k + 1 ( s > k ∏ A ( e s , f s ) ) .
Write
π − ( i ) = d i − N , i ∈ [ n ] . \pi^{-}(i)=\frac{d_i^{-}}{N},\qquad i\in[n]. π − ( i ) = N d i − , i ∈ [ n ] .
for the probability that a uniformly chosen tail is attached to i i i .
Lemma 2.5 (Telescoping decomposition, Lemma 3.1 in [15 ] ). For ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 , the following identity holds:
P ( ℓ ) = P ‾ ( ℓ ) + ∑ k = 1 ℓ P ( k − 1 ) 1 ( π − ) T P ‾ ( ℓ − k ) − 1 N ∑ k = 1 ℓ R ℓ , k . (13) P^{(\ell)}=\underline{P}^{(\ell)}+\sum_{k=1}^{\ell}P^{(k-1)}1(\pi^-)^{\mathsf T}\underline{P}^{(\ell-k)}-\frac{1}{N}\sum_{k=1}^{\ell}R^{\ell,k}. \tag*{(13)} P ( ℓ ) = P ( ℓ ) + k = 1 ∑ ℓ P ( k − 1 ) 1 ( π − ) T P ( ℓ − k ) − N 1 k = 1 ∑ ℓ R ℓ , k . (13)
Define, for integers ℓ , t ≥ 1 \ell,t\ge1 ℓ , t ≥ 1 ,
Q ( ℓ ) = P ‾ ( ℓ ) − 1 N ∑ k = 1 ℓ R ℓ , k , z ℓ = 1 n 1 T Q ( ℓ ) 1 , z ℓ , t = z ℓ m − 1 z ℓ 0 , X ℓ , t = tr ( ( Q ( ℓ ) ) m − 1 Q ( ℓ 0 ) ) , (14) Q^{(\ell)}=\underline{P}^{(\ell)}-\frac{1}{N}\sum_{k=1}^{\ell}R^{\ell,k},\qquad z_{\ell}=\frac{1}{n}\mathbf{1}^{\mathsf T}Q^{(\ell)}\mathbf{1},\qquad z_{\ell,t}=z_{\ell}^{m-1}z_{\ell_0},\qquad X_{\ell,t}=\operatorname{tr}\left((Q^{(\ell)})^{m-1}Q^{(\ell_0)}\right), \tag*{(14)} Q ( ℓ ) = P ( ℓ ) − N 1 k = 1 ∑ ℓ R ℓ , k , z ℓ = n 1 1 T Q ( ℓ ) 1 , z ℓ , t = z ℓ m − 1 z ℓ 0 , X ℓ , t = tr ( ( Q ( ℓ ) ) m − 1 Q ( ℓ 0 ) ) , (14)
where t = ( m − 1 ) ℓ + ℓ 0 t=(m-1)\ell+\ell_0 t = ( m − 1 ) ℓ + ℓ 0 and m = ⌈ t / ℓ ⌉ m=\lceil t/\ell\rceil m = ⌈ t / ℓ ⌉ . The following lemma connects tr P t \operatorname{tr}P^t tr P t with ( X ℓ , t , z ℓ , t ) (X_{\ell,t},z_{\ell,t}) ( X ℓ , t , z ℓ , t ) on the event H ℓ \mathcal{H}_{\ell} H ℓ .
Lemma 2.6. Let ℓ , t ≥ 1 \ell,t\ge1 ℓ , t ≥ 1 be integers. On the tangle-free event H ℓ \mathcal{H}_{\ell} H ℓ ,
tr P t − 1 = X ℓ , t − z ℓ , t . (15) \operatorname{tr}P^t-1=X_{\ell,t}-z_{\ell,t}. \tag*{(15)} tr P t − 1 = X ℓ , t − z ℓ , t . (15)
Proof. On the event H ℓ \mathcal{H}_{\ell} H ℓ , (2.5) becomes
P ℓ = P ‾ ( ℓ ) + ∑ k = 1 ℓ P k − 1 1 ( π − ) T P ‾ ( ℓ − k ) − 1 N ∑ k = 1 ℓ R ℓ , k . (16) P^{\ell}=\underline{P}^{(\ell)}+\sum_{k=1}^{\ell}P^{k-1}1(\pi^-)^{\mathsf T}\underline{P}^{(\ell-k)}-\frac{1}{N}\sum_{k=1}^{\ell}R^{\ell,k}. \tag*{(16)} P ℓ = P ( ℓ ) + k = 1 ∑ ℓ P k − 1 1 ( π − ) T P ( ℓ − k ) − N 1 k = 1 ∑ ℓ R ℓ , k . (16)
::: Since P P P is row stochastic, P k − 1 1 = 1 P^{k-1}\mathbf{1}=\mathbf{1} P k − 1 1 = 1 for any k ≥ 1 k \ge1 k ≥ 1 . From (16) , we can write P ℓ P^\ell P ℓ as a rank-one perturbation of Q ( ℓ ) Q^{(\ell)} Q ( ℓ ) :
P ℓ = Q ( ℓ ) + 1 v ℓ T , where v ℓ T = ∑ k = 1 ℓ ( π − ) T P ( ℓ − k ) . P^\ell=Q^{(\ell)}+\mathbf{1}v_\ell^{\mathsf{T}},\qquad\text{where}\qquad v_\ell^{\mathsf{T}}=\sum_{k=1}^{\ell}(\pi^{-})^{\mathsf{T}}P^{(\ell-k)}. P ℓ = Q ( ℓ ) + 1 v ℓ T , where v ℓ T = k = 1 ∑ ℓ ( π − ) T P ( ℓ − k ) .
A simple calculation shows z ℓ = 1 n 1 T Q ( ℓ ) 1 = 1 − v ℓ T 1 z_\ell=\frac{1}{n}\mathbf{1}^{\mathsf{T}}Q^{(\ell)}\mathbf{1}=1-v_\ell^{\mathsf{T}}\mathbf{1} z ℓ = n 1 1 T Q ( ℓ ) 1 = 1 − v ℓ T 1 and Q ( ℓ ) 1 = ( 1 − v ℓ T 1 ) 1 = z ℓ 1 Q^{(\ell)}\mathbf{1}=(1-v_\ell^{\mathsf{T}}\mathbf{1})\mathbf{1}=z_\ell\mathbf{1} Q ( ℓ ) 1 = ( 1 − v ℓ T 1 ) 1 = z ℓ 1 . If m ≥ 2 m\ge2 m ≥ 2 , we now telescope the matrix powers:
P ( m − 1 ) ℓ − ( Q ( ℓ ) ) m − 1 = ∑ j = 1 m − 1 ( Q ( ℓ ) ) j − 1 ( P ℓ − Q ( ℓ ) ) P ( m − 1 − j ) ℓ = ∑ j = 1 m − 1 ( Q ( ℓ ) ) j − 1 1 v ℓ T P ( m − 1 − j ) ℓ = ∑ j = 1 m − 1 z ℓ j − 1 1 v ℓ T P ( m − 1 − j ) ℓ . \begin{aligned}
P^{(m-1)\ell}-(Q^{(\ell)})^{m-1}=\sum_{j=1}^{m-1}(Q^{(\ell)})^{j-1}(P^\ell-Q^{(\ell)})P^{(m-1-j)\ell} \\
&=\sum_{j=1}^{m-1}(Q^{(\ell)})^{j-1}\mathbf{1}v_\ell^{\mathsf{T}}P^{(m-1-j)\ell}
=\sum_{j=1}^{m-1}z_\ell^{j-1}\mathbf{1}v_\ell^{\mathsf{T}}P^{(m-1-j)\ell}.
\end{aligned} P ( m − 1 ) ℓ − ( Q ( ℓ ) ) m − 1 = j = 1 ∑ m − 1 ( Q ( ℓ ) ) j − 1 ( P ℓ − Q ( ℓ ) ) P ( m − 1 − j ) ℓ = j = 1 ∑ m − 1 ( Q ( ℓ ) ) j − 1 1 v ℓ T P ( m − 1 − j ) ℓ = j = 1 ∑ m − 1 z ℓ j − 1 1 v ℓ T P ( m − 1 − j ) ℓ .
We next compose by P ℓ 0 = Q ( ℓ 0 ) + 1 v ℓ 0 T P^{\ell_0}=Q^{(\ell_0)}+\mathbf{1}v_{\ell_0}^{\mathsf{T}} P ℓ 0 = Q ( ℓ 0 ) + 1 v ℓ 0 T (since ℓ 0 ≤ ℓ \ell_0\le\ell ℓ 0 ≤ ℓ implies H ℓ ⊂ H ℓ 0 \mathcal{H}_\ell\subset\mathcal{H}_{\ell_0} H ℓ ⊂ H ℓ 0 ). We find
P t − ( Q ( ℓ ) ) m − 1 Q ( ℓ 0 ) = ∑ j = 1 m − 1 z ℓ j − 1 1 v ℓ T P ( m − 1 − j ) ℓ + ℓ 0 + z ℓ m − 1 1 v ℓ 0 T . P^t-(Q^{(\ell)})^{m-1}Q^{(\ell_0)}
=\sum_{j=1}^{m-1}z_\ell^{j-1}\mathbf{1}v_\ell^{\mathsf{T}}P^{(m-1-j)\ell+\ell_0}
+z_\ell^{m-1}\mathbf{1}v_{\ell_0}^{\mathsf{T}}. P t − ( Q ( ℓ ) ) m − 1 Q ( ℓ 0 ) = j = 1 ∑ m − 1 z ℓ j − 1 1 v ℓ T P ( m − 1 − j ) ℓ + ℓ 0 + z ℓ m − 1 1 v ℓ 0 T .
Taking traces and using P k 1 = 1 P^k\mathbf{1}=\mathbf{1} P k 1 = 1 gives
tr P t − X ℓ , t = ∑ j = 1 m − 1 z ℓ j − 1 v ℓ T 1 + z ℓ m − 1 v ℓ 0 T 1 = ∑ j = 1 m − 1 z ℓ j − 1 ( 1 − z ℓ ) + z ℓ m − 1 ( 1 − z ℓ 0 ) = 1 − z ℓ m − 1 z ℓ 0 . \operatorname{tr}P^t-X_{\ell,t}
=\sum_{j=1}^{m-1}z_\ell^{j-1}v_\ell^{\mathsf{T}}\mathbf{1}
+z_\ell^{m-1}v_{\ell_0}^{\mathsf{T}}\mathbf{1}
=\sum_{j=1}^{m-1}z_\ell^{j-1}(1-z_\ell)+z_\ell^{m-1}(1-z_{\ell_0})
=1-z_\ell^{m-1}z_{\ell_0}. tr P t − X ℓ , t = j = 1 ∑ m − 1 z ℓ j − 1 v ℓ T 1 + z ℓ m − 1 v ℓ 0 T 1 = j = 1 ∑ m − 1 z ℓ j − 1 ( 1 − z ℓ ) + z ℓ m − 1 ( 1 − z ℓ 0 ) = 1 − z ℓ m − 1 z ℓ 0 .
This proves (15) .
Trace power expansion
For the remainder of this section, we set
ℓ = ⌈ log n 8 log Δ ⌉ (17) \ell=\left\lceil\frac{\log n}{8\log\Delta}\right\rceil \tag*{(17)} ℓ = ⌈ 8 log Δ log n ⌉ (17)
and consider an integer t t t as in (7) . We set m = ⌈ t / ℓ ⌉ m=\lceil t/\ell\rceil m = ⌈ t / ℓ ⌉ and write t t t as
t = ℓ ( m − 1 ) + ℓ 0 , t=\ell(m-1)+\ell_0, t = ℓ ( m − 1 ) + ℓ 0 ,
with 1 ≤ ℓ 0 ≤ ℓ 1\le\ell_0\le\ell 1 ≤ ℓ 0 ≤ ℓ . Our assumption on t t t implies that
m = o ( log n log log n ) (18) m=o\left(\frac{\log n}{\log\log n}\right) \tag*{(18)} m = o ( log log n log n ) (18)
From (15) , to prove Theorem 1.3 , it suffices to understand the moments of X ℓ , t X_{\ell,t} X ℓ , t and the scalar term z ℓ , t z_{\ell,t} z ℓ , t . We start by calculating the moments of X ℓ , t X_{\ell,t} X ℓ , t . Expand X ℓ , t X_{\ell,t} X ℓ , t as
X ℓ , t = ∑ x 1 , … , x m ∈ [ n ] Q ( ℓ ) ( x 1 , x 2 ) ⋯ Q ( ℓ ) ( x m − 1 , x m ) Q ( ℓ 0 ) ( x m , x 1 ) . X_{\ell,t}=\sum_{x_1,\ldots,x_m\in[n]}Q^{(\ell)}(x_1,x_2)\cdots Q^{(\ell)}(x_{m-1},x_m)Q^{(\ell_0)}(x_m,x_1). X ℓ , t = x 1 , … , x m ∈ [ n ] ∑ Q ( ℓ ) ( x 1 , x 2 ) ⋯ Q ( ℓ ) ( x m − 1 , x m ) Q ( ℓ 0 ) ( x m , x 1 ) .
We set ℓ j = ℓ \ell_j=\ell ℓ j = ℓ if 1 ≤ j ≤ m − 1 1\le j\le m-1 1 ≤ j ≤ m − 1 and ℓ m = ℓ 0 \ell_m=\ell_0 ℓ m = ℓ 0 . Write x = ( x i j ) i ∈ [ p ] , j ∈ [ m ] \mathbf{x}=(x_{ij})_{i\in[p],j\in[m]} x = ( x ij ) i ∈ [ p ] , j ∈ [ m ] and use the cyclic convention x i , m + 1 = x i 1 x_{i,m+1}=x_{i1} x i , m + 1 = x i 1 . Then
E X ℓ , t p = ∑ x ∈ [ n ] [ p ] × [ m ] E ∏ i = 1 p ∏ j = 1 m Q ( ℓ j ) ( x i j , x i , j + 1 ) . (19) \mathbb{E}X_{\ell,t}^{p}
=\sum_{\mathbf{x}\in[n]^{[p]\times[m]}}\mathbb{E}\prod_{i=1}^{p}\prod_{j=1}^{m}Q^{(\ell_j)}(x_{ij},x_{i,j+1}). \tag*{(19)} E X ℓ , t p = x ∈ [ n ] [ p ] × [ m ] ∑ E i = 1 ∏ p j = 1 ∏ m Q ( ℓ j ) ( x ij , x i , j + 1 ) . (19)
From (14) , we can further expand each Q ( ℓ j ) ( x i j , x i , j + 1 ) Q^{(\ell_j)}(x_{ij},x_{i,j+1}) Q ( ℓ j ) ( x ij , x i , j + 1 ) term as
Q ( ℓ j ) ( x i j , x i , j + 1 ) = P ( ℓ j ) ( x i j , x i , j + 1 ) − 1 N ∑ k = 1 ℓ j R ℓ j , k ( x i j , x i , j + 1 ) . Q^{(\ell_j)}(x_{ij},x_{i,j+1})
=P^{(\ell_j)}(x_{ij},x_{i,j+1})-\frac{1}{N}\sum_{k=1}^{\ell_j}R^{\ell_j,k}(x_{ij},x_{i,j+1}). Q ( ℓ j ) ( x ij , x i , j + 1 ) = P ( ℓ j ) ( x ij , x i , j + 1 ) − N 1 k = 1 ∑ ℓ j R ℓ j , k ( x ij , x i , j + 1 ) .
A block is one length-ℓ j \ell_j ℓ j path representing the matrix entry Q ( ℓ j ) ( x i j , x i , j + 1 ) Q^{(\ell_j)}(x_{ij},x_{i,j+1}) Q ( ℓ j ) ( x ij , x i , j + 1 ) at a fixed position ( i , j ) (i,j) ( i , j ) in (19) . The index i i i selects a trace and j j j selects one of its m m m consecutive blocks. Concatenating these m m m paths gives a closed path of length t t t .
Let I ⊆ [ p ] × [ m ] \mathcal{I} \subseteq[p] \times[m] I ⊆ [ p ] × [ m ] be the set of positions where a remainder contributing a factor − 1 / N -1/N − 1/ N is chosen. For each ( i , j ) ∈ I (i,j) \in\mathcal{I} ( i , j ) ∈ I , choose its omitted position k i j ∈ [ ℓ j ] k_{ij} \in[\ell_j] k ij ∈ [ ℓ j ] (this determines a term involving R ℓ j , k i j R^{\ell_j,k_{ij}} R ℓ j , k ij ), and write k = ( k i j ) ( i , j ) ∈ I \mathbf{k} = (k_{ij})_{(i,j)\in\mathcal{I}} k = ( k ij ) ( i , j ) ∈ I .
We call a block ordinary if ( i , j ) ∉ I (i,j) \notin\mathcal{I} ( i , j ) ∈ / I , so its path comes from P ( ℓ j ) P^{(\ell_j)} P ( ℓ j ) , and a remainder block if ( i , j ) ∈ I (i,j) \in\mathcal{I} ( i , j ) ∈ I , so its path comes from R ℓ j , k i j R^{\ell_j,k_{ij}} R ℓ j , k ij . We then obtain the following expansion:
∏ i = 1 p ∏ j = 1 m Q ( ℓ j ) ( x i j , x i , j + 1 ) = ∑ I ⊆ [ p ] × [ m ] ∑ k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] ( − 1 N ) ∣ I ∣ ∏ ( i , j ) ∉ I P ( ℓ j ) ( x i j , x i , j + 1 ) ∏ ( i , j ) ∈ I R ℓ j , k i j ( x i j , x i , j + 1 ) . (20) \prod_{i=1}^{p}\prod_{j=1}^{m} Q^{(\ell_j)}(x_{ij},x_{i,j+1})
=
\sum_{\mathcal{I}\subseteq[p]\times[m]}
\sum_{\mathbf{k}\in\prod_{(i,j)\in\mathcal{I}}[\ell_j]}
\left(\frac{-1}{N}\right)^{|\mathcal{I}|}
\prod_{(i,j)\notin\mathcal{I}}P^{(\ell_j)}(x_{ij},x_{i,j+1})
\prod_{(i,j)\in\mathcal{I}}R^{\ell_j,k_{ij}}(x_{ij},x_{i,j+1}). \tag*{(20)} i = 1 ∏ p j = 1 ∏ m Q ( ℓ j ) ( x ij , x i , j + 1 ) = I ⊆ [ p ] × [ m ] ∑ k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] ∑ ( N − 1 ) ∣ I ∣ ( i , j ) ∈ / I ∏ P ( ℓ j ) ( x ij , x i , j + 1 ) ( i , j ) ∈ I ∏ R ℓ j , k ij ( x ij , x i , j + 1 ) . (20)
An ordered trace family is the complete data
γ = ( ( γ i j ) i ∈ [ p ] , j ∈ [ m ] , I , k ) , γ i j = ( e i j , s , f i j , s ) s = 1 ℓ j , \gamma=\bigl((\gamma_{ij})_{i\in[p],j\in[m]},\mathcal{I},\mathbf{k}\bigr),
\qquad
\gamma_{ij}=(e_{ij,s},f_{ij,s})_{s=1}^{\ell_j}, γ = ( ( γ ij ) i ∈ [ p ] , j ∈ [ m ] , I , k ) , γ ij = ( e ij , s , f ij , s ) s = 1 ℓ j ,
where I ⊆ [ p ] × [ m ] \mathcal{I}\subseteq[p]\times[m] I ⊆ [ p ] × [ m ] , k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] \mathbf{k}\in\prod_{(i,j)\in\mathcal{I}}[\ell_j] k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] , and
γ i j ∈ T ℓ j ( x i j , x i , j + 1 ) ( i , j ) ∉ I , \gamma_{ij}\in\mathcal{T}^{\ell_j}(x_{ij},x_{i,j+1})
\qquad(i,j)\notin\mathcal{I}, γ ij ∈ T ℓ j ( x ij , x i , j + 1 ) ( i , j ) ∈ / I ,
γ i j ∈ R ℓ j , k i j ( x i j , x i , j + 1 ) ( i , j ) ∈ I , \gamma_{ij}\in\mathcal{R}^{\ell_j,k_{ij}}(x_{ij},x_{i,j+1})
\qquad(i,j)\in\mathcal{I}, γ ij ∈ R ℓ j , k ij ( x ij , x i , j + 1 ) ( i , j ) ∈ I ,
with x i , m + 1 = x i 1 x_{i,m+1}=x_{i1} x i , m + 1 = x i 1 . An ordered trace family corresponds to one term in the sum from (20) . The omitted positions are precisely the positions ( i , j , k i j ) (i,j,k_{ij}) ( i , j , k ij ) for ( i , j ) ∈ I (i,j)\in\mathcal{I} ( i , j ) ∈ I .
The degree weight of the family γ \gamma γ is the product of the weights of its block paths γ i j \gamma_{ij} γ ij :
ω ( γ ) = ∏ i = 1 p ∏ j = 1 m ω ( γ i j ) = ∏ i = 1 p ∏ j = 1 m ∏ s = 1 ℓ j ( d e i j , s + ) − 1 . (21) \omega(\gamma)=\prod_{i=1}^{p}\prod_{j=1}^{m}\omega(\gamma_{ij})
=\prod_{i=1}^{p}\prod_{j=1}^{m}\prod_{s=1}^{\ell_j}(d^+_{e_{ij,s}})^{-1}. \tag*{(21)} ω ( γ ) = i = 1 ∏ p j = 1 ∏ m ω ( γ ij ) = i = 1 ∏ p j = 1 ∏ m s = 1 ∏ ℓ j ( d e ij , s + ) − 1 . (21)
Its associated random matching factors have expectation
μ ( γ ) = E [ ∏ ( i , j ) ∉ I ∏ s = 1 ℓ j M e i j , s , f i j , s ∏ ( i , j ) ∈ I ( ∏ s < k i j M e i j , s , f i j , s ) ( ∏ s > k i j M e i j , s , f i j , s ) ] . (22) \mu(\gamma)=\mathbb{E}\left[
\prod_{(i,j)\notin\mathcal{I}}\prod_{s=1}^{\ell_j}M_{e_{ij,s},f_{ij,s}}
\prod_{(i,j)\in\mathcal{I}}
\left(\prod_{s<k_{ij}}M_{e_{ij,s},f_{ij,s}}\right)
\left(\prod_{s>k_{ij}}M_{e_{ij,s},f_{ij,s}}\right)
\right]. \tag*{(22)} μ ( γ ) = E ( i , j ) ∈ / I ∏ s = 1 ∏ ℓ j M e ij , s , f ij , s ( i , j ) ∈ I ∏ s < k ij ∏ M e ij , s , f ij , s s > k ij ∏ M e ij , s , f ij , s . (22)
Inserting all the definitions into (20) and (19) gives the following exact expansion:
E X ℓ , t p = ∑ I ⊆ [ p ] × [ m ] ∑ k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] ( − 1 N ) ∣ I ∣ ∑ x ∈ [ n ] [ p ] × [ m ] ∑ γ i j ∈ T ℓ j ( x i j , x i , j + 1 ) ( i , j ) ∉ I ∑ γ i j ∈ R ℓ j , k i j ( x i j , x i , j + 1 ) ( i , j ) ∈ I ω ( γ ) μ ( γ ) . (23) \mathbb{E}X_{\ell,t}^{p}
=
\sum_{\mathcal{I}\subseteq[p]\times[m]}
\sum_{\mathbf{k}\in\prod_{(i,j)\in\mathcal{I}}[\ell_j]}
\left(\frac{-1}{N}\right)^{|\mathcal{I}|}
\sum_{\mathbf{x}\in[n]^{[p]\times[m]}}
\sum_{\substack{\gamma_{ij}\in\mathcal{T}^{\ell_j}(x_{ij},x_{i,j+1})\\(i,j)\notin\mathcal{I}}}
\sum_{\substack{\gamma_{ij}\in\mathcal{R}^{\ell_j,k_{ij}}(x_{ij},x_{i,j+1})\\(i,j)\in\mathcal{I}}}
\omega(\gamma)\mu(\gamma). \tag*{(23)} E X ℓ , t p = I ⊆ [ p ] × [ m ] ∑ k ∈ ∏ ( i , j ) ∈ I [ ℓ j ] ∑ ( N − 1 ) ∣ I ∣ x ∈ [ n ] [ p ] × [ m ] ∑ γ ij ∈ T ℓ j ( x ij , x i , j + 1 ) ( i , j ) ∈ / I ∑ γ ij ∈ R ℓ j , k ij ( x ij , x i , j + 1 ) ( i , j ) ∈ I ∑ ω ( γ ) μ ( γ ) . (23)
Grouping the terms in the trace sum
We next separate the equality pattern of each path family from its actual vertex and half-edge labels.
Definition 2.7 (Canonical family). Explore the blocks γ i j \gamma_{ij} γ ij in lexicographic order ( i , j ) (i,j) ( i , j ) , reading the initial vertex and then the steps of each block in increasing order. Replace the distinct vertices by 1 , 2 , … , v 1,2,\ldots,v 1 , 2 , … , v in order of first appearance. At each vertex, number the distinct heads and the distinct tails separately starting from 1 1 1 , again in order of first appearance.
This relabeling includes the half-edges at omitted steps. Keep the remainder-block set I \mathcal{I} I , the cuts k \mathbf{k} k , and the order of all traces, blocks, and steps unchanged. The resulting family is called the canonical family . We denote it by γ \gamma γ , with block paths γ i j \gamma_{ij} γ ij .
Since there is one omitted edge in the definition of R ℓ , k R^{\ell,k} R ℓ , k when we perform the path expansion, we will define the augmented support of a canonical family by putting back these edges.
Definition 2.8 (Augmented support). Let γ \gamma γ be a canonical family, with remainder blocks I \mathcal{I} I and cuts k \mathbf{k} k as in (23) , and put r = ∣ I ∣ r = |\mathcal{I}| r = ∣ I ∣ . Its augmented support is the directed multigraph with all vertices of γ \gamma γ , one edge for each distinct oriented edge at a non-omitted step, and one formal directed edge for each of the r r r omitted steps. Each formal edge is distinct from every other edge, even when their endpoints coincide.
Let a a a be the number of distinct edges at non-omitted steps and v v v the number of vertices. Define
q = a + r − v . q = a + r - v. q = a + r − v . We call q q q the excess of the augmented support of γ \gamma γ .
Lemma 2.9. We have a ≥ v a \ge v a ≥ v . Hence q ≥ r q \ge r q ≥ r .
Proof. Consider the support graph formed by all non-omitted edges and all v v v vertices. Each remainder block has genus at least two by the definition of tangles, and the paths before and after the omitted edge are tangle-free. There are two cases:
If the two paths are disjoint, adding the omitted edge back makes their union connected without creating a cycle. Then each path must contain at least one cycle for the remainder block to have genus at least two.
If they intersect, their union is connected, and putting the omitted edge back increases its genus by at most one. Their union therefore already contains a cycle.
Any connected component containing an edge from a remainder block therefore contains a cycle. Moreover, any connected component containing no edges from remainder blocks contains an entire closed trace and thus contains a cycle. Thus every connected component in the support graph contains a cycle; therefore a ≥ v a \ge v a ≥ v .
Let deg x \deg x deg x be the non-oriented degree of x x x in the augmented support, with a loop contributing two and parallel edges counted separately. Each of its a + r a+r a + r edges contributes two to the total degree, so
∑ x deg x = 2 ( a + r ) , ∑ x ( deg x − 2 ) = ∑ x deg x − 2 v = 2 ( a + r ) − 2 v = 2 q . (24) \sum_x \deg x = 2(a+r), \qquad\sum_x(\deg x-2) = \sum_x \deg x - 2v = 2(a+r)-2v = 2q. \tag*{(24)} x ∑ deg x = 2 ( a + r ) , x ∑ ( deg x − 2 ) = x ∑ deg x − 2 v = 2 ( a + r ) − 2 v = 2 q . (24)
Let a 1 a_1 a 1 count consistent single edges whose unique factor is centered, as in Lemma 2.1. For the canonical family γ \gamma γ , write ( v i j , 0 , … , v i j , ℓ j ) (v_{ij,0},\ldots,v_{ij,\ell_j}) ( v ij , 0 , … , v ij , ℓ j ) for the sequence of vertex symbols in block γ i j \gamma_{ij} γ ij . For each x ∈ [ v ] x \in[v] x ∈ [ v ] , define the total number of path steps that leave vertex x x x
t x = # { ( i , j , s ) : i ∈ [ p ] , j ∈ [ m ] , s ∈ [ ℓ j ] , v i j , s − 1 = x } . t_x = \#\{(i,j,s): i \in[p],\ j \in[m],\ s \in[\ell_j],\ v_{ij,s-1}=x\}. t x = # {( i , j , s ) : i ∈ [ p ] , j ∈ [ m ] , s ∈ [ ℓ j ] , v ij , s − 1 = x } .
Since every step has one initial vertex,
∑ x = 1 v t x = p t . \sum_{x=1}^{v} t_x = pt. x = 1 ∑ v t x = pt .
For a fixed vertex tuple, grouping the factors in (21) by the departure vertex therefore gives
ω ( γ ) = ∏ i = 1 p ∏ j = 1 m ∏ s = 1 ℓ j ( d e i j , s + ) − 1 = ∏ x = 1 v ( d i x + ) − t x . \omega(\gamma) = \prod_{i=1}^{p}\prod_{j=1}^{m}\prod_{s=1}^{\ell_j}(d^+_{e_{ij,s}})^{-1} = \prod_{x=1}^{v}(d^+_{i_x})^{-t_x}. ω ( γ ) = i = 1 ∏ p j = 1 ∏ m s = 1 ∏ ℓ j ( d e ij , s + ) − 1 = x = 1 ∏ v ( d i x + ) − t x .
Let h x ± h_x^{\pm} h x ± count distinct heads and tails at vertex symbol x x x , including those at omitted steps. Fix the first-visit tuple i = ( i 1 , … , i v ) \mathbf{i}=(i_1,\ldots,i_v) i = ( i 1 , … , i v ) , so vertex symbol x x x receives the actual vertex label i x i_x i x . Its h x + h_x^+ h x + distinct head symbols must receive distinct elements of E + ( i x ) E^+(i_x) E + ( i x ) . In their order of first appearance, the first symbol has d i x + d^+_{i_x} d i x + choices, the second has d i x + − 1 d^+_{i_x}-1 d i x + − 1 , and so on. Thus the number of assignments for heads is
d i x + ( d i x + − 1 ) ⋯ ( d i x + − h x + + 1 ) = ( d i x + ) h x + . d^+_{i_x}(d^+_{i_x}-1)\cdots(d^+_{i_x}-h_x^++1)=(d^+_{i_x})_{h_x^+}. d i x + ( d i x + − 1 ) ⋯ ( d i x + − h x + + 1 ) = ( d i x + ) h x + .
Similarly, assigning the h x − h_x^{-} h x − distinct tail symbols to E − ( i x ) E^{-}(i_x) E − ( i x ) gives ( d i x − ) h x − \left(d^{-}_{i_x}\right)_{h_x^{-}} ( d i x − ) h x − choices. Multiplying these counts therefore gives the total number of assignments:
∏ x = 1 v ( d i x + ) h x + ( d i x − ) h x − . \prod_{x=1}^{v}\left(d^{+}_{i_x}\right)_{h_x^{+}}\left(d^{-}_{i_x}\right)_{h_x^{-}}. x = 1 ∏ v ( d i x + ) h x + ( d i x − ) h x − .
For a canonical family γ \gamma γ , let W ( γ ) W(\gamma) W ( γ ) denote the sum of all terms in (23) whose ordered path families have canonical representative γ \gamma γ . We call W ( γ ) W(\gamma) W ( γ ) the class contribution . This sum includes all choices of distinct vertices i 1 , … , i v ∈ [ n ] i_1,\ldots,i_v \in[n] i 1 , … , i v ∈ [ n ] and all half-edge assignments; the block choices and cuts are fixed by γ \gamma γ .
Relabeling heads and tails preserves the uniform matching law, so all these assignments have the same matching expectation μ ( γ ) \mu(\gamma) μ ( γ ) . Multiplying the assignment count by the degree weight and this expectation, including the coefficient ( − 1 / N ) r (-1/N)^r ( − 1/ N ) r , and summing over the vertex tuple therefore gives
W ( γ ) = ( − 1 N ) r μ ( γ ) ∑ i ∈ [ n ] v all distinct ∏ x = 1 v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x . (25) W(\gamma)=\left(\frac{-1}{N}\right)^r\mu(\gamma)\sum_{\substack{i\in[n]^v\\\text{all distinct}}}\prod_{x=1}^{v}\left(d^{+}_{i_x}\right)_{h_x^{+}}\left(d^{-}_{i_x}\right)_{h_x^{-}}\left(d^{+}_{i_x}\right)^{-t_x}. \tag*{(25)} W ( γ ) = ( N − 1 ) r μ ( γ ) i ∈ [ n ] v all distinct ∑ x = 1 ∏ v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x . (25)
Write F q , a 1 \mathcal{F}_{q,a_1} F q , a 1 for the canonical families in (23) with a given q q q and a 1 a_1 a 1 . Grouping its terms gives the following identity:
E X ℓ , t p = ∑ q ≥ 0 ∑ a 1 ≥ 0 ∑ γ ∈ F q , a 1 W ( γ ) . (26) \mathbb{E}X_{\ell,t}^{p}=\sum_{q\geq0}\sum_{a_1\geq0}\sum_{\gamma\in\mathcal{F}_{q,a_1}}W(\gamma). \tag*{(26)} E X ℓ , t p = q ≥ 0 ∑ a 1 ≥ 0 ∑ γ ∈ F q , a 1 ∑ W ( γ ) . (26)
We first bound the classes with q + a 1 ≥ 1 q+a_1\geq1 q + a 1 ≥ 1 , then compute the leading class q = a 1 = 0 q=a_1=0 q = a 1 = 0 .
Path-counting estimates
We adapt the analysis in [6 , 15 ] . All degrees below refer to the augmented support. A branch vertex has degree at least three, or it is one of the starting vertices x i , 1 x_{i,1} x i , 1 , 1 ≤ i ≤ p 1\leq i\leq p 1 ≤ i ≤ p of a trace. A maximal non-branching path is a directed sequence of edges of positive length whose endpoints are branch vertices and whose internal vertices are not branch vertices.
Lemma 2.10 (Branches and single edges). For each canonical family with a given excess q q q , the following holds:
(1) There are at most 2 q + p 2q+p 2 q + p branch vertices, with total degree at most 6 q + 2 p 6q+2p 6 q + 2 p , and at most 3 q + p 3q+p 3 q + p maximal non-branching paths.
(2) There are at most 6 q 6q 6 q distinct inconsistent edges and at most q ℓ q\ell q ℓ raw single edges.
Proof. (1) From (24) , the number of vertices with degree greater than two is at most
∑ x ( deg ( x ) − 2 ) = 2 q . (27) \sum_x(\deg(x)-2)=2q. \tag*{(27)} x ∑ ( deg ( x ) − 2 ) = 2 q . (27)
Together with at most p p p degree-two starting vertices of a trace, there are at most 2 q + p 2q+p 2 q + p many branch vertices. Then the total degree satisfies
∑ x branch vertices deg ( x ) ≤ ∑ x ( deg ( x ) − 2 ) + 2 # { branch vertices } ≤ 6 q + 2 p . \sum_{x\text{ branch vertices}}\deg(x)\leq\sum_x(\deg(x)-2)+2\#\{\text{branch vertices}\}\leq6q+2p. x branch vertices ∑ deg ( x ) ≤ x ∑ ( deg ( x ) − 2 ) + 2# { branch vertices } ≤ 6 q + 2 p .
The endpoints of each maximal non-branching path are branch vertices. By counting degrees, there are at most 3 q + p 3q+p 3 q + p such paths.
(2) An inconsistent edge shares a head with another outgoing edge or a tail with another incoming edge. This shared vertex has degree at least three. Therefore, from (24) and (27) , the number of distinct inconsistent edges is bounded by
∑ x : deg ( x ) ≥ 3 deg ( x ) ≤ ∑ x : deg ( x ) ≥ 3 ( deg ( x ) − 2 ) + 4 q ≤ 6 q . \sum_{x:\deg(x)\geq3}\deg(x)\leq\sum_{x:\deg(x)\geq3}(\deg(x)-2)+4q\leq6q. x : d e g ( x ) ≥ 3 ∑ deg ( x ) ≤ x : d e g ( x ) ≥ 3 ∑ ( deg ( x ) − 2 ) + 4 q ≤ 6 q .
Each raw single edge belongs to a remainder block, so from Lemma 2.9 , there are at most r ℓ ≤ q ℓ r\ell\le q\ell r ℓ ≤ q ℓ such edges. □ \square □
At a vertex with one incoming and one outgoing edge, the paths use one head and one tail. If the vertex has label i i i and the paths leave it k k k times, its half-edge choices and departure weights contribute d i + d i − ( d i + ) − k d_i^+d_i^-(d_i^+)^{-k} d i + d i − ( d i + ) − k . Generalizing β 3 \beta_3 β 3 in (4) , we define the following quantity to track its contribution
β k = 1 N ∑ i d i − ( d i + ) k − 1 , k ≥ 1. \beta_k = \frac{1}{N}\sum_i \frac{d_i^-}{(d_i^+)^{k-1}}, \qquad k \ge1. β k = N 1 i ∑ ( d i + ) k − 1 d i − , k ≥ 1.
Lemma 2.11. We have β 1 = 1 \beta_1=1 β 1 = 1 , β 2 = ρ 2 \beta_2=\rho^2 β 2 = ρ 2 , and for k ≥ 3 k\ge3 k ≥ 3 ,
β k ≤ e − θ ρ k , \beta_k \le e^{-\theta}\rho^k, β k ≤ e − θ ρ k , where θ \theta θ is as in (4) . Moreover, (4) holds with θ = ( δ − δ ) / Δ \theta=(\delta-\sqrt{\delta})/\Delta θ = ( δ − δ ) /Δ .
Proof. The first two identities follow from the definition. Since (3) implies that ( d i + ) − 1 ≤ δ − 1 ≤ ρ (d_i^+)^{-1}\le\delta^{-1}\le\rho ( d i + ) − 1 ≤ δ − 1 ≤ ρ , it gives for k ≥ 3 k\ge3 k ≥ 3 ,
β k ≤ ρ k − 3 1 N ∑ i d i − ( d i + ) 2 = ρ k − 3 β 3 ≤ e − θ ρ k . \beta_k \le\rho^{k-3}\frac{1}{N}\sum_i\frac{d_i^-}{(d_i^+)^2}=\rho^{k-3}\beta_3\le e^{-\theta}\rho^k. β k ≤ ρ k − 3 N 1 i ∑ ( d i + ) 2 d i − = ρ k − 3 β 3 ≤ e − θ ρ k .
It remains to prove the last statement. For x ∈ [ 1 / Δ , ρ ] x\in[1/\Delta,\rho] x ∈ [ 1/Δ , ρ ] , we have the affine bound x 2 ≤ ( ρ + 1 / Δ ) x − ρ / Δ x^2\le(\rho+1/\Delta)x-\rho/\Delta x 2 ≤ ( ρ + 1/Δ ) x − ρ /Δ . We apply this to x = 1 / d i + x=1/d_i^+ x = 1/ d i + and average with weights d i − / N d_i^-/N d i − / N :
β 3 ≤ ( ρ + 1 Δ ) ρ 2 − ρ Δ = ( 1 − 1 / ρ 2 − 1 / ρ Δ ) ρ 3 ≤ ( 1 − δ − δ Δ ) ρ 3 , \beta_3\le\left(\rho+\frac{1}{\Delta}\right)\rho^2-\frac{\rho}{\Delta}=\left(1-\frac{1/\rho^2-1/\rho}{\Delta}\right)\rho^3\le\left(1-\frac{\delta-\sqrt{\delta}}{\Delta}\right)\rho^3, β 3 ≤ ( ρ + Δ 1 ) ρ 2 − Δ ρ = ( 1 − Δ 1/ ρ 2 − 1/ ρ ) ρ 3 ≤ ( 1 − Δ δ − δ ) ρ 3 ,
where the last inequality follows from ρ ≤ 1 / δ \rho\le1/\sqrt{\delta} ρ ≤ 1/ δ . Since ( 1 − x ) ≤ e − x (1-x)\le e^{-x} ( 1 − x ) ≤ e − x , we get
β 3 ≤ exp ( − ( δ − δ ) / Δ ) ρ 3 \beta_3\le\exp\left(-(\delta-\sqrt{\delta})/\Delta\right)\rho^3 β 3 ≤ exp ( − ( δ − δ ) /Δ ) ρ 3
as claimed. □ \square □
Lemma 2.12 (Class weight). If p t ≤ N pt\le\sqrt{N} pt ≤ N , then for the canonical family γ \gamma γ with given a 1 a_1 a 1 and q q q , we have
∣ W ( γ ) ∣ ≤ C ρ p t ( 2 6 Δ 10 n ρ ℓ + 6 ) q ( 3 p t ρ 2 n ) a 1 . |W(\gamma)|\le C\rho^{pt}\left(\frac{2^6\Delta^{10}}{n\rho^{\ell+6}}\right)^q\left(\frac{3pt}{\rho\sqrt{2n}}\right)^{a_1}. ∣ W ( γ ) ∣ ≤ C ρ pt ( n ρ ℓ + 6 2 6 Δ 10 ) q ( ρ 2 n 3 pt ) a 1 .
Proof. Recall the definition of μ ( γ ) \mu(\gamma) μ ( γ ) from (22) . There are p t − r pt-r pt − r matching factors, and a a a distinct edges. In Lemma 2.1, we have b ≤ 6 q b\le6q b ≤ 6 q due to part (2) of Lemma 2.10 . Applying Lemma 2.1 to (25) gives
∣ W ( γ ) ∣ ≤ C 2 6 q ( 3 p t N ) a 1 1 N a + r ∑ i ∈ [ n ] v all distinct ∏ x = 1 v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x . |W(\gamma)|\le C2^{6q}\left(\frac{3pt}{\sqrt{N}}\right)^{a_1}\frac{1}{N^{a+r}}\sum_{\substack{i\in[n]^v\\\text{all distinct}}}\prod_{x=1}^{v}(d_{i_x}^+)^{h_x^+}(d_{i_x}^-)^{h_x^-}(d_{i_x}^+)^{-t_x}. ∣ W ( γ ) ∣ ≤ C 2 6 q ( N 3 pt ) a 1 N a + r 1 i ∈ [ n ] v all distinct ∑ x = 1 ∏ v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x .
Let r x r_x r x be the in-degree of x x x in the augmented support graph. Then
∑ x r x = a + r . \sum_x r_x=a+r. x ∑ r x = a + r .
Dropping the requirement that the vertex labels be distinct gives
1 N a + r ∑ i ∈ [ n ] v all distinct ∏ x = 1 v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x ≤ ∏ x = 1 v 1 N r x ( ∑ i = 1 n ( d i + ) h x + ( d i − ) h x − ( d i + ) − t x ) \frac{1}{N^{a+r}}\sum_{\substack{i\in[n]^v\\\text{all distinct}}}\prod_{x=1}^{v}(d_{i_x}^+)^{h_x^+}(d_{i_x}^-)^{h_x^-}(d_{i_x}^+)^{-t_x}
\le\prod_{x=1}^{v}\frac{1}{N^{r_x}}\left(\sum_{i=1}^{n}(d_i^+)^{h_x^+}(d_i^-)^{h_x^-}(d_i^+)^{-t_x}\right) N a + r 1 i ∈ [ n ] v all distinct ∑ x = 1 ∏ v ( d i x + ) h x + ( d i x − ) h x − ( d i x + ) − t x ≤ x = 1 ∏ v N r x 1 ( i = 1 ∑ n ( d i + ) h x + ( d i − ) h x − ( d i + ) − t x )
Denote
μ x : = 1 N r x ∑ i = 1 n ( d i + ) h x + ( d i − ) h x − ( d i + ) − t x . \mu_x := \frac{1}{N^{r_x}} \sum_{i=1}^{n} (d_i^+)_{h_x^+}(d_i^-)_{h_x^-}(d_i^+)^{-t_x}. μ x := N r x 1 i = 1 ∑ n ( d i + ) h x + ( d i − ) h x − ( d i + ) − t x .
Call a vertex ordinary if it has degree two and has no incident formal edge; then r x = h x + = h x − = 1 r_x=h_x^+=h_x^-=1 r x = h x + = h x − = 1 , and μ x = β t x \mu_x=\beta_{t_x} μ x = β t x . By Lemma 2.11 , if t x = 1 t_x=1 t x = 1 , μ x = 1 \mu_x=1 μ x = 1 and μ x ≤ ρ t x \mu_x\leq\rho^{t_x} μ x ≤ ρ t x if t x ≥ 2 t_x\geq2 t x ≥ 2 . Then the number of ordinary vertices with t x = 1 t_x=1 t x = 1 is bounded by the total number of centered consistent single edges (which is a 1 a_1 a 1 by definition), centered inconsistent single edges (bounded by 6 q 6q 6 q from Lemma 2.10 ) and raw single edges (bounded by ℓ q \ell q ℓ q from Lemma 2.10 ), which is a 1 + ( 6 + ℓ ) q a_1+(6+\ell)q a 1 + ( 6 + ℓ ) q .
All other vertices are called exceptional , including vertices with degree at least three (whose total degree is at most 6 q 6q 6 q from Lemma 2.10 ) and degree-two vertices incident to a formal edge. And for an exceptional x x x ,
μ x ≤ n 1 − r x Δ ρ h x + + h x − ρ t x ≤ n 1 − r x Δ ρ deg ( x ) ρ t x . \mu_x \leq n^{1-r_x\Delta} \rho^{h_x^++h_x^-}\rho^{t_x} \leq n^{1-r_x\Delta}\rho^{\deg(x)}\rho^{t_x}. μ x ≤ n 1 − r x Δ ρ h x + + h x − ρ t x ≤ n 1 − r x Δ ρ d e g ( x ) ρ t x .
Their total degree is at most 6 q + 4 r 6q+4r 6 q + 4 r by Lemma 2.10 . Moreover, we have
∑ x e x c e p t i o n a l 1 − r x = v − ( a + r ) = − q . \sum_{x\ \mathrm{exceptional}} 1-r_x=v-(a+r)=-q. x exceptional ∑ 1 − r x = v − ( a + r ) = − q .
Putting all estimates together, using r ≤ q r\leq q r ≤ q from Lemma 2.9 and N ≥ δ n ≥ 2 n N\geq\delta n\geq2n N ≥ δ n ≥ 2 n ,
∣ W ( γ ) ∣ ≤ C 2 6 q Δ 10 q n − q ρ p t − a 1 − ( 6 + ℓ ) q ( 3 p t 2 n ) a 1 . |W(\gamma)|\leq C2^{6q}\Delta^{10q}n^{-q}\rho^{pt-a_1-(6+\ell)q}\left(\frac{3pt}{\sqrt{2n}}\right)^{a_1}. ∣ W ( γ ) ∣ ≤ C 2 6 q Δ 10 q n − q ρ pt − a 1 − ( 6 + ℓ ) q ( 2 n 3 pt ) a 1 .
as desired. □
Having bounded the weight of a single class, we now count how many classes can have a given excess q q q .
Lemma 2.13 (Canonical count).
∑ a 1 ≥ 0 ∣ F q , a 1 ∣ ≤ ( 2 p t ) 19 p m ( q + 1 ) . (28) \sum_{a_1\geq0}|\mathcal{F}_{q,a_1}|\leq(2pt)^{19pm(q+1)}. \tag*{(28)} a 1 ≥ 0 ∑ ∣ F q , a 1 ∣ ≤ ( 2 pt ) 19 p m ( q + 1 ) . (28)
Proof. We adapt the spanning-tree and cycling-time encoding of [6 , 15 ] . Our support may be disconnected, so we use a spanning forest. We record the support and the omitted edges first, then describe each tangle-free path by its crossings outside the spanning forest and its repeated turns around a cycle. Finally, we specify the half-edge identifications.
The support: at most 9 q + 3 p 9q+3p 9 q + 3 p integers. For any γ ∈ F q , a 1 \gamma\in\mathcal{F}_{q,a_1} γ ∈ F q , a 1 , explore { γ i j , i ∈ [ p ] , j ∈ [ m ] } \{\gamma_{ij},i\in[p],j\in[m]\} { γ ij , i ∈ [ p ] , j ∈ [ m ]} in lexicographic order as in Definition 2.7 . Number the vertices in the order of first visit from 1 1 1 to v v v . Number the edges in the order of first visit from 1 1 1 to a + r a+r a + r . Number the maximal non-branching paths in the order of the smallest edge label within the path. By Lemma 2.10 , there are at most 3 q + p 3q+p 3 q + p maximal non-branching paths. Reserve 3 q + p 3q+p 3 q + p slots for triples
( initial branch vertex , final branch vertex , length ) . (\text{initial branch vertex},\ \text{final branch vertex},\ \text{length}). ( initial branch vertex , final branch vertex , length ) .
List the actual maximal non-branching paths in their assigned order and fill unused slots with ( 0 , 0 , 0 ) (0,0,0) ( 0 , 0 , 0 ) .
The block types, cuts, and formal edges: 2 p m 2pm 2 p m integers. For each block, record
{ ( 0 , 0 ) , if it is ordinary , ( k i j , index assigned to the edge at the omitted step ) , if it is a remainder . \begin{cases}
(0,0), & \text{if it is ordinary},\\
(k_{ij},\ \text{index assigned to the edge at the omitted step}), & \text{if it is a remainder}.
\end{cases} { ( 0 , 0 ) , ( k ij , index assigned to the edge at the omitted step ) , if it is ordinary , if it is a remainder .
The first entry distinguishes the block types and specifies the cut when present; the second locates the formal edge. This uses two integers per block, hence 2 p m 2pm 2 p m in total.
3. Spanning trees and cycling times: at most 2 p m ( 2 q + 5 ) 2pm(2q+5) 2 p m ( 2 q + 5 ) integers. Start with all support vertices and no edges. Process the support edges in their assigned order, ignoring orientations. Add an edge if it does not create a cycle; otherwise, skip it. The resulting spanning forest T T T has one tree in each connected component and is uniquely determined. In a connected component H H H , exactly g ( H ) g(H) g ( H ) edges lie outside T T T . Since
q = ∑ H ( ∣ E ( H ) ∣ − ∣ V ( H ) ∣ ) = ∑ H ( g ( H ) − 1 ) , q=\sum_H\left(|E(H)|-|V(H)|\right)=\sum_H\left(g(H)-1\right), q = H ∑ ( ∣ E ( H ) ∣ − ∣ V ( H ) ∣ ) = H ∑ ( g ( H ) − 1 ) ,
we have g ( H ) ≤ q + 1 g(H)\le q+1 g ( H ) ≤ q + 1 for every connected component in the augmented support graph.
For each ordinary block, consider its whole path. For each remainder block ( i , j ) (i,j) ( i , j ) , consider the paths formed by its first k i j − 1 k_{ij}-1 k ij − 1 and last ℓ j − k i j \ell_j-k_{ij} ℓ j − k ij steps. There are p m + r ≤ 2 p m pm+r\le2pm p m + r ≤ 2 p m such indexed tangle-free paths, ordered by block and then by their position in the block.
Denote one of these paths by γ \gamma γ . Its length is determined by the block type and cut. If γ \gamma γ is not simple, tangle-freeness implies that its support has exactly one unoriented cycle. Deleting any edge outside this cycle disconnects the support, and we call such an edge a bridge. After crossing a bridge, a directed walk cannot return to the connected component it left, since this would require traversing the same edge in the opposite direction. Thus
γ = γ i n c ν c ′ γ o u t , ν ≥ 1 , 0 ≤ ∣ c ′ ∣ < ∣ c ∣ , \gamma=\gamma_{\mathrm{in}}\mathbf{c}^{\nu}\mathbf{c}'\gamma_{\mathrm{out}},\qquad\nu\ge1,\qquad0\le|\mathbf{c}'|<|\mathbf{c}|, γ = γ in c ν c ′ γ out , ν ≥ 1 , 0 ≤ ∣ c ′ ∣ < ∣ c ∣ ,
where γ i n \gamma_{\mathrm{in}} γ in and γ o u t \gamma_{\mathrm{out}} γ out are simple, possibly empty paths containing no cycle edges, c \mathbf{c} c is the directed cycle based at the entry vertex visited ν \nu ν times, and c ′ \mathbf{c}' c ′ is an initial segment of c \mathbf{c} c . Delete the extra complete turns and set
γ ^ = γ i n c c ′ γ o u t . \widehat{\gamma}=\gamma_{\mathrm{in}}\mathbf{c}\mathbf{c}'\gamma_{\mathrm{out}}. γ = γ in c c ′ γ out .
Every edge of γ ^ \widehat{\gamma} γ is traversed at most twice: edges outside the cycle are traversed once, while cycle edges are traversed once in c \mathbf{c} c and possibly once more in c ′ \mathbf{c}' c ′ .
For a simple or empty path, set γ ^ = γ \widehat{\gamma}=\gamma γ = γ instead. No additional cycle records are needed: the reconstruction below restores the deleted turns from the compressed path and the original length, which is fixed by the block type and cut.
We now encode γ ^ \widehat{\gamma} γ using T T T . A cycling time relative to T T T is a time when the path traverses an edge outside T T T . Record the initial and final vertex indices of γ ^ \widehat{\gamma} γ , the number of times it traverses an edge outside T T T , and the indices of these edges in traversal order. Record repeated traversals of the same edge separately. There are at most q + 1 q+1 q + 1 edges outside T T T in its component, and each is traversed at most twice. Thus the list has at most 2 ( q + 1 ) 2(q+1) 2 ( q + 1 ) entries.
These records determine γ ^ \widehat{\gamma} γ . Starting at its initial vertex, follow the unique tree path to the initial vertex of the first listed edge, traverse that edge, and continue in the same way through the list. After the last listed edge, follow the unique tree path to the recorded final vertex. If the list is empty, follow the tree path between the two recorded vertices. Thus one indexed path uses at most
2 ⏟ initial and final vertices + 1 ⏟ list length + 2 ( q + 1 ) ⏟ list entries = 2 q + 5 \underbrace{2}_{\text{initial and final vertices}}+\underbrace{1}_{\text{list length}}+\underbrace{2(q+1)}_{\text{list entries}}=2q+5 initial and final vertices 2 + list length 1 + list entries 2 ( q + 1 ) = 2 q + 5
integers. The at most 2 p m 2pm 2 p m indexed paths therefore use at most 2 p m ( 2 q + 5 ) 2pm(2q+5) 2 p m ( 2 q + 5 ) integers.
4. The half-edge identifications: at most 6 q 6q 6 q integers. The preceding records specify the support edges traversed by each path, but not which distinct outgoing edges share a head or which distinct incoming edges share a tail.
At each vertex of degree at least three, number the distinct heads and tails separately, starting from one in order of first appearance. For each outgoing or incoming edge, record its head or tail number accordingly. Equal numbers specify a shared half-edge. This uses one integer per outgoing edge and one per incoming edge at a vertex of degree at least three. Thus the cost is at most
∑ deg x ≥ 3 deg x ≤ 6 q . (29) \sum_{\deg x\ge3}\deg x\le6q. \tag*{(29)} d e g x ≥ 3 ∑ deg x ≤ 6 q . (29)
Reconstruction. First expand the nonzero support records into directed paths and cycles. The block records identify the formal edges, and the edge indices in the support determine T T T . For each indexed path, its endpoints and list of edges traversed outside T T T recover γ ^ \widehat{\gamma} γ by the unique tree paths.
If γ ^ \widehat{\gamma} γ is simple, no turns were deleted, because the compression keeps one complete turn whenever a cycle is present. Otherwise, its first repeated vertex identifies the cycle c c c and its entry point. The original length ∣ γ ∣ |\gamma| ∣ γ ∣ is known from the block data, so insert ⌊ ∣ γ ∣ − ∣ γ ^ ∣ ∣ c ∣ ⌋ \left\lfloor\frac{|\gamma|-|\widehat{\gamma}|}{|c|}\right\rfloor ⌊ ∣ c ∣ ∣ γ ∣ − ∣ γ ∣ ⌋ additional complete turns at that entry point to recover γ \gamma γ . Join the two paths of each remainder block through its formal edge, and apply the head and tail identifications from Step 4. Thus every valid record list determines a unique canonical family.
Counting the records. The total number of integers is at most
( 9 q + 3 p ) + 2 p m + 2 p m ( 2 q + 5 ) + 6 q ≤ 19 p m ( q + 1 ) , (9q+3p)+2pm+2pm(2q+5)+6q\le19pm(q+1), ( 9 q + 3 p ) + 2 p m + 2 p m ( 2 q + 5 ) + 6 q ≤ 19 p m ( q + 1 ) ,
The support has at most p t pt pt edges and vertices, so every vertex, edge, and half-edge identification index is at most p t pt pt . Cuts and the lengths of the lists of edges traversed outside T T T are also at most p t pt pt . Including zero for unused records, each integer therefore has at most p t + 1 ≤ 2 p t pt+1\le2pt pt + 1 ≤ 2 pt possible values. Since distinct canonical families have distinct integer sequences, this proves (28) . □
Figure 1 illustrates the encoding for two traces according to Lemma 2.13.
Figure 1. Encoding two traces with p = 2 p=2 p = 2 , m = 2 m=2 m = 2 , ℓ = 4 \ell=4 ℓ = 4 , and t = 8 t=8 t = 8 : ( 1 , 2 , 3 , 4 , 5 ) ∣ ( 5 , 6 , 3 , 2 , 1 ) (1,2,3,4,5)\mid(5,6,3,2,1) ( 1 , 2 , 3 , 4 , 5 ) ∣ ( 5 , 6 , 3 , 2 , 1 ) and ( 2 , 3 , 2 , 1 , 2 ) ∣ ( 2 , 1 , 2 , 1 , 2 ) (2,3,2,1,2)\mid(2,1,2,1,2) ( 2 , 3 , 2 , 1 , 2 ) ∣ ( 2 , 1 , 2 , 1 , 2 ) , where bars separate blocks. The only remainder block is γ 21 \gamma_{21} γ 21 , with k 21 = 2 k_{21}=2 k 21 = 2 . The matching factor at 3 → 2 3\to2 3 → 2 is omitted, leaving the tangle-free paths 2 → 3 2\to3 2 → 3 and 2 → 1 → 2 2\to1\to2 2 → 1 → 2 . In (a), the blue edge e 9 e_9 e 9 records this omitted step; it is distinct from e 7 e_7 e 7 but uses the same head and tail. Thus a = 8 a=8 a = 8 , r = 1 r=1 r = 1 , v = 6 v=6 v = 6 , and q = 3 q=3 q = 3 . Open circles are the trace starting vertices; the red edges and e 9 e_9 e 9 lie outside the spanning tree T = { e 1 , e 2 , e 3 , e 4 , e 5 } T=\{e_1,e_2,e_3,e_4,e_5\} T = { e 1 , e 2 , e 3 , e 4 , e 5 } . In (b), each arrow represents a maximal non-branching path labelled by its length. Panel (c) shows the half-edge labels at vertex 2, with heads and tails numbered separately: e 2 , e 8 e_2,e_8 e 2 , e 8 share a head and e 7 , e 9 e_7,e_9 e 7 , e 9 share a tail. In (d), deleting one complete turn from γ 22 = ( 2 , 1 , 2 , 1 , 2 ) \gamma_{22}=(2,1,2,1,2) γ 22 = ( 2 , 1 , 2 , 1 , 2 ) gives γ ^ 22 = ( 2 , 1 , 2 ) \widehat{\gamma}_{22}=(2,1,2) γ 22 = ( 2 , 1 , 2 ) .
We combine Lemmas 2.12 and 2.13 to control the classes with q + a 1 ≥ 1 q+a_1\ge1 q + a 1 ≥ 1 .
Lemma 2.14 (Error sum). For t , ℓ t,\ell t , ℓ in {(xref)}(1.7)–{(xref)}(2.9) and any fixed positive integer p p p , the following holds:
∑ q , a 1 ≥ 0 q + a 1 ≥ 1 ∑ γ ∈ F q , a 1 ∣ W ( γ ) ∣ ≤ 24 C p t Δ n ( 2 p t ) 19 p m = o ( ρ p t ) . (30) \sum_{\substack{q,a_1\geq0\\q+a_1\geq1}}\sum_{\gamma\in\mathcal{F}_{q,a_1}} |W(\gamma)| \leq\frac{24Cpt\sqrt{\Delta}}{\sqrt{n}}(2pt)^{19pm}=o(\rho^{pt}). \tag*{(30)} q , a 1 ≥ 0 q + a 1 ≥ 1 ∑ γ ∈ F q , a 1 ∑ ∣ W ( γ ) ∣ ≤ n 24 C pt Δ ( 2 pt ) 19 p m = o ( ρ pt ) . (30)
Proof. Since N ≥ 2 n N\geq2n N ≥ 2 n , the parameter choice {(xref)}(1.7) gives
p t = O p ( ( log n ) 2 ) = o ( N ) , and Δ ℓ ≤ n 1 / 8 . pt=O_p\left((\log n)^2\right)=o(\sqrt{N}), \qquad\text{and} \qquad\Delta^\ell\leq n^{1/8}. pt = O p ( ( log n ) 2 ) = o ( N ) , and Δ ℓ ≤ n 1/8 .
Also, since m = o ( log n / log log n ) m=o(\log n/\log\log n) m = o ( log n / log log n ) from {(xref)}(2.10), we find
p m log ( 2 p t ) = o ( log n ) . (31) pm\log(2pt)=o(\log n). \tag*{(31)} p m log ( 2 pt ) = o ( log n ) . (31)
Thus ( 2 p t ) p m = n o ( 1 ) (2pt)^{pm}=n^{o(1)} ( 2 pt ) p m = n o ( 1 ) . By {(xref)}(1.3), ρ 2 ≥ Δ − 1 \rho^2\geq\Delta^{-1} ρ 2 ≥ Δ − 1 . Together with Δ ℓ ≤ n 1 / 8 \Delta^\ell\leq n^{1/8} Δ ℓ ≤ n 1/8 , this gives
2 6 Δ 10 n ρ ℓ + 6 ≤ 2 6 Δ 13 n 15 / 16 . \frac{2^6\Delta^{10}}{n\rho^{\ell+6}}\leq\frac{2^6\Delta^{13}}{n^{15/16}}. n ρ ℓ + 6 2 6 Δ 10 ≤ n 15/16 2 6 Δ 13 .
Multiplying Lemmas 2.12 and 2.13 therefore yields, for every q , a 1 ≥ 0 q,a_1\geq0 q , a 1 ≥ 0 ,
ρ − p t ∑ γ ∈ F q , a 1 ∣ W ( γ ) ∣ ≤ C ( 2 p t ) 19 p m ( q + 1 ) ( 2 6 Δ 13 n 15 / 16 ) q ( 3 p t Δ 2 n ) a 1 . (32) \rho^{-pt}\sum_{\gamma\in\mathcal{F}_{q,a_1}}|W(\gamma)|\leq C(2pt)^{19pm(q+1)}\left(\frac{2^6\Delta^{13}}{n^{15/16}}\right)^q\left(\frac{3pt\sqrt{\Delta}}{\sqrt{2n}}\right)^{a_1}. \tag*{(32)} ρ − pt γ ∈ F q , a 1 ∑ ∣ W ( γ ) ∣ ≤ C ( 2 pt ) 19 p m ( q + 1 ) ( n 15/16 2 6 Δ 13 ) q ( 2 n 3 pt Δ ) a 1 . (32)
Set
u = 2 6 Δ 13 ( 2 p t ) 19 p m n 15 / 16 , v = 3 p t Δ 2 n . u=\frac{2^6\Delta^{13}(2pt)^{19pm}}{n^{15/16}},\qquad v=\frac{3pt\sqrt{\Delta}}{\sqrt{2n}}. u = n 15/16 2 6 Δ 13 ( 2 pt ) 19 p m , v = 2 n 3 pt Δ .
Then from {(xref)}(2.22) and the condition Δ = n o ( 1 ) \Delta=n^{o(1)} Δ = n o ( 1 ) , for sufficiently large n n n ,
0 < u ≤ v = n − 1 / 2 + o ( 1 ) ≤ 1 / 2 , 0<u\leq v=n^{-1/2+o(1)}\leq1/2, 0 < u ≤ v = n − 1/2 + o ( 1 ) ≤ 1/2 ,
and the bound for fixed ( q , a 1 ) (q,a_1) ( q , a 1 ) for the right hand side of {(xref)}(2.23) is C ( 2 p t ) 19 p m u q v a 1 C(2pt)^{19pm}u^qv^{a_1} C ( 2 pt ) 19 p m u q v a 1 . By the geometric sum,
∑ q , a 1 ≥ 0 q + a 1 ≥ 1 u q v a 1 = ( ∑ q ≥ 0 u q ) ( ∑ a 1 ≥ 0 v a 1 ) − 1 = 1 ( 1 − u ) ( 1 − v ) − 1 = u + v − u v ( 1 − u ) ( 1 − v ) ≤ 8 v . \sum_{\substack{q,a_1\geq0\\q+a_1\geq1}}u^qv^{a_1}=\left(\sum_{q\geq0}u^q\right)\left(\sum_{a_1\geq0}v^{a_1}\right)-1=\frac{1}{(1-u)(1-v)}-1=\frac{u+v-uv}{(1-u)(1-v)}\leq8v. q , a 1 ≥ 0 q + a 1 ≥ 1 ∑ u q v a 1 = ( q ≥ 0 ∑ u q ) ( a 1 ≥ 0 ∑ v a 1 ) − 1 = ( 1 − u ) ( 1 − v ) 1 − 1 = ( 1 − u ) ( 1 − v ) u + v − uv ≤ 8 v .
Therefore the left hand side of {(xref)}(2.23) satisfies
ρ − p t ∑ q , a 1 ≥ 0 q + a 1 ≥ 1 ∑ γ ∈ F q , a 1 ∣ W ( γ ) ∣ ≤ 24 C p t Δ ( 2 p t ) 19 p m n = o ( 1 ) . \rho^{-pt}\sum_{\substack{q,a_1\geq0\\q+a_1\geq1}}\sum_{\gamma\in\mathcal{F}_{q,a_1}}|W(\gamma)|\leq\frac{24Cpt\sqrt{\Delta}(2pt)^{19pm}}{\sqrt{n}}=o(1). ρ − pt q , a 1 ≥ 0 q + a 1 ≥ 1 ∑ γ ∈ F q , a 1 ∑ ∣ W ( γ ) ∣ ≤ n 24 C pt Δ ( 2 pt ) 19 p m = o ( 1 ) .
This proves {(xref)}(2.21). □
The leading term
Lemma 2.14 and {(xref)}(2.18) give, for every fixed positive integer p p p ,
E X ℓ , t p = ∑ γ ∈ F 0 , 0 W ( γ ) + o ( ρ p t ) . (33) \mathbb{E}X_{\ell,t}^p=\sum_{\gamma\in\mathcal{F}_{0,0}}W(\gamma)+o(\rho^{pt}). \tag*{(33)} E X ℓ , t p = γ ∈ F 0 , 0 ∑ W ( γ ) + o ( ρ pt ) . (33)
When q = 0 q=0 q = 0 , every vertex in the canonical family γ \gamma γ has in-degree and out-degree one in the augmented support, so each connected component is a directed cycle with r = 0 r=0 r = 0 and all matching factors are centered. All edges are consistent, because each vertex has only one incoming and one outgoing edge. Since a 1 = 0 a_1=0 a 1 = 0 , every edge has multiplicity at least two. Each trace lies in one cycle component. Let Q Q Q be the resulting partition of [ p ] [p] [ p ] : a set A ∈ Q A \in Q A ∈ Q contains the indices of the traces following the same cycle. If this cycle has length j A j_A j A , then
j A ∣ t , t A = t ∣ A ∣ j A ≥ 2 , a = ∑ A ∈ Q j A ≤ p t 2 . j_A \mid t,\qquad t_A=\frac{t|A|}{j_A}\ge2,\qquad a=\sum_{A\in Q}j_A\le\frac{pt}{2}. j A ∣ t , t A = j A t ∣ A ∣ ≥ 2 , a = A ∈ Q ∑ j A ≤ 2 pt .
Here t A t_A t A is the multiplicity of every edge in that cycle, and a a a is the total number of distinct edges. For all γ ∈ F 0 , 0 \gamma\in\mathcal{F}_{0,0} γ ∈ F 0 , 0 , with a given Q , j = ( j A ) A ∈ Q Q,\mathbf{j}=(j_A)_{A\in Q} Q , j = ( j A ) A ∈ Q , Lemma 2.1 gives for some ε Q , j \varepsilon_{Q,\mathbf{j}} ε Q , j depending on Q , j Q,\mathbf{j} Q , j ,
μ ( γ ) = 1 + ε Q , j ( N ) a , ∣ ε Q , j ∣ ≤ 2 p t N . \mu(\gamma)=\frac{1+\varepsilon_{Q,\mathbf{j}}}{(N)_a},\qquad|\varepsilon_{Q,\mathbf{j}}|\le\frac{2pt}{N}. μ ( γ ) = ( N ) a 1 + ε Q , j , ∣ ε Q , j ∣ ≤ N 2 pt .
Consider the traces following the same cycles in A A A . Since their starting vertices can be different, there are j A ∣ A ∣ − 1 j_A^{|A|-1} j A ∣ A ∣ − 1 choices for their relative starting locations. List the actual vertices of this cycle in directed order, starting at the initial vertex of the trace corresponding to the minimal index in A A A :
i A , 1 → ⋯ → i A , j A → i A , 1 . i_{A,1}\to\cdots\to i_{A,j_A}\to i_{A,1}. i A , 1 → ⋯ → i A , j A → i A , 1 .
Choose distinct values of i A , u i_{A,u} i A , u , A ∈ Q A\in Q A ∈ Q , 1 ≤ u ≤ j A 1\le u\le j_A 1 ≤ u ≤ j A determines the labeling of all γ ∈ F 0 , 0 \gamma\in\mathcal{F}_{0,0} γ ∈ F 0 , 0 . Then we have the following full expansion:
∑ γ ∈ F 0 , 0 W ( γ ) = ∑ Q partition of [ p ] ∑ j = ( j A ) A ∈ Q j A ∣ t , t ∣ A ∣ / j A ≥ 2 1 + ε Q , j ( N ) a ∏ A ∈ Q j A ∣ A ∣ − 1 × ∑ ( i A , u ) ∈ [ n ] a all distinct ∏ A ∈ Q ∏ u = 1 j A d i A , u − ( d i A , u + ) t A − 1 . (34) \begin{aligned}
\sum_{\gamma\in\mathcal{F}_{0,0}}W(\gamma)
&=\sum_{\substack{Q\text{ partition of }[p]}}\ \sum_{\substack{\mathbf{j}=(j_A)_{A\in Q}\\ j_A\mid t,\ t|A|/j_A\ge2}}
\frac{1+\varepsilon_{Q,\mathbf{j}}}{(N)_a}
\prod_{A\in Q}j_A^{|A|-1}\\
&\qquad\qquad\times
\sum_{\substack{(i_{A,u})\in[n]^a\\\text{all distinct}}}
\prod_{A\in Q}\prod_{u=1}^{j_A}
\frac{d_{i_{A,u}}^-}{(d_{i_{A,u}}^+)^{t_A-1}}. \tag*{(34)}
\end{aligned} γ ∈ F 0 , 0 ∑ W ( γ ) = Q partition of [ p ] ∑ j = ( j A ) A ∈ Q j A ∣ t , t ∣ A ∣/ j A ≥ 2 ∑ ( N ) a 1 + ε Q , j A ∈ Q ∏ j A ∣ A ∣ − 1 × ( i A , u ) ∈ [ n ] a all distinct ∑ A ∈ Q ∏ u = 1 ∏ j A ( d i A , u + ) t A − 1 d i A , u − . (34)
We now evaluate the pairings of traces on cycles of length t t t and show that all other cycle arrangements are negligible.
Lemma 2.15 (Gaussian moments). For t , ℓ t,\ell t , ℓ as in (7) –(17) , Δ = n o ( 1 ) \Delta=n^{o(1)} Δ = n o ( 1 ) , and any fixed positive integer p p p ,
E ( X ℓ , t t ρ t ) p ⟶ { ( p − 1 ) ! ! , p even , 0 , p odd . (35) \mathbb{E}\left(\frac{X_{\ell,t}}{\sqrt{t\rho^t}}\right)^p
\longrightarrow
\begin{cases}
(p-1)!!, & p\text{ even},\\
0, & p\text{ odd}.
\end{cases} \tag*{(35)} E ( t ρ t X ℓ , t ) p ⟶ { ( p − 1 )!! , 0 , p even , p odd . (35) Therefore
X ℓ , t t ρ t ⟹ N ( 0 , 1 ) . \frac{X_{\ell,t}}{\sqrt{t\rho^t}}\Longrightarrow\mathcal{N}(0,1). t ρ t X ℓ , t ⟹ N ( 0 , 1 ) .
Proof. Since p p p is fixed and t = O ( ( log n ) 2 ) t=O((\log n)^2) t = O (( log n ) 2 ) , we have p t = o ( N ) pt=o(\sqrt{N}) pt = o ( N ) . From (11) , uniformly for a ≤ p t / 2 a\le pt/2 a ≤ pt /2 ,
N a ( N ) a = 1 + o ( 1 ) . (36) \frac{N^a}{(N)_a}=1+o(1). \tag*{(36)} ( N ) a N a = 1 + o ( 1 ) . (36)
Leading terms. For even p p p , choose a pairing Q Q Q , that is, a partition of [ p ] [p] [ p ] into p / 2 p/2 p /2 sets of size two. Set j A = t j_A=t j A = t for every pair A ∈ Q A\in Q A ∈ Q . The two traces in each pair traverse their common cycle once, so every edge is used twice:
t A = t ∣ A ∣ j A = 2 t t = 2 , a = ∑ A ∈ Q j A = p t 2 . t_A=\frac{t|A|}{j_A}=\frac{2t}{t}=2,\qquad a=\sum_{A\in Q}j_A=\frac{pt}{2}. t A = j A t ∣ A ∣ = t 2 t = 2 , a = A ∈ Q ∑ j A = 2 pt .
All pairings with each trace traversing a cycle of length t t t give the leading term in (34) . Enumerate the labels of these a a a cycle vertices as i 1 , … , i a i_1,\ldots,i_a i 1 , … , i a . Since t A − 1 = 1 t_A-1=1 t A − 1 = 1 , the degree sum in (34) for this pairing is
∑ ( i 1 , … , i a ) ∈ [ n ] a all distinct ∏ u = 1 a d i u − d i u + . \sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\\text{all distinct}}}\prod_{u=1}^{a}\frac{d_{i_u}^-}{d_{i_u}^+}. ( i 1 , … , i a ) ∈ [ n ] a all distinct ∑ u = 1 ∏ a d i u + d i u − .
If we drop the distinct-label restriction, each label ranges independently over [ n ] [n] [ n ] , and the sum factors:
∑ i 1 = 1 n ⋯ ∑ i a = 1 n ∏ u = 1 a d i u − d i u + = ∏ u = 1 a ( ∑ i = 1 n d i − d i + ) = ( N ρ 2 ) a . \sum_{i_1=1}^{n}\cdots\sum_{i_a=1}^{n}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}=\prod_{u=1}^{a}\left(\sum_{i=1}^{n}\frac{d_i^{-}}{d_i^{+}}\right)=(N\rho^2)^a. i 1 = 1 ∑ n ⋯ i a = 1 ∑ n u = 1 ∏ a d i u + d i u − = u = 1 ∏ a ( i = 1 ∑ n d i + d i − ) = ( N ρ 2 ) a .
We now show that imposing distinctness changes this sum by a relative o ( 1 ) o(1) o ( 1 ) . Assumption (3) gives
max i d i − d i + 1 N ρ 2 ≤ Δ δ N ≤ Δ n . \max_i\frac{d_i^{-}}{d_i^{+}}\frac{1}{N\rho^2}\leq\frac{\Delta\delta}{N}\leq\frac{\Delta}{n}. i max d i + d i − N ρ 2 1 ≤ N Δ δ ≤ n Δ .
Every tuple excluded by the distinct-label restriction satisfies i s = i s ′ i_s=i_{s'} i s = i s ′ for some 1 ≤ s < s ′ ≤ a 1\leq s<s'\leq a 1 ≤ s < s ′ ≤ a . Since all summands are nonnegative,
0 ≤ ( N ρ 2 ) a − ∑ ( i 1 , … , i a ) ∈ [ n ] a all distinct ∏ u = 1 a d i u − d i u + ≤ ∑ 1 ≤ s < s ′ ≤ a ∑ ( i 1 , … , i a ) ∈ [ n ] a i s = i s ′ ∏ u = 1 a d i u − d i u + . 0\leq(N\rho^2)^a-\sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\\text{all distinct}}}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}
\leq\sum_{1\leq s<s'\leq a}\ \sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\i_s=i_{s'}}}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}. 0 ≤ ( N ρ 2 ) a − ( i 1 , … , i a ) ∈ [ n ] a all distinct ∑ u = 1 ∏ a d i u + d i u − ≤ 1 ≤ s < s ′ ≤ a ∑ ( i 1 , … , i a ) ∈ [ n ] a i s = i s ′ ∑ u = 1 ∏ a d i u + d i u − .
For each pair s < s ′ s<s' s < s ′ , the two equal labels contribute a squared factor, while the other a − 2 a-2 a − 2 labels can be summed separately:
∑ ( i 1 , … , i a ) ∈ [ n ] a i s = i s ′ ∏ u = 1 a d i u − d i u + = ( N ρ 2 ) a − 2 ∑ i = 1 n ( d i − d i + ) 2 ≤ ( N ρ 2 ) a − 1 max i d i − d i + ≤ Δ n ( N ρ 2 ) a . \sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\i_s=i_{s'}}}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}=(N\rho^2)^{a-2}\sum_{i=1}^{n}\left(\frac{d_i^{-}}{d_i^{+}}\right)^2\leq(N\rho^2)^{a-1}\max_i\frac{d_i^{-}}{d_i^{+}}\leq\frac{\Delta}{n}(N\rho^2)^a. ( i 1 , … , i a ) ∈ [ n ] a i s = i s ′ ∑ u = 1 ∏ a d i u + d i u − = ( N ρ 2 ) a − 2 i = 1 ∑ n ( d i + d i − ) 2 ≤ ( N ρ 2 ) a − 1 i max d i + d i − ≤ n Δ ( N ρ 2 ) a .
Summing over the ( a 2 ) \binom{a}{2} ( 2 a ) pairs gives
0 ≤ 1 − ∑ ( i 1 , … , i a ) ∈ [ n ] a all distinct ∏ u = 1 a d i u − d i u + ( N ρ 2 ) a ≤ ( a 2 ) Δ n = o ( 1 ) . 0\leq1-\frac{\sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\\text{all distinct}}}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}}{(N\rho^2)^a}\leq\binom{a}{2}\frac{\Delta}{n}=o(1). 0 ≤ 1 − ( N ρ 2 ) a ∑ ( i 1 , … , i a ) ∈ [ n ] a all distinct ∏ u = 1 a d i u + d i u − ≤ ( 2 a ) n Δ = o ( 1 ) .
By (36) and the matching error bound, the contribution of this fixed pairing is
1 + ε Q , j t p / 2 ( N ) a ∑ ( i 1 , … , i a ) ∈ [ n ] a all distinct ∏ u = 1 a d i u − d i u + = t p / 2 ρ p t ( 1 + o ( 1 ) ) . \frac{1+\varepsilon_{Q,j}t^{p/2}}{(N)_a}\sum_{\substack{(i_1,\ldots,i_a)\in[n]^a\\\text{all distinct}}}\prod_{u=1}^{a}\frac{d_{i_u}^{-}}{d_{i_u}^{+}}=t^{p/2}\rho^{pt}(1+o(1)). ( N ) a 1 + ε Q , j t p /2 ( i 1 , … , i a ) ∈ [ n ] a all distinct ∑ u = 1 ∏ a d i u + d i u − = t p /2 ρ pt ( 1 + o ( 1 )) .
There are ( p − 1 ) ! ! (p-1)!! ( p − 1 )!! such pairings when p p p is even, and zero when p p p is odd.
All other terms. For any given Q \mathcal{Q} Q , dropping label distinctness in a term of (34) factors its degree sum as
∏ A ∈ Q ( ∑ i d i − ( d i + ) t A − 1 ) j A = N a ∏ A ∈ Q β t A j A . \prod_{A\in\mathcal{Q}}\left(\sum_i\frac{d_i^{-}}{(d_i^{+})^{t_A-1}}\right)^{j_A}=N^a\prod_{A\in\mathcal{Q}}\beta_{t_A}^{j_A}. A ∈ Q ∏ ( i ∑ ( d i + ) t A − 1 d i − ) j A = N a A ∈ Q ∏ β t A j A .
Together with (36) , this bounds the absolute value of the contribution for a given Q \mathcal{Q} Q in (34) by
∑ j = ( j A ) A ∈ Q j A ∣ t , ∣ A ∣ t / j A ≥ 2 2 ∏ A ∈ Q j A ∣ A ∣ − 1 β t A j A (37) \sum_{\substack{\mathbf{j}=(j_A)_{A\in\mathcal{Q}}\\j_A\mid t,\ |A|t/j_A\geq2}}2\prod_{A\in\mathcal{Q}}j_A^{|A|-1}\beta_{t_A}^{j_A} \tag*{(37)} j = ( j A ) A ∈ Q j A ∣ t , ∣ A ∣ t / j A ≥ 2 ∑ 2 A ∈ Q ∏ j A ∣ A ∣ − 1 β t A j A (37)
for sufficiently large n n n .
In (35) , E X ℓ , t p \mathbb{E}X_{\ell,t}^{p} E X ℓ , t p is normalized by t p / 2 ρ p t t^{p/2}\rho^{pt} t p /2 ρ pt . Since ∑ A ∈ Q ∣ A ∣ = p \sum_{A\in\mathcal{Q}}|A|=p ∑ A ∈ Q ∣ A ∣ = p , this normalization factors as
t p / 2 ρ p t = ∏ A ∈ Q t ∣ A ∣ / 2 ρ t ∣ A ∣ . t^{p/2}\rho^{pt}=\prod_{A\in\mathcal{Q}}t^{|A|/2}\rho^{t|A|}. t p /2 ρ pt = A ∈ Q ∏ t ∣ A ∣/2 ρ t ∣ A ∣ .
We may therefore divide the factor for a cycle followed by b b b traces by t b / 2 ρ b t t^{b/2}\rho^{bt} t b /2 ρ b t , and then multiply these normalized factors over all cycles in (34) .
We now separate the remaining terms into two cases.
(i) Q Q Q is a pairing , but at least one j A < t j_A < t j A < t . Here p p p is even and every cycle is followed by two traces. For the shorter cycles, define their normalized contribution by
s 2 = 1 t ρ 2 t ∑ j ∣ t j < t j β 2 t / j j . s_2 = \frac{1}{t\rho^{2t}} \sum_{\substack{j\mid t \\ j<t}} j\beta^{j}_{2t/j}. s 2 = t ρ 2 t 1 j ∣ t j < t ∑ j β 2 t / j j .
A proper divisor j j j of t t t satisfies j ≤ t / 2 j \le t/2 j ≤ t /2 , so the multiplicity 2 t / j 2t/j 2 t / j is at least four. Lemma 2.11 gives
j β 2 t / j j ≤ ρ 2 t j e − θ j ≤ θ − 1 ρ 2 t , j\beta^{j}_{2t/j} \le\rho^{2t}j e^{-\theta j} \le\theta^{-1}\rho^{2t}, j β 2 t / j j ≤ ρ 2 t j e − θ j ≤ θ − 1 ρ 2 t ,
where the first inequality uses 1 − x ≤ e − x 1-x\le e^{-x} 1 − x ≤ e − x for x ≥ 0 x\ge0 x ≥ 0 and the last inequality uses e x ≥ x e^x\ge x e x ≥ x for x ≥ 0 x\ge0 x ≥ 0 . Write τ ( t ) \tau(t) τ ( t ) for the number of positive divisors of t t t . We use the standard bound [24 Theorem 315] that τ ( t ) = t o ( 1 ) \tau(t)=t^{o(1)} τ ( t ) = t o ( 1 ) . Hence, since t θ ≥ t 1 / 2 − o ( 1 ) t\theta\ge t^{1/2-o(1)} tθ ≥ t 1/2 − o ( 1 ) from (7) , we get
0 ≤ s 2 ≤ τ ( t ) t θ = o ( 1 ) . 0\le s_2\le\frac{\tau(t)}{t\theta}=o(1). 0 ≤ s 2 ≤ tθ τ ( t ) = o ( 1 ) .
For one pair of traces, separate the length j = t j=t j = t from the shorter lengths. Since β 2 = ρ 2 \beta_2=\rho^2 β 2 = ρ 2 , the sum of its normalized cycle bounds is
∑ j ∣ t j β 2 t / j j t ρ 2 t = t β 2 t t ρ 2 t + s 2 = 1 + s 2 . \sum_{j\mid t}\frac{j\beta^{j}_{2t/j}}{t\rho^{2t}}=\frac{t\beta^t_2}{t\rho^{2t}}+s_2=1+s_2. j ∣ t ∑ t ρ 2 t j β 2 t / j j = t ρ 2 t t β 2 t + s 2 = 1 + s 2 .
Now fix a pairing Q Q Q , which has p / 2 p/2 p /2 pairs. Summing the product of these bounds over the cycle length of each pair gives
∑ ( j A ) A ∈ Q j A ∣ t ∏ A ∈ Q j A β 2 t / j A j A t ρ 2 t = ∏ A ∈ Q ( ∑ j ∣ t j β 2 t / j j t ρ 2 t ) = ( 1 + s 2 ) p / 2 . \sum_{\substack{(j_A)_{A\in Q}\\j_A\mid t}}\prod_{A\in Q}\frac{j_A\beta^{j_A}_{2t/j_A}}{t\rho^{2t}}
=\prod_{A\in Q}\left(\sum_{j\mid t}\frac{j\beta^j_{2t/j}}{t\rho^{2t}}\right)
=(1+s_2)^{p/2}. ( j A ) A ∈ Q j A ∣ t ∑ A ∈ Q ∏ t ρ 2 t j A β 2 t / j A j A = A ∈ Q ∏ j ∣ t ∑ t ρ 2 t j β 2 t / j j = ( 1 + s 2 ) p /2 .
The unique choice j A = t j_A=t j A = t for every pair contributes 1 1 1 to this sum of bounds. Subtracting it leaves precisely the choices with at least one shorter cycle:
( 1 + s 2 ) p / 2 − 1 = o ( 1 ) . (1+s_2)^{p/2}-1=o(1). ( 1 + s 2 ) p /2 − 1 = o ( 1 ) .
Finally, (37) gives the factor 2 2 2 , and there are ( p − 1 ) ! ! (p-1)!! ( p − 1 )!! perfect pairings. Their total normalized absolute contribution with at least one shorter cycle is therefore at most
2 ( p − 1 ) ! ! [ ( 1 + s 2 ) p / 2 − 1 ] = o ( 1 ) . 2(p-1)!!\left[(1+s_2)^{p/2}-1\right]=o(1). 2 ( p − 1 )!! [ ( 1 + s 2 ) p /2 − 1 ] = o ( 1 ) .
(ii) Q Q Q is not a pairing. Such a partition has at least one set A A A with ∣ A ∣ ≠ 2 |A|\ne2 ∣ A ∣ = 2 . For a cycle followed by b ≠ 2 b\ne2 b = 2 traces, define the normalized sum over all its permitted lengths by
s b = 1 t b / 2 ρ b t ∑ j ∣ t b t / j ≥ 2 j b − 1 β b t / j j . s_b=\frac{1}{t^{b/2}\rho^{bt}}\sum_{\substack{j\mid t\\bt/j\ge2}}j^{b-1}\beta^j_{bt/j}. s b = t b /2 ρ b t 1 j ∣ t b t / j ≥ 2 ∑ j b − 1 β b t / j j .
For b = 1 b=1 b = 1 , Lemma 2.11 immediately gives
0 ≤ s 1 ≤ τ ( t ) t = o ( 1 ) . 0\le s_1\le\frac{\tau(t)}{\sqrt{t}}=o(1). 0 ≤ s 1 ≤ t τ ( t ) = o ( 1 ) .
For b ≥ 3 b\ge3 b ≥ 3 , every permitted multiplicity is at least three and Lemma 2.11 gives
j b − 1 β b t / j j ≤ ρ b t j b − 1 e − θ j ≤ ρ b t ( b − 1 ) ! θ − ( b − 1 ) . j^{b-1}\beta^j_{bt/j}\le\rho^{bt}j^{b-1}e^{-\theta j}\le\rho^{bt}(b-1)!\theta^{-(b-1)}. j b − 1 β b t / j j ≤ ρ b t j b − 1 e − θ j ≤ ρ b t ( b − 1 )! θ − ( b − 1 ) .
where the last inequality uses e x ≥ x b − 1 / ( b − 1 ) ! e^x \ge x^{b-1}/(b-1)! e x ≥ x b − 1 / ( b − 1 )! . Summing over the permitted lengths yields, for each fixed b ≥ 3 b \ge3 b ≥ 3 ,
0 ≤ s b ≤ τ ( t ) ( b − 1 ) ! t ( t θ ) − ( b − 1 ) = o ( 1 ) , 0 \le s_b \le\frac{\tau(t)(b-1)!}{\sqrt{t}}(\sqrt{t}\theta)^{-(b-1)} = o(1), 0 ≤ s b ≤ t τ ( t ) ( b − 1 )! ( t θ ) − ( b − 1 ) = o ( 1 ) ,
where we have used b ≤ p b \le p b ≤ p and ( t θ ) − 1 ≤ t o ( 1 ) (\sqrt{t}\theta)^{-1} \le t^{o(1)} ( t θ ) − 1 ≤ t o ( 1 ) . Cycles followed by two traces still have normalized length sum 1 + s 2 1+s_2 1 + s 2 . Thus (37) bounds the total normalized absolute contribution of the partitions in this case by
2 ∑ Q partition of [ p ] Q not a pairing ( ∏ A ∈ Q ∣ A ∣ = 2 ( 1 + s 2 ) ) ( ∏ A ∈ Q ∣ A ∣ ≠ 2 s ∣ A ∣ ) = o ( 1 ) . 2\sum_{\substack{Q\text{ partition of }[p]\\Q\text{ not a pairing}}}
\left(\prod_{\substack{A\in Q\\|A|=2}}(1+s_2)\right)
\left(\prod_{\substack{A\in Q\\|A|\ne2}}s_{|A|}\right)
=o(1). 2 Q partition of [ p ] Q not a pairing ∑ A ∈ Q ∣ A ∣ = 2 ∏ ( 1 + s 2 ) A ∈ Q ∣ A ∣ = 2 ∏ s ∣ A ∣ = o ( 1 ) .
Combining this bound with the leading pairing contribution gives
∑ γ ∈ F 0 , 0 W ( γ ) = t p / 2 ρ p t { ( p − 1 ) ! ! + o ( 1 ) , p even , o ( 1 ) , p odd . \sum_{\gamma\in\mathcal{F}_{0,0}}W(\gamma)
=t^{p/2}\rho^{pt}
\begin{cases}
(p-1)!!+o(1), & p\text{ even},\\
o(1), & p\text{ odd}.
\end{cases} γ ∈ F 0 , 0 ∑ W ( γ ) = t p /2 ρ pt { ( p − 1 )!! + o ( 1 ) , o ( 1 ) , p even , p odd .
Together with (33) , this proves (35) : its error after normalization is o ( t − p / 2 ) = o ( 1 ) o(t^{-p/2})=o(1) o ( t − p /2 ) = o ( 1 ) . Since the Gaussian distribution is determined by its moments, the convergence in distribution holds. □
Bounding the scalar product term
To use (15) , we must show that the scalar product correction z ℓ , t z_{\ell,t} z ℓ , t is negligible at the desired scale. It suffices to bound the second moment of z k z_k z k for 1 ≤ k ≤ ℓ 1\le k\le\ell 1 ≤ k ≤ ℓ .
Lemma 2.16 (Negligible scalar term). Assume Δ = n o ( 1 ) \Delta=n^{o(1)} Δ = n o ( 1 ) . For any integer sequence k = k n k=k_n k = k n with 1 ≤ k ≤ ℓ 1\le k\le\ell 1 ≤ k ≤ ℓ and ℓ \ell ℓ as in (17) ,
z k ρ k ⟶ 0 in probability . (38) \frac{z_k}{\rho^k}\longrightarrow0 \quad\text{in probability}. \tag*{(38)} ρ k z k ⟶ 0 in probability . (38)
Proof. Expansion and the support. Expand the two matrix entries into paths and group by canonical families, as in (26) :
E z k 2 = 1 n 2 ∑ x 1 , y 1 , x 2 , y 2 ∈ [ n ] E Q ( k ) ( x 1 , y 1 ) Q ( k ) ( x 2 , y 2 ) = ∑ γ W ( γ ) . \mathbb{E}z_k^2
=\frac{1}{n^2}\sum_{x_1,y_1,x_2,y_2\in[n]}
\mathbb{E}Q^{(k)}(x_1,y_1)Q^{(k)}(x_2,y_2)
=\sum_{\gamma}W(\gamma). E z k 2 = n 2 1 x 1 , y 1 , x 2 , y 2 ∈ [ n ] ∑ E Q ( k ) ( x 1 , y 1 ) Q ( k ) ( x 2 , y 2 ) = γ ∑ W ( γ ) .
Each family γ \gamma γ now consists of two length-k k k paths γ 1 , γ 2 \gamma_1,\gamma_2 γ 1 , γ 2 , and W ( γ ) W(\gamma) W ( γ ) is given by (25) with the additional factor n − 2 n^{-2} n − 2 .
For this proof, a branch vertex is a vertex of degree at least three or one of the endpoints x 1 , y 1 , x 2 , y 2 x_1,y_1,x_2,y_2 x 1 , y 1 , x 2 , y 2 . Maximal non-branching paths are defined as before. Moreover, a a a counts distinct edges carrying matching factors, r ≤ 2 r\le2 r ≤ 2 counts omitted edges, v v v counts vertices, and a 1 a_1 a 1 counts consistent centered single edges. The augmented support has a + r a+r a + r edges and c c c connected components for 1 ≤ c ≤ 2 1\le c\le2 1 ≤ c ≤ 2 . Define
q = a + r − v + 2 = ∑ H component g ( H ) + 2 − c . q=a+r-v+2=\sum_{H\text{ component}}g(H)+2-c. q = a + r − v + 2 = H component ∑ g ( H ) + 2 − c .
By the same argument as in Lemma 2.9, every connected component with edges from the remainder block contains a cycle. Then the number of tree components is at most ( 2 − r ) (2-r) ( 2 − r ) and a − v ≥ − ( 2 − r ) = r − 2 a-v\ge-(2-r)=r-2 a − v ≥ − ( 2 − r ) = r − 2 . This implies q ≥ 2 r q\ge2r q ≥ 2 r .
If q = 0 q=0 q = 0 , then c = 2 c=2 c = 2 and both components are trees. A directed walk in a tree cannot repeat a vertex, and neither block can be a tangled remainder block. Thus the two paths are disjoint ordinary simple paths, giving one canonical pattern with a 1 = 2 k a_1=2k a 1 = 2 k . Every vertex other than an original path endpoint has positive indegree and outdegree. Hence there are at most four degree-one vertices, at most two vertices with zero indegree, and at most two with zero outdegree. Since ∑ x deg x = 2 ( a + r ) \sum_x \deg x = 2(a+r) ∑ x deg x = 2 ( a + r ) and a + r − v = q − 2 a+r-v=q-2 a + r − v = q − 2 , the degree sums give
∑ deg x ≥ 3 ( deg x − 2 ) = 2 q − 4 + # { x : deg x = 1 } ≤ 2 q . \sum_{\deg x\ge3}(\deg x-2)=2q-4+\#\{x:\deg x=1\}\le2q. d e g x ≥ 3 ∑ ( deg x − 2 ) = 2 q − 4 + # { x : deg x = 1 } ≤ 2 q .
∑ deg ± ( x ) ≥ 2 ( deg ± ( x ) − 1 ) = q − 2 + # { x : deg ± ( x ) = 0 } ≤ q . \sum_{\deg^{\pm}(x)\ge2}(\deg^{\pm}(x)-1)=q-2+\#\{x:\deg^{\pm}(x)=0\}\le q. d e g ± ( x ) ≥ 2 ∑ ( deg ± ( x ) − 1 ) = q − 2 + # { x : deg ± ( x ) = 0 } ≤ q .
The first identity gives at most 2 q 2q 2 q vertices of degree at least three, with total degree at most 6 q 6q 6 q . The second bounds the total indegree at vertices of indegree at least two by 2 q 2q 2 q , and likewise for outdegree. Including the at most four additional endpoints of degree at most two, there are at most 2 q + 4 2q+4 2 q + 4 branch vertices, with total degree at most 6 q + 8 6q+8 6 q + 8 .
Every inconsistent edge uses one of these incoming or outgoing half edges, so there are at most 4 q 4q 4 q such edges. Also, every raw edge belongs to a remainder block; hence there are at most r k ≤ q k rk\le qk r k ≤ q k raw single edges.
Counting and class weights. Use the encoding of Lemma 2.13. The total degree of branch vertices is at most 6 q + 8 6q+8 6 q + 8 , so there are at most 3 q + 4 3q+4 3 q + 4 maximal non-branching paths. Reserve 3 q + 4 3q+4 3 q + 4 triple slots for these paths, as in Step 1 in the proof of Lemma 2.13. There are 3 ( 3 q + 4 ) 3(3q+4) 3 ( 3 q + 4 ) integers.
The two block pairs are recorded as in Step 2, and the two blocks give 2 + r ≤ 4 2+r\le4 2 + r ≤ 4 indexed tangle-free paths whose lengths are determined by the block types and cuts. This requires 4 integers.
Choose a spanning forest as in Lemma 2.13. Since
∑ H g ( H ) = q + c − 2 ≤ q , \sum_H g(H)=q+c-2\le q, H ∑ g ( H ) = q + c − 2 ≤ q ,
there are at most q q q edges outside the forest. Each compressed tangle-free path traverses every edge at most twice, so its list of edges traversed outside the forest has at most 2 q 2q 2 q entries. It therefore uses at most 2 q + 3 2q+3 2 q + 3 records: its initial and final vertices, and the list length and entries, with 8 q + 12 8q+12 8 q + 12 integers in total.
For half-edge identifications, we record one integer per incoming or outgoing support edge at each branch. The vertices of degree at least three have total degree at most 6 q 6q 6 q . There are at most four additional original endpoints, each of degree at most two. Therefore,
∑ x b r a n c h deg x ≤ 6 q + 8. \sum_{x\ \mathrm{branch}}\deg x\le6q+8. x branch ∑ deg x ≤ 6 q + 8.
Putting together, these records use at most
3 ( 3 q + 4 ) + 4 + ( 8 q + 12 ) + ( 6 q + 8 ) ≤ 36 ( q + 1 ) 3(3q+4)+4+(8q+12)+(6q+8)\le36(q+1) 3 ( 3 q + 4 ) + 4 + ( 8 q + 12 ) + ( 6 q + 8 ) ≤ 36 ( q + 1 )
integers. The two paths have 2 k 2k 2 k steps in total, so the augmented support has at most 2 k 2k 2 k edges and 2 k + 2 2k+2 2 k + 2 vertices, and we may encode with integers { 0 , … , 2 k + 2 } \{0,\ldots,2k+2\} { 0 , … , 2 k + 2 } . The encoding therefore gives
# { γ : q ( γ ) = q } ≤ ( 2 k + 3 ) 36 ( q + 1 ) . \#\{\gamma:q(\gamma)=q\}\le(2k+3)^{36(q+1)}. # { γ : q ( γ ) = q } ≤ ( 2 k + 3 ) 36 ( q + 1 ) .
For the weights, apply the local degree calculation of Lemma 2.12 . An ordinary vertex is defined to have degree two and is not a branch or incident to a formal edge. It has r x = h x + = h x − = 1 r_x=h_x^+=h_x^-=1 r x = h x + = h x − = 1 and contributes β t x \beta_{t_x} β t x , where r x r_x r x is its augmented indegree. The number of ordinary vertices with t x = 1 t_x=1 t x = 1 is at most a 1 + ( k + 4 ) q a_1+(k+4)q a 1 + ( k + 4 ) q , by the bounds on single edge counts above. All other vertices are exceptional: they are branches or degree-two vertices incident to formal edges. Their total degree is at most 6 q + 8 + 4 r ≤ 6 q + 16 6q+8+4r\le6q+16 6 q + 8 + 4 r ≤ 6 q + 16 . The ordinary vertices have r x = 1 r_x=1 r x = 1 , so
∑ x e x c e p t i o n a l ( 1 − r x ) = v − ( a + r ) = 2 − q . \sum_{x\ \mathrm{exceptional}}(1-r_x)=v-(a+r)=2-q. x exceptional ∑ ( 1 − r x ) = v − ( a + r ) = 2 − q .
Thus
n − 2 ∏ x e x c e p t i o n a l n 1 − r x = n − 2 n 2 − q = n − q . n^{-2}\prod_{x\ \mathrm{exceptional}} n^{1-r_x}=n^{-2}n^{2-q}=n^{-q}. n − 2 x exceptional ∏ n 1 − r x = n − 2 n 2 − q = n − q .
Since ∑ x t x = 2 k \sum_x t_x=2k ∑ x t x = 2 k and 2 k = o ( N ) 2k=o(\sqrt{N}) 2 k = o ( N ) , the matching estimate from Lemma 2.1 and the local degree bounds in Lemma 2.11 give
∣ W ( γ ) ∣ ≤ C 2 6 q Δ 6 q + 16 n − q ρ 2 k − a 1 − ( k + 4 ) q ( 6 k 2 n ) a 1 . |W(\gamma)|\le C2^{6q}\Delta^{6q+16}n^{-q}\rho^{2k-a_1-(k+4)q}\left(\frac{6k}{\sqrt{2n}}\right)^{a_1}. ∣ W ( γ ) ∣ ≤ C 2 6 q Δ 6 q + 16 n − q ρ 2 k − a 1 − ( k + 4 ) q ( 2 n 6 k ) a 1 .
Multiplying by the count, and using ρ − 1 ≤ Δ \rho^{-1}\le\sqrt{\Delta} ρ − 1 ≤ Δ and Δ k ≤ n 1 / 8 \Delta^k\le n^{1/8} Δ k ≤ n 1/8 as in Lemma 2.14 , gives
ρ − 2 k ∑ γ : q ( γ ) = q a 1 ( γ ) = a 1 ∣ W ( γ ) ∣ ≤ C n − 15 q 16 − a 1 2 ( 4 Δ ( k + 1 ) ) 44 q + 52 + a 1 ≤ C n − 15 q 16 − a 1 2 ( 4 Δ ( k + 1 ) ) 52 ( q + a 1 + 1 ) . \rho^{-2k}\sum_{\substack{\gamma:q(\gamma)=q\\a_1(\gamma)=a_1}}|W(\gamma)|
\le Cn^{-\frac{15q}{16}-\frac{a_1}{2}}(4\Delta(k+1))^{44q+52+a_1}
\le Cn^{-\frac{15q}{16}-\frac{a_1}{2}}(4\Delta(k+1))^{52(q+a_1+1)}. ρ − 2 k γ : q ( γ ) = q a 1 ( γ ) = a 1 ∑ ∣ W ( γ ) ∣ ≤ C n − 16 15 q − 2 a 1 ( 4Δ ( k + 1 ) ) 44 q + 52 + a 1 ≤ C n − 16 15 q − 2 a 1 ( 4Δ ( k + 1 ) ) 52 ( q + a 1 + 1 ) .
Summation and the scalar power. Since Δ = n o ( 1 ) \Delta=n^{o(1)} Δ = n o ( 1 ) and k = O ( log n ) k=O(\log n) k = O ( log n ) , ( 16 Δ ( k + 1 ) ) 52 = n o ( 1 ) (16\Delta(k+1))^{52}=n^{o(1)} ( 16Δ ( k + 1 ) ) 52 = n o ( 1 ) . Hence the two geometric ratios
( 16 Δ ( k + 1 ) ) 52 n 15 / 16 , ( 16 Δ ( k + 1 ) ) 52 n \frac{(16\Delta(k+1))^{52}}{n^{15/16}},\qquad
\frac{(16\Delta(k+1))^{52}}{\sqrt n} n 15/16 ( 16Δ ( k + 1 ) ) 52 , n ( 16Δ ( k + 1 ) ) 52
are at most 1 / 2 1/2 1/2 for sufficiently large n n n . The case ( q , a 1 ) = ( 0 , 0 ) (q,a_1)=(0,0) ( q , a 1 ) = ( 0 , 0 ) is absent, so summing over q + a 1 ≥ 1 q+a_1\ge1 q + a 1 ≥ 1 by the same calculation as in Lemma 2.14 yields
E z k 2 ρ 2 k ≤ 8 C ( 4 Δ ( ℓ + 1 ) ) 104 n = n − 1 / 2 + o ( 1 ) . \frac{\mathbb E z_k^2}{\rho^{2k}}\le\frac{8C(4\Delta(\ell+1))^{104}}{\sqrt n}=n^{-1/2+o(1)}. ρ 2 k E z k 2 ≤ n 8 C ( 4Δ ( ℓ + 1 ) ) 104 = n − 1/2 + o ( 1 ) .
By Markov’s inequality,
P { ∣ z k ∣ > n − 1 / 8 ρ } ≤ n 1 / 4 E z k 2 ρ 2 k = o ( 1 ) . \mathbb P\{|z_k|>n^{-1/8}\rho\}\le\frac{n^{1/4}\mathbb E z_k^2}{\rho^{2k}}=o(1). P { ∣ z k ∣ > n − 1/8 ρ } ≤ ρ 2 k n 1/4 E z k 2 = o ( 1 ) .
This proves (38) .
Proof of Theorem 1.3
Lemma 2.4 , applied with α = 1 / 8 \alpha=1/8 α = 1/8 , gives P ( H ℓ c ) = o ( 1 ) \mathbb P(\mathcal H_\ell^c)=o(1) P ( H ℓ c ) = o ( 1 ) . On H ℓ \mathcal H_\ell H ℓ , Lemma 2.6 gives
X ℓ , t − z ℓ , t t ρ t = tr P t − 1 t ρ t . \frac{X_{\ell,t}-z_{\ell,t}}{\sqrt{t}\rho^t}
=
\frac{\operatorname{tr}P^t-1}{\sqrt{t}\rho^t}. t ρ t X ℓ , t − z ℓ , t = t ρ t tr P t − 1 .
By Lemma 2.16 , z ℓ , t / ρ t → 0 z_{\ell,t}/\rho^t\to0 z ℓ , t / ρ t → 0 in probability. Then Lemma 2.15 and Slutsky’s theorem give a Gaussian limit for the left-hand side. The equality on H ℓ \mathcal H_\ell H ℓ then transfers this limit to the trace:
tr P t − 1 t ρ t ⟹ N ( 0 , 1 ) . \frac{\operatorname{tr}P^t-1}{\sqrt{t}\rho^t}\Longrightarrow\mathcal N(0,1). t ρ t tr P t − 1 ⟹ N ( 0 , 1 ) .
AI statements
The authors developed the proof ideas, performed the calculations, and wrote the manuscript. Large language models were used solely for polishing the language and creating the figures.
Acknowledgments
The authors thank Jorge Garza-Vargas for helpful discussion during the early stage of this project. C.B. has started this work during his stay at the Institute for Advanced Study. He acknowledges support from the James D. Wolfensohn Fund and from French ANR grant Tagada (ANR-25-CE40-5672). Y.Z. was partially supported by the Simons Grant MPS-TSM-00013944 and NSF DMS-2606337. Part of the work was done while C.B. and Y.Z. were visiting the Simons Institute for the Theory of Computing during the Spectral Theory Beyond Graphs program in Fall 2026.
I2M, CNRS, Aix-Marseille Université
Email address: charles.bordenave@univ-amu.fr
Department of Mathematics, University of Southern California
Email address: yizhezhu@usc.edu