Perron-Wright asymptotics and critical component processes for regular inhomogeneous random graphs
Wentao Hu, Wen Sun
math.PR
Oct 16, 2026 · v1
math.CO
TL;DR
The main results (Theorems 3.6, 3.8, 3.9 and 3.10) on critical inhomogeneous random graphs are stated to be formalized and checked in Lean 4.
Abstract
We extend Wright's enumeration of connected labelled graphs with fixed surplus to irreducible critical finite type kernels and regular compact type kernels. Let $C_t(k,r)$ denote the total weight of connected labelled graphs with $k$ vertices and surplus $r$. Let $u>0$ satisfy $Ku=u$ and $\int u\,dμ=1$, and put $α=\int u^2\,dμ$ and $β=\int u^3\,dμ$. We prove that the rooted-tree radius $ρ$ is positive and real analytic near $1$, with $ρ(1)=1$ and $\logρ(t)=\frac{α^2}{2β}(t-1)^2+O(|t-1|^3)$, and that, for fixed $r\in\mathbb{Z}_{\ge0}$ and $0\le L < \infty$, $C_t(k,r)=w_rβ^{(r-1)/2}e^{-k}ρ(t)^{-k}k^{k+3r/2-2}\{1+O_{r,L}(k^{-1/2})\}$, uniformly for $|t-1|\le Lk^{-1/2}$, where $w_r$ is the classical Wright constant. At $t_n=1+λn^{-1/3}$, these asymptotics yield local size and surplus point-process limits for deterministic finite type models and annealed compact type Bollobas-Janson-Riordan models satisfying projective quadratic regularity. After rescaling component sizes by $β^{1/3}n^{-2/3}$, the limit is the Aldous process at parameter $αβ^{-2/3}λ$, and the corresponding type profiles concentrate at the Perron law $p(dx)=u(x)μ(dx)$. For every regular countable critical kernel, we construct graph sequences with growing finite supports and the same local limits, and identify the additive shift of the critical window caused by spectral perturbations of order $n^{-1/3}$.
Problem
Wright's enumeration of connected labelled graphs with fixed surplus, and its link to Aldous's critical component process, is known for the homogeneous Erdős–Rényi graph. The question is what replaces the Wright enumerator and its amplitude for Perron-critical inhomogeneous kernels.
Approach
The authors define a kernel-weighted connected graph enumerator C_t(k,r) and analyze the rooted-tree radius ρ(t) using the Perron eigenfunction u of the kernel operator, via holomorphic implicit-function and spectral arguments. They combine exact formulas for ordered component counts with factorial moment measures and type-profile concentration. Finite and compact type models are treated first, and countable kernels are handled by finite truncations assembled into diagonal graph sequences. The main theorems are reported as formalized and checked in Lean 4.
Results
ρ is real analytic near 1, with log ρ(t) = (α²/2β)(t−1)² + O(|t−1|³). The asymptotic C_t(k,r) = w_r β^{(r−1)/2} e^{−k} ρ(t)^{−k} k^{k+3r/2−2}(1+O(k^{−1/2})) holds uniformly for |t−1| ≤ Lk^{−1/2}. In the critical window, rescaled component sizes and surpluses converge to the Aldous process at parameter αβ^{−2/3}λ, with type profiles concentrating at the Perron law u dμ. Countable kernels yield the same local limits, and the authors identify the window shift caused by spectral perturbations of order n^{−1/3}.