The second eigenvalue of random walks on sparse directed Erdős–Rényi graphs

Let A be the adjacency matrix of a directed Erdős–Rényi graph on N vertices with independent Bernoulli(p) entries, and let P = D⁻¹A be the transition matrix of the simple random walk, where D is the diagonal matrix of out-degrees. Write κ = √(Np/(1−p)). If Np(1−p)/(log N)⁴ → ∞, then almost surely every out-degree is positive for all large N, the eigenvalue 1 of P is simple, and every other eigenvalue satisfies |λ| ≤ (1+o(1))/κ. If moreover p ≤ 1/2 and Np ≥ Nᵃ for some a ∈ (3/4, 1), the empirical spectral distribution of κP converges in probability to the uniform law on the unit disc, and κ|λ₂(P)| → 1 in probability. Both results hold with and without loops. The upper bound reduces the outlier eigenvalues of P to a rank-one perturbation and a small diagonal perturbation of the centred adjacency matrix. It controls the resolvent of that matrix outside the disc of radius 1+ε by three tools: the universality theorem of Brailovskaya and van Handel, a comparison with the real Ginibre ensemble, and an analytic extension argument that needs only fixed moments of bilinear forms. The lower bound rests on a smallest singular value bound for κP − z. That bound is proved by an integrality argument for the 0/1 structure of the graph, Odlyzko’s lemma and the Kolmogorov–Rogozin inequality. The deterministic algebra and every elementary estimate are verified in Lean 4 with Mathlib (89 declarations, with no axioms beyond the standard three); the remaining steps are cited results.