# The Maximal Length of 2-Path in Random Critical Graphs

Authors: Vonjy Rasendrahasina; Vlady Ravelomanana; Liva Aly Raonenantsoamihaja
Journal: Journal of Applied Mathematics
 (2018)

---

## Abstract

Given a graph, its2-core is the maximal subgraph of G without vertices of degree 1. A 2-path in a connected graph is a simple path in its 2-core such that all vertices in the path have degree 2, except the endpoints which have degree ⩾3. Consider the Erdős-Rényi random graph G(n,M) built with n vertices and M edges uniformly randomly chosen from the set of n2 edges. Let ξn,M be the maximum 2-path length of G(n,M). In this paper, we determine that there exists a constant c(λ) such that Eξn,n/21+λn-1/3~c(λ)n1/3,foranyrealλ. This parameter is studied through the use of generating functions and complex analysis.


---

## Body

## 1. Preliminaries

Let us recall that anundirected graphG is a couple (V,E), where V is the set of vertices and E the set of edges, and an edge is an unordered pair of vertices. If we allow an edge between a vertex and itself (loop) or multiple edges between two vertices, we obtain amultigraph. An undirected graph without loops or multiple edges is known as asimple graph. Apath in graph G=(V,E) is sequence of vertices v0,v1,…,vk, where vi,vi+1∈E for i∈0,k-1 and vi≠vj for i≠j except that its first vertex v0 might be the same as its last vk. When any two vertices of G are connected by a path G is calledconnected.A connected graph hasexcess if it has more edges than vertices. A connected component of excess l is also called l-component. A tree or acyclic component is a connected component of excess -1, an unicyclic component in a connected component of excess 0. If l⩾1, l-components are called complex. A graph (not necessarily connected) is calledcomplex when all its components are complex. Thetotal excessr of a graph is the number of edges plus the number of acyclic components, minus the number of vertices. In other words, the total excess of a graph is the sum of the excess of its complex components. Note that the total excess of a tree component is equal to 0 whereas its excess is equal to -1 and the total excess of a graph is nonnegative.Given a graphG, its 2-core is obtained by deleting recursively all nodes of degree 1. A 3-core orkernel of a complex graph is the graph obtained from its 2-core by repeating the following process on any vertex of degree two: for a vertex of degree two, we can remove it and splice together the two edges that it formerly touched. We observe that G, its 2-core, and its kernel have the same excess. A graph is saidcubic or 3-regular if all of its vertices are of degree 3. A graph is calledclean if its 3-core is 3-regular (see [1]).A random graphG(n,M=cn) is calledcritical if the density c=1/2±O(n-1/3). Such a graph contains a complex component with nonzero probability [2, 3]. Janson et al. [1] proved these graphs are clean (its complex components are clean) with high probability when the size of graph goes to infinity.Theorem 1.
The maximum2-path length ξn,M of G(n,M) satisfies(1)Eξn,n/21+λn-1/3~cλn1/3,where(2)cλ=1α∫0+∞1-∑r⩾02πerA3r+1/2,λ1-e-x3rdx,where α is the positive solution of(3)λ=α-1-α,er is given by(4)er=6r!25r32r3r!2r!, and the function A is defined by(5)Ay,λ=e-λ3/63y+1/3∑k⩾01/232/3λkk!Γy+1-2k/3.We remark that for Erdős-Rényi random graphGn,p=1+ε/n, Ding et al. [4] and Ding et al. [5] provided a complete characterisation of the structure of the giant component when ε=o(1) but ε3n→∞. Using our notation, ε=λn-1/3 but λ→∞ as n→∞. They describe that the 2-core of a graph is obtained by “stretching” the edges into paths of lengths i.i.d. geometric with mean 1/ε=λ-1n1/3. Next, in order to reconstruct the graph, they attached trees to vertices i.i.d. Poisson(1-ε)-Galton-Watson.


## 2. Enumerative Tools

As shown in [1, 3], exponential generating functions (EGFs) can lead to stringent results about the main characteristics of random graphs when they apply. Let us recall briefly the main EGFs involved in our proofs. We refer the reader to Harary and Palmer [6] for EGFs related to graphical enumeration.Forn⩾0 and -1⩽l⩽n2, let c(n,n+l) be the number of connected graphs of excess l and(6)Wlz=∑n=0+∞cn,n+lznn!,the associated EGF. We know from [7] that c(n,n-1)=nn-2 and(7)W-1z=∑n=1+∞nn-2znn!=Tz2-12Tz2,where T(z) is the EGF of rooted Cayley trees given by(8)Tz=zeTz=∑n=1+∞nn-1znn!.We also have (see, e.g., [1, Equation (3.5)])(9)W0z=12log11-Tz-Tz2-Tz24.Wright [8] has shown that the EGFs (Wl)l⩾1 can be expressed in terms of T(z). More precisely, Wright proved that for each l⩾1 there exist rational coefficients wl,d,d∈{0,…,3l+2} such that (10)Wlz=∑d=03l+2wl,d1-Tz3l-d.The coefficientsbl≔wl,0 are known as Wright’s constants (see [9]). For complex graphs, denote by Er(z) the EGF of these graphs of excess r. Then we have E0(z)=1 (empty graphs) and E1(z)=W1(z). More generally, as detailed in [1, Section 8], the EGF Er(z) satisfies(11)∑r=0+∞Erz=exp⁡∑r=1+∞Wlz.Following [1], the EGF Er(z) can also be expressed as a rational function of T(z)(12)Erz=∑d⩾0er,dTz5r-d1-Tz3r-d=∑d⩾0er,d′1-Tz3r-d,where er≔er,0=er,0′. The coefficients (er) and (br) are related by(13)e0=1,rer=rbr+∑j=1r-1jbjer-jasr⩾1.As shown in [1, 10], we remark that the dominant asymptotic behavior of [zn]Wl(z) and [zn]Er(z) (for any power series A(z)=∑anzn, [zn]A(z) denotes the nth coefficient of A(z), namely, [zn]A(z)=an.) is governed by the leading coefficients bl and er. In particular, if l and r are about o(n1/3), these EGFs satisfy(14)Wlz≍lbl1-Tz3l,Erz≍rer1-Tz3r,where A(z)≍lB(z) if and only if [zn]A(z)~[zn]B(z) as n→+∞ and l=o(n1/3).The EGFbl/1-Tz3l (resp., er/1-Tz3r) can be interpreted as EGF of connected graphs (resp., complex graphs) whose kernels are 3-regular. Such a graph has exactly 3l (resp., 3r) 2-paths. A 2-path in the 2-core is enumerated by 1/1-z. Substituting z by T(z) to obtain 1/1-T(z) means attaching tree to each vertex of the 2-core. Since a 3-regular graph of excess r has exactly 3r edges, the associated graph has 3r2-paths. Note that, in the stated range, complex graphs and multigraphs of excess r are both enumerated by er/1-Tz3r and for large r, er~br (see [1, Equation (7.16)] and [9, Section 7]).In our case, we need to control the length of each 2-path to a graph. We restrict our attention to complex graphs whose 2-paths are of length at mostk. So, instead of allowing 2-path of any length (1/1-T(z)=1+T(z)+Tz2+⋯+Tzk+⋯), we use a 2-path of length at most k (1+T(z)+Tz2+⋯+Tzk). The associated EGF is(15)er1+Tz+Tz2+⋯+Tzk3r=er1-Tzk+13r1-Tz3r.


## 3. Proof of Theorem1

Consider a graph withn vertices, M edges, and a total excess r. Such a graph contains exactly n-M+r tree components. They are enumerated by the following EGF:(16)W-1zn-M+rn-M+r!expW0zErz.Since the total number of graphs withn vertices and M edges is n2M, the probability that a random (n,M)-graph (graphs with n vertices and M edges) is of total excess r is(17)n!n2MznW-1zn-M+rn-M+r!exp⁡W0zErz.Similarly, the probability that a random(n,M)-graph is of total excess r and has no 2-path of length greater than k is(18)n!n2MznW-1zn-M+rn-M+r!exp⁡W0zErkz,where Er[k](z) denotes the EGF of all complex components of total excess r whose 2-paths are of length at most k, k⩾1. Then summing over r, we get that the probability that a random (n,M)-graph has no 2-path of length greater than k is(19)Pξn,M⩽k=∑r⩾0n!n2MznW-1zn-M+rn-M+r!exp⁡W0zErkz.Following discussion in the previous section and using (15), the probability of a random Pξn,M⩽k is asymptotically equivalent to(20)Pξn,M⩽k~∑r⩾0n!n2MznW-1zn-M+rn-M+r!exp⁡W0zer1-Tzk+13r1-Tz3r.As in [11, Section 4] where Flajolet et al. described generating functions based methods to study extremal statistics on random mappings, we characterize the expectation of ξn,M by means of truncated generating functions aforementioned. In fact, the mean value of ξn,M is given by(21)Eξn,M=∑k⩾0kPξn,M=k=∑k⩾01-PX⩽k.Then, combining (19), (20), and (21), we have(22)Eξn,M~∑k⩾01-∑r⩾0n!n2MznW-1zn-M+rn-M+r!exp⁡W0zer1-Tzk+13r1-Tz3r.To computeE(ξn,M), we use the following lemma.Lemma 2.
LetM=n/21+λn-1/3. For any natural integers r and k, one has(23)pr,kn,M≔n!n2MznW-1zn-M+rn-M+r!exp⁡W0z1-Tzk3r1-Tz3r=2πA3r+12,λ1-ekαn-1/33r1+Oλ4n1/3.Proof.
We set(24)Stn,M,r=n!n2Mn-M+r!,Can,M,r=znW-1zn-M+reW0z1-Tzk3r1-Tz3r.
First, using Stirling’s formula, we obtain(25)StM,n=2πn2n-M+rnrexp-λ36+34-n1+Oλ4n1/3.
Next, using Cauchy integral’s formula and substitutingz by ze-z, we obtain(26)CaM,n=12πi∮Tz-Tz22n-M+re-Tz/2-Tz2/41-Tzk3r1-Tz3r+1/2dzzn+1=2M-n-ren2πi∮gzexp⁡nhzdzz,where(27)gz=2z-z2re-z/2-z2/41-zk3r1-z3r-1/2,hz=z-1-log⁡z-1-Mnlog⁡11-z-12.
The contour in (26) should keep z<1. At the critical value M=n/2, we also have h(1)=h′(1)=h′′(1)=0. This triple zero occurs in the procedure Janson et al. [1] used when investigating the value of the integral for large n. Let ν=n-1/3, and let α be the positive solution of (3). Following the proof of [1, Lemma 3], we will evaluate (26) on the path z=e-(α+it)ν, where t runs from -πn1/3 to πn1/3:(28)∮fzdzz=iν∫-πn1/3πn1/3fe-α+itνdt.
The main contribution to the value of this integral comes from the vicinity oft=0. The magnitude of eh(z) depends on the real part of h(z), namely, Re hz. Re he-α+itν decreases as t increases and enhz has its maximum on the circle z=e-(α+it)ν when t=0.
We have fornhe-sν(29)nhe-sν=13s3+12λs2+Oλ2s2+s4ν, uniformly in any region such that sν<log⁡2. In [1, equation (10.7)], the authors define(30)Ay,μ=12πi∫Π1s1-yeKμ,sds, where K(μ,s) is the polynomial(31)Kμ,s=s+μ22s-μ6=s33+μs22-μ36and Π(α) is a path in the complex plane that consists of the following three straight line segments:(32)st=-e-πi/3t,for-∞<t⩽-2α;α+itsin⁡π3,for-2α⩽t⩽+2α;e+πi/3t,for+2α⩽t<+∞.
In particular, they proved thatA(y,μ) can be expressed as (5).
For the functiong(z), we have(33)ge-sν=2e-sν-e-2sνr1-e-sν3r-1/2e-e-sν/2-e-2sν/41-e-ksν3r=sν1/2-3re-3/41-e-ksν3r1+Osν.
Forg(z)enh(z) in the integrand of (26), we have(34)e-λ3/6fe-sν=e-3/4ν1/2-3r1-e-ksν3rs1-3r+1/2eKλ,s1+Osν+Oλ2s2ν+Os4ν
whens=O(n1/12). Next,(35)e-λ3/62πi∮gzenhzdzz=e-3/41-e-kαν3rν3/2-3rA3r+12,λ+Oν5/2-3re-λ3/6λ3r/2+1/4, where the error term has been derived from those already in [1]. The proof of the lemma is completed by multiplying (25), (26), and er.Now, to complete the proof of the theorem, we use first Lemma2 to get(36)Pξn,M⩽k~∑r⩾02πerA3r+12,λ1-e-k+1αn-1/33r.Next, using Euler-Maclaurin summation, and after a change of variable (x=(k+1)αn-1/3 so dx/dk=αn-1/3 and dk=α-1n1/3dx), we get(37)Eξn,M=∑k=0+∞1-Pξn,M⩽k,~∑k=0+∞1-∑r⩾02πerA3r+12,λ1-e-k+1αn-1/33r~∫0+∞1-∑r⩾02πerA3r+12,λ1-e-x3rdk~α-1n1/3∫0+∞1-∑r⩾02πerA3r+12,λ1-e-x3rdx.


## 4. Conclusion

In this paper, we have studied the expectation of the maximal length of 2-path in random critical graph by means of enumerative and analytic combinatorics approaches when the size of the graph goes to infinity. Our analysis gives a precise description of the parameter near the critical point.



---

*Source: 8983218-2018-05-14.xml*