Model and scope
Fix d ≥ 2 d \ge2 d ≥ 2 N = ( n d ) N=\binom{n}{d} N = ( d n ) H d ( n , M ) H_d(n,M) H d ( n , M ) d d d [ n ] [n] [ n ] M M M
M = n d ( d − 1 ) ( 1 + λ n − 1 / 3 ) + O ( 1 ) , λ ∈ R . (1) M=\frac{n}{d(d-1)}(1+\lambda n^{-1/3})+O(1),\qquad\lambda\in\mathbb{R}. \tag*{(1)} M = d ( d − 1 ) n ( 1 + λ n − 1/3 ) + O ( 1 ) , λ ∈ R . (1) Let L n L_n L n ( d − 1 ) d M / n = 1 + λ n − 1 / 3 + O ( n − 1 ) (d-1)dM/n=1+\lambda n^{-1/3}+O(n^{-1}) ( d − 1 ) d M / n = 1 + λ n − 1/3 + O ( n − 1 ) n 2 / 3 n^{2/3} n 2/3
Theorem 1.1 (Main theorem). For every fixed integer d ≥ 2 d \ge2 d ≥ 2 λ ∈ R \lambda\in\mathbb{R} λ ∈ R M = n d ( d − 1 ) ( 1 + λ n − 1 / 3 ) + O ( 1 ) M = \frac{n}{d(d-1)}(1+\lambda n^{-1/3})+O(1) M = d ( d − 1 ) n ( 1 + λ n − 1/3 ) + O ( 1 ) L n L_n L n H d ( n , M ) H_d(n,M) H d ( n , M ) a > 0 a>0 a > 0
lim n → ∞ P { n − 2 / 3 L n ≤ a } = F P i t ( ( d − 1 ) 1 / 3 a , λ ( d − 1 ) − 2 / 3 ) , \lim_{n\to\infty}\mathbb{P}\{n^{-2/3}L_n\le a\}=F_{\mathrm{Pit}}\left((d-1)^{1/3}a,\lambda(d-1)^{-2/3}\right), n → ∞ lim P { n − 2/3 L n ≤ a } = F Pit ( ( d − 1 ) 1/3 a , λ ( d − 1 ) − 2/3 ) , where F P i t ( x , μ ) F_{\mathrm{Pit}}(x,\mu) F Pit ( x , μ ) [17 ] .
2020 Mathematics Subject Classification. Primary 05C80; Secondary 60C05, 05C65.
Key words and phrases. random hypergraphs, phase transition, largest component, Pittel law, functional invariance principle, excursions, analytic combinatorics.
ORCID: 0009-0003-2432-9361.
This result is proved in Corollary 8.4 by the probabilistic route, without any hypothesis on hypergraph kernels.
Two routes are developed, with distinct logical statuses. Sections 2–6 establish the exact identities, the fixed-excess expansions and the cancellation mechanism, without deriving a transfer uniform in the excess. Section 7 proves unconditionally the convergence of excursions, then their transfer to H d ( n , M ) H_d(n,M) H d ( n , M ) d d d v v v e e e
ℓ = ( d − 1 ) e − v . (2) \ell= (d-1)e-v. \tag*{(2)} ℓ = ( d − 1 ) e − v . (2) A hypertree, that is, a connected hypergraph whose incidence graph is acyclic, satisfies v = 1 + ( d − 1 ) e v=1+(d-1)e v = 1 + ( d − 1 ) e − 1 -1 − 1 e = v + ℓ e=v+\ell e = v + ℓ d = 2 d=2 d = 2 ℓ ≥ 1 \ell\ge1 ℓ ≥ 1
Pittel's integral formula (JCTB, 2001) and its d-uniform adaptation
For a > 0 a>0 a > 0 Journal of Combinatorial Theory, Series B , volume 82 (2001), pages 237–269, in particular his equation (3.25) [17 ] . The expression below is the d d d
F d c o n t ( a , λ ) = A d ( a , λ ) ∫ − ∞ ∞ exp { H d , a , λ ( v ∗ + i w ) } d w , (3) F_d^{\mathrm{cont}}(a,\lambda)=A_d(a,\lambda)\int_{-\infty}^{\infty}\exp\{H_{d,a,\lambda}(v^*+iw)\}\,dw, \tag*{(3)} F d cont ( a , λ ) = A d ( a , λ ) ∫ − ∞ ∞ exp { H d , a , λ ( v ∗ + i w )} d w , (3) where
H d , a , λ ( z ) = ( β − λ ) z + I d ( z ) , β = − 2 2 π a , H_{d,a,\lambda}(z)=(\beta-\lambda)z+I_d(z),\qquad\beta=-\frac{2}{\sqrt{2\pi a}}, H d , a , λ ( z ) = ( β − λ ) z + I d ( z ) , β = − 2 π a 2 , and
I d ( z ) = ∫ 0 a [ 1 2 π ( e z y − 1 − z y y 5 / 2 + g d ( y ) e z y ) + e z y − 1 4 y ] d y . (4) I_d(z)=\int_0^a\left[\frac{1}{\sqrt{2\pi}}\left(\frac{e^{zy}-1-zy}{y^{5/2}}+g_d(y)e^{zy}\right)+\frac{e^{zy}-1}{4y}\right]\,dy. \tag*{(4)} I d ( z ) = ∫ 0 a [ 2 π 1 ( y 5/2 e z y − 1 − z y + g d ( y ) e z y ) + 4 y e z y − 1 ] d y . (4) Here v ∗ v^* v ∗ g d g_d g d g d g_d g d
More precisely, any analytic use of (4) assumes that the series defining g d g_d g d ≤ C R ℓ ℓ − ℓ / 2 \le CR^\ell\ell^{-\ell/2} ≤ C R ℓ ℓ − ℓ /2 ≤ C R ℓ / Γ ( ℓ / 2 + 1 ) \le CR^\ell/\Gamma(\ell/2+1) ≤ C R ℓ /Γ ( ℓ /2 + 1 ) (32) . Until this is verified, g d g_d g d
Exact laws from the exponential formula
Let C d ( v , e ) C_d(v,e) C d ( v , e ) d d d v v v e e e
C d , m ( x , z ) = ∑ v = 1 m x v v ! ∑ e = 0 ( v d ) C d ( v , e ) z e , (5) C_{d,m}(x,z)=\sum_{v=1}^{m}\frac{x^v}{v!}\sum_{e=0}^{\binom{v}{d}}C_d(v,e)z^e, \tag*{(5)} C d , m ( x , z ) = v = 1 ∑ m v ! x v e = 0 ∑ ( d v ) C d ( v , e ) z e , (5) where C d , m ( x , z ) C_{d,m}(x,z) C d , m ( x , z ) d d d m m m C d ( 1 , 0 ) = 1 C_d(1,0)=1 C d ( 1 , 0 ) = 1
Theorem 2.1 (Exact coefficient formula with a fixed number of edges). For 1 ≤ m ≤ n 1\le m\le n 1 ≤ m ≤ n 0 ≤ M ≤ N 0\le M\le N 0 ≤ M ≤ N
P { L n ≤ m } = n ! ( N M ) [ x n z M ] exp ( C d , m ( x , z ) ) . (6) \mathbb{P}\{L_n\le m\}=\frac{n!}{\binom{N}{M}}[x^n z^M]\exp(C_{d,m}(x,z)). \tag*{(6)} P { L n ≤ m } = ( M N ) n ! [ x n z M ] exp ( C d , m ( x , z )) . (6) The same expression is exactly 1 when m = n m=n m = n
Proof. Decompose each labelled hypergraph uniquely into its connected components. The exponential formula counts partitions of the label set, while z z z v ≤ m v\le m v ≤ m ( N M ) \binom{N}{M} ( M N ) M M M m = n m=n m = n ( N M ) \binom{N}{M} ( M N )
Remark 2.2 (Combinatorial reading). The coefficient [ x n z M ] exp ( C d , m ( x , z ) ) [x^n z^M]\exp(C_{d,m}(x,z)) [ x n z M ] exp ( C d , m ( x , z )) n ! n! n ! d d d [ n ] [n] [ n ] M M M m m m P { L n ≤ m } \mathbb{P}\{L_n\le m\} P { L n ≤ m } ( N M ) \binom{N}{M} ( M N ) [ n ] [n] [ n ]
This reading reveals the following gap: for hypertrees (ℓ = − 1 \ell=-1 ℓ = − 1 C d ( v , e ) = ( v − 1 ) ! v e − 1 / [ e ! ( ( d − 1 ) ! ) e ] C_d(v,e)=(v-1)!v^{e-1}/[e!((d-1)!)^e] C d ( v , e ) = ( v − 1 )! v e − 1 / [ e ! (( d − 1 )! ) e ] ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 [23 ] in the case d = 2 d=2 d = 2 d ≥ 3 d\ge3 d ≥ 3 § 7 , which dispenses with any fixed-excess analytic expansion.
Remark 2.3 (Independent-edge model). In H d ( n , p ) H_d(n,p) H d ( n , p ) N N N z = p / ( 1 − p ) z=p/(1-p) z = p / ( 1 − p )
P p { L n ≤ m } = ( 1 − p ) N n ! [ x n ] exp ( C d , m ( x , z ) ) . \mathbb{P}_p\{L_n\le m\}=(1-p)^N n![x^n]\exp(C_{d,m}(x,z)). P p { L n ≤ m } = ( 1 − p ) N n ! [ x n ] exp ( C d , m ( x , z )) . The factor z e z^e z e μ ( d − 1 ) e − v \mu^{(d-1)e-v} μ ( d − 1 ) e − v
For the subsequent analysis, one can group (5) by excess:
C d , m ( x , z ) = ∑ ℓ ≥ − 1 ∑ 1 ≤ v ≤ m v + ℓ ≡ 0 ( m o d d − 1 ) C d ( v , v + ℓ d − 1 ) x v v ! z ( v + ℓ ) / ( d − 1 ) . (7) C_{d,m}(x,z)=\sum_{\ell\ge-1}\ \sum_{\substack{1\le v\le m\\v+\ell\equiv0\;(\mathrm{mod}\ d-1)}} C_d\left(v,\frac{v+\ell}{d-1}\right)\frac{x^v}{v!}z^{(v+\ell)/(d-1)}. \tag*{(7)} C d , m ( x , z ) = ℓ ≥ − 1 ∑ 1 ≤ v ≤ m v + ℓ ≡ 0 ( mod d − 1 ) ∑ C d ( v , d − 1 v + ℓ ) v ! x v z ( v + ℓ ) / ( d − 1 ) . (7) For fixed m m m d > 2 d>2 d > 2 C d ( v , ( v + ℓ ) / ( d − 1 ) ) C_d(v,(v+\ell)/(d-1)) C d ( v , ( v + ℓ ) / ( d − 1 )) C d ( v , e ) C_d(v,e) C d ( v , e ) ℓ = ( d − 1 ) e − v \ell=(d-1)e-v ℓ = ( d − 1 ) e − v d = 2 d=2 d = 2 C d ( v , v + ℓ ) C_d(v,v+\ell) C d ( v , v + ℓ )
Positioning with respect to previous work
The notions of excess, hypertree, unicyclic component and kernel are classical [3 , 13 , 18 , 5 ] . Fixed-excess asymptotics and the structure near the birth of complex components are known in more general weighted models [6 ] . This article does not claim novelty for them.
Its contribution is the organization of these elements through the exact formula (6) , the rescaling of Theorem 6.1, and the explicit cancellation of Theorem 6.2. The contour integral for the largest component requires estimates uniform in the excess that go beyond this framework; the probabilistic route does not need them. The critical window for hypergraphs goes back to [21 , 14 ] ; see also [4 , 19 ] for the phase transition in more general models (inhomogeneous random graphs and the configuration model) where similar techniques apply. The excursion description relies on [2 , 15 , 16 , 12 ] ; the metric structure of the critical random graph at the same scale is studied in [1 ] . For enumeration of connected hypergraphs, see [3 , 10 ] .
Conditioning the independent-edge model
Let E E E H d ( n , p ) H_d(n,p) H d ( n , p ) A A A p ∈ ( 0 , 1 ) p \in(0,1) p ∈ ( 0 , 1 )
P { H d ( n , M ) ∈ A } = P p { H d ( n , p ) ∈ A ∣ E = M } . (8) \mathbb{P}\{H_d(n,M) \in A\}=\mathbb{P}_p\{H_d(n,p) \in A \mid E=M\}. \tag*{(8)} P { H d ( n , M ) ∈ A } = P p { H d ( n , p ) ∈ A ∣ E = M } . (8) In the independent-edge model, every hypergraph with M M M p M ( 1 − p ) N − M p^M(1-p)^{N-M} p M ( 1 − p ) N − M (6) remains necessary for the exact law.
Exact Cauchy representation and normalization
For any radii r , s > 0 r,s>0 r , s > 0 (6) gives
P { L n ≤ m } = n ! ( N M ) 1 ( 2 π i ) 2 ∮ ∣ x ∣ = r ∮ ∣ z ∣ = s exp ( C d , m ( x , z ) ) d z d x x n + 1 z M + 1 . (9) \mathbb{P}\{L_n\le m\}=\frac{n!}{\binom{N}{M}}\frac{1}{(2\pi i)^2}\oint_{|x|=r}\oint_{|z|=s}\exp(C_{d,m}(x,z))\frac{dz\,dx}{x^{n+1}z^{M+1}}. \tag*{(9)} P { L n ≤ m } = ( M N ) n ! ( 2 π i ) 2 1 ∮ ∣ x ∣ = r ∮ ∣ z ∣ = s exp ( C d , m ( x , z )) x n + 1 z M + 1 d z d x . (9) The integrand is entire before coefficient extraction: the radii may be chosen freely, without any singularity of the finite polynomial (5) . A singular object appears only in the limit m → ∞ m\to\infty m → ∞ m = n m=n m = n
Exact Poisson representation of the bivariate coefficient
The two-variable saddle point has a direct probabilistic interpretation. It reduces the local contour problem to a lattice local limit theorem, and gives the covariance matrix without formal manipulation.
Theorem 2.4 (Poissonization identity). Fix m , r , s > 0 m,r,s>0 m , r , s > 0 ( v , e ) (v,e) ( v , e ) 1 ≤ v ≤ m 1\le v\le m 1 ≤ v ≤ m Z v , e Z_{v,e} Z v , e
θ v , e = C d ( v , e ) v ! r v s e . \theta_{v,e}=\frac{C_d(v,e)}{v!}r^v s^e. θ v , e = v ! C d ( v , e ) r v s e . and put S V = ∑ v , e v Z v , e S_V=\sum_{v,e}vZ_{v,e} S V = ∑ v , e v Z v , e S E = ∑ v , e e Z v , e S_E=\sum_{v,e}eZ_{v,e} S E = ∑ v , e e Z v , e
[ x n z M ] e C d , m ( x , z ) = e C d , m ( r , s ) r − n s − M P { S V = n , S E = M } . (10) [x^n z^M]e^{C_{d,m}(x,z)}=e^{C_{d,m}(r,s)}r^{-n}s^{-M}\mathbb{P}\{S_V=n,S_E=M\}. \tag*{(10)} [ x n z M ] e C d , m ( x , z ) = e C d , m ( r , s ) r − n s − M P { S V = n , S E = M } . (10) Consequently,
E ( S V , S E ) = ( r ∂ r C d , m ( r , s ) , s ∂ s C d , m ( r , s ) ) , \mathbb{E}(S_V,S_E)=(r\partial_r C_{d,m}(r,s),s\partial_s C_{d,m}(r,s)), E ( S V , S E ) = ( r ∂ r C d , m ( r , s ) , s ∂ s C d , m ( r , s )) , and the covariance matrix is
Σ m ( r , s ) = ∑ v , e θ v , e ( v 2 v e v e e 2 ) . (11) \Sigma_m(r,s)=\sum_{v,e}\theta_{v,e}
\begin{pmatrix}
v^2 & ve\\
ve & e^2
\end{pmatrix}. \tag*{(11)} Σ m ( r , s ) = v , e ∑ θ v , e ( v 2 v e v e e 2 ) . (11) Thus the positive saddle equations are exactly the centring equations E S V = n \mathbb{E}S_V=n E S V = n E S E = M \mathbb{E}S_E=M E S E = M
Proof. The joint probability generating function is
E [ u S V w S E ] = ∏ v , e exp { θ v , e ( u v w e − 1 ) } = e − C d , m ( r , s ) exp { C d , m ( r u , s w ) } . \mathbb{E}[u^{S_V}w^{S_E}] = \prod_{v,e} \exp\{\theta_{v,e}(u^v w^e-1)\} = e^{-C_{d,m}(r,s)}\exp\{C_{d,m}(ru,sw)\}. E [ u S V w S E ] = v , e ∏ exp { θ v , e ( u v w e − 1 )} = e − C d , m ( r , s ) exp { C d , m ( r u , s w )} . Extracting u n w M u^n w^M u n w M (10) . Differentiating the logarithm of the joint generating function gives the expectation and (11) . □
Lemma 2.5 (Exact angular damping). For x = r e i α x=re^{i\alpha} x = r e i α z = s e i β z=se^{i\beta} z = s e i β
∣ e C d , m ( x , z ) ∣ = e C d , m ( r , s ) exp { − D m ( α , β ; r , s ) } . (12) \left|e^{C_{d,m}(x,z)}\right| = e^{C_{d,m}(r,s)}\exp\{-D_m(\alpha,\beta;r,s)\}. \tag*{(12)} e C d , m ( x , z ) = e C d , m ( r , s ) exp { − D m ( α , β ; r , s )} . (12) D m ( α , β ; r , s ) = ∑ v , e θ v , e ( 1 − cos ( v α + e β ) ) ≥ 0. D_m(\alpha,\beta;r,s) = \sum_{v,e}\theta_{v,e}(1-\cos(v\alpha+e\beta)) \ge0. D m ( α , β ; r , s ) = v , e ∑ θ v , e ( 1 − cos ( v α + e β )) ≥ 0. Near the origin, D m ( α , β ; r , s ) = 1 2 ( α , β ) Σ m ( r , s ) ( α , β ) T + R m D_m(\alpha,\beta;r,s)=\frac{1}{2}(\alpha,\beta)\Sigma_m(r,s)(\alpha,\beta)^{\mathsf{T}}+R_m D m ( α , β ; r , s ) = 2 1 ( α , β ) Σ m ( r , s ) ( α , β ) T + R m
∣ R m ∣ ≤ 1 24 ∑ v , e θ v , e ∣ v α + e β ∣ 4 . |R_m| \le\frac{1}{24}\sum_{v,e}\theta_{v,e}|v\alpha+e\beta|^4. ∣ R m ∣ ≤ 24 1 v , e ∑ θ v , e ∣ v α + e β ∣ 4 . More precisely, if λ min ( Σ m ) > 0 \lambda_{\min}(\Sigma_m)>0 λ m i n ( Σ m ) > 0 U U U
∑ v , e θ v , e ∣ v α + e β ∣ 4 ≤ 6 λ min ( Σ m ) ( α 2 + β 2 ) , \sum_{v,e}\theta_{v,e}|v\alpha+e\beta|^4 \le6\lambda_{\min}(\Sigma_m)(\alpha^2+\beta^2), v , e ∑ θ v , e ∣ v α + e β ∣ 4 ≤ 6 λ m i n ( Σ m ) ( α 2 + β 2 ) , then, uniformly on U U U
D m ( α , β ; r , s ) ≥ 1 4 λ min ( Σ m ) ( α 2 + β 2 ) . D_m(\alpha,\beta;r,s)\ge\frac{1}{4}\lambda_{\min}(\Sigma_m)(\alpha^2+\beta^2). D m ( α , β ; r , s ) ≥ 4 1 λ m i n ( Σ m ) ( α 2 + β 2 ) . Proof. Take the real part of C d , m ( r e i α , s e i β ) C_{d,m}(re^{i\alpha},se^{i\beta}) C d , m ( r e i α , s e i β ) ℜ e i t = cos t \Re e^{it}=\cos t ℜ e i t = cos t ∣ 1 − cos t − t 2 / 2 ∣ ≤ ∣ t ∣ 4 / 24 |1-\cos t-t^2/2|\le|t|^4/24 ∣1 − cos t − t 2 /2∣ ≤ ∣ t ∣ 4 /24
Proposition 2.6 (Exact Poisson quotient). For the same radii r , s > 0 r,s>0 r , s > 0 P m \mathbb{P}_m P m m m m P n \mathbb{P}_n P n
P { L n ≤ m } = e C d , m ( r , s ) − C d , n ( r , s ) P m { S V = n , S E = M } P n { S V = n , S E = M } . (13) \mathbb{P}\{L_n\le m\}=e^{C_{d,m}(r,s)-C_{d,n}(r,s)}
\frac{\mathbb{P}_m\{S_V=n,S_E=M\}}{\mathbb{P}_n\{S_V=n,S_E=M\}}. \tag*{(13)} P { L n ≤ m } = e C d , m ( r , s ) − C d , n ( r , s ) P n { S V = n , S E = M } P m { S V = n , S E = M } . (13) This identity is valid for all r , s > 0 r,s>0 r , s > 0
Proof. Apply (10) to the numerator of (6) , then to the case m = n m=n m = n n ! r − n s − M / ( N n ) n!r^{-n}s^{-M}/\binom{N}{n} n ! r − n s − M / ( n N ) (13) . □
Proposition 2.7 (Aperiodicity and outer minor arcs). Suppose the critical radii satisfy
r n ≍ n , s n ≍ n − ( d − 1 ) . (14) r_n\asymp n,\qquad s_n\asymp n^{-(d-1)}. \tag*{(14)} r n ≍ n , s n ≍ n − ( d − 1 ) . (14) There is then c > 0 c>0 c > 0 m ≥ d m\ge d m ≥ d ( α , β ) ∈ [ − π , π ] 2 (\alpha,\beta)\in[-\pi,\pi]^2 ( α , β ) ∈ [ − π , π ] 2
D m ( α , β ; r n , s n ) ≥ c n ( ∥ α ∥ 2 π 2 + ∥ d α + β ∥ 2 π 2 ) , (15) D_m(\alpha,\beta;r_n,s_n)\ge cn\left(\|\alpha\|_{2\pi}^2+\|d\alpha+\beta\|_{2\pi}^2\right), \tag*{(15)} D m ( α , β ; r n , s n ) ≥ c n ( ∥ α ∥ 2 π 2 + ∥ d α + β ∥ 2 π 2 ) , (15) where ∥ u ∥ 2 π \|u\|_{2\pi} ∥ u ∥ 2 π u u u 2 π Z 2\pi\mathbb{Z} 2 π Z
max { ∥ α ∥ 2 π , ∥ d α + β ∥ 2 π } ≥ δ n \max\{\|\alpha\|_{2\pi},\|d\alpha+\beta\|_{2\pi}\}\ge\delta_n max { ∥ α ∥ 2 π , ∥ d α + β ∥ 2 π } ≥ δ n is at most O ( e − c n δ n 2 ) O(e^{-cn\delta_n^2}) O ( e − c n δ n 2 ) n δ n 2 − C log n → ∞ n\delta_n^2-C\log n\to\infty n δ n 2 − C log n → ∞ C > 0 C>0 C > 0
Proof. Among the permitted components are the isolated vertex ( v , e ) = ( 1 , 0 ) (v,e)=(1,0) ( v , e ) = ( 1 , 0 ) ( v , e ) = ( d , 1 ) (v,e)=(d,1) ( v , e ) = ( d , 1 )
θ 1 , 0 = r n ≍ n , θ d , 1 = r n d s n d ! ≍ n . \theta_{1,0}=r_n\asymp n,\qquad\theta_{d,1}=\frac{r_n^d s_n}{d!}\asymp n. θ 1 , 0 = r n ≍ n , θ d , 1 = d ! r n d s n ≍ n . Keeping only these two terms in (12) gives
D m ≥ c 0 n { 1 − cos α + 1 − cos ( d α + β ) } . D_m\ge c_0n\{1-\cos\alpha+1-\cos(d\alpha+\beta)\}. D m ≥ c 0 n { 1 − cos α + 1 − cos ( d α + β )} . The inequality 1 − cos u ≥ c 1 ∥ u ∥ 2 π 2 1-\cos u\ge c_1\lVert u\rVert_{2\pi}^2 1 − cos u ≥ c 1 ∥ u ∥ 2 π 2 ( 1 , 0 ) (1,0) ( 1 , 0 ) ( d , 1 ) (d,1) ( d , 1 ) Z 2 \mathbb{Z}^2 Z 2 ( 0 , 0 ) (0,0) ( 0 , 0 )
Theorem 2.4 and Lemma 2.5 remove two ambiguities in the contour argument. If Σ m \Sigma_m Σ m ( 2 π det Σ m ) − 1 (2\pi\sqrt{\det\Sigma_m})^{-1} ( 2 π det Σ m ) − 1 δ n ≫ n − 1 / 2 \delta_n\gg n^{-1/2} δ n ≫ n − 1/2 m ≍ n 2 / 3 m\asymp n^{2/3} m ≍ n 2/3 Σ m \Sigma_m Σ m
A rigorous criterion for closing the contour calculation
The following result isolates sufficient conditions for an autonomous analytic route, without choosing angular scales prematurely. In particular, it avoids confusing pointwise convergence of the phase with convergence of the integral.
For k ∈ { m , n } k\in\{m,n\} k ∈ { m , n }
Ψ k , n ( θ ) = C d , k ( r n e i θ 1 , s n e i θ 2 ) − C d , k ( r n , s n ) − i ( n θ 1 + M θ 2 ) , θ ∈ [ − π , π ] 2 , \Psi_{k,n}(\theta)=C_{d,k}(r_ne^{i\theta_1},s_ne^{i\theta_2})-C_{d,k}(r_n,s_n)-i(n\theta_1+M\theta_2),\qquad\theta\in[-\pi,\pi]^2, Ψ k , n ( θ ) = C d , k ( r n e i θ 1 , s n e i θ 2 ) − C d , k ( r n , s n ) − i ( n θ 1 + M θ 2 ) , θ ∈ [ − π , π ] 2 , and I k , n = ∫ [ − π , π ] 2 e Ψ k , n ( θ ) d θ I_{k,n}=\int_{[-\pi,\pi]^2}e^{\Psi_{k,n}(\theta)}\,d\theta I k , n = ∫ [ − π , π ] 2 e Ψ k , n ( θ ) d θ
P { L n ≤ m } = e C d , m ( r n , s n ) − C d , n ( r n , s n ) I m , n I n , n . (16) \mathbb{P}\{L_n\le m\}=e^{C_{d,m}(r_n,s_n)-C_{d,n}(r_n,s_n)}\frac{I_{m,n}}{I_{n,n}}. \tag*{(16)} P { L n ≤ m } = e C d , m ( r n , s n ) − C d , n ( r n , s n ) I n , n I m , n . (16) Lemma 2.8 (Uniform dominated convergence with a parameter). Let ( X , A , μ ) (X,\mathcal{A},\mu) ( X , A , μ ) K K K f n , a , f a : X → C f_{n,a},f_a:X\to\mathbb{C} f n , a , f a : X → C H ∈ L 1 ( μ ) H\in L^1(\mu) H ∈ L 1 ( μ ) X 0 ⊂ X X_0\subset X X 0 ⊂ X
sup a ∈ K ∣ f n , a ( x ) − f a ( x ) ∣ ⟶ 0 ( x ∈ X 0 ) , \sup_{a\in K}|f_{n,a}(x)-f_a(x)|\longrightarrow0\qquad(x\in X_0), a ∈ K sup ∣ f n , a ( x ) − f a ( x ) ∣ ⟶ 0 ( x ∈ X 0 ) , and ∣ f n , a ( x ) ∣ ≤ H ( x ) |f_{n,a}(x)|\le H(x) ∣ f n , a ( x ) ∣ ≤ H ( x ) a ∈ K a\in K a ∈ K n n n x x x ∣ f a ∣ ≤ H |f_a|\le H ∣ f a ∣ ≤ H a ∈ K a\in K a ∈ K
sup a ∈ K ∣ ∫ X f n , a d μ − ∫ X f a d μ ∣ ⟶ 0. (17) \sup_{a\in K}\left|\int_X f_{n,a}\,d\mu-\int_X f_a\,d\mu\right|\longrightarrow0. \tag*{(17)} a ∈ K sup ∫ X f n , a d μ − ∫ X f a d μ ⟶ 0. (17) Proof. On X 0 X_0 X 0 ∣ f a ( x ) ∣ ≤ H ( x ) |f_a(x)|\le H(x) ∣ f a ( x ) ∣ ≤ H ( x ) a ∈ K a\in K a ∈ K
g n ( x ) = sup a ∈ K ∣ f n , a ( x ) − f a ( x ) ∣ . g_n(x)=\sup_{a\in K}|f_{n,a}(x)-f_a(x)|. g n ( x ) = a ∈ K sup ∣ f n , a ( x ) − f a ( x ) ∣. In the application below, the functions depend continuously on the parameter on each cell where m n ( a ) m_n(a) m n ( a ) g n g_n g n g n → 0 g_n\to0 g n → 0 0 ≤ g n ≤ 2 H 0 \le g_n \le2H 0 ≤ g n ≤ 2 H g n g_n g n ∫ X g n d μ → 0 \int_X g_n\,d\mu\to0 ∫ X g n d μ → 0
But
sup a ∈ K ∣ ∫ X ( f n , a − f a ) d μ ∣ ≤ ∫ X sup a ∈ K ∣ f n , a − f a ∣ d μ = ∫ X g n d μ . \sup_{a\in K}\left|\int_X(f_{n,a}-f_a)\,d\mu\right|
\le\int_X\sup_{a\in K}|f_{n,a}-f_a|\,d\mu
= \int_X g_n\,d\mu. a ∈ K sup ∫ X ( f n , a − f a ) d μ ≤ ∫ X a ∈ K sup ∣ f n , a − f a ∣ d μ = ∫ X g n d μ . which proves (17). □ \square □
Theorem 2.9. Let K ⋐ ( 0 , ∞ ) K\Subset(0,\infty) K ⋐ ( 0 , ∞ ) m = m n ( a ) = ⌊ a n 2 / 3 ⌋ m=m_n(a)=\lfloor an^{2/3}\rfloor m = m n ( a ) = ⌊ a n 2/3 ⌋ B n B_n B n Ω n = B n [ − π , π ] 2 \Omega_n=B_n[-\pi,\pi]^2 Ω n = B n [ − π , π ] 2 R 2 \mathbb{R}^2 R 2 Φ a , Φ ∞ ∈ L 1 ( R 2 ) \Phi_a,\Phi_\infty\in L^1(\mathbb{R}^2) Φ a , Φ ∞ ∈ L 1 ( R 2 ) H ∈ L 1 ( R 2 ) H\in L^1(\mathbb{R}^2) H ∈ L 1 ( R 2 ) a ∈ K a\in K a ∈ K
(1) For almost every u ∈ R 2 u\in\mathbb{R}^2 u ∈ R 2 a ∈ K a\in K a ∈ K a a a
1 Ω n ( u ) e Ψ m n ( a ) , n ( B n − 1 u ) → Φ a ( u ) , 1 Ω n ( u ) e Ψ n , n ( B n − 1 u ) → Φ ∞ ( u ) . \mathbf{1}_{\Omega_n}(u)e^{\Psi_{m_n(a),n}(B_n^{-1}u)}\to\Phi_a(u),\qquad
\mathbf{1}_{\Omega_n}(u)e^{\Psi_{n,n}(B_n^{-1}u)}\to\Phi_\infty(u). 1 Ω n ( u ) e Ψ m n ( a ) , n ( B n − 1 u ) → Φ a ( u ) , 1 Ω n ( u ) e Ψ n , n ( B n − 1 u ) → Φ ∞ ( u ) . (2) Both moduli on the left-hand side are bounded by H ( u ) H(u) H ( u ) n n n a ∈ K a\in K a ∈ K
(3) J ∞ : = ∫ R 2 Φ ∞ ( u ) d u ≠ 0 J_\infty:=\int_{\mathbb{R}^2}\Phi_\infty(u)\,du\ne0 J ∞ := ∫ R 2 Φ ∞ ( u ) d u = 0
(4) For a continuous function E ( a ) E(a) E ( a )
C d , m n ( a ) ( r n , s n ) − C d , n ( r n , s n ) → E ( a ) C_{d,m_n(a)}(r_n,s_n)-C_{d,n}(r_n,s_n)\to E(a) C d , m n ( a ) ( r n , s n ) − C d , n ( r n , s n ) → E ( a ) uniformly on K K K
Then, uniformly for a ∈ K a\in K a ∈ K
P { L n ≤ a n 2 / 3 } ⟶ e E ( a ) ∫ R 2 Φ a ( u ) d u J ∞ . (18) \mathbb{P}\{L_n\le an^{2/3}\}\longrightarrow e^{E(a)}\frac{\int_{\mathbb{R}^2}\Phi_a(u)\,du}{J_\infty}. \tag*{(18)} P { L n ≤ a n 2/3 } ⟶ e E ( a ) J ∞ ∫ R 2 Φ a ( u ) d u . (18) If the right-hand side is identified with F P i t ( ( d − 1 ) 1 / 3 a , λ ( d − 1 ) − 2 / 3 ) F_{\mathrm{Pit}}((d-1)^{1/3}a,\lambda(d-1)^{-2/3}) F Pit (( d − 1 ) 1/3 a , λ ( d − 1 ) − 2/3 )
Proof. For u ∈ R 2 u\in\mathbb{R}^2 u ∈ R 2
f n , a ( u ) = 1 Ω n ( u ) e Ψ m n ( a ) , n ( B n − 1 u ) , f a ( u ) = Φ a ( u ) , f_{n,a}(u)=\mathbf{1}_{\Omega_n}(u)e^{\Psi_{m_n(a),n}(B_n^{-1}u)},\qquad f_a(u)=\Phi_a(u), f n , a ( u ) = 1 Ω n ( u ) e Ψ m n ( a ) , n ( B n − 1 u ) , f a ( u ) = Φ a ( u ) , g n ( u ) = 1 Ω n ( u ) e Ψ n , n ( B n − 1 u ) , g ( u ) = Φ ∞ ( u ) . g_n(u)=\mathbf{1}_{\Omega_n}(u)e^{\Psi_{n,n}(B_n^{-1}u)},\qquad g(u)=\Phi_\infty(u). g n ( u ) = 1 Ω n ( u ) e Ψ n , n ( B n − 1 u ) , g ( u ) = Φ ∞ ( u ) . Define
N n ( a ) = ∫ R 2 f n , a ( u ) d u , N ( a ) = ∫ R 2 Φ a ( u ) d u , N_n(a)=\int_{\mathbb{R}^2}f_{n,a}(u)\,du,\qquad N(a)=\int_{\mathbb{R}^2}\Phi_a(u)\,du, N n ( a ) = ∫ R 2 f n , a ( u ) d u , N ( a ) = ∫ R 2 Φ a ( u ) d u , and
D n = ∫ R 2 g n ( u ) d u , D = J ∞ = ∫ R 2 Φ ∞ ( u ) d u . D_n=\int_{\mathbb{R}^2}g_n(u)\,du,\qquad D=J_\infty=\int_{\mathbb{R}^2}\Phi_\infty(u)\,du. D n = ∫ R 2 g n ( u ) d u , D = J ∞ = ∫ R 2 Φ ∞ ( u ) d u . First step: uniform convergence of the integrals. Hypotheses 1 and 2 and Lemma 2.8 give
δ n : = sup a ∈ K ∣ N n ( a ) − N ( a ) ∣ → 0 , η n : = ∣ D n − D ∣ → 0. (19) \delta_n:=\sup_{a\in K}|N_n(a)-N(a)|\to0,\qquad\eta_n:=|D_n-D|\to0. \tag*{(19)} δ n := a ∈ K sup ∣ N n ( a ) − N ( a ) ∣ → 0 , η n := ∣ D n − D ∣ → 0. (19) It follows that
sup n ≥ n 0 sup a ∈ K ∣ N n ( a ) ∣ ≤ ∥ H ∥ 1 , sup a ∈ K ∣ N ( a ) ∣ ≤ ∥ H ∥ 1 . (20) \sup_{n\ge n_0}\sup_{a\in K}|N_n(a)|\le\|H\|_1,\qquad\sup_{a\in K}|N(a)|\le\|H\|_1. \tag*{(20)} n ≥ n 0 sup a ∈ K sup ∣ N n ( a ) ∣ ≤ ∥ H ∥ 1 , a ∈ K sup ∣ N ( a ) ∣ ≤ ∥ H ∥ 1 . (20) Second step: stability of the complex quotient. Since D ≠ 0 D \ne0 D = 0 n 1 n_{1} n 1 ∣ D n ∣ ≥ ∣ D ∣ / 2 |D_{n}| \ge|D|/2 ∣ D n ∣ ≥ ∣ D ∣/2 n ≥ n 1 n \ge n_{1} n ≥ n 1 n n n
sup a ∈ K ∣ N n ( a ) D n − N ( a ) D ∣ ≤ 2 δ n ∣ D ∣ + 2 ∥ H ∥ 1 η n ∣ D ∣ 2 → 0. (21) \sup_{a \in K} \left| \frac{N_{n}(a)}{D_{n}} - \frac{N(a)}{D} \right| \le\frac{2\delta_{n}}{|D|} + \frac{2\lVert H\rVert_{1}\eta_{n}}{|D|^{2}} \to0. \tag*{(21)} a ∈ K sup D n N n ( a ) − D N ( a ) ≤ ∣ D ∣ 2 δ n + ∣ D ∣ 2 2 ∥ H ∥ 1 η n → 0. (21) This estimate explicitly justifies passage to the quotient and shows that no positivity of the complex integrals is required.
Third step: the exponential factor. Put
E n ( a ) = C d , m n ( a ) ( r n , s n ) − C d , n ( r n , s n ) . E_{n}(a) = C_{d,m_{n}(a)}(r_{n},s_{n}) - C_{d,n}(r_{n},s_{n}). E n ( a ) = C d , m n ( a ) ( r n , s n ) − C d , n ( r n , s n ) . Hypothesis 4 gives ε n : = sup a ∈ K ∣ E n ( a ) − E ( a ) ∣ → 0 \varepsilon_{n} := \sup_{a \in K} |E_{n}(a) - E(a)| \to0 ε n := sup a ∈ K ∣ E n ( a ) − E ( a ) ∣ → 0 E E E K K K n n n ∣ E n ( a ) ∣ ≤ R |E_{n}(a)| \le R ∣ E n ( a ) ∣ ≤ R ∣ E ( a ) ∣ ≤ R |E(a)| \le R ∣ E ( a ) ∣ ≤ R a a a
sup a ∈ K ∣ e E n ( a ) − e E ( a ) ∣ ≤ e R ε n → 0. (22) \sup_{a \in K} \left|e^{E_{n}(a)} - e^{E(a)}\right| \le e^{R}\varepsilon_{n} \to0. \tag*{(22)} a ∈ K sup e E n ( a ) − e E ( a ) ≤ e R ε n → 0. (22) Fourth step: return to the contours. The change of variables u = B n θ u = B_{n}\theta u = B n θ
I k , n = ∣ det B n ∣ − 1 ∫ Ω n e Ψ k , n ( B n − 1 u ) d u . I_{k,n} = |\det B_{n}|^{-1} \int_{\Omega_{n}} e^{\Psi_{k,n}(B_{n}^{-1}u)}\,du. I k , n = ∣ det B n ∣ − 1 ∫ Ω n e Ψ k , n ( B n − 1 u ) d u . The two Jacobian factors cancel in quotient (16). Thus
P { L n ≤ a n 2 / 3 } = e E n ( a ) N n ( a ) D n . \mathbb{P}\{L_{n} \le an^{2/3}\} = e^{E_{n}(a)}\frac{N_{n}(a)}{D_{n}}. P { L n ≤ a n 2/3 } = e E n ( a ) D n N n ( a ) . Bounds (21) and (22), together with (20), imply
sup a ∈ K ∣ e E n ( a ) N n ( a ) D n − e E ( a ) N ( a ) D ∣ → 0 , \sup_{a \in K} \left|e^{E_{n}(a)}\frac{N_{n}(a)}{D_{n}} - e^{E(a)}\frac{N(a)}{D}\right| \to0, a ∈ K sup e E n ( a ) D n N n ( a ) − e E ( a ) D N ( a ) → 0 , which is exactly (18). The last assertion is a substitution of identities, not an additional convergence hypothesis. □ \square □
Remark 2.11. Proposition 2.7 already provides domination outside a neighbourhood of the saddle. Theorem 2.9 is an autonomous transfer theorem: all its analytic implications are proved above. Applying it to a concrete family naturally requires verification of its four hypotheses, in particular construction of B n B_{n} B n
Hypertrees and singularities
Let T d ( x ) T_{d}(x) T d ( x ) d d d d − 1 d-1 d − 1
T d ( x ) = x exp ( T d ( x ) d − 1 ( d − 1 ) ! ) . (23) T_{d}(x) = x\exp\left(\frac{T_{d}(x)^{d-1}}{(d-1)!}\right). \tag*{(23)} T d ( x ) = x exp ( ( d − 1 )! T d ( x ) d − 1 ) . (23) Let U d ( x ) U_{d}(x) U d ( x )
Proposition 3.1 (Exact enumeration and EGF of hypertrees). For v = 1 + ( d − 1 ) e v = 1 + (d-1)e v = 1 + ( d − 1 ) e d d d v v v e e e
C d ( v , e ) = ( v − 1 ) ! v e − 1 e ! ( ( d − 1 ) ! ) e . (24) C_{d}(v,e) = \frac{(v-1)!v^{e-1}}{e!((d-1)!)^{e}}. \tag*{(24)} C d ( v , e ) = e ! (( d − 1 )! ) e ( v − 1 )! v e − 1 . (24) It is zero for other values of v v v
U d ( x ) = T d ( x ) − d − 1 d ! T d ( x ) d = T d ( x ) − T d ( x ) d d ( d − 2 ) ! . (25) U_d(x)=T_d(x)-\frac{d-1}{d!}T_d(x)^d=T_d(x)-\frac{T_d(x)^d}{d(d-2)!}. \tag*{(25)} U d ( x ) = T d ( x ) − d ! d − 1 T d ( x ) d = T d ( x ) − d ( d − 2 )! T d ( x ) d . (25) Proof. Lagrange inversion applied to (23) gives [ x v ] T d ( x ) = v e − 1 / [ e ! ( ( d − 1 ) ! ) e ] [x^v]T_d(x)=v^{e-1}/[e!((d-1)!)^e] [ x v ] T d ( x ) = v e − 1 / [ e ! (( d − 1 )! ) e ] v − 1 = ( d − 1 ) e v-1=(d-1)e v − 1 = ( d − 1 ) e v v v v ! [ x v ] T d ( x ) v![x^v]T_d(x) v ! [ x v ] T d ( x ) v v v d = 2 d=2 d = 2 v v − 2 v^{v-2} v v − 2 [13 ] ; for d ≥ 3 d\ge3 d ≥ 3 [3 ] . Since x U d ′ ( x ) = T d ( x ) xU_d'(x)=T_d(x) x U d ′ ( x ) = T d ( x ) x = t exp ( − t d − 1 / ( d − 1 ) ! ) x=t\exp(-t^{d-1}/(d-1)!) x = t exp ( − t d − 1 / ( d − 1 )!) 0 0 0 t t t
For d = 2 d=2 d = 2 C 2 ( v , v − 1 ) = v v − 2 C_2(v,v-1)=v^{v-2} C 2 ( v , v − 1 ) = v v − 2 v ! e v v!e^v v ! e v v v v
Proposition 3.2 (Puiseux expansion on the positive axis). Put
τ d = ( ( d − 2 ) ! ) 1 / ( d − 1 ) , ρ d = τ d e − 1 / ( d − 1 ) , σ d = τ d 2 d − 1 . \tau_d=((d-2)!)^{1/(d-1)},\qquad\rho_d=\tau_d e^{-1/(d-1)},\qquad\sigma_d=\tau_d\sqrt{\frac{2}{d-1}}. τ d = (( d − 2 )! ) 1/ ( d − 1 ) , ρ d = τ d e − 1/ ( d − 1 ) , σ d = τ d d − 1 2 . As x ↑ ρ d x\uparrow\rho_d x ↑ ρ d
T d ( x ) = τ d − σ d 1 − x / ρ d + O ( 1 − x / ρ d ) , (26) T_d(x)=\tau_d-\sigma_d\sqrt{1-x/\rho_d}+O(1-x/\rho_d), \tag*{(26)} T d ( x ) = τ d − σ d 1 − x / ρ d + O ( 1 − x / ρ d ) , (26) U d ( x ) = d − 1 d τ d − τ d ( 1 − x / ρ d ) + O ( ( 1 − x / ρ d ) 3 / 2 ) . (27) U_d(x)=\frac{d-1}{d}\tau_d-\tau_d(1-x/\rho_d)+O((1-x/\rho_d)^{3/2}). \tag*{(27)} U d ( x ) = d d − 1 τ d − τ d ( 1 − x / ρ d ) + O (( 1 − x / ρ d ) 3/2 ) . (27) For d > 2 d>2 d > 2 T d T_d T d ρ d \rho_d ρ d
Proof. Let x ( t ) = t exp [ − t d − 1 / ( d − 1 ) ! ] x(t)=t\exp[-t^{d-1}/(d-1)!] x ( t ) = t exp [ − t d − 1 / ( d − 1 )!] t d − 1 = ( d − 2 ) ! t^{d-1}=(d-2)! t d − 1 = ( d − 2 )! t = τ d t=\tau_d t = τ d x ( τ d ) = ρ d x(\tau_d)=\rho_d x ( τ d ) = ρ d x ′ ( τ d ) = 0 x'(\tau_d)=0 x ′ ( τ d ) = 0 x ′ ′ ( τ d ) / ρ d = − ( d − 1 ) / τ d 2 x''(\tau_d)/\rho_d=-(d-1)/\tau_d^2 x ′′ ( τ d ) / ρ d = − ( d − 1 ) / τ d 2 U d ( ρ d ) = ( d − 1 ) τ d / d U_d(\rho_d)=(d-1)\tau_d/d U d ( ρ d ) = ( d − 1 ) τ d / d x U d ′ ( x ) = T d ( x ) xU_d'(x)=T_d(x) x U d ′ ( x ) = T d ( x ) ρ d U d ′ ( ρ d ) = τ d \rho_dU_d'(\rho_d)=\tau_d ρ d U d ′ ( ρ d ) = τ d − τ d ( 1 − x / ρ d ) -\tau_d(1-x/\rho_d) − τ d ( 1 − x / ρ d ) U d ′ ( x ) = T d ( x ) / x U_d'(x)=T_d(x)/x U d ′ ( x ) = T d ( x ) / x 1 1 1 d − 1 d-1 d − 1
Corollary 3.4 (Scale of the hypertree coefficients). Along v ≡ 1 ( m o d d − 1 ) v\equiv1\pmod{d-1} v ≡ 1 ( mod d − 1 )
C d ( v , v − 1 d − 1 ) ∼ ( d − 1 ) σ d 2 π v ! ρ d − v v − 5 / 2 . C_d\left(v,\frac{v-1}{d-1}\right)\sim\frac{(d-1)\sigma_d}{2\sqrt{\pi}}v!\rho_d^{-v}v^{-5/2}. C d ( v , d − 1 v − 1 ) ∼ 2 π ( d − 1 ) σ d v ! ρ d − v v − 5/2 . Proof. From x U d ′ ( x ) = T d ( x ) xU_d'(x)=T_d(x) x U d ′ ( x ) = T d ( x ) ε = 1 − x / ρ d \varepsilon=1-x/\rho_d ε = 1 − x / ρ d
U d ( x ) = d − 1 d τ d − τ d ε + 2 σ d 3 ε 3 / 2 + O ( ε 2 ) . U_d(x)=\frac{d-1}{d}\tau_d-\tau_d\varepsilon+\frac{2\sigma_d}{3}\varepsilon^{3/2}+O(\varepsilon^2). U d ( x ) = d d − 1 τ d − τ d ε + 3 2 σ d ε 3/2 + O ( ε 2 ) . Transfer of the singular term gives σ d ρ d − v v − 5 / 2 / ( 2 π ) \sigma_d\rho_d^{-v}v^{-5/2}/(2\sqrt{\pi}) σ d ρ d − v v − 5/2 / ( 2 π ) Γ ( − 3 / 2 ) = 4 π / 3 \Gamma(-3/2)=4\sqrt{\pi}/3 Γ ( − 3/2 ) = 4 π /3 d − 1 d-1 d − 1 v ≡ 1 ( m o d d − 1 ) v\equiv1\pmod{d-1} v ≡ 1 ( mod d − 1 )
Table of tree constants
The constants of Proposition 3.2, in particular A d a r b = U d ( ρ d ) A_d^{\mathrm{arb}} = U_d(\rho_d) A d arb = U d ( ρ d ) B d a r b B_d^{\mathrm{arb}} B d arb ( 1 − x / ρ d ) (1-x/\rho_d) ( 1 − x / ρ d ) U d ( x ) U_d(x) U d ( x )
Table 1.
All entries follow from A d a r b = ( d − 1 ) τ d / d A_d^{\mathrm{arb}}=(d-1)\tau_d/d A d arb = ( d − 1 ) τ d / d B d a r b = − τ d B_d^{\mathrm{arb}}=-\tau_d B d arb = − τ d
Unicyclic components
For a connected d d d v + e v+e v + e d e de d e d e − ( v + e ) + 1 = ( d − 1 ) e − v + 1 = ℓ + 1 de-(v+e)+1=(d-1)e-v+1=\ell+1 d e − ( v + e ) + 1 = ( d − 1 ) e − v + 1 = ℓ + 1 V d ( x ) V_d(x) V d ( x )
Theorem 4.1 (EGF of unicyclic components). Put
Y d ( x ) = T d ( x ) d − 1 ( d − 2 ) ! . Y_d(x)=\frac{T_d(x)^{d-1}}{(d-2)!}. Y d ( x ) = ( d − 2 )! T d ( x ) d − 1 . Then
V d ( x ) = 1 2 ( log 1 1 − Y d ( x ) − Y d ( x ) − Y d ( x ) 2 2 ) + 1 { d ≥ 3 } Y d ( x ) 2 4 . (28) V_d(x)=\frac{1}{2}\left(\log\frac{1}{1-Y_d(x)}-Y_d(x)-\frac{Y_d(x)^2}{2}\right)+\mathbf{1}_{\{d\geq3\}}\frac{Y_d(x)^2}{4}. \tag*{(28)} V d ( x ) = 2 1 ( log 1 − Y d ( x ) 1 − Y d ( x ) − 2 Y d ( x ) 2 ) + 1 { d ≥ 3 } 4 Y d ( x ) 2 . (28) For d = 2 d=2 d = 2 d ≥ 3 d\geq3 d ≥ 3 d d d
Proof. The incidence graph of a unicyclic hypergraph has a unique alternating cycle. For an incidence cycle of length 2 j 2j 2 j j ≥ 3 j\geq3 j ≥ 3 j j j d − 2 d-2 d − 2 T d d − 2 / ( d − 2 ) ! T_d^{d-2}/(d-2)! T d d − 2 / ( d − 2 )! 2 j 2j 2 j Y d j / ( 2 j ) Y_d^j/(2j) Y d j / ( 2 j ) j ≥ 3 j\geq3 j ≥ 3 d ≥ 3 d\geq3 d ≥ 3 d − 2 ≥ 1 d-2\geq1 d − 2 ≥ 1 Y d 2 / 4 Y_d^2/4 Y d 2 /4 d = 2 d=2 d = 2
Proposition 4.2 (Singularity and unicyclic coefficients). As x ↑ ρ d x\uparrow\rho_d x ↑ ρ d
V d ( x ) = 1 4 log 1 1 − x / ρ d + K d ( 0 ) + O ( 1 − x / ρ d ) . (29) V_d(x)=\frac{1}{4}\log\frac{1}{1-x/\rho_d}+K_d^{(0)}+O\left(\sqrt{1-x/\rho_d}\right). \tag*{(29)} V d ( x ) = 4 1 log 1 − x / ρ d 1 + K d ( 0 ) + O ( 1 − x / ρ d ) . (29) where K d ( 0 ) K_d^{(0)} K d ( 0 ) v → ∞ v\to\infty v → ∞ d − 1 d-1 d − 1
C d ( v , v d − 1 ) = d − 1 4 v v ! ρ d − v ( 1 + O ( v − 1 / 2 ) ) . (30) C_d\left(v,\frac{v}{d-1}\right)=\frac{d-1}{4v}v!\rho_d^{-v}\left(1+O\left(v^{-1/2}\right)\right). \tag*{(30)} C d ( v , d − 1 v ) = 4 v d − 1 v ! ρ d − v ( 1 + O ( v − 1/2 ) ) . (30) For other values of v v v
Proof. Equation (26) and τ d d − 1 = ( d − 2 ) ! \tau_d^{d-1}=(d-2)! τ d d − 1 = ( d − 2 )!
1 − Y d ( x ) = 2 ( d − 1 ) 1 − x / ρ d + O ( 1 − x / ρ d ) . 1-Y_d(x)=\sqrt{2(d-1)}\sqrt{1-x/\rho_d}+O(1-x/\rho_d). 1 − Y d ( x ) = 2 ( d − 1 ) 1 − x / ρ d + O ( 1 − x / ρ d ) . Substitution in (28) proves (29) . By (23) , V d ( x ) V_d(x) V d ( x ) x d − 1 x^{d-1} x d − 1 d − 1 d-1 d − 1 v ≡ 0 ( m o d d − 1 ) v \equiv0 \pmod{d-1} v ≡ 0 ( mod d − 1 ) ( d − 1 ) ρ d − v / ( 4 v ) (d-1)\rho_d^{-v}/(4v) ( d − 1 ) ρ d − v / ( 4 v ) O ( ρ d − v v − 3 / 2 ) O(\rho_d^{-v}v^{-3/2}) O ( ρ d − v v − 3/2 ) (23) and (28) admit the required local slit domains by analytic inversion near their finitely many critical points [8 Theorem VI.3] . Multiplication by v ! v! v ! (30) . □
A partial harmonic sum
Put a v = [ x v ] V d ( x ) ρ d v a_v=[x^v]V_d(x)\rho_d^v a v = [ x v ] V d ( x ) ρ d v S m = ∑ 1 ≤ v ≤ m a v S_m=\sum_{1\le v\le m}a_v S m = ∑ 1 ≤ v ≤ m a v (30) ,
S m = 1 4 ∑ j ≤ m / ( d − 1 ) 1 j + O ( 1 ) = 1 4 log m + O ( 1 ) . S_m=\frac{1}{4}\sum_{j\le m/(d-1)}\frac{1}{j}+O(1)=\frac{1}{4}\log m+O(1). S m = 4 1 j ≤ m / ( d − 1 ) ∑ j 1 + O ( 1 ) = 4 1 log m + O ( 1 ) . In fact, the error after subtraction of the harmonic term converges, since its terms are O ( j − 3 / 2 ) O(j^{-3/2}) O ( j − 3/2 )
Complex components and analytic passage to a limit law
The results of this section belong to the analytic route: they establish exact identities and fixed-excess expansions, but do not provide the estimates uniform in ℓ \ell ℓ § 7 ), without using any result of this section.
For ℓ ≥ 1 \ell\ge1 ℓ ≥ 1
A ℓ , d ( x ) = ∑ v ≥ 1 v + ℓ ≡ 0 ( m o d d − 1 ) C d ( v , v + ℓ d − 1 ) x v v ! . A_{\ell,d}(x)=\sum_{\substack{v\ge1\\v+\ell\equiv0\pmod{d-1}}}C_d\left(v,\frac{v+\ell}{d-1}\right)\frac{x^v}{v!}. A ℓ , d ( x ) = v ≥ 1 v + ℓ ≡ 0 ( mod d − 1 ) ∑ C d ( v , d − 1 v + ℓ ) v ! x v . These series describe components whose incidence graph has at least two independent cycles. For fixed v v v (7) . At the critical scale, controlling their contributions requires uniform estimates over the excesses present in the saddle region. The precise form of such an estimate depends on the combinatorial kernel decomposition used.
Theorem 5.1 (Wright transfer under a local singular hypothesis). Fix d ≥ 2 d\ge2 d ≥ 2 ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 A ℓ , d A_{\ell,d} A ℓ , d
A ℓ , d ( x ) = b ℓ , d ( 1 − x / ρ d ) − 3 ℓ / 2 + O ( ( 1 − x / ρ d ) − 3 ℓ / 2 + 1 / 2 ) , A_{\ell,d}(x)=b_{\ell,d}(1-x/\rho_d)^{-3\ell/2}+O\left((1-x/\rho_d)^{-3\ell/2+1/2}\right), A ℓ , d ( x ) = b ℓ , d ( 1 − x / ρ d ) − 3 ℓ /2 + O ( ( 1 − x / ρ d ) − 3 ℓ /2 + 1/2 ) , where b ℓ , d > 0 b_{\ell,d}>0 b ℓ , d > 0 v v v
C d ( v , v + ℓ d − 1 ) = ( d − 1 ) b ℓ , d Γ ( 3 ℓ / 2 ) v ! ρ d − v v 3 ℓ / 2 − 1 ( 1 + O ( v − 1 / 2 ) ) . C_d\left(v,\frac{v+\ell}{d-1}\right)=\frac{(d-1)b_{\ell,d}}{\Gamma(3\ell/2)}v!\rho_d^{-v}v^{3\ell/2-1}\left(1+O(v^{-1/2})\right). C d ( v , d − 1 v + ℓ ) = Γ ( 3 ℓ /2 ) ( d − 1 ) b ℓ , d v ! ρ d − v v 3 ℓ /2 − 1 ( 1 + O ( v − 1/2 ) ) . In particular, when d = 2 d=2 d = 2 ( d = 2 ) (d=2) ( d = 2 )
C 2 ( v , v + ℓ ) = b ℓ , 2 Γ ( 3 ℓ / 2 ) v ! ρ 2 − v v 3 ℓ / 2 − 1 ( 1 + O ( v − 1 / 2 ) ) . (31) C_2(v,v+\ell)=\frac{b_{\ell,2}}{\Gamma(3\ell/2)}v!\rho_2^{-v}v^{3\ell/2-1}\left(1+O(v^{-1/2})\right). \tag*{(31)} C 2 ( v , v + ℓ ) = Γ ( 3 ℓ /2 ) b ℓ , 2 v ! ρ 2 − v v 3 ℓ /2 − 1 ( 1 + O ( v − 1/2 ) ) . (31) Proof. Apply the standard transfer theorem [8 ] to the dominant algebraic singularity and the indicated remainder at each dominant point. The rotation symmetry eliminates nonadmissible powers and multiplies the leading coefficient on admissible powers by d − 1 d-1 d − 1
Theorem 5.1 is deliberately pointwise in ℓ \ell ℓ b ℓ , d b_{\ell,d} b ℓ , d ℓ → ∞ \ell\to\infty ℓ → ∞ ℓ \ell ℓ d d d T T T T d T_d T d
Proposition 5.2 (Quantitative criterion for excess summation). Let K ⋐ ( 0 , ∞ ) K \Subset(0,\infty) K ⋐ ( 0 , ∞ ) m n ( a ) = ⌊ a n 2 / 3 ⌋ m_n(a)=\lfloor an^{2/3}\rfloor m n ( a ) = ⌊ a n 2/3 ⌋ ( y n , z n ) (y_n,z_n) ( y n , z n ) C , R > 0 C,R>0 C , R > 0 a ∈ K a\in K a ∈ K n n n ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 θ \theta θ
∣ z n ℓ / ( d − 1 ) A ℓ , d , m n ( a ) ( y n e i θ ) ∣ ≤ C R ℓ Γ ( ℓ / 2 + 1 ) . (32) \left|z_n^{\ell/(d-1)}A_{\ell,d,m_n(a)}(y_ne^{i\theta})\right|\le C\frac{R^\ell}{\Gamma(\ell/2+1)}. \tag*{(32)} z n ℓ / ( d − 1 ) A ℓ , d , m n ( a ) ( y n e i θ ) ≤ C Γ ( ℓ /2 + 1 ) R ℓ . (32) If, for each fixed ℓ \ell ℓ a ∈ K a\in K a ∈ K G ℓ , a G_{\ell,a} G ℓ , a
∑ ℓ ≥ 1 z n ℓ / ( d − 1 ) A ℓ , d , m n ( a ) ( y n e i θ ) ⟶ ∑ ℓ ≥ 1 G ℓ , a ( θ ) \sum_{\ell\ge1}z_n^{\ell/(d-1)}A_{\ell,d,m_n(a)}(y_ne^{i\theta})\longrightarrow\sum_{\ell\ge1}G_{\ell,a}(\theta) ℓ ≥ 1 ∑ z n ℓ / ( d − 1 ) A ℓ , d , m n ( a ) ( y n e i θ ) ⟶ ℓ ≥ 1 ∑ G ℓ , a ( θ ) uniformly in a ∈ K a\in K a ∈ K
Proof. The series ∑ ℓ ≥ 1 R ℓ / Γ ( ℓ / 2 + 1 ) \sum_{\ell\ge1}R^\ell/\Gamma(\ell/2+1) ∑ ℓ ≥ 1 R ℓ /Γ ( ℓ /2 + 1 ) R < ∞ R<\infty R < ∞ e R 2 − 1 e^{R^2}-1 e R 2 − 1 R 2 R^2 R 2 Γ ( ℓ / 2 + 1 ) ∼ 2 π ( ℓ / 2 ) ℓ / 2 e − ℓ / 2 \Gamma(\ell/2+1)\sim\sqrt{2\pi}(\ell/2)^{\ell/2}e^{-\ell/2} Γ ( ℓ /2 + 1 ) ∼ 2 π ( ℓ /2 ) ℓ /2 e − ℓ /2 a a a □ \square □
Remark 5.3 (Scope of the analytic criterion). Proposition 5.2 reduces excess summation to verification of a pointwise bound. It is a conditional implication: it does not prove (32), but only states what would follow from it. § 9 draws the boundary between fixed-excess asymptotics and the uniform estimates required; this criterion plays no part in the probabilistic proof of Theorem 1.1.
Remark 5.4 (Passage to hypergraph excess notation). The notation C d ( v , v + ℓ ) C_d(v,v+\ell) C d ( v , v + ℓ ) d = 2 d=2 d = 2 ℓ = e − v \ell=e-v ℓ = e − v d > 2 d>2 d > 2 ℓ = ( d − 1 ) e − v \ell=(d-1)e-v ℓ = ( d − 1 ) e − v e = ( v + ℓ ) / ( d − 1 ) e=(v+\ell)/(d-1) e = ( v + ℓ ) / ( d − 1 ) C d ( v , ( v + ℓ ) / ( d − 1 ) ) C_d(v,(v+\ell)/(d-1)) C d ( v , ( v + ℓ ) / ( d − 1 )) v + ℓ ≡ 0 ( m o d d − 1 ) v+\ell\equiv0\pmod{d-1} v + ℓ ≡ 0 ( mod d − 1 )
To obtain a limit for the largest component from (9) , one must control these component classes uniformly and carry out a saddle-point calculation with the correct fixed-edge normalization. For graphs, these difficulties are resolved by known critical results [17 , 15 ] . We do not deduce a general integral law for d d d
Excess rescaling and the cancellation mechanism
Group connected components by excess before applying the saddle-point method. Put h = d − 1 h=d-1 h = d − 1 ℓ ≥ − 1 \ell\ge-1 ℓ ≥ − 1
A ℓ , d , m ( y ) = ∑ 1 ≤ v ≤ m v + ℓ ≡ 0 ( m o d h ) C d ( v , v + ℓ h ) y v v ! . A_{\ell,d,m}(y)=\sum_{\substack{1\le v\le m\\v+\ell\equiv0\pmod h}}C_d\left(v,\frac{v+\ell}{h}\right)\frac{y^v}{v!}. A ℓ , d , m ( y ) = 1 ≤ v ≤ m v + ℓ ≡ 0 ( mod h ) ∑ C d ( v , h v + ℓ ) v ! y v . In particular, A − 1 , d , m A_{-1,d,m} A − 1 , d , m A 0 , d , m A_{0,d,m} A 0 , d , m
Theorem 6.1 (Exact rescaling by excess). For every real z > 0 z>0 z > 0 with y = x z 1 / h y=xz^{1/h} y = x z 1/ h
C d , m ( x , z ) = ∑ ℓ ≥ − 1 z ℓ / h A ℓ , d , m ( y ) . (33) C_{d,m}(x,z)=\sum_{\ell\geq-1}z^{\ell/h}A_{\ell,d,m}(y). \tag*{(33)} C d , m ( x , z ) = ℓ ≥ − 1 ∑ z ℓ / h A ℓ , d , m ( y ) . (33) Consequently, putting q = 1 − p q=1-p q = 1 − p z = p / q z=p/q z = p / q
P p { L n ≤ m } = q N n ! z n / h [ y n ] exp ( z − 1 / h A − 1 , d , m ( y ) + A 0 , d , m ( y ) + ∑ ℓ ≥ 1 z ℓ / h A ℓ , d , m ( y ) ) . (34) \mathbb{P}_p\{L_n\leq m\}=q^N n!z^{n/h}[y^n]\exp\left(z^{-1/h}A_{-1,d,m}(y)+A_{0,d,m}(y)+\sum_{\ell\geq1}z^{\ell/h}A_{\ell,d,m}(y)\right). \tag*{(34)} P p { L n ≤ m } = q N n ! z n / h [ y n ] exp ( z − 1/ h A − 1 , d , m ( y ) + A 0 , d , m ( y ) + ℓ ≥ 1 ∑ z ℓ / h A ℓ , d , m ( y ) ) . (34) Proof. For each component, h e = v + ℓ he=v+\ell h e = v + ℓ z e x v = z ℓ / h ( x z 1 / h ) v z^{e}x^v=z^{\ell/h}(xz^{1/h})^v z e x v = z ℓ / h ( x z 1/ h ) v [ x n ] f ( x z 1 / h ) = z n / h [ y n ] f ( y ) [x^n]f(xz^{1/h})=z^{n/h}[y^n]f(y) [ x n ] f ( x z 1/ h ) = z n / h [ y n ] f ( y ) z > 0 z>0 z > 0 z z z
In window (1), p = M / N p=M/N p = M / N z = ( τ d / n ) h ( 1 + λ n − 1 / 3 + O ( n − 1 ) ) z=(\tau_d/n)^h(1+\lambda n^{-1/3}+O(n^{-1})) z = ( τ d / n ) h ( 1 + λ n − 1/3 + O ( n − 1 )) z − 1 / h ≍ n z^{-1/h}\asymp n z − 1/ h ≍ n z 0 / h = 1 z^{0/h}=1 z 0/ h = 1 z ℓ / h ≍ n − ℓ z^{\ell/h}\asymp n^{-\ell} z ℓ / h ≍ n − ℓ ℓ ≥ 1 \ell\geq1 ℓ ≥ 1 n n n n ( d − 1 ) 2 n^{(d-1)2} n ( d − 1 ) 2
Theorem 6.2 (Cancellation of the tree normalization). Let p = M / N p=M/N p = M / N q = 1 − p q=1-p q = 1 − p z = p / q z=p/q z = p / q and suppose M M M satisfies (1). Define the positive quantity
B n = q N n ! z n / h ρ d − n exp ( z − 1 / h U d ( ρ d ) ) . B_n=q^N n!z^{n/h}\rho_d^{-n}\exp\left(z^{-1/h}U_d(\rho_d)\right). B n = q N n ! z n / h ρ d − n exp ( z − 1/ h U d ( ρ d ) ) . For fixed d d d and λ \lambda λ in a bounded set,
log B n = 1 2 log n + O ( 1 ) . (35) \log B_n=\frac{1}{2}\log n+O(1). \tag*{(35)} log B n = 2 1 log n + O ( 1 ) . (35) In particular, its terms of orders n n n n 2 / 3 n^{2/3} n 2/3 n 1 / 3 n^{1/3} n 1/3 m ≍ n 2 / 3 m\asymp n^{2/3} m ≍ n 2/3 U d ( ρ d ) U_d(\rho_d) U d ( ρ d ) A − 1 , d , m ( ρ d ) A_{-1,d,m}(\rho_d) A − 1 , d , m ( ρ d ) log B n \log B_n log B n O ( 1 ) O(1) O ( 1 )
Proof. Put t = λ n − 1 / 3 t=\lambda n^{-1/3} t = λ n − 1/3 τ d h = ( d − 2 ) ! \tau_d^h=(d-2)! τ d h = ( d − 2 )! U d ( ρ d ) = h τ d / d U_d(\rho_d)=h\tau_d/d U d ( ρ d ) = h τ d / d ρ d = τ d e − 1 / h \rho_d=\tau_d e^{-1/h} ρ d = τ d e − 1/ h
log ( q N ) = − n d h ( 1 + t ) + O ( 1 ) , \log(q^N)=-\frac{n}{dh}(1+t)+O(1), log ( q N ) = − d h n ( 1 + t ) + O ( 1 ) , log ( n ! z n / h ρ d − n ) = n ( − 1 + 1 h + 1 h log ( 1 + t ) ) + 1 2 log n + O ( 1 ) , \log(n!z^{n/h}\rho_d^{-n})=n\left(-1+\frac{1}{h}+\frac{1}{h}\log(1+t)\right)+\frac{1}{2}\log n+O(1), log ( n ! z n / h ρ d − n ) = n ( − 1 + h 1 + h 1 log ( 1 + t ) ) + 2 1 log n + O ( 1 ) , z − 1 / h U d ( ρ d ) = n h d ( 1 + t ) − 1 / h + O ( 1 ) . z^{-1/h}U_d(\rho_d)=\frac{nh}{d}(1+t)^{-1/h}+O(1). z − 1/ h U d ( ρ d ) = d nh ( 1 + t ) − 1/ h + O ( 1 ) . For d = 2 d=2 d = 2 O ( 1 ) O(1) O ( 1 ) N log ( 1 − p ) N\log(1-p) N log ( 1 − p ) λ \lambda λ
f h ( t ) = − 1 + t d h − 1 + 1 h + 1 h log ( 1 + t ) + h d ( 1 + t ) − 1 / h . f_h(t)=-\frac{1+t}{dh}-1+\frac{1}{h}+\frac{1}{h}\log(1+t)+\frac{h}{d}(1+t)^{-1/h}. f h ( t ) = − d h 1 + t − 1 + h 1 + h 1 log ( 1 + t ) + d h ( 1 + t ) − 1/ h . Since d = h + 1 d=h+1 d = h + 1 f h ( 0 ) = f h ′ ( 0 ) = f h ′ ′ ( 0 ) = 0 f_h(0)=f_h'(0)=f_h''(0)=0 f h ( 0 ) = f h ′ ( 0 ) = f h ′′ ( 0 ) = 0 n f h ( t ) = O ( n t 3 ) = O ( 1 ) nf_h(t)=O(nt^3)=O(1) n f h ( t ) = O ( n t 3 ) = O ( 1 ) [ x v ] U d ( x ) ρ d v = O ( v − 5 / 2 ) [x^v]U_d(x)\rho_d^v=O(v^{-5/2}) [ x v ] U d ( x ) ρ d v = O ( v − 5/2 ) m m m O ( m − 3 / 2 ) O(m^{-3/2}) O ( m − 3/2 ) z − 1 / h = O ( n ) z^{-1/h}=O(n) z − 1/ h = O ( n ) O ( n m − 3 / 2 ) = O ( 1 ) O(nm^{-3/2})=O(1) O ( n m − 3/2 ) = O ( 1 )
Corollary 6.3 (Critical cubic contribution). With the notation of Theorem 6.2 , the part of log B n − 1 2 log n \log B_n-\frac{1}{2}\log n log B n − 2 1 log n depending on the three displayed order- n n n terms has limit
− λ 3 6 ( d − 1 ) 2 . -\frac{\lambda^3}{6(d-1)^2}. − 6 ( d − 1 ) 2 λ 3 . All other bounded terms come from the next term of Stirling’s formula, the exact expansion of N log ( 1 − p ) N\log(1-p) N log ( 1 − p ) and the O ( n − 1 ) O(n^{-1}) O ( n − 1 ) correction in z z z
Proof. Writing h = d − 1 h=d-1 h = d − 1 f h ′ ′ ′ ( 0 ) = − h − 2 f_h'''(0)=-h^{-2} f h ′′′ ( 0 ) = − h − 2 t = λ n − 1 / 3 t=\lambda n^{-1/3} t = λ n − 1/3 f h ( 0 ) = f h ′ ( 0 ) = f h ′ ′ ( 0 ) = 0 f_h(0)=f_h'(0)=f_h''(0)=0 f h ( 0 ) = f h ′ ( 0 ) = f h ′′ ( 0 ) = 0 n f h ( t ) = − λ 3 / ( 6 h 2 ) + O ( n − 1 / 3 ) nf_h(t)=-\lambda^3/(6h^2)+O(n^{-1/3}) n f h ( t ) = − λ 3 / ( 6 h 2 ) + O ( n − 1/3 )
Balance of complex components
Suppose the fixed-excess singular expansion of Theorem 5.1 holds with exponent 3 ℓ / 2 3\ell/2 3 ℓ /2 1 − y / ρ d ≍ n − 2 / 3 1-y/\rho_d\asymp n^{-2/3} 1 − y / ρ d ≍ n − 2/3 A ℓ , d ( y ) ≍ n ℓ A_{\ell,d}(y)\asymp n^\ell A ℓ , d ( y ) ≍ n ℓ ℓ \ell ℓ z ℓ / h ≍ n − ℓ z^{\ell/h}\asymp n^{-\ell} z ℓ / h ≍ n − ℓ (34) then makes each fixed-excess class of order one. This explains the initial argument leading to the n 2 / 3 n^{2/3} n 2/3 ℓ \ell ℓ ℓ \ell ℓ
Euler–Maclaurin structure of small components
The tree and unicyclic estimates already explain the two nonpolynomial normalization terms appearing in a critical coefficient calculation. For m = ⌊ a n 2 / 3 ⌋ m=\lfloor an^{2/3}\rfloor m = ⌊ a n 2/3 ⌋ Corollary 3.4 gives
z − 1 / h ∑ v > m [ x v ] U d ( x ) ρ d v = O ( 1 ) , z^{-1/h}\sum_{v>m}[x^v]U_d(x)\rho_d^v=O(1), z − 1/ h v > m ∑ [ x v ] U d ( x ) ρ d v = O ( 1 ) , uniformly for a a a ( 0 , ∞ ) (0,\infty) ( 0 , ∞ )
∑ v ≤ m [ x v ] V d ( x ) ρ d v = 1 4 log m + K d ( 0 ) + O ( m − 1 / 2 ) = 1 6 log n + 1 4 log a + K d ( 0 ) + O ( n − 1 / 3 ) . \begin{aligned}
\sum_{v\leq m}[x^v]V_d(x)\rho_d^v=\frac{1}{4}\log m+K_d^{(0)}+O(m^{-1/2}) \\
&=\frac{1}{6}\log n+\frac{1}{4}\log a+K_d^{(0)}+O(n^{-1/3}).
\end{aligned} v ≤ m ∑ [ x v ] V d ( x ) ρ d v = 4 1 log m + K d ( 0 ) + O ( m − 1/2 ) = 6 1 log n + 4 1 log a + K d ( 0 ) + O ( n − 1/3 ) . The constant K d ( 0 ) K_d^{(0)} K d ( 0 ) ℓ ≥ 1 \ell\geq1 ℓ ≥ 1
Controls needed for the saddle-point method
In (9), write the phase formally as
Φ n , m ( x , z ) = C d , m ( x , z ) − n log x − M log z . \Phi_{n,m}(x,z)=C_{d,m}(x,z)-n\log x-M\log z. Φ n , m ( x , z ) = C d , m ( x , z ) − n log x − M log z . At every admissible positive saddle ( x ∗ , z ∗ ) (x_*,z_*) ( x ∗ , z ∗ ) x ∗ ∂ x C d , m ( x ∗ , z ∗ ) = n x_*\partial_x C_{d,m}(x_*,z_*)=n x ∗ ∂ x C d , m ( x ∗ , z ∗ ) = n z ∗ ∂ z C d , m ( x ∗ , z ∗ ) = M z_*\partial_z C_{d,m}(x_*,z_*)=M z ∗ ∂ z C d , m ( x ∗ , z ∗ ) = M
The normalization factor in (9) is exactly n ! / ( N M ) n!/\binom{N}{M} n ! / ( M N ) n n n
Exploration, martingales, and excursions
In the independent-edge model, choose p p p ( d − 1 ) ( n − 1 d − 1 ) p = 1 + λ n − 1 / 3 + O ( n − 1 ) (d-1)\binom{n-1}{d-1}p=1+\lambda n^{-1/3}+O(n^{-1}) ( d − 1 ) ( d − 1 n − 1 ) p = 1 + λ n − 1/3 + O ( n − 1 ) d − 1 d-1 d − 1 d − 1 d-1 d − 1 n 2 / 3 n^{2/3} n 2/3 n 1 / 3 n^{1/3} n 1/3 S t S_t S t Q t = R ( S ) t = S t − min 0 ≤ j ≤ t S j Q_t=\mathcal{R}(S)_t=S_t-\min_{0\le j\le t}S_j Q t = R ( S ) t = S t − min 0 ≤ j ≤ t S j
n − 1 / 3 S ⌊ s n 2 / 3 ⌋ , (36) n^{-1/3}S_{\lfloor sn^{2/3}\rfloor}, \tag*{(36)} n − 1/3 S ⌊ s n 2/3 ⌋ , (36) the n − 2 / 3 n^{-2/3} n − 2/3 λ − ( d − 1 ) s \lambda-(d-1)s λ − ( d − 1 ) s d − 1 \sqrt{d-1} d − 1 d ≥ 3 d\ge3 d ≥ 3
In what follows, write
W d , λ ( s ) = d − 1 B ( s ) + λ s − d − 1 2 s 2 , R f ( s ) = f ( s ) − inf 0 ≤ u ≤ s f ( u ) . W_{d,\lambda}(s)=\sqrt{d-1}B(s)+\lambda s-\frac{d-1}{2}s^2,\qquad\mathcal{R}f(s)=f(s)-\inf_{0\le u\le s}f(u). W d , λ ( s ) = d − 1 B ( s ) + λ s − 2 d − 1 s 2 , R f ( s ) = f ( s ) − 0 ≤ u ≤ s inf f ( u ) . Definition 7.1 (Exploration walk S t S_t S t Q t Q_t Q t Explore the vertices of H d ( n , p ) H_d(n,p) H d ( n , p ) S 0 = 0 S_0=0 S 0 = 0 t ≥ 1 t\ge1 t ≥ 1 v t v_t v t d d d v t v_t v t ξ t \xi_t ξ t
Δ S t = ξ t − 1 , S t = ∑ j = 1 t Δ S j . \Delta S_t=\xi_t-1,\qquad S_t=\sum_{j=1}^{t}\Delta S_j. Δ S t = ξ t − 1 , S t = j = 1 ∑ t Δ S j . When the queue becomes empty (component completed), start the next component with an arbitrary neutral vertex and increment S S S − 1 -1 − 1
Q t = R ( S ) t = S t − min 0 ≤ j ≤ t S j ≥ 0 , Q_t=\mathcal{R}(S)_t=S_t-\min_{0\le j\le t}S_j\ge0, Q t = R ( S ) t = S t − 0 ≤ j ≤ t min S j ≥ 0 , which represents the active queue length. Its returns to zero correspond exactly to component ends.
Remark 7.2 (Excursions of Q Q Q Q Q Q [ t s t a r t , t e n d ] [t_{\mathrm{start}},t_{\mathrm{end}}] [ t start , t end ] t e n d − t s t a r t t_{\mathrm{end}}-t_{\mathrm{start}} t end − t start s = t n − 2 / 3 s=tn^{-2/3} s = t n − 2/3 n − 1 / 3 Q ⌊ s n 2 / 3 ⌋ n^{-1/3}Q_{\lfloor sn^{2/3}\rfloor} n − 1/3 Q ⌊ s n 2/3 ⌋ R ( W d , λ ) \mathcal{R}(W_{d,\lambda}) R ( W d , λ )
Theorem 7.3 (Unconditional excursion law). In H d ( n , p ) H_d(n,p) H d ( n , p ) ( ∣ C 1 ∣ , ∣ C 2 ∣ , … ) (|C_1|,|C_2|,\ldots) ( ∣ C 1 ∣ , ∣ C 2 ∣ , … )
n − 2 / 3 ( ∣ C 1 ∣ , ∣ C 2 ∣ , … ) ⟹ ( ξ 1 , ξ 2 , … ) in ℓ ↓ 2 . n^{-2/3}(|C_1|,|C_2|,\ldots)\Longrightarrow(\xi_1,\xi_2,\ldots)\quad\text{in }\ell^2_{\downarrow}. n − 2/3 ( ∣ C 1 ∣ , ∣ C 2 ∣ , … ) ⟹ ( ξ 1 , ξ 2 , … ) in ℓ ↓ 2 . where ( ξ 1 , ξ 2 , … ) (\xi_1,\xi_2,\ldots) ( ξ 1 , ξ 2 , … ) R ( W d , λ ) \mathcal{R}(W_{d,\lambda}) R ( W d , λ ) H d ( n , M ) H_d(n,M) H d ( n , M )
n − 2 / 3 L n ⟹ ξ 1 . n^{-2/3}L_n\Longrightarrow\xi_1. n − 2/3 L n ⟹ ξ 1 . Proof. The first assertion is Theorem 7.13 , obtained from the invariance principle on compact sets and uniform control of late excursions. The second is Theorem 7.14 , based on a monotone coupling. □
Exploration filtration and exact martingale
Let F t \mathcal{F}_t F t t t t Δ S t = S t + 1 − S t \Delta S_t=S_{t+1}-S_t Δ S t = S t + 1 − S t
Theorem 7.4 (Doob martingale of the exploration). Define
A t = ∑ j = 0 t − 1 E ( Δ S j ∣ F j ) , M t = S t − S 0 − A t . A_t=\sum_{j=0}^{t-1}\mathbb{E}(\Delta S_j\mid\mathcal{F}_j),\qquad M_t=S_t-S_0-A_t. A t = j = 0 ∑ t − 1 E ( Δ S j ∣ F j ) , M t = S t − S 0 − A t . Then ( M t , F t ) (M_t,\mathcal{F}_t) ( M t , F t )
⟨ M ⟩ t = ∑ j = 0 t − 1 Var ( Δ S j ∣ F j ) . (37) \langle M\rangle_t=\sum_{j=0}^{t-1}\operatorname{Var}(\Delta S_j\mid\mathcal{F}_j). \tag*{(37)} ⟨ M ⟩ t = j = 0 ∑ t − 1 Var ( Δ S j ∣ F j ) . (37) If exploration is stopped before any increment exceeds b n b_n b n u , v > 0 u,v>0 u , v > 0
P { max s ≤ t M s ≥ u , ⟨ M ⟩ t ≤ v } ≤ exp ( − u 2 2 ( v + b n u / 3 ) ) . (38) \mathbb{P}\left\{\max_{s\le t}M_s\ge u,\ \langle M\rangle_t\le v\right\}\le\exp\left(-\frac{u^2}{2(v+b_nu/3)}\right). \tag*{(38)} P { s ≤ t max M s ≥ u , ⟨ M ⟩ t ≤ v } ≤ exp ( − 2 ( v + b n u /3 ) u 2 ) . (38) Proof. The increment M t + 1 − M t = Δ S t − E ( Δ S t ∣ F t ) M_{t+1}-M_t=\Delta S_t-\mathbb{E}(\Delta S_t\mid\mathcal{F}_t) M t + 1 − M t = Δ S t − E ( Δ S t ∣ F t ) (38) is Freedman’s inequality applied to the stopped martingale [9 ] . □
Proposition 7.5 (Exact one-step conditional moments). At step t t t v t v_t v t U t U_t U t E t \mathcal{E}_t E t v t v_t v t w , w ′ ∈ U t w,w'\in U_t w , w ′ ∈ U t
a t ( w ) = ∣ { E ∈ E t : w ∈ E } ∣ , c t ( w , w ′ ) = ∣ { E ∈ E t : w , w ′ ∈ E } ∣ . a_t(w)=|\{E\in\mathcal{E}_t:w\in E\}|,\qquad c_t(w,w')=|\{E\in\mathcal{E}_t:w,w'\in E\}|. a t ( w ) = ∣ { E ∈ E t : w ∈ E } ∣ , c t ( w , w ′ ) = ∣ { E ∈ E t : w , w ′ ∈ E } ∣. In H d ( n , p ) H_d(n,p) H d ( n , p ) F t \mathcal{F}_t F t I t ( w ) I_t(w) I t ( w ) E t \mathcal{E}_t E t w w w q = 1 − p q=1-p q = 1 − p
π t ( w ) : = E ( I t ( w ) ∣ F t ) = 1 − q a t ( w ) . (39) \pi_t(w):=\mathbb{E}(I_t(w)\mid\mathcal{F}_t)=1-q^{a_t(w)}. \tag*{(39)} π t ( w ) := E ( I t ( w ) ∣ F t ) = 1 − q a t ( w ) . (39) Cov ( I t ( w ) , I t ( w ′ ) ∣ F t ) = q a t ( w ) + a t ( w ′ ) − c t ( w , w ′ ) − q a t ( w ) + a t ( w ′ ) . (40) \operatorname{Cov}(I_t(w),I_t(w')\mid\mathcal{F}_t)=q^{a_t(w)+a_t(w')-c_t(w,w')}-q^{a_t(w)+a_t(w')}. \tag*{(40)} Cov ( I t ( w ) , I t ( w ′ ) ∣ F t ) = q a t ( w ) + a t ( w ′ ) − c t ( w , w ′ ) − q a t ( w ) + a t ( w ′ ) . (40) Outside the times at which a new component is started,
E ( Δ S t ∣ F t ) = − 1 + ∑ w ∈ U t π t ( w ) , (41) \mathbb{E}(\Delta S_t \mid\mathcal{F}_t) = -1 + \sum_{w \in U_t} \pi_t(w), \tag*{(41)} E ( Δ S t ∣ F t ) = − 1 + w ∈ U t ∑ π t ( w ) , (41) Var ( Δ S t ∣ F t ) = ∑ w ∈ U t π t ( w ) ( 1 − π t ( w ) ) + 2 ∑ { w , w ′ } ⊂ U t Cov ( I t ( w ) , I t ( w ′ ) ∣ F t ) . (42) \begin{aligned}
\operatorname{Var}(\Delta S_t \mid\mathcal{F}_t)
&= \sum_{w \in U_t} \pi_t(w)(1-\pi_t(w)) \\
&\quad+ 2 \sum_{\{w,w'\}\subset U_t} \operatorname{Cov}(I_t(w),I_t(w') \mid\mathcal{F}_t). \tag*{(42)}
\end{aligned} Var ( Δ S t ∣ F t ) = w ∈ U t ∑ π t ( w ) ( 1 − π t ( w )) + 2 { w , w ′ } ⊂ U t ∑ Cov ( I t ( w ) , I t ( w ′ ) ∣ F t ) . (42) Proof. Conditionally on F t \mathcal{F}_t F t I t ( w ) = 0 I_t(w)=0 I t ( w ) = 0 a t ( w ) a_t(w) a t ( w )
P ( I t ( w ) = I t ( w ′ ) = 1 ∣ F t ) = 1 − q a t ( w ) − q a t ( w ′ ) + q a t ( w ) + a t ( w ′ ) − c t ( w , w ′ ) , \mathbb{P}(I_t(w)=I_t(w')=1\mid\mathcal{F}_t)=1-q^{a_t(w)}-q^{a_t(w')}+q^{a_t(w)+a_t(w')-c_t(w,w')}, P ( I t ( w ) = I t ( w ′ ) = 1 ∣ F t ) = 1 − q a t ( w ) − q a t ( w ′ ) + q a t ( w ) + a t ( w ′ ) − c t ( w , w ′ ) , which yields (40). Finally, Δ S t = − 1 + ∑ w ∈ U t I t ( w ) \Delta S_t=-1+\sum_{w\in U_t}I_t(w) Δ S t = − 1 + ∑ w ∈ U t I t ( w )
Corollary 7.6 (Calibration at the start of exploration). At t = 0 t=0 t = 0
p = 1 + λ n − 1 / 3 + O ( n − 1 ) ( d − 1 ) ( n − 1 d − 1 ) . p=\frac{1+\lambda n^{-1/3}+O(n^{-1})}{(d-1)\binom{n-1}{d-1}}. p = ( d − 1 ) ( d − 1 n − 1 ) 1 + λ n − 1/3 + O ( n − 1 ) . Then
E Δ S 0 = λ n − 1 / 3 + O ( n − 1 ) , Var ( Δ S 0 ) = d − 1 + O ( n − 1 / 3 ) . \mathbb{E}\Delta S_0=\lambda n^{-1/3}+O(n^{-1}),\qquad\operatorname{Var}(\Delta S_0)=d-1+O(n^{-1/3}). E Δ S 0 = λ n − 1/3 + O ( n − 1 ) , Var ( Δ S 0 ) = d − 1 + O ( n − 1/3 ) . Proof. Initially a 0 ( w ) = ( n − 2 d − 2 ) a_0(w)=\binom{n-2}{d-2} a 0 ( w ) = ( d − 2 n − 2 ) w ≠ w ′ w\ne w' w = w ′ c 0 ( w , w ′ ) = ( n − 3 d − 3 ) c_0(w,w')=\binom{n-3}{d-3} c 0 ( w , w ′ ) = ( d − 3 n − 3 ) d = 2 d=2 d = 2 p a 0 ( w ) = ( 1 + λ n − 1 / 3 + O ( n − 1 ) ) / ( n − 1 ) pa_0(w)=(1+\lambda n^{-1/3}+O(n^{-1}))/(n-1) p a 0 ( w ) = ( 1 + λ n − 1/3 + O ( n − 1 )) / ( n − 1 ) 1 − ( 1 − p ) a = p a + O ( p 2 a 2 ) 1-(1-p)^a=pa+O(p^2a^2) 1 − ( 1 − p ) a = p a + O ( p 2 a 2 ) 1 + O ( n − 1 / 3 ) 1+O(n^{-1/3}) 1 + O ( n − 1/3 )
( n − 1 ) ( n − 2 ) p ( n − 3 d − 3 ) = d − 2 + O ( n − 1 / 3 ) , (n-1)(n-2)p\binom{n-3}{d-3}=d-2+O(n^{-1/3}), ( n − 1 ) ( n − 2 ) p ( d − 3 n − 3 ) = d − 2 + O ( n − 1/3 ) , and expansion of (40) shows that this is the total ordered covariance contribution. The variance is therefore 1 + ( d − 2 ) + O ( n − 1 / 3 ) 1+(d-2)+O(n^{-1/3}) 1 + ( d − 2 ) + O ( n − 1/3 )
In the independent-edge model, direct revelation of incident hyperedges first leads to the expansions
E ( Δ S t ∣ F t ) = n − 1 / 3 ( λ − ( d − 1 ) s ) + E n , t , s = t / n 2 / 3 , (43) \mathbb{E}(\Delta S_t\mid\mathcal{F}_t)=n^{-1/3}\bigl(\lambda-(d-1)s\bigr)+\mathcal{E}_{n,t},\qquad s=t/n^{2/3}, \tag*{(43)} E ( Δ S t ∣ F t ) = n − 1/3 ( λ − ( d − 1 ) s ) + E n , t , s = t / n 2/3 , (43) Var ( Δ S t ∣ F t ) = d − 1 + V n , t . (44) \operatorname{Var}(\Delta S_t\mid\mathcal{F}_t)=d-1+\mathcal{V}_{n,t}. \tag*{(44)} Var ( Δ S t ∣ F t ) = d − 1 + V n , t . (44) The error terms include depletion due to the active set, repeated discoveries and hyperedges meeting several already exposed vertices. The rigorous passage is organized around the following three estimates:
sup t ≤ T n 2 / 3 ∣ n − 1 / 3 ∑ j < t E n , j ∣ → p 0 , n − 2 / 3 ∑ j < T n 2 / 3 V n , j → p 0 , \sup_{t\leq Tn^{2/3}}\left|n^{-1/3}\sum_{j<t}\mathcal{E}_{n,j}\right|\xrightarrow{\mathrm{p}}0,\qquad n^{-2/3}\sum_{j<Tn^{2/3}}\mathcal{V}_{n,j}\xrightarrow{\mathrm{p}}0, t ≤ T n 2/3 sup n − 1/3 j < t ∑ E n , j p 0 , n − 2/3 j < T n 2/3 ∑ V n , j p 0 , together with a Lindeberg condition on the stopped martingale increments. The following criterion collects precisely these conditions.
Theorem 7.7 (Martingale criterion on a finite horizon). Fix T < ∞ T<\infty T < ∞ ε > 0 \varepsilon>0 ε > 0
n − 2 / 3 ∑ j < T n 2 / 3 E [ ( Δ M j ) 2 1 { ∣ Δ M j ∣ > ε n 1 / 3 } ∣ F j ] → p 0. (45) n^{-2/3}\sum_{j<Tn^{2/3}}\mathbb{E}\left[(\Delta M_j)^2\mathbf{1}_{\{|\Delta M_j|>\varepsilon n^{1/3}\}}\mid\mathcal{F}_j\right]\xrightarrow{\mathrm{p}}0. \tag*{(45)} n − 2/3 j < T n 2/3 ∑ E [ ( Δ M j ) 2 1 { ∣Δ M j ∣ > ε n 1/3 } ∣ F j ] p 0. (45) Then, before reflection and on [ 0 , T ] [0,T] [ 0 , T ]
n − 1 / 3 S ⌊ s n 2 / 3 ⌋ ⟹ d − 1 B ( s ) + λ s − d − 1 2 s 2 n^{-1/3}S_{\lfloor sn^{2/3}\rfloor}\Longrightarrow\sqrt{d-1}B(s)+\lambda s-\frac{d-1}{2}s^2 n − 1/3 S ⌊ s n 2/3 ⌋ ⟹ d − 1 B ( s ) + λ s − 2 d − 1 s 2 in the Skorokhod topology, up to the deterministic convention used at component starts. Reflection at the running minimum gives convergence of the reflected processes on [ 0 , T ] [0,T] [ 0 , T ]
Proof. By (37), the variance-error estimate gives, uniformly for s ≤ T s\le T s ≤ T
n − 2 / 3 ⟨ M ⟩ ⌊ s n 2 / 3 ⌋ → p ( d − 1 ) s . n^{-2/3}\langle M\rangle_{\lfloor sn^{2/3}\rfloor}\xrightarrow{p}(d-1)s. n − 2/3 ⟨ M ⟩ ⌊ s n 2/3 ⌋ p ( d − 1 ) s . Together with (45), this allows application of the functional central limit theorem for martingales [7 ] , giving convergence of n − 1 / 3 M n^{-1/3}M n − 1/3 M d − 1 B \sqrt{d-1}B d − 1 B
n − 1 / 3 A ⌊ s n 2 / 3 ⌋ → p ∫ 0 s ( λ − ( d − 1 ) u ) d u . n^{-1/3}A_{\lfloor sn^{2/3}\rfloor}\xrightarrow{p}\int_0^s(\lambda-(d-1)u)\,du. n − 1/3 A ⌊ s n 2/3 ⌋ p ∫ 0 s ( λ − ( d − 1 ) u ) d u . Adding the two limits establishes the unreflected assertion. The reflection map is Lipschitz for the uniform norm on compact intervals and continuous, in the Skorokhod topology, at continuous paths; this proves the last assertion. □
Lemma 7.8 (Uniform estimates on a finite horizon). Fix T , K < ∞ T,K<\infty T , K < ∞
τ K = inf { t : Q t > K n 1 / 3 } . \tau_K=\inf\{t:Q_t>Kn^{1/3}\}. τ K = inf { t : Q t > K n 1/3 } . Uniformly for t ≤ T n 2 / 3 ∧ τ K t\le Tn^{2/3}\wedge\tau_K t ≤ T n 2/3 ∧ τ K s = t / n 2 / 3 s=t/n^{2/3} s = t / n 2/3
E ( Δ S t ∣ F t ) = n − 1 / 3 ( λ − ( d − 1 ) s ) + O T , K ( n − 2 / 3 ) , (46) \mathbb{E}(\Delta S_t\mid\mathcal{F}_t)=n^{-1/3}(\lambda-(d-1)s)+O_{T,K}(n^{-2/3}), \tag*{(46)} E ( Δ S t ∣ F t ) = n − 1/3 ( λ − ( d − 1 ) s ) + O T , K ( n − 2/3 ) , (46) Var ( Δ S t ∣ F t ) = d − 1 + O T , K ( n − 1 / 3 ) . (47) \operatorname{Var}(\Delta S_t\mid\mathcal{F}_t)=d-1+O_{T,K}(n^{-1/3}). \tag*{(47)} Var ( Δ S t ∣ F t ) = d − 1 + O T , K ( n − 1/3 ) . (47) By (47), the Lindeberg condition (45) holds for the stopped process.
Proof. Adopt the following convention: a hyperedge is tested when its first vertex in exploration order is processed. After t t t w w w d − 2 d-2 d − 2
a t ( w ) = ( n − t − 2 d − 2 ) , c t ( w , w ′ ) = ( n − t − 3 d − 3 ) , a_t(w)=\binom{n-t-2}{d-2},\qquad c_t(w,w')=\binom{n-t-3}{d-3}, a t ( w ) = ( d − 2 n − t − 2 ) , c t ( w , w ′ ) = ( d − 3 n − t − 3 ) , the second quantity being zero for d = 2 d=2 d = 2
∣ U t ∣ = n − t − Q t + O ( 1 ) . |U_t|=n-t-Q_t+O(1). ∣ U t ∣ = n − t − Q t + O ( 1 ) . These identities remain valid if active vertices occur among the d − 2 d-2 d − 2 a = a t ( w ) a=a_t(w) a = a t ( w ) u = ∣ U t ∣ u=|U_t| u = ∣ U t ∣ p a = O ( n − 1 ) pa=O(n^{-1}) p a = O ( n − 1 ) 1 − ( 1 − p ) a = p a + O ( p 2 a 2 ) 1-(1-p)^a=pa+O(p^2a^2) 1 − ( 1 − p ) a = p a + O ( p 2 a 2 )
u p a = 1 + n − 1 / 3 ( λ − ( d − 1 ) s − Q t n ) + O T ( n − 2 / 3 ) . upa=1+n^{-1/3}\left(\lambda-(d-1)s-\frac{Q_t}{n}\right)+O_T(n^{-2/3}). u p a = 1 + n − 1/3 ( λ − ( d − 1 ) s − n Q t ) + O T ( n − 2/3 ) . On { t < τ K } \{t<\tau_K\} { t < τ K } Q t / n Q_t/n Q t / n O K ( n − 2 / 3 ) O_K(n^{-2/3}) O K ( n − 2/3 ) u O ( p 2 a 2 ) uO(p^2a^2) u O ( p 2 a 2 ) O ( n − 1 ) O(n^{-1}) O ( n − 1 )
For the variance, the sum of individual variances in (42) is
u π t ( w ) ( 1 − π t ( w ) ) = 1 + O T , K ( n − 1 / 3 ) . u\pi_t(w)(1-\pi_t(w))=1+O_{T,K}(n^{-1/3}). u π t ( w ) ( 1 − π t ( w )) = 1 + O T , K ( n − 1/3 ) . When d ≥ 3 d \ge3 d ≥ 3 (40) and p c t ( w , w ′ ) = O ( n − 2 ) p_{\mathrm{ct}}(w,w') = O(n^{-2}) p ct ( w , w ′ ) = O ( n − 2 )
q 2 a − c t ( w , w ′ ) − q 2 a = p ( n − t − 3 d − 3 ) + O ( n − 3 ) . q^{2a-\mathrm{ct}(w,w')}-q^{2a}=p\binom{n-t-3}{d-3}+O(n^{-3}). q 2 a − ct ( w , w ′ ) − q 2 a = p ( d − 3 n − t − 3 ) + O ( n − 3 ) . Summing over ordered pairs of neutral vertices,
u ( u − 1 ) p ( n − t − 3 d − 3 ) = d − 2 + O T , K ( n − 1 / 3 ) . u(u-1)p\binom{n-t-3}{d-3}=d-2+O_{T,K}(n^{-1/3}). u ( u − 1 ) p ( d − 3 n − t − 3 ) = d − 2 + O T , K ( n − 1/3 ) . For d = 2 d=2 d = 2 (47) in every case. Finally, if Z t Z_t Z t t t t
∣ Δ S t ∣ ≤ 1 + ( d − 1 ) Z t . |\Delta S_t|\le1+(d-1)Z_t. ∣Δ S t ∣ ≤ 1 + ( d − 1 ) Z t . Conditionally on F t \mathcal{F}_t F t Z t Z_t Z t t ≤ T n 2 / 3 t\le Tn^{2/3} t ≤ T n 2/3 C = C ( d , T ) C=C(d,T) C = C ( d , T ) r ≥ C r\ge C r ≥ C
P ( Z t ≥ r ∣ F t ) ≤ ( e C / r ) r . \mathbb{P}(Z_t\ge r\mid\mathcal{F}_t)\le(eC/r)^r. P ( Z t ≥ r ∣ F t ) ≤ ( e C / r ) r . After integrating this tail and summing O ( n 2 / 3 ) O(n^{2/3}) O ( n 2/3 ) (45) tends to zero. Conditional centring does not change this conclusion, completing the proof. □
Theorem 7.10 (Invariance principle without a finite-horizon hypothesis). In H d ( n , p ) H_d(n,p) H d ( n , p ) T < ∞ T<\infty T < ∞
( n − 1 / 3 S ⌊ s n 2 / 3 ⌋ ) 0 ≤ s ≤ T ⟹ ( d − 1 B ( s ) + λ s − d − 1 2 s 2 ) 0 ≤ s ≤ T . \left(n^{-1/3}S_{\lfloor sn^{2/3}\rfloor}\right)_{0\le s\le T}\Longrightarrow\left(\sqrt{d-1}B(s)+\lambda s-\frac{d-1}{2}s^2\right)_{0\le s\le T}. ( n − 1/3 S ⌊ s n 2/3 ⌋ ) 0 ≤ s ≤ T ⟹ ( d − 1 B ( s ) + λ s − 2 d − 1 s 2 ) 0 ≤ s ≤ T . The same convergence holds after reflection at the running minimum.
Proof. For fixed K K K Lemma 7.8 verifies all hypotheses of Theorem 7.7 up to τ K \tau_K τ K [ 0 , T n 2 / 3 ∧ τ K ] [0,Tn^{2/3}\wedge\tau_K] [ 0 , T n 2/3 ∧ τ K ] n 1 / 3 n^{1/3} n 1/3 C T + o ( 1 ) C_T+o(1) C T + o ( 1 ) K K K Q t / n Q_t/n Q t / n K n 1 / 3 Kn^{1/3} K n 1/3 K T n − 1 / 3 = o ( 1 ) KTn^{-1/3}=o(1) K T n − 1/3 = o ( 1 ) K K K (47) , there is C T < ∞ C_T<\infty C T < ∞
E ⟨ M ⟩ T n 2 / 3 ∧ τ K ≤ C T n 2 / 3 . \mathbb{E}\langle M\rangle_{Tn^{2/3}\wedge\tau_K}\le C_Tn^{2/3}. E ⟨ M ⟩ T n 2/3 ∧ τ K ≤ C T n 2/3 . Doob’s maximal inequality then gives, for K > 4 C T K>4C_T K > 4 C T
P { max t ≤ T n 2 / 3 ∧ τ K ∣ M t ∣ > K 4 n 1 / 3 } ≤ 16 C T K 2 . \mathbb{P}\left\{\max_{t\le Tn^{2/3}\wedge\tau_K}|M_t|>\frac{K}{4}n^{1/3}\right\}\le\frac{16C_T}{K^2}. P { t ≤ T n 2/3 ∧ τ K max ∣ M t ∣ > 4 K n 1/3 } ≤ K 2 16 C T . Since ∥ R f ∥ ∞ ≤ 2 ∥ f ∥ ∞ \lVert Rf\rVert_\infty\le2\lVert f\rVert_\infty ∥ R f ∥ ∞ ≤ 2 ∥ f ∥ ∞ f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 { τ K ≤ T n 2 / 3 } \{\tau_K \le Tn^{2/3}\} { τ K ≤ T n 2/3 } n n n
lim K → ∞ lim sup n → ∞ P ( τ K ≤ T n 2 / 3 ) = 0. \lim_{K\to\infty}\limsup_{n\to\infty}\mathbb{P}(\tau_K \le Tn^{2/3})=0. K → ∞ lim n → ∞ lim sup P ( τ K ≤ T n 2/3 ) = 0. Stopped convergence then implies unstopped convergence. Continuity of reflection at continuous paths gives the last assertion. □ \square □
Lemma 7.11 (Subcritical domination after a macroscopic time). There are constants c , C , T 0 > 0 c,C,T_0>0 c , C , T 0 > 0 d d d λ \lambda λ T ≥ T 0 T\ge T_0 T ≥ T 0 t ≥ T n 2 / 3 t\ge Tn^{2/3} t ≥ T n 2/3 F t \mathcal{F}_t F t X n , t X_{n,t} X n , t
E X n , t ≤ 1 − c T n − 1 / 3 . \mathbb{E}X_{n,t}\le1-cTn^{-1/3}. E X n , t ≤ 1 − c T n − 1/3 . If T n , t \mathcal{T}_{n,t} T n , t k ≥ 1 k\ge1 k ≥ 1
P ( T n , t ≥ k ∣ F t ) ≤ C k − 1 / 2 exp ( − c T 2 k n − 2 / 3 ) , (48) \mathbb{P}(\mathcal{T}_{n,t}\ge k\mid\mathcal{F}_t)\le Ck^{-1/2}\exp(-cT^2kn^{-2/3}), \tag*{(48)} P ( T n , t ≥ k ∣ F t ) ≤ C k − 1/2 exp ( − c T 2 k n − 2/3 ) , (48) E ( T n , t ∣ F t ) ≤ C n 1 / 3 / T . (49) \mathbb{E}(\mathcal{T}_{n,t}\mid\mathcal{F}_t)\le Cn^{1/3}/T. \tag*{(49)} E ( T n , t ∣ F t ) ≤ C n 1/3 / T . (49) Proof. At time t t t ( n − t − 1 d − 1 ) \binom{n-t-1}{d-1} ( d − 1 n − t − 1 ) d − 1 d-1 d − 1
X n , t ⪯ ( d − 1 ) Bin ( ( n − t − 1 d − 1 ) , p ) . X_{n,t}\preceq(d-1)\operatorname{Bin}\left(\binom{n-t-1}{d-1},p\right). X n , t ⪯ ( d − 1 ) Bin ( ( d − 1 n − t − 1 ) , p ) . Collisions and already active vertices can only decrease the true offspring. Uniformly for t ≥ T n 2 / 3 t\ge Tn^{2/3} t ≥ T n 2/3
E X n , t ≤ ( 1 + λ n − 1 / 3 + O ( n − 1 ) ) ( 1 − t / n ) d − 1 ≤ 1 − c T n − 1 / 3 \mathbb{E}X_{n,t}\le(1+\lambda n^{-1/3}+O(n^{-1}))(1-t/n)^{d-1}\le1-cTn^{-1/3} E X n , t ≤ ( 1 + λ n − 1/3 + O ( n − 1 )) ( 1 − t / n ) d − 1 ≤ 1 − c T n − 1/3 as soon as T ≥ T 0 T\ge T_0 T ≥ T 0 X n , t X_{n,t} X n , t ε = c T n − 1 / 3 \varepsilon=cTn^{-1/3} ε = c T n − 1/3 ( d − 1 ) Bin ( ( n − t − 1 d − 1 ) , p ) (d-1)\operatorname{Bin}\left(\binom{n-t-1}{d-1},p\right) ( d − 1 ) Bin ( ( d − 1 n − t − 1 ) , p ) E [ e θ X n , t ] \mathbb{E}[e^{\theta X_{n,t}}] E [ e θ X n , t ] θ \theta θ p = O ( 1 / n ) p=O(1/n) p = O ( 1/ n ) ε \varepsilon ε
P ( T n , t = j ) ≤ C j − 3 / 2 e − c ε 2 j . \mathbb{P}(\mathcal{T}_{n,t}=j)\le Cj^{-3/2}e^{-c\varepsilon^2j}. P ( T n , t = j ) ≤ C j − 3/2 e − c ε 2 j . Summing over j ≥ k j\ge k j ≥ k E T n , t = ( 1 − E X n , t ) − 1 \mathbb{E}\mathcal{T}_{n,t}=(1-\mathbb{E}X_{n,t})^{-1} E T n , t = ( 1 − E X n , t ) − 1 □ \square □
Lemma 7.12 (Active queue at the cutoff time). For every compact set of λ \lambda λ C , c , T 0 > 0 C,c,T_0>0 C , c , T 0 > 0 T ≥ T 0 T\ge T_0 T ≥ T 0 x ≥ 0 x\ge0 x ≥ 0
lim sup n → ∞ P ( Q ⌊ T n 2 / 3 ⌋ > x n 1 / 3 T ) ≤ C e − c x . \limsup_{n\to\infty}\mathbb{P}\left(Q_{\lfloor Tn^{2/3}\rfloor}>x\frac{n^{1/3}}{T}\right)\le Ce^{-cx}. n → ∞ lim sup P ( Q ⌊ T n 2/3 ⌋ > x T n 1/3 ) ≤ C e − c x . Thus Q ⌊ T n 2 / 3 ⌋ = O P ( n 1 / 3 / T ) Q_{\lfloor Tn^{2/3}\rfloor}=O_{\mathbb{P}}(n^{1/3}/T) Q ⌊ T n 2/3 ⌋ = O P ( n 1/3 / T ) n → ∞ n\to\infty n → ∞ T → ∞ T\to\infty T → ∞
Proof. First fix T < ∞ T<\infty T < ∞ T T T
n − 1 / 3 Q ⌊ T n 2 / 3 ⌋ ⇒ R ( W d , λ ) ( T ) . (50) n^{-1/3}Q_{\lfloor Tn^{2/3}\rfloor}\xRightarrow{}R(W_{d,\lambda})(T). \tag*{(50)} n − 1/3 Q ⌊ T n 2/3 ⌋ R ( W d , λ ) ( T ) . (50) It therefore suffices to obtain an estimate uniform in T T T h = d − 1 h=d-1 h = d − 1
R ( W d , λ ) ( T ) = l a w sup 0 ≤ r ≤ T { h B ~ ( r ) + ( λ − h T ) r + h 2 r 2 } . \mathcal{R}(W_{d,\lambda})(T) \overset{\mathrm{law}}{=} \sup_{0\le r\le T}\left\{\sqrt{h}\,\widetilde{B}(r)+(\lambda-hT)r+\frac{h}{2}r^2\right\}. R ( W d , λ ) ( T ) = law 0 ≤ r ≤ T sup { h B ( r ) + ( λ − h T ) r + 2 h r 2 } . where B ~ \widetilde{B} B T ≥ T 0 : = 4 ( 1 + ∣ λ ∣ ) / h T\ge T_0:=4(1+|\lambda|)/h T ≥ T 0 := 4 ( 1 + ∣ λ ∣ ) / h 0 ≤ r ≤ T 0\le r\le T 0 ≤ r ≤ T
( λ − h T ) r + h 2 r 2 ≤ − h T 4 r . (\lambda-hT)r+\frac{h}{2}r^2\le-\frac{hT}{4}r. ( λ − h T ) r + 2 h r 2 ≤ − 4 h T r . Consequently,
R ( W d , λ ) ( T ) ≤ sup r ≥ 0 { h B ~ ( r ) − h T 4 r } . \mathcal{R}(W_{d,\lambda})(T)\le\sup_{r\ge0}\left\{\sqrt{h}\,\widetilde{B}(r)-\frac{hT}{4}r\right\}. R ( W d , λ ) ( T ) ≤ r ≥ 0 sup { h B ( r ) − 4 h T r } . The supremum of Brownian motion of variance h h h − h T / 4 -hT/4 − h T /4 T / 2 T/2 T /2
P ( sup r ≥ 0 { h B ~ ( r ) − h T r / 4 } > y ) = e − T y / 2 , y ≥ 0. \mathbb{P}\left(\sup_{r\ge0}\{\sqrt{h}\,\widetilde{B}(r)-hTr/4\}>y\right)=e^{-Ty/2},\qquad y\ge0. P ( r ≥ 0 sup { h B ( r ) − h T r /4 } > y ) = e − T y /2 , y ≥ 0. Taking y = x / T y=x/T y = x / T [ x / T , ∞ ) [x/T,\infty) [ x / T , ∞ )
lim sup n → ∞ P ( Q ⌊ T n 2 / 3 ⌋ > x n 1 / 3 T ) ≤ e − x / 2 . \limsup_{n\to\infty}\mathbb{P}\left(Q_{\lfloor Tn^{2/3}\rfloor}>x\frac{n^{1/3}}{T}\right)\le e^{-x/2}. n → ∞ lim sup P ( Q ⌊ T n 2/3 ⌋ > x T n 1/3 ) ≤ e − x /2 . The proof is uniform for λ \lambda λ T 0 T_0 T 0
Theorem 7.13 (Global excursion convergence in the binomial model). In H d ( n , p ) H_d(n,p) H d ( n , p )
n − 2 / 3 ( ∣ C 1 ∣ , ∣ C 2 ∣ , … ) ⟹ ( ξ 1 , ξ 2 , … ) in ℓ ↓ 2 . n^{-2/3}(|C_1|,|C_2|,\ldots)\Longrightarrow(\xi_1,\xi_2,\ldots)\quad\text{in }\ell^2_{\downarrow}. n − 2/3 ( ∣ C 1 ∣ , ∣ C 2 ∣ , … ) ⟹ ( ξ 1 , ξ 2 , … ) in ℓ ↓ 2 . Proof. On [ 0 , T ] [0,T] [ 0 , T ] R ( W d , λ ) \mathcal{R}(W_{d,\lambda}) R ( W d , λ ) [2 ] and in the metric analysis of [1 ] , therefore implies convergence of every finite family of excursions of length at least η > 0 \eta>0 η > 0 [ 0 , T ] [0,T] [ 0 , T ]
It remains to eliminate successively η ↓ 0 \eta\downarrow0 η ↓ 0 T → ∞ T\to\infty T → ∞ [ 0 , T ] [0,T] [ 0 , T ] η \eta η
∑ i : ∣ I i ∣ ≤ η ∣ I i ∣ 2 ≤ η ∑ i ∣ I i ∣ ≤ η T . \sum_{i:|I_i|\le\eta}|I_i|^2\le\eta\sum_i|I_i|\le\eta T. i : ∣ I i ∣ ≤ η ∑ ∣ I i ∣ 2 ≤ η i ∑ ∣ I i ∣ ≤ η T . The same inequality holds for the discrete excursions after division by n 2 / 3 n^{2/3} n 2/3 o ( 1 ) o(1) o ( 1 ) η \eta η T n 2 / 3 Tn^{2/3} T n 2/3
∑ i ∣ C i ∣ 2 = ∑ v = 1 n ∣ C ( v ) ∣ \sum_i|C_i|^2=\sum_{v=1}^n|C(v)| i ∑ ∣ C i ∣ 2 = v = 1 ∑ n ∣ C ( v ) ∣ expresses the sum of squared sizes as a sum over vertices. For a late vertex v v v ∣ C ( v ) ∣ |C(v)| ∣ C ( v ) ∣ T n , t v T_{n,t_v} T n , t v
at the exploration time t v ≥ T n 2 / 3 t_v \ge Tn^{2/3} t v ≥ T n 2/3 v v v (49) thus give, by the law of total expectation,
E [ n − 4 / 3 ∑ C i l a t e ∣ C i ∣ 2 ] ≤ n − 4 / 3 ∑ v l a t e E ∣ C ( v ) ∣ ≤ n − 4 / 3 ⋅ n ⋅ C n 1 / 3 T = C T . \mathbb{E}\left[n^{-4/3}\sum_{C_i\ \mathrm{late}} |C_i|^2\right]\le n^{-4/3}\sum_{v\ \mathrm{late}}\mathbb{E}|C(v)|
\le n^{-4/3}\cdot n\cdot\frac{Cn^{1/3}}{T}=\frac{C}{T}. E [ n − 4/3 C i late ∑ ∣ C i ∣ 2 ] ≤ n − 4/3 v late ∑ E ∣ C ( v ) ∣ ≤ n − 4/3 ⋅ n ⋅ T C n 1/3 = T C . The component possibly in progress at time T n 2 / 3 Tn^{2/3} T n 2/3 Q t Q_t Q t Q ⌊ T n 2 / 3 ⌋ = q Q_{\lfloor Tn^{2/3}\rfloor}=q Q ⌊ T n 2/3 ⌋ = q Lemma 7.11 , started with q q q R n , T R_{n,T} R n , T q q q
E ( R n , T ∣ F ⌊ T n 2 / 3 ⌋ ) ≤ C n 1 / 3 T Q ⌊ T n 2 / 3 ⌋ . \mathbb{E}(R_{n,T}\mid\mathcal{F}_{\lfloor Tn^{2/3}\rfloor})\le\frac{Cn^{1/3}}{T}Q_{\lfloor Tn^{2/3}\rfloor}. E ( R n , T ∣ F ⌊ T n 2/3 ⌋ ) ≤ T C n 1/3 Q ⌊ T n 2/3 ⌋ . Lemma 7.12 gives, with uniform quantifiers, Q ⌊ T n 2 / 3 ⌋ = O P ( n 1 / 3 / T ) Q_{\lfloor Tn^{2/3}\rfloor}=O_{\mathbb{P}}(n^{1/3}/T) Q ⌊ T n 2/3 ⌋ = O P ( n 1/3 / T ) { Q ⌊ T n 2 / 3 ⌋ ≤ A n 1 / 3 / T } \{Q_{\lfloor Tn^{2/3}\rfloor}\le An^{1/3}/T\} { Q ⌊ T n 2/3 ⌋ ≤ A n 1/3 / T } δ > 0 \delta>0 δ > 0
P ( R n , T > δ n 2 / 3 ∣ F ⌊ T n 2 / 3 ⌋ ) ≤ C A δ T 2 . \mathbb{P}(R_{n,T}>\delta n^{2/3}\mid\mathcal{F}_{\lfloor Tn^{2/3}\rfloor})\le\frac{CA}{\delta T^2}. P ( R n , T > δ n 2/3 ∣ F ⌊ T n 2/3 ⌋ ) ≤ δ T 2 C A . Combining this estimate with Lemma 7.12 gives explicitly
lim sup n → ∞ P ( R n , T > δ n 2 / 3 ) ≤ C e − c A + C A δ T 2 . \limsup_{n\to\infty}\mathbb{P}(R_{n,T}>\delta n^{2/3})\le Ce^{-cA}+\frac{CA}{\delta T^2}. n → ∞ lim sup P ( R n , T > δ n 2/3 ) ≤ C e − c A + δ T 2 C A . First choose A A A T T T
lim T → ∞ lim sup n → ∞ P ( R n , T > δ n 2 / 3 ) = 0. \lim_{T\to\infty}\limsup_{n\to\infty}\mathbb{P}(R_{n,T}>\delta n^{2/3})=0. T → ∞ lim n → ∞ lim sup P ( R n , T > δ n 2/3 ) = 0. The part of this component before the cutoff time already belongs to the excursions observed on [ 0 , T ] [0,T] [ 0 , T ] R n , T R_{n,T} R n , T ℓ ↓ 2 \ell^2_\downarrow ℓ ↓ 2 T T T
lim T → ∞ lim sup n → ∞ P { n − 4 / 3 ∑ C i l a t e ∣ C i ∣ 2 > δ } = 0. \lim_{T\to\infty}\limsup_{n\to\infty}\mathbb{P}\left\{n^{-4/3}\sum_{C_i\ \mathrm{late}}|C_i|^2>\delta\right\}=0. T → ∞ lim n → ∞ lim sup P { n − 4/3 C i late ∑ ∣ C i ∣ 2 > δ } = 0. The same property holds for the limiting process, whose parabolic drift tends to − ∞ -\infty − ∞ ℓ ↓ 2 \ell^2_\downarrow ℓ ↓ 2
Theorem 7.14 (Transfer to the fixed-edge model). For M M M
n − 2 / 3 L n ⟹ ξ 1 n^{-2/3}L_n\Longrightarrow\xi_1 n − 2/3 L n ⟹ ξ 1 in H d ( n , M ) H_d(n,M) H d ( n , M )
Proof. For θ ∈ R \theta\in\mathbb{R} θ ∈ R
m n ( θ ) = ⌊ n d ( d − 1 ) ( 1 + θ n − 1 / 3 ) ⌋ , p n ( θ ) = m n ( θ ) N . m_n(\theta)=\left\lfloor\frac{n}{d(d-1)}(1+\theta n^{-1/3})\right\rfloor,\qquad p_n(\theta)=\frac{m_n(\theta)}{N}. m n ( θ ) = ⌊ d ( d − 1 ) n ( 1 + θ n − 1/3 ) ⌋ , p n ( θ ) = N m n ( θ ) . Fix ε > 0 \varepsilon>0 ε > 0 [ 0 , 1 ] [0,1] [ 0 , 1 ] U E U_E U E N N N U E U_E U E p ∈ [ 0 , 1 ] p\in[0,1] p ∈ [ 0 , 1 ]
H ( p ) = { E : U E ≤ p } , E ( p ) = ∣ H ( p ) ∣ . H(p)=\{E:U_E\le p\},\qquad E(p)=|H(p)|. H ( p ) = { E : U E ≤ p } , E ( p ) = ∣ H ( p ) ∣. Then H ( p ) H(p) H ( p ) H d ( n , p ) H_d(n,p) H d ( n , p ) E ( p ) = r E(p)=r E ( p ) = r H ( p ) H(p) H ( p ) r r r M M M H d ( n , M ) H_d(n,M) H d ( n , M )
Put p − = p n ( λ − ε ) p_-=p_n(\lambda-\varepsilon) p − = p n ( λ − ε ) p + = p n ( λ + ε ) p_+=p_n(\lambda+\varepsilon) p + = p n ( λ + ε ) E − = E ( p − ) E_-=E(p_-) E − = E ( p − ) E + = E ( p + ) E_+=E(p_+) E + = E ( p + ) H ( p − ) ⊆ H ( p + ) H(p_-)\subseteq H(p_+) H ( p − ) ⊆ H ( p + ) E − ≤ E + E_-\leq E_+ E − ≤ E +
E E ± = m n ( λ ± ε ) , Var ( E ± ) = N p ± ( 1 − p ± ) = O ( n ) . \mathbb{E}E_\pm=m_n(\lambda\pm\varepsilon), \qquad\operatorname{Var}(E_\pm)=Np_\pm(1-p_\pm)=O(n). E E ± = m n ( λ ± ε ) , Var ( E ± ) = N p ± ( 1 − p ± ) = O ( n ) . Since M = m n ( λ ) + O ( 1 ) M=m_n(\lambda)+O(1) M = m n ( λ ) + O ( 1 )
m n ( λ ± ε ) − M = ± ε d ( d − 1 ) n 2 / 3 + O ( 1 ) , m_n(\lambda\pm\varepsilon)-M=\pm\frac{\varepsilon}{d(d-1)}n^{2/3}+O(1), m n ( λ ± ε ) − M = ± d ( d − 1 ) ε n 2/3 + O ( 1 ) , Chebyshev’s inequality, or a Chernoff bound, gives
P { E − ≤ M ≤ E + } ⟶ 1 , \mathbb{P}\{E_-\leq M\leq E_+\}\longrightarrow1, P { E − ≤ M ≤ E + } ⟶ 1 , because the gap between their means and M M M n 2 / 3 n^{2/3} n 2/3 n 1 / 2 n^{1/2} n 1/2
H ( p − ) ⊆ H d ( n , M ) ⊆ H ( p + ) , H(p_-)\subseteq H_d(n,M)\subseteq H(p_+), H ( p − ) ⊆ H d ( n , M ) ⊆ H ( p + ) , and consequently
L n ( λ − ε ) ≤ L n ( M ) ≤ L n ( λ + ε ) . L_n(\lambda-\varepsilon)\leq L_n(M)\leq L_n(\lambda+\varepsilon). L n ( λ − ε ) ≤ L n ( M ) ≤ L n ( λ + ε ) . Theorem 7.13 identifies the two extreme laws. Under a common Brownian motion, W d , λ ± ε W_{d,\lambda\pm\varepsilon} W d , λ ± ε W d , λ W_{d,\lambda} W d , λ ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0
ξ 1 ( λ ± ε ) ⟹ ξ 1 ( λ ) . \xi_1(\lambda\pm\varepsilon)\mathrel{\Longrightarrow}\xi_1(\lambda). ξ 1 ( λ ± ε ) ⟹ ξ 1 ( λ ) . For every continuous bounded increasing function f f f
E f ( n − 2 / 3 L n ( λ − ε ) ) − o ( 1 ) ≤ E f ( n − 2 / 3 L n ( M ) ) ≤ E f ( n − 2 / 3 L n ( λ + ε ) ) + o ( 1 ) . \begin{aligned}
\mathbb{E}f(n^{-2/3}L_n(\lambda-\varepsilon))-o(1)\leq\mathbb{E}f(n^{-2/3}L_n(M)) \\
&\leq\mathbb{E}f(n^{-2/3}L_n(\lambda+\varepsilon))+o(1).
\end{aligned} E f ( n − 2/3 L n ( λ − ε )) − o ( 1 ) ≤ E f ( n − 2/3 L n ( M )) ≤ E f ( n − 2/3 L n ( λ + ε )) + o ( 1 ) . First let n n n ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 R \mathbb{R} R
Remark 7.15 (Absence of local conditioning). The preceding proof never divides by P { E ( p ) = M } \mathbb{P}\{E(p)=M\} P { E ( p ) = M } λ \lambda λ d ≥ 2 d\geq2 d ≥ 2
Lemma 7.8 and Theorem 7.10 close finite-horizon convergence without hypotheses. This result does not suffice for the infinite ordered sequence of excursions: tightness beyond every horizon and control of component starts are still needed.
Wright normalization and identification with Pittel
Correct normalization of Wright’s constants
Two families bear the name Wright constants. The coefficients c ℓ c_\ell c ℓ [11 ] . The normalized coefficients γ ℓ \gamma_\ell γ ℓ γ ℓ , d \gamma_{\ell,d} γ ℓ , d d d d d = 2 d=2 d = 2
C 2 ( k , k + ℓ ) = ( 1 + o ( 1 ) ) γ ℓ k k − 1 / 2 + 3 ℓ / 2 ( k → ∞ ) . (51) C_2(k,k+\ell)=(1+o(1))\gamma_\ell k^{k-1/2+3\ell/2}\qquad(k\to\infty). \tag*{(51)} C 2 ( k , k + ℓ ) = ( 1 + o ( 1 )) γ ℓ k k − 1/2 + 3 ℓ /2 ( k → ∞ ) . (51) and satisfy [23 , 24 , 25 , 22 ]
γ ℓ = ( 1 + o ( 1 ) ) 3 4 π ( e 12 ℓ ) ℓ / 2 . (52) \gamma_{\ell}=(1+o(1))\sqrt{\frac{3}{4\pi}}\left(\frac{e}{12\ell}\right)^{\ell/2}. \tag*{(52)} γ ℓ = ( 1 + o ( 1 )) 4 π 3 ( 12 ℓ e ) ℓ /2 . (52) Consequently,
G ( s ) = ∑ ℓ ≥ − 1 γ ℓ s ℓ (53) G(s)=\sum_{\ell\geq-1}\gamma_{\ell}s^{\ell} \tag*{(53)} G ( s ) = ℓ ≥ − 1 ∑ γ ℓ s ℓ (53) converges absolutely for every s ≠ 0 s\ne0 s = 0 [20 , 22 ] . The factor Γ ( 3 ℓ / 2 ) \Gamma(3\ell/2) Γ ( 3 ℓ /2 ) b ℓ , d / Γ ( 3 ℓ / 2 ) b_{\ell,d}/\Gamma(3\ell/2) b ℓ , d /Γ ( 3 ℓ /2 ) γ ℓ ⋅ ( 1 + o ( 1 ) ) \gamma_{\ell}\cdot(1+o(1)) γ ℓ ⋅ ( 1 + o ( 1 )) b ℓ , d b_{\ell,d} b ℓ , d Γ ( 3 ℓ / 2 ) \Gamma(3\ell/2) Γ ( 3 ℓ /2 ) γ ℓ \gamma_{\ell} γ ℓ (32) , meanwhile, uses Γ ( ℓ / 2 + 1 ) \Gamma(\ell/2+1) Γ ( ℓ /2 + 1 )
Proposition 8.1 (Compatibility of the critical normalizations). Put h = d − 1 h=d-1 h = d − 1
m n ( θ ) = ⌊ n d ( d − 1 ) ( 1 + θ n − 1 / 3 ) ⌋ , p n ( θ ) = m n ( θ ) ( n d ) . m_n(\theta)=\left\lfloor\frac{n}{d(d-1)}(1+\theta n^{-1/3})\right\rfloor,\qquad p_n(\theta)=\frac{m_n(\theta)}{\binom{n}{d}}. m n ( θ ) = ⌊ d ( d − 1 ) n ( 1 + θ n − 1/3 ) ⌋ , p n ( θ ) = ( d n ) m n ( θ ) . Then, uniformly for θ \theta θ
p n ( θ ) = 1 + θ n − 1 / 3 + O ( n − 1 ) h ( n − 1 d − 1 ) . (54) p_n(\theta)=\frac{1+\theta n^{-1/3}+O(n^{-1})}{h\binom{n-1}{d-1}}. \tag*{(54)} p n ( θ ) = h ( d − 1 n − 1 ) 1 + θ n − 1/3 + O ( n − 1 ) . (54) Consequently, exploration at scale t = ⌊ s n 2 / 3 ⌋ t=\lfloor sn^{2/3}\rfloor t = ⌊ s n 2/3 ⌋
W d , θ ( s ) = h B ( s ) + θ s − h 2 s 2 . W_{d,\theta}(s)=\sqrt{h}B(s)+\theta s-\frac{h}{2}s^2. W d , θ ( s ) = h B ( s ) + θ s − 2 h s 2 . After the time change s = h − 1 / 3 u s=h^{-1/3}u s = h − 1/3 u
W d , θ ( h − 1 / 3 u ) = l a w h 1 / 3 { B ( u ) + θ h − 2 / 3 u − 1 2 u 2 } . (55) W_{d,\theta}(h^{-1/3}u)\mathrel{\mathop{=}^{\mathrm{law}}}h^{1/3}\left\{B(u)+\theta h^{-2/3}u-\frac{1}{2}u^2\right\}. \tag*{(55)} W d , θ ( h − 1/3 u ) = law h 1/3 { B ( u ) + θ h − 2/3 u − 2 1 u 2 } . (55) Thus the three normalizations used in the manuscript (critical window, n 2 / 3 n^{2/3} n 2/3
Proof. The identity
n d ( d − 1 ) ( n d ) − 1 = 1 ( d − 1 ) ( n − 1 d − 1 ) \frac{n}{d(d-1)}\binom{n}{d}^{-1}=\frac{1}{(d-1)\binom{n-1}{d-1}} d ( d − 1 ) n ( d n ) − 1 = ( d − 1 ) ( d − 1 n − 1 ) 1 and the rounding error O ( 1 ) O(1) O ( 1 ) m n ( θ ) m_n(\theta) m n ( θ ) O ( n − 1 ) O(n^{-1}) O ( n − 1 ) m n ( θ ) m_n(\theta) m n ( θ ) n n n Theorem 7.10 then give the displayed process. Finally, self-similarity B ( h − 1 / 3 u ) = l a w h − 1 / 6 B ( u ) B(h^{-1/3}u)\mathrel{\mathop{=}^{\mathrm{law}}}h^{-1/6}B(u) B ( h − 1/3 u ) = law h − 1/6 B ( u )
h B ( h − 1 / 3 u ) = h 1 / 3 B ( u ) , θ h − 1 / 3 u = h 1 / 3 ( θ h − 2 / 3 u ) , \sqrt{h}B(h^{-1/3}u)=h^{1/3}B(u),\qquad\theta h^{-1/3}u=h^{1/3}(\theta h^{-2/3}u), h B ( h − 1/3 u ) = h 1/3 B ( u ) , θ h − 1/3 u = h 1/3 ( θ h − 2/3 u ) , and ( h / 2 ) h − 2 / 3 u 2 = h 1 / 3 u 2 / 2 (h/2)h^{-2/3}u^2=h^{1/3}u^2/2 ( h /2 ) h − 2/3 u 2 = h 1/3 u 2 /2
Exact reduction of the hypergraph law to Pittel’s law
Let F P i t ( x , μ ) F_{\mathrm{Pit}}(x,\mu) F Pit ( x , μ )
B ( t ) + μ t − 1 2 t 2 . B(t) + \mu t - \frac{1}{2}t^2. B ( t ) + μ t − 2 1 t 2 . Pittel [17, equation (3.25)] gives an explicit integral representation and proves that it is the limiting law of the largest component of the critical graph. This notation fixes the published integral without ambiguity, including its amplitude and contour, and avoids reconstructing these constants from a merely formal phase.
Theorem 8.2 (Identification with Pittel’s law by Brownian self-similarity). For every d ≥ 2 d \ge2 d ≥ 2 a > 0 a > 0 a > 0 λ ∈ R \lambda\in\mathbb{R} λ ∈ R h = d − 1 h = d - 1 h = d − 1 Theorem 7.3 satisfies
P { ξ 1 ≤ a } = F P i t ( h 1 / 3 a , λ h − 2 / 3 ) . (56) \mathbb{P}\{\xi_1 \le a\} = F_{\mathrm{Pit}}(h^{1/3}a,\lambda h^{-2/3}). \tag*{(56)} P { ξ 1 ≤ a } = F Pit ( h 1/3 a , λ h − 2/3 ) . (56) Thus, after the substitution
a P i t = h 1 / 3 a , λ P i t = λ h − 2 / 3 , a_{\mathrm{Pit}} = h^{1/3}a,\qquad\lambda_{\mathrm{Pit}} = \lambda h^{-2/3}, a Pit = h 1/3 a , λ Pit = λ h − 2/3 , Pittel’s integral representation identifies the limit law for every d ≥ 2 d \ge2 d ≥ 2
Proof. Proposition 8.1, with θ = λ \theta= \lambda θ = λ h 1 / 3 h^{1/3} h 1/3 s = h − 1 / 3 t s = h^{-1/3}t s = h − 1/3 t [7 Chapter VI] ), so excursion lengths are multiplied by h − 1 / 3 h^{-1/3} h − 1/3
ξ 1 ( d , λ ) = l a w h − 1 / 3 ξ 1 ( 2 , λ h − 2 / 3 ) . \xi_1(d,\lambda) \mathrel{\stackrel{\mathrm{law}}{=}} h^{-1/3}\xi_1(2,\lambda h^{-2/3}). ξ 1 ( d , λ ) = law h − 1/3 ξ 1 ( 2 , λ h − 2/3 ) . The case d = 2 d = 2 d = 2 [17 ] ; this gives (55). □
Remark 8.3 (Attribution of the integral equality). Identification of the limit law with Pittel’s integral formula rests on two distinct contributions. The equality between the law of the largest excursion of B ( t ) + μ t − 1 2 t 2 B(t) + \mu t - \frac{1}{2}t^2 B ( t ) + μ t − 2 1 t 2 [17 ] and Aldous [2 ] . The specific contribution of the present article lies in the rescaling factors h 1 / 3 h^{1/3} h 1/3 λ h − 2 / 3 \lambda h^{-2/3} λ h − 2/3 d d d d ≥ 2 d \ge2 d ≥ 2 h = d − 1 h = d - 1 h = d − 1
Corollary 8.4 (Main theorem by the probabilistic route). For every fixed integer d ≥ 2 d \ge2 d ≥ 2 λ ∈ R \lambda\in\mathbb{R} λ ∈ R
M = n d ( d − 1 ) ( 1 + λ n − 1 / 3 ) + O ( 1 ) , M = \frac{n}{d(d-1)}(1+\lambda n^{-1/3}) + O(1), M = d ( d − 1 ) n ( 1 + λ n − 1/3 ) + O ( 1 ) , if L n L_n L n H d ( n , M ) H_d(n,M) H d ( n , M ) a > 0 a > 0 a > 0
lim n → ∞ P { n − 2 / 3 L n ≤ a } = F P i t ( ( d − 1 ) 1 / 3 a , λ ( d − 1 ) − 2 / 3 ) . (57) \lim_{n\to\infty}\mathbb{P}\{n^{-2/3}L_n \le a\}
= F_{\mathrm{Pit}}\bigl((d-1)^{1/3}a,\lambda(d-1)^{-2/3}\bigr). \tag*{(57)} n → ∞ lim P { n − 2/3 L n ≤ a } = F Pit ( ( d − 1 ) 1/3 a , λ ( d − 1 ) − 2/3 ) . (57) Proof. Theorem 7.10 gives convergence of the exploration process on every compact interval. Lemma 7.11 and Theorem 7.13 ensure tightness of the ordered excursions and passage to ℓ ↓ 2 \ell^2_{\downarrow} ℓ ↓ 2 M M M
Corollary 8.6 (A differential equation for verification). Setting
Φ ( x ; μ ) = 1 x 2 π G ( x 3 / 2 ) exp { − μ 3 6 + ( μ − x ) 3 6 } , \Phi(x;\mu)=\frac{1}{x\sqrt{2\pi}}G(x^{3/2})\exp\left\{-\frac{\mu^3}{6}+\frac{(\mu-x)^3}{6}\right\}, Φ ( x ; μ ) = x 2 π 1 G ( x 3/2 ) exp { − 6 μ 3 + 6 ( μ − x ) 3 } , one obtains
∂ x F P i t ( x , μ ) = F P i t ( x , μ − x ) Φ ( x ; μ ) . (58) \partial_xF_{\mathrm{Pit}}(x,\mu)=F_{\mathrm{Pit}}(x,\mu-x)\Phi(x;\mu). \tag*{(58)} ∂ x F Pit ( x , μ ) = F Pit ( x , μ − x ) Φ ( x ; μ ) . (58) This identity, proved by the local theorem of [22 ] , provides an independent check on the normalization and positivity of the density.
The d-uniform Bollobás bound and the analytic domain
The Bollobás bound is formulated here with the proved quantifiers, in two regimes: Wright for each fixed excess, combinatorial throughout the domain. It does not enter the proof of Theorem 1.1 .
Proposition 9.1 (Verified Puiseux expansion). Let h = d − 1 h=d-1 h = d − 1 and let T d ( x ) T_d(x) T d ( x ) be defined by T d = x exp ( T d h / h ! ) T_d=x\exp(T_d^h/h!) T d = x exp ( T d h / h !) If τ d \tau_d τ d satisfies h τ d h / h ! = 1 h\tau_d^h/h!=1 h τ d h / h ! = 1 and ρ d = τ d exp ( − τ d h / h ! ) \rho_d=\tau_d\exp(-\tau_d^h/h!) ρ d = τ d exp ( − τ d h / h !) then
T d ( x ) = τ d − τ d 2 h 1 − x / ρ d + O ( 1 − x / ρ d ) . T_d(x)=\tau_d-\tau_d\sqrt{\frac{2}{h}}\sqrt{1-x/\rho_d}+O(1-x/\rho_d). T d ( x ) = τ d − τ d h 2 1 − x / ρ d + O ( 1 − x / ρ d ) . Proof. Put x ( T ) = T exp ( − T h / h ! ) x(T)=T\exp(-T^h/h!) x ( T ) = T exp ( − T h / h !) x ′ ( τ d ) = 0 x'(\tau_d)=0 x ′ ( τ d ) = 0
x ′ ′ ( τ d ) ρ d = − h τ d 2 . \frac{x''(\tau_d)}{\rho_d}=-\frac{h}{\tau_d^2}. ρ d x ′′ ( τ d ) = − τ d 2 h . Taylor’s formula gives 1 − x / ρ d = h 2 τ d 2 ( T − τ d ) 2 + O ( ( T − τ d ) 3 ) 1-x/\rho_d=\frac{h}{2\tau_d^2}(T-\tau_d)^2+O((T-\tau_d)^3) 1 − x / ρ d = 2 τ d 2 h ( T − τ d ) 2 + O (( T − τ d ) 3 ) [8 Theorem VI.6] . □
Theorem 9.2 (d d d Fix d ≥ 2 d\ge2 d ≥ 2 and put h = d − 1 h=d-1 h = d − 1
(i) Wright regime. For each fixed integer ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 there exist K d , ℓ < ∞ K_{d,\ell}<\infty K d , ℓ < ∞ and v 0 ( d , ℓ ) v_0(d,\ell) v 0 ( d , ℓ ) such that, for every v ≥ v 0 ( d , ℓ ) v\ge v_0(d,\ell) v ≥ v 0 ( d , ℓ ) satisfying v + ℓ ≡ 0 ( m o d h ) v+\ell\equiv0\pmod h v + ℓ ≡ 0 ( mod h )
C d ( v , v + ℓ h ) ≤ K d , ℓ v ! ρ d − v v 3 ℓ / 2 − 1 . (59) C_d\left(v,\frac{v+\ell}{h}\right)\le K_{d,\ell}v!\rho_d^{-v}v^{3\ell/2-1}. \tag*{(59)} C d ( v , h v + ℓ ) ≤ K d , ℓ v ! ρ d − v v 3 ℓ /2 − 1 . (59) (ii) Global domain. For all admissible v ≥ 1 v\ge1 v ≥ 1 and ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 putting q = ( v + ℓ ) / h q=(v+\ell)/h q = ( v + ℓ ) / h
C d ( v , q ) ≤ ( v q ) ≤ ( e ( v / d ) q ) q . (60) C_d(v,q)\le{v\choose q}\le\left(\frac{e(v/d)}{q}\right)^q. \tag*{(60)} C d ( v , q ) ≤ ( q v ) ≤ ( q e ( v / d ) ) q . (60) Proof. For (i), Theorem 5.1 gives, for fixed ℓ \ell ℓ
C d ( v , v + ℓ h ) = γ ℓ , d v ! ρ d − v v 3 ℓ / 2 − 1 ( 1 + O d , ℓ ( v − 1 / 2 ) ) . C_d\left(v,\frac{v+\ell}{h}\right)=\gamma_{\ell,d}v!\rho_d^{-v}v^{3\ell/2-1}\left(1+O_{d,\ell}(v^{-1/2})\right). C d ( v , h v + ℓ ) = γ ℓ , d v ! ρ d − v v 3 ℓ /2 − 1 ( 1 + O d , ℓ ( v − 1/2 ) ) . It suffices to choose v 0 ( d , ℓ ) v_0(d,\ell) v 0 ( d , ℓ ) 1 1 1 K d , ℓ = 2 γ ℓ , d K_{d,\ell}=2\gamma_{\ell,d} K d , ℓ = 2 γ ℓ , d C d ( v , q ) C_d(v,q) C d ( v , q ) q q q ( v d ) {v\choose d} ( d v ) ( N q ) ≤ ( e N / q ) q {N\choose q}\le(eN/q)^q ( q N ) ≤ ( e N / q ) q
Assessment of the two routes
Corollary 8.4 closes the limit law unconditionally by the probabilistic route: convergence of the exploration process on every finite horizon (Theorem 7.10 ), tightness of ordered excursions (Theorem 7.13 ), transfer to the M M M Theorem 7.14 ), and identification of the law by Brownian self-similarity (Theorem 8.2 ). No uniformity in the excess enters.
The analytic route, for its part, produces exact identities and normalization cancellations that the probabilistic route does not establish. The formulas in Theorem 2.1 , Proposition 3.1, and Theorem 4.1 hold for every fixed d ≥ 2 d \ge2 d ≥ 2 § 9 delineates is precisely what the analytic route proves today, and what it does not yet prove without an additional hypothesis on hypergraph kernels.
Acknowledgements
The author is grateful to Professor Vlady Ravelomanana (IRIF, CNRS, Université Paris Cité) for his careful reading of an earlier draft, his precise remarks on the analytic combinatorics arguments, and his encouragement to pursue the d d d d = 2 d = 2 d = 2
Email address: wirdane.youssouf@univ-comores.com
