A Pittel-type limit law for the largest component of random $d$-uniform hypergraphs: enumeration and excursions

Source abstract

Let $H_d(n,M)$ be a $d$-uniform hypergraph with $n$ vertices and $M$ hyperedges. In the critical window $M=\frac{n}{d(d-1)}(1+λn^{-1/3})+O(1)$, its largest component $L_n$ satisfies $$n^{-2/3}L_n\xrightarrow{\mathcal L} \mathcal{F}_{\mathrm{Pit}}\bigl((d-1)^{1/3}a,λ(d-1)^{-2/3}\bigr).$$ (Here $\mathcal{F}_{\mathrm{Pit}}(x,μ)$ denotes the limiting law of the largest component of the critical random graph established by Pittel (2001).) The proof rests on two pillars. First, a bivariate exponential formula gives the exact finite-size law of $L_n$. Subsequently, cancellation of the orders $n,n^{2/3},n^{1/3}$ in the tree normalization determines the series of rooted hypertrees, then that of unicyclic components and its singular expansions at the radius of convergence $ρ_d$. These calculations are exact; they serve the fixed-excess identities and the cancellation mechanism, and nothing more: no unproved uniformity in the excess enters the proof of the limit law. Next, by exploration and martingale approximation, the ordered sizes converge unconditionally to the excursion lengths of a Brownian motion with parabolic drift. A monotone coupling transfers the law to $H_d(n,M)$. The limit law is then identified with Pittel's law by a Brownian rescaling: if $h=d-1$, it suffices to multiply lengths by $h^{-1/3}$ and evaluate at parameter $λh^{-2/3}$. The exact Poisson representation dispenses with any separate deconditioning. We also formulate a two-regime $d$-uniform Bollobas bound (Wright for fixed $\ell$, global combinatorial beyond that), and explicitly indicate why neither regime alone suffices to close the analytic route.