Further results on random cubic planar graphs

Further results on random cubic planar graphs Marc Noy ∗Cl´ement Requil´e †Juanjo Ru´e ‡ Abstract We provide precise asymptotic estimates for the number of several classes of labeled cubic planar graphs, and we analyze properties of such random graphs under the uniform distribution. This model was first analyzed by Bodirsky et al. (Random Structures Algorithms 2007). We revisit their work and obtain new results on the enumeration of cubic planar graphs and on random cubic planar graphs. In particular, we determine the exact probability of a random cubic planar graph being connected, and we show that the distribution of the number of triangles in random cubic planar graphs is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution for the number of copies of a fixed graph containing a cycle in classes of random planar graphs arising from planar maps. 1 Introduction and summary of results The enumeration of labeled planar graphs has been recently the subject of much research; see [11, 12] for surveys on the area. The problem of counting planar graphs was first solved by Gim´enez and Noy [6], while cubic planar graphs where enumerated by Bodirsky, Kang, L¨offler and McDiarmid [2]. More recently, the present authors solved the problem of enumerating 4-regular planar graphs [14]. Several open problems remain, like the enumeration of bipartite or triangle-free planar graphs. The goal of this paper is to sharpen the results from [2], as well as to prove new results. We first enumerate asymptotically several classes of labeled cubic planar graphs. Among our new results are the enumeration of cubic planar multigraphs and of triangle-free cubic planar graphs. In order to achieve this goal we need to use the so-called Dissymmetry Theorem for counting unrooted graphs whose structure can be encoded by means of a decomposition tree. Random cubic planar graphs are analyzed according to the uniform distribution. More precisely, let G be the class of labeled cubic planar graphs and let gnbe the number of graphs in Gwith nvertices. Then each graph in Gwith nvertices is taken with the same probability 1/gn. We obtain the exact probability that a random cubic planar graph is connected, and we prove several results on the distribution of the number of copies of a fixed subgraph. In particular, we show that the distribution of the number of triangles is asymptotically normal with linear expectation and variance. To the best of our knowledge, this is the first time one is able to determine the asymptotic distribution of the number of copies of a fixed graph H containing a cycle in classes of random planar graphs arising from planar maps. We also obtain Gaussian limit laws for the number of copies of certain almost cubic subgraphs. ∗Universitat Polit`ecnica de Catalunya and Barcelona Graduate School of Mathematics, Department of Mathematics, Edifici Omega, 08034 Barcelona, Spain. E-mail: [email protected]. Supported by the Spanish Ministerio de Econom´ıa y Competitividad projects MTM2014-54745-P, MTM2017-82166-P and MDM-2014-0445. †Institute for Algebra, Johannes Kepler Universit¨at Linz, Austria. E-mail: [email protected]. Supported by the Austrian Science Fund (FWF) grant F5004. The work presented in this paper was carried out while the author was affiliated with the Institut f¨ur Mathematik und Informatik, Freie Universit¨at Berlin, and Berlin Mathematical School, Germany, and partially supported by the Marie Curie Career Integration Grant FP7 PEOPLE - 2013-CIG 630749 - Countgraph. ‡Universitat Polit`ecnica de Catalunya and Barcelona Graduate School of Mathematics, Department of Mathematics, Edifici Omega, 08034 Barcelona, Spain. E-mail: [email protected]. Supported by the Spanish Ministerio de Econom´ıa y Competitividad project MTM2014-54745-P, MTM2017-82166-P and the Marie Curie Career Integration Grant FP7 PEOPLE - 2013-CIG 630749 - Countgraph. 1 The proofs are based on combinatorial decompositions, generating functions and asymptotic analysis of their coefficients, using the tools of analytic combinatorics [5]. In several places we use Maple to perform symbolic and numerical computations. 1.1 Results on enumeration In the first place we obtain an asymptotic estimate for the number cnof connected cubic planar graphs. In all the statements that follow, nshould be even since a cubic graph has necessarily an even number of vertices. To avoid repetition, we assume this is always the case when referring to the number of vertices in cubic graphs. All the numerical constants in this paper are given with a precision of 6 decimals places. Theorem 1. The number cnof connected cubic planar graphs with nvertices is asymptotically cn∼c·n−7/2γnn!, where c≈0.060973 and γ=ρ−1≈3.132591, where ρ≈0.319225 is the smallest positive root of the equation 729x12 + 17496x10 + 148716x8+ 513216x6−7293760x4+ 279936x2+ 46656 = 0.(1) Next we estimate the number of all cubic planar graphs. Theorem 2. The number gnof cubic planar graphs with nvertices is asymptotically gn∼g·n−7/2γnn!, where γis as in Theorem 1 and g≈0.061010. As a consequence, the limiting probability pthat a random cubic planar graph is connected is equal to p=c g≈0.999397. We remark that the actual value of pwas not computed in [2], only estimated from values of cnand gn for small n. As we will see later, pcan be computed exactly using the Dissymmetry Theorem. Once we have the value of p, a standard proof (see [7]) shows that the number of connected components in a random cubic graph is asymptotically distributed as X+ 1, where Xis a Poisson law of parameter λ≈0.000604. It is also possible to estimate the number of 2-connected cubic planar graphs. Theorem 3. Let bnbe the number of 2-connected cubic planar graphs on nvertices. Then bn∼b·n−7/2γn bn!, where b≈0.059244,γb=ρ−1 b≈3.129666, where ρb≈0.319523 is the smallest positive solution of 54x6+ 324x4−4265x2+ 432 = 0. Our next result is an estimate on the number of cubic planar multigraphs. This class of graphs is instrumental in the study of the phase transition of the Erd˝os-R´enyi random graph [8, 9, 13]. In these references cubic multigraphs are equipped with a weight that depends on the number of loops and multiple edges. Here we count unweighted cubic multigraphs, which is a result interesting by itself. Theorem 4. The number hnof cubic planar multigraphs is asymptotically hn∼h·n−7/2γn mn!, with h≈0.224743 and γm=ρ−1 m≈3.985537, where ρm≈0.250907 is the smallest positive root of the equation 729 x12 −17496 x10 + 148716 x8−513216 x6−7293760 x4−279936 x2+ 46656 = 0.(2) 2 The same estimate holds for the number of connected cubic planar multigraphs, but with hreplaced by the constant h0≈0.209410. The limiting probability of connectivity is pm=h0 h≈0.931778. We remark that the proof needs again an application of the Dissymmetry Theorem, since the presence of loops and multiple edges does not allow us, as for simple graphs, to directly relate the number of graphs rooted at a vertex with those rooted at an edge. In addition, the similarity between equations (1) and (2) will be explained later. We recall that a sequence (an) is P-recursive if it satisfies a linear recurrence relation whose coefficients are polynomials in n. Theorem 5. The following sequences are P-recursive: the numbers of arbitrary, connected and 2-connected cubic planar graphs, and the number of cubic planar multigraphs. The proofs rely on the algebraic character of several of the generating functions involved and, in the case of cubic multigraphs, on a further application of the Dissymmetry Theorem. Our last result in this section is the enumeration of triangle-free cubic planar graphs. The proof is more involved and will be given after the proof of Theorem 7, since it uses the techniques introduced there for studying the distribution of the number of triangles in random cubic planar graphs. Theorem 6. The number unof connected triangle-free cubic planar graphs with nvertices is asymptotically fn∼f·n−7/2γn tn!, with f≈0.000911 and γt=ρ−1 t≈2.641747, where ρt≈0.378537 is the smallest positive solution of the equation x40 −2x38 −41x36 + 180x34 + 285x32 −3630x30 −26651 4x28 +5654783 32 x26 −3989098451 4096 x24 +50409552353 16384 x22 −246713078305261 37748736 x20 +8988271236666325 905969664 x18 −34616066062430108809 3131031158784 x16 +148714112813428613 16307453952 x14 −88102457851295 15925248 x12 +28819599609215 11943936 x10 −2805808889 3888 x8+130387637 972 x6−8646784 729 x4−128x2+ 64 = 0. (3) In addition, the number tnof triangle-free cubic planar graphs with nvertices is asymptotically tn∼α·n−7/2γn tn!, where α≈0.0009109. The multiplicative constant αin the last theorem is the only constant in our work for which we do not obtain an exact expression. It would be in principle possible to obtain this expression, but the computations would be very complex. The approximate value given in the statement is estimated from small values of n. At the end of the paper we provide a table with the numbers of cubic planar graphs for small values of n for the new families we have enumerated: multigraphs and triangle-free graphs. The numbers for arbitrary, connected and 2-connected cubic planar graphs are listed in [2]. 1.2 Results on limit laws Given an unlabeled graph H, a copy of Hin a labeled graph Gis a subgraph isomorphic to H. Our results in this section deal with the number of copies of a fixed subgraph. We start with the number of triangles, the main result in this section. We say that a sequence Xnof random variables is asymptotically normal if the standardized variables (Xn−E[Xn])/σ(Xn) converge in distribution to the standard normal law. 3 Theorem 7. Let Xnbe the number of triangles in a random cubic planar graph. Then Xnis asymptotically normal with moments E[Xn]∼µn, Var[Xn]∼λn, where µ≈0.121974, λ ≈0.064985. It was proved in [2] that Xnis linear with high probability. Our result is a considerable sharpening of this fact. The proof, based on the so-called Quasi-powers Theorem, is technically involved and we are not able to extend it, for instance, to the number of cycles of length 4. The key property here is that two triangles in a cubic graph are either vertex disjoint or share one edge. Our final results concern the number of copies of graphs which are close to being cubic. We define a cherry as a planar graph in which all vertices have degree 3 except for one vertex of degree 1. The smallest cherry has 6 vertices and is obtained by subdividing one edge of K4and attaching one vertex of degree 1. In what follows, we denote by aut(H) the number of automorphisms of a graph H. We recall that the number of different ways of labeling an unlabeled graph His equal n!/aut(H). Theorem 8. Let XH,n be the number of copies of a fixed unlabeled cherry Hwith hvertices in a random cubic planar graph. Then XH,n is asymptotically normal with moments E[XH,n]∼µn, Var[XH,n]∼λn, where µ=4374(ρ4+ 8ρ+ 4)2 ρ2P1·ρh aut(H), λ =8748(ρ4+ 8ρ+ 4)(P2h+P3) ρ4P3 1·ρ2h aut(H)2+µ+µ2, where ρis as in Theorem 1, and P1=−(2187ρ10 + 43740ρ8+ 297432ρ6+ 769824ρ4−7293760ρ2+ 139968) >0, P2=−4374 ρ4+ 8 ρ2+ 43P1, P3=−14348907ρ22 −593088156ρ20 −10235553660ρ18 −95276742480ρ16 −464803389936ρ14 −412656456960ρ12 + 7449015918528ρ10 + 32947458310656ρ8−457978474586624ρ6 +18919725382656ρ4+ 3101861081088ρ2−19591041024. Moreover, for h≥2we have that λ > 0. It was shown in [10] that, with high probability, XH,n is at least cn for some constant c > 0 that depends only on H. Our result provides a precise limit distribution. Define a brick as a graph obtained from a 3-connected cubic planar graph by removing one edge, so that all vertices have degree 3 expect two vertices uand vthat have degree 2, and such that uand vare distinguishable (as if the edge removed was oriented). Our last result gives the distribution of the number of copies of a given brick. We denote by K− 4the graph obtained from K4by removing one edge. Theorem 9. Let XB,n be the number of copies of a fixed unlabeled brick B, different from K− 4, with b vertices in a random cubic planar graph. Then XB,n is asymptotically normal with moments E[XB,n]∼µn, Var[XB,n]∼λn, where µ=10185312ρ2 P1 ρb aut(B), λ =242688ρ2(P2h+P3) P3 1 ρ2b aut(B)2+µ+µ2, 4 ρis as in Theorem 1, and P1=−(2187ρ10 + 43740ρ8+ 297432ρ6+ 769824ρ4−7293760ρ2+ 139968) >0, P2=−854929626ρ2P1, P3= 880066296 ρ20 + 35202651840 ρ18 + 591404550912 ρ16 + 5407127322624 ρ14 +19994308272243 ρ12 −51726289953708 ρ10 −559899907432200 ρ8−1063749220662816 ρ6 −5760872476783424 ρ4+ 43131140739648 ρ2+ 3604751548416. Moreover, for b≥2we have that λ > 0. The same result holds for B=K− 4with constants µ≈0.004529, λ ≈0.004343. The case when B=K− 4has to be treated separately, since it can appear in two different ways: as a 3-connected core, or as the parallel composition of two loop networks, as explained in the next section. Bricks other than K− 4can only appear as 3-connected cores. We have obtained similar results for parameters that have been studied for several classes of planar and related classes of graphs [7]. We can show that the number of cut vertices, the number of isthmuses (separating edges) and the number of blocks (2-connected components, including isthmuses) are all asymptotically normal with linear expectation and variance. For the sake of brevity we omit the proofs and give only the values of the constants for the expectation and variance: Parameter µ λ Cut vertices 0.001877 0.003793 Isthmuses 0.000939 0.000950 Blocks 0.001878 0.003796 2 Preliminaries In this section we collect a number of analytic and combinatorial results that are needed in the sequel. Analytic combinatorics. We use the elements of analytic combinatorics as in [5]. To a class Gof labeled graphs, we associate the exponential generating function G(x) = Pn≥0gnxn/n!, where gnis the number of graphs in Gwith nvertices. We define G•as the class of graphs in Gwith a distinguished vertex (that we call the root). By the basic rules of the symbolic method, its generating function is G•(x) = xG0(x). Given a complex number ζ6= 0, a ∆-domain at ζis an open set in the complex plane of the form ∆(R, φ) = {z:|z|< R, z 6=ζ, |arg(z−ζ)|> φ}. A dominant singularity of a complex function is a singularity of the smallest modulus. The basic tool for extracting asymptotic estimates from generating functions is the following (see [5, Corollary VI.1]). Lemma 10 (Transfer Theorem).Assume that f(z)has a unique dominant singularity ρ > 0and is analytic in a ∆-domain at ρ. If fsatisfies, locally around ρ, the estimate f(z)∼ z→ρ(1 −z/ρ)−α, with α6∈ {0,−1,−2, . . . }, then the coefficients of f(z)satisfy [zn]f(z)∼ n→∞ nα−1 Γ(α)ρ−n. 5 If fhas several dominant singularities coming from pure periodicities, then the contributions from each of them must be combined (see [5, IV.6.1]). In our case, the periodicities are due to the fact that cubic graphs have necessarily an even number of vertices and the corresponding generating functions are even. We will locate the (unique) positive dominant singularity ρand will add the contributions from ρand −ρ. All the singularities we will encounter are of square-root type, that is, the expansion of a function at a singularity ρis of the form f(x) = X i≥0 fiXi, X =p1−x/ρ. The singular expansions we encounter are of the form f(z) = f0+f2X2+···+f2kX2k+f2k+1X2k+1 +O(X2k+2), with k= 1 or k= 2. The only non-analytic term is f2k+1X2k+1, and it is from this term that asymptotic estimates are derived using the Transfer Theorem. In order to prove asymptotic normal limit laws, we need a simplified version of the so-called Quasi-powers Theorem (see [5, Theorem IX.8]). Lemma 11 (Quasi-powers Theorem).Let {Xn}n≥1be a sequence of non-negative discrete random variables with probability generating functions pn(u). Assume that, uniformly in a fixed complex neighborhood of u= 1 pn(u) = A(u)∆B(u)n1 + On−1, where A(u), B(u)are analytic at u= 1 and A(1) = B(1) = 1. Assume finally that B(u)satisfies the condition B00(1) + B0(1) −B0(1)26= 0. Then the distribution of Xnis, after standardization, asymptotically normal, and the mean and variance satisfy E[Xn]∼B0(1)n, Var[Xn]∼B00(1) + B0(1) −B0(1)2n. In our applications we will have B(u) = ρ(1)/ρ(u), where ρ(u) will be the dominant singularity (as a function of z) of a bivariate generating function f(z, u). The former expressions then become E[Xn]∼−ρ0(1) ρ(1) n, Var[Xn]∼ −ρ00(1) ρ(1) −ρ0(1) ρ(1) +ρ0(1) ρ(1) 2!n. Planar maps and triangulations. We recall that a planar map is a connected planar multigraph embedded in the plane up to homeomorphism. A map is rooted if one of its edges is distinguished and oriented. In this way a rooted map has a root edge and a root vertex (the tail of the root edge). We define the root face as the face to the right of the directed root edge. A rooted map has no automorphism, in the sense that every vertex, edge and face is distinguishable. From now on all maps are planar and rooted. Since maps are not labeled, the associated generating functions are ordinary. A map is a triangulation if it is 3-connected and every face is a triangle (one can consider more general triangulations having loops and multiple edges but they are not needed in this paper). The dual of a triangulation is a 3-connected cubic map, since 3-connectivity in maps is preserved under duality (a map is 3-connected if it is 3-connected as a graph and it has no multiple edges). Let T(z) be the (ordinary) generating function of 3-connected triangulations together with the map consisting of a triangle, where the variable zmarks the number of vertices minus two. Then, as shown by Tutte [16], T(z) = U(z) (1 −2U(z)) ,(4) where Uis an algebraic function defined by z=U(z)(1 −U(z))3.(5) 6 Equation (5) has a unique solution with positive coefficients, given by U(z) = z+ 3z2+ 15z3+ 91z4+··· Then T(z) = z+z2+ 3z3+ 13z4+··· As shown in [16], the unique singularity of U(and hence of T) is located at τ= 27/256. In particular, U(τ)=1/4, T(τ)=1/8. The singular expansion of U(z) at τis equal to U(z) = 1 4−√6 8Z+1 12Z2−31√6 1728 Z3+37 1296Z4−2093√6 248832 Z5+O(Z6),(6) where Z=p1−z/τ. From Equation (4) we obtain the singular expansion of T(z) at τ T(z) = 1 8−3 16Z2+√6 24 Z3−13 192Z4+35√6 1728 Z5+O(Z6). We also need to consider the family of 4-connected triangulations, which are those not containing a separating triangle (a triangle that is not a face) and having at least 6 vertices. The smallest 4-connected triangulation is the graph of the octahedron. The associated generating function T4(z), where again zmarks vertices minus two, is equal to (see [16]) T4(z) = z+V(z)(V(z)−1)(V(z) + 1)−2−z2,(7) where V(z) is given by z=V(z)(1 −V(z))2. The unique solution with positive coefficients is V(z) = z+ 2z2+ 7z3+ 30z4+. . . , and T4(z) = z4+ 3z5+ 12z6+ 52z7+. . . The unique singularity of T4is at ς= 4/27 and we have V(ς)=1/3, T4(ς)=7/5832. The singular expansion of V(z) at ςis equal to V(z) = 1 3−2√3 9Z+2 27Z2−5√3 243 Z3+16 729Z4−77√3 8748 Z5+O(Z6), Z =p1−z/ς. As before, using (7) we obtain T4(z) = 7 5832 −245 23328Z2+√3 96 Z3−833 93312Z4−√3 864Z5+O(Z6). 7 3-connected cubic planar graphs. Let M(x, y) be the GF of labeled 3-connected cubic planar graphs rooted at a directed edge, where xmarks vertices and ymarks edges. There is a bijection between triangulations and planar 3-connected cubic maps given by duality. Also, by Whitney Theorem, every 3-connected cubic planar graph admits a unique embedding in the plane up to orientation. Using this fact we can express M(x, y) in terms of the generating function T(z) of rooted unlabeled triangulations, where zcounts the number of vertices minus two. The relation is M(x, y) = 1 2T(x2y3)−x2y3.(8) The subtracted term x2y3corresponds to the triangulation consisting of a single triangle. We have M(x, y) = 12 x4 4! y6+ 1080 x6 6! y9+··· The first monomial corresponds to K4(a unique labeling and 12 possible roots) and the second one to the triangular prism (60 ways to label and 18 roots). We will also need the generating function M(x, y) of (unrooted) labeled 3-connected cubic planar graphs, which is obtained by integration. We have M(x, y)=2y∂M(x, y)/∂y, hence M(x, y) = 1 2ZM(x, y) ydy =1 4ZT(x2y3)−x2y3 ydy. We change variables as z=x2y3and are left with the integral 1 12 RT(z)/z dz. We make the further change v=U(z) and, using Equations (4) and (5), we get M(x, y) = 1 12 ZT(z) zdz −z =1 12 Z(1 −2v)(1 −4v) 1−vdv −z =−1 12 4v2+ 2v+ 3 log(1 −v) + z. Hence M(x, y) = −1 12 4U(x2y3)2+ 2U(x2y3) + 3 log(1 −U(x2y3)) + x2y3.(9) Networks. We follow the definitions from [2] but deviate slightly from the notation there. A network is a connected cubic planar multigraph Gwith an ordered pair of adjacent vertices (s, t) such that the graph obtained by removing the edge st is simple. There could be an additional edge between sand twhich is not removed. We notice that st can be a simple edge, a loop or a belong to a double edge. The oriented edge st is the root of the network and s, t are the poles. Given a network H, with root edge st, and a directed edge e=uv of another network G, the replacement of ewith His the network obtained from Gby performing the following operation. Subdivide the edge uv twice producing a path uu0v0v, remove the edge u0v0, and identify u0and v0, respectively, with vertices sand tof H−st. Notice that if Gand Hare cubic and planar, so is the resulting network. A cut vertex in a cubic graph is necessarily incident with one or three isthmuses. For each cut vertex uincident with exactly one isthmus e, we can remove the component containing eand erase the resulting vertex of degree 2 resulting in a cubic graph. We call this operation suppressing the cut vertex u. By classifying the possible situations obtained by removing the edge st, networks fall into five classes, as shown in [2]. For the sake of completeness we offer an alternative proof based on Tutte’s decomposition of 2-connected graphs into 3-connected components [3]. Lemma 12. Let Gbe a network and let st be the root edge. Then Gbelongs to one and only one of the following classes. 8 • L (Loop). The root edge is a loop. • I (Isthmus). The root edge is an isthmus. • S (Series). G−st is connected but is not 2-connected. • P (Parallel). G−st is 2-connected and G−{s, t}is not connected. • H (3-connected). Gis obtained from a 3-connected graph by possibly replacing each non-root edge with a network of types L,S,Por H. Proof. Let Gbe a network with root edge st, and suppose st is neither a loop nor an isthmus, so we are not in the classes Lor I. Consider the 2-connected core Cobtained by suppressing all cut vertices incident with exactly one isthmus. By Tutte’s decomposition into 3-connected components, Cbelongs to either S,P or H. Let now Dbe the class of networks for which the graph resulting from the removal of the root edge remains connected. It is by definition, D=L+S+P+H, where + denotes the disjoint union of classes, and the class Iis excluded since removing the root edge of networks in this class disconnects the graph. Let then L(x), I(x), S(x), P(x), H(x), D(x) be the associated generating functions. The following result, based on simple combinatorial arguments, is shown in [2, Section 3]. Lemma 13. The following equations hold: D=L+S+P+H, L=x2 2(I+D−L), S=D(D−S), I=L2 x2, P=x2D+x2 2D2, H=M(x, 1 + D) 1 + D. (10) Notice that all the functions involved are even, in agreement with the fact that a cubic graph has an even number of vertices. Using the relations D−L=S+P+Hand D−S=L+P+H, the system (10) can be rewritten so that all the functions on the right hand-side have non-negative coefficients when expanded in terms of x, L, I, S, H and D. This is also true for the equation H=M(x, 1 + D)/(1 + D), since M(x, y) is divisible by y. It follows (see [4]) that there is a unique solution of the system with non-negative coefficients, which is the combinatorial solution. Let C(x) be the generating function of connected cubic planar graphs, and C•(x) = xC0(x) that of connected graphs rooted at a vertex. As shown in [2], C•(x) can be expressed in terms of networks as 3C•(x) = D(x) + I(x)−L(x)−x2D(x)−L(x)2.(11) The factor 3 comes from double counting since at every root vertex vwe have 3 possible root edges with v as a tail. The term D(x) + I(x) encodes all types of networks, from which one has to subtract those which are not simple. These are L, where the root edge is a loop, and those where the root edge is a double edge: parallel networks encoded by x2D(x), and series networks encoded by L(x)2. 9 Let now −→ B(x) be the generating function of 2-connected cubic planar graphs rooted at a directed edge. Then −→ B(x) = D(x)−x2D(x). The reason is that from the networks encoded by D(x) we have to exclude the parallel networks with a double edge, that correspond to x2D(x). If now B•is the generating function for 2-connected vertex-rooted cubic graphs, by double counting we have B•(x) = −→ B(x) 3. Applying the Transfer Theorem we obtain for even n n·bn=n![xn]B•(x)∼2(1 −ρ2 b)D3 3·Γ(−3/2) ·n−5/2·ρ−n bn!, and from here the estimate on bnfollows with b=2(1−ρ2 b)D3 3·Γ(−3/2) ≈0.059244. 3.4 Cubic planar multigraphs Similarly to the simple case, we decompose connected cubic planar multigraphs using networks. In this situation we do not demand that removing the edge between the poles gives a simple graph. We also use the same notation for networks as before. The equations are as follows. D=L+S+P+H, L=x2+x2L+x2 2(I+D−L), I=L2 x2, S=D(D−S), P=x2+x2D+x2D2 2, H=M(x, 1 + D) 1 + D. (16) The only differences with the system of equations describing the networks associated with simple graphs are the term x2, in the equation for P, encoding the 3-bond, and the term x2(1 + L), in the equation for L, encoding the cubic multigraph with two vertices and two loops, rooted at a loop and where the non-rooted loop is possibly replaced by a loop-network (see Figure 3). Figure 3: Left is the only cubic multigraph with two vertices and two loops. Right is the same multigraph whose non-rooted loop has been replaced by a loop-network. Using the same arguments as before, one can show that there exists a unique solution with non-negative coefficients of the above system, which is the combinatorial solution. Let C(x) be the generating function of connected cubic planar multigraphs. Due to the presence of multiple edges and loops, there is no direct algebraic relation expressing C•(x) in terms of networks. As in Section 3.2, we need to resort once more to the Dissymmetry Theorem. 16 Proof of Theorem 4. We start by obtaining a single equation for Dfrom the system (16). First, we combine the second and the third equations and solve for Las L= 1 −x2 2−rx4 4+ 1 −x2(D+ 3). Then we have D=D2 1 + D+x2+x2D+x2 2D2+ 1 −x2 2−rx4 4+ 1 −x2(D+ 3) + M(x, 1 + D) 1 + D. A simple manipulation together with (8) gives F(x, D) = (1 + D)rx4 4+ 1 −x2(D+ 3) −Tx2(1 + D)3 2−1=0.(17) We rewrite as Hx, D, T x2(1 + D)3=1 + 1 2Tx2(1 + D)32 −(1 + D)2x4 4+ 1 −x2(D+ 3)= 0, where now His a polynomial. We proceed as in the proofs of Theorems 1 and 3. Equations (17) and x2(1 + D)3=τhave a unique positive solution ρm≈0.250907 and D0=D(ρm)≈0.187679. The minimal polynomial p(x) of D(x) is obtained by elimination and is equal to the one in the statement. We check that ρmis a root of p(x), together with the remaining analytic conditions of Lemma 15. The rest of the proof is a further application of the Dissymmetry Theorem and is very similar to that of Theorem 2 with some small changes. The rooted tree-decompositions are the same, except that we have to update the corresponding classes to encode the 3-bond and the multigraph with two vertices and two loops. Those changes only affect M-nodes and L-nodes. The new equation for the generating function associated to M-nodes is then CM=x2 21 + D+D2 2+D3 6, As for L-nodes, we need to introduce two new types of cut-vertices, those adjacent to a loop or to a double edge (see Figure 4). The equation for the associated generating function becomes CL=L+L2+L(D−L) 2+L3 6x2. Now when the tree is either rooted at an edge or at an oriented edge, we need to consider the new case when two cut-vertices are connected by a double edge (see the multigraph on the right of Figure 4). The corresponding equations are given by CL−L =L2 2x2+L2 2, CL→L =L2 x2+L2. We then apply Theorem 14 and, after a straightforward calculation, obtain C(x) = x2 21 + D+D2 2+D3 6+M(x, 1 + D) + L3 6x2 −1 2log(1 −D+S) + D−S+(D−S)2 2+P(S+H) + HS +P2+H2 2+L2 x2+L2. (18) 17 Figure 4: In white are the two new types of cut-vertices in a multigraph. That are respectively adjacent to a loop (left) and to a double edge (right). The Puiseux expansion at ρmis computed from that of D(x) using the previous expression for C(x) and is of the form C(x) = C0+C2X2+C4X4+C5X5+O(X6). Since we do not have a singular expansion for C•(x) that we can integrate as in the proof of Theorem 2, we need to show directly that C3= 0. Assume for contradiction that C36= 0. Then, by the Transfer Theorem, the ratio between the number of connected cubic planar multigraphs with nvertices and the number of connected networks with nvertices would tend to a constant as ngoes to infinity. Let us define a bad edge as either a double edge or a loop. For n≥4, a vertex of a connected cubic planar multigraph can be adjacent to at most one bad edge. Hence each vertex is adjacent to at least one simple edge, hence there are at least n/2 simple edges. Each time a simple edge of a connected cubic planar multigraph is distinguished and directed, we get a different connected network, hence the number of connected networks with nvertices is at least n/2 times greater than the number of connected cubic planar multigraphs with nvertices, which is a contradiction. We proceed as in the last part of the proof of Theorem 2. We compute C0=C(ρm)≈0.070660 and C5≈ −0.098979, together with the singular expansion of G(x) = exp(C(x)), which is given by G0+G2X2+G4X4+G5X5+O(X6), where G0≈1.073217 and G5≈ −0.106226. Finally, an application of Lemma 10 gives the estimates as claimed. As a corollary, the probability that a random cubic planar multigraph is connected is pm=h0/h ≈0.931778. Remark. We provide here a short explanation for the similarity between equations (1) and (2). Let p1(x2) be the polynomial in (1) and p2(x2) that in (2). After making the change of variables y=x2,p1(y) and p2(y) are obtained, by eliminating, respectively, in the systems of equations H1=1 + 1 2Ty(1 + D)32−(1 + D)2y2 4+ 1 −y(D−1)= 0, y(1 + D)3=τ, H2=1 + 1 2Ty(1 + D)32−(1 + D)2y2 4+ 1 −y(D+ 3)= 0, y(1 + D)3=τ. Now rewrite H1and H2as H1=1 + 1 2Ty(1 + D)32−(1 + D)2y2 4+ 1−2y(1 + D)2−τ, H2=1 + 1 2Ty(1 + D)32−(1 + D)2y2 4+ 1+ 2y(1 + D)2−τ. We deduce from here that p2(y) = p1(−y), which is equivalent to the relation between (1) and (2). 18 3.5 P-recursive sequences A series is D-finite if it satisfies a linear differential equation with polynomial coefficients. It is well-known (see Chapter 6 in [15]) that {fn}is P-recursive if and only if Pfnxn/n! is D-finite. Proof of Theorem 5. We show that in each case the corresponding generating functions are D-finite. Connected and 2-connected graphs. The generating function C0(x) is algebraic, hence it is D-finite [15]. It follows that C(x) is also D-finite. The same argument applies to the generating function B(x) of 2-connected graphs. Arbitrary graphs. We use the same argument as in [14], namely that if C0(x) is algebraic then exp(C(x)) is D-finite. For completeness we briefly recall the proof. Let G(x) = eC(x). One shows by induction that G(i)=Ri(C0, x)G(x), where Riis a rational function in C0and x. Since C0is algebraic, Q(C0, x) is finite dimensional over Q(x), say of dimension k. Hence there are rational functions Si(x) such that Pk i=0 Si(x)Ri(C0, x)=0.It follows that S0(x)G+S1(x)G0+···+Sk(x)G(k)= 0. proving that Gis D-finite. Multigraphs. In this case we cannot apply the previous argument, since there is no direct relation between the generating functions D(x) and C0(x). It follows from Equation (17) that D(x) is algebraic. We use Equation (18) to express G(x) = exp(C(x)) in terms of D(x), and the fact that the exponential of an algebraic function is D-finite, to obtain G(x) = eC(x)=J(x)eM(x,1+D), where J(x) is a D-finite function (notice that the logarithm in (18) cancels with the exponential). We next use the explicit expression (9) and the fact that U(z) is algebraic to conclude that exp(M(x, 1 + D)) is D-finite (again a logarithm cancels). Since the product of D-finite functions is D-finite, we conclude that G(x) is D-finite. 4 Proofs of limit law results: triangles In this section we obtain generating functions encoding triangles in cubic planar graphs and its distribution in random cubic planar graphs. The main idea behind these proofs is that we are able to enrich the network decomposition of graphs in order to encode the number of triangles. More precisely, in order to study the distribution of the number of triangles, we start with 3-connected cubic planar graphs. By duality this amounts to studying vertices of degree 3 in triangulations. The latter problem is solved in Section 4.1. We then use it to count triangles in networks in Section 4.2. In Section 4.3 we perform the singularity analysis of the equations obtained in Section 4.2, and complete the proof of Theorem 7. Finally, as a byproduct of the previous ideas, in Section 4.4 we apply these tools to enumerate planar cubic triangle-free graphs. This does not follow directly from Theorem 7 as one needs to adapt the equations satisfied by the associated generating functions and perform a delicate analysis of singularities. 4.1 Vertices of degree 3 in triangulations In this section we obtain the generating function of triangulations encoding the number of vertices of degree 3. This will be done by enriching the classical decomposition by Tutte of triangulations in terms of 4-connected triangulations [16]. Throughout this section T∗denotes the class of triangulations not reduced to a triangle. The associated generating function is T∗(z) = T(z)−z, where T(z) is as in Equation (4). Additionally z−1T∗(z) counts triangulations (not reduced to a triangle) in terms of internal triangles. Recall that T4(z) is the generating function of 4-connected triangulations, given in (7). In both cases, zencodes the number of vertices minus 19 two. A triangulation A∈ T ∗has a 4-connected core C, obtained by removing the vertices inside maximal separating triangles; the core is either a 4-connected triangulation or is isomorphic to K4. Then Ais obtained by possibly replacing the internal faces of Cwith arbitrary triangulations. This leads to the following equation, linking T∗(z) and T4(z): T∗(z) = T4z1 + z−1T∗(z)2 1 + z−1T∗(z)+z2(1 + z−1T∗(z))3.(19) The first term in the right hand-side is equivalent to Equation (2.6) from [16]; the second one corresponds to the case when the core is K4. Note that here we want to replace with triangulations in T∗instead of T, as replacing a face with a single triangle amounts to doing nothing. This is already encoded by the term 1 in 1 + z−1T∗(z). Our goal is to refine (19) by counting vertices of degree 3. An internal vertex in a triangulation is a vertex not incident with the root face, otherwise it is called external. Let t(z, u) be the generating function of triangulations, where zis as before and uencodes internal vertices of degree 3. In particular, T∗(z) = t(z, 1). Let now T0be the set of triangulations (except K4) in which the degree of the root vertex is equal to 3, and T1those where the degree is greater than 3. Then we have T∗=T0∪T1∪{K4}. Let T0(z, u) and T1(z, u) be the associated generating functions, where unow counts the total number of vertices of degree 3, including the external ones. Then we have T∗(z, u) = T0(z, u) + T1(z, u) + z2u4. In the next lemma we obtain expressions for both T0(z, u) and T1(z, u): Lemma 16. The generating function t=t(z, u)is defined implicitly in terms of T4(z)as t= T4z1 + z−1t2 1 + z−1t+z2(1 + z−1t)3+u−1.(20) In addition, we have T1(z, u) = zut, (21) T0(z, u) = (1 + 2zu −3z)t−z2u. (22) Proof. The first equation follows directly from (19). The only difference comes from the second term associated to K4: when none of the internal faces is replaced with a triangulation, the central vertex has degree 3 and the configuration is encoded as u. When removing the root vertex (and the three adjacent edges) of a triangulation in T1, we obtain a smaller triangulation. The reverse operation is to take a triangulation, draw a vertex on its root face, join it with the three vertices on the external face, and re-root the resulting map. This gives (21). In order to obtain T0we first compute T(z, u). The following equation follows from (20) by analyzing again the case where the core is K4, and taking into account how many internal faces are replaced with triangulations: T∗(z, u) = T4z1 + z−1t2 1 + z−1t+z2(1 + z−1t)3−1−3z−1t+ 3uz−1t+u4. Finally, we use T∗(z, u) = T0(z, u) + T1(z, u) + z2u4, and after a simple computation we get (22). 4.2 Triangles in networks We are now back to labeled graphs and exponential generating functions. In this section the goal is to obtain equations for networks encoding also triangles. Here, variable xmarks vertices and umarks triangles. 20 Di(x, u) is the generating function of non-isthmus networks in which the root edge belongs to exactly i∈ {0,1,2}triangles. (observe that in a cubic graph there is no other possibility). The same convention applies to series, parallel and h-networks. The special case when the 3-connected core of an h-network is K4is encoded in the generating functions Wi. We let E(x, u) be the generating function of networks where triangles incident to the root edge are not counted, that is, E(x, u) = D0+u−1D1+u−2D2. The next two lemmas provide the expressions for the series Di,Si,Pi,Wi,I,Land for H0, H1(H0, H1will be treated separately as they are technically more involved). Lemma 17. The following equations hold: D0=S0+P0+W0+L+H0, D1=S1+P1+W1+H1, D2=P2+W2, I=L2 x2, L=1 2x2(I+E−L) + 1 2x2(u−1) x2(E−L) + ux2L+L2), P0=x2(E−L) + 1 2x2(E−L)2, P1=ux2L(E−L) + u2x2L, P2=1 2u2x2L2, S0=EE−(S0+u−1S1)−u−1S1, S1=uL3+ 2ux2L(E−L)+2u2x2L2, W0=1 2x42(1 + u)E2+ 8E3+ 5E4+E5, W1=1 2x44u2E+ 6uE2+ 2uE3, W2=1 2x4u4+u2E. Proof. Equations for D0, D1and D2are clear, since S2=P2=H2= 0. The equation for Iis the same as in the univariate case. The equation for Lis obtained as follows: from the main term x2 2(I+E−L) we need to consider separately three situations in which a new triangle is created: they are illustrated in Figure 5. The corresponding generating functions are 1 2ux4(E−L), 1 2u2x4Land 1 2ux2L2, hence the term x2 2(u−1) x2(E−L) + x2 2uL +1 2L2. E−L L Figure 5: The three configurations in Lwhere an extra triangle is created. The associated generating functions are respectively 1 2x4u(E−L), 1 2x4u2Land 1 2x2uL2. In the case of parallel networks, when using networks in Lwe create triangles incident with the root edge of the network. The possible cases in P1and P2are illustrated in Figure 6. 21 E−L L LL Figure 6: Contributions of ux2L(E−L) to P1and 1 2x2u2L2to P2. The equation for S1follows by considering the possible cases in which the root edge is incident with a triangles, as described in Figure 7. L L L L E−L L L Figure 7: Contributions to S1: the corresponding generating functions are uL3,ux2L(E−L), u2x2L2. For the second and third configuration there are two possibilities. The equation for S0is obtained as in the univariate case, by subtracting the term u−1S1. Finally, the equations for W0, W1and W2are obtained by considering all cases where K4is the core of the h-network. Observe that the different coefficients that appear in the expressions of W0,W1and W2are due to symmetries of K4. The previous system can be easily rewritten as we have done earlier (see the paragraph after the statement of Lemma 13) so that the right-hand terms have non-negative coefficients, and thus admits a unique nonnegative power series as solution. The following lemma gives the expression for H0and H1in terms of T0(z) and T1(z). Joint with the previous lemma, this completes the system of equations encoding triangles: Lemma 18. Let t(x, u)be the generating function defined by Equation (20). Then H0and H1are given by the following expressions: H1(x, u) = 1 2x2u·tx2(1 + E)3,1 + u−1 (1 + E)3, H0(x, u) = 1 2tx2(1 + E)3,1 + u−1 (1 + E)31−x2(E−2u+ 3) 1 + E−1 2x4(1 + E)2((1 + E)3+u−1)). Proof. We say that a triangle in a network is external if it is incident with the root edge. The edges of an external triangle that are not the root edge are called special. We denote by M0and M1the family of edge-rooted 3-connected cubic planar graphs (except K4) without external triangles and with one external triangle, respectively, and let M0(x, y, u), M1(x, y, u) be the 22 associated generating functions, where x,yand umark vertices, edges and triangles, respectively. Similarly to Equation (8) we have that M0(x, y, u) = 1 2T0(x2y3, u), M1(x, y, u) = 1 2T1(x2y3, u). Let m1(x, y, u) = M1(x, y, u)/(uy3), where now ucounts non-external triangles, and ycounts the number of edges minus three (we do not count the root edge and the special edges). A network in H1is obtained from a graph Gin M1in which we replace edges (except the root edge) with networks, and where the three edges of the external triangle of Gare not replaced (recall that the external triangle is the only triangle incident with the root edge). Observe that triangles in Gare isolated (because Gis 3-connected), hence there are no triangles sharing edges and the previous replacement can be made. In particular, the term u+ 3E+ 3E2+E3= (1 + E)3+u−1 encodes the substitution of networks on 3-sets of edges defining triangles (except the external triangle and the corresponding edges, which are not substituted). This translates into the equation H1(x, u) = u·m1x, 1 + E, 1 + u−1 (1 + E)3. The expression for H1is obtained by writing first m1in terms of T1, and then writing T1in terms of t using (21). Let us now consider a network in H0. It can be obtained in two different ways: either from a core without an external triangle, or from a core with an external triangle in which some special edges are replaced with a non-empty network. Using a similar encoding argument as before we arrive at H0(x, u) = M0x, 1 + E, 1 + u−1 (1 + E)3 1 + E+ (2E+E2)·m1x, 1 + E, 1 + u−1 (1 + E)3, where the factor 2E+E2in the second summand corresponds to the substitution of networks on the pair of special edges. Using the expressions of M0and m1in terms of T0and T1, and Equations (21) and (22), after simplification we get the expression for H0, as claimed. We conclude this section by expressing the generating function of vertex-rooted graphs C•(x, u), where xmarks vertices and umarks triangles, in terms of networks: 3C•(x, u) = D0+D1+D2+I−L−x2(D0+D1+D2)−L2.(23) This equation is obtained by considering all networks (which is counted by D0+D1+D2+I) and removing those where the root edge is either a loop or a multiple edge (term L+x2(D0+D1+D2) + L2). This difference is equal to the generating function for networks with only simple edges, which by double counting it is equal to 3C•(x, u). 4.3 Singularity analysis and proof of the main result After obtaining the system of equations in Lemmas 17, 18 and Equation (23) we proceed to analyze it. In order to apply Lemma 11 for proving a Gaussian limit law, our first task is to find the dominant singularities (of xas a function of u, for uclose to 1) of the function C(x, u) counting triangles in connected cubic planar graphs. We start finding the singularities for 3-connected graphs. Later, we use the results from the previous section to obtain the singularities of C(x, u). Singularities of 3-connected graphs. Recall that the generating function t(z, u) encodes triangulations, where zis the number of vertices minus 2 uencodes internal vertices of degree 3. Its expression in terms of T4(z) is given in Lemma 16. The next result gives the dominant singularities of the generating function of 3-connected graphs: 23 Lemma 19. Let t(z, u)be as in Lemma 16. Let ube a fixed complex number with |u−1|< ε, where ε > 0 is sufficiently small. Then the point z0=z0(u)where t(z, u)ceases to be analytic is the solution of the following equation: z0(1 + (u−1)z0)2=27 256.(24) Moreover, at the critical point (z0, u)we have the relation: (z0(u−1) + 1)t(z0, u) = 1 8−z0(1 + (u−1)z0).(25) Proof. The unique singularity of T4(z) is at 4/27 (see Section 2). Hence, for uin a small neighborhood of 1, the only possible source of singularities for t(z, u) in Equation (20) comes from the singularity of T4(z), giving the relation z0(1 + z−1 0t(z0, u))2= 4/27. We also know that T4(4/27) = 7/5832, hence at the singular point we have t(z0, u) = 7/5832 1 + z−1 0t(z0, u)+z2 0((1 + z−1 0t(z0, u))3+u−1). Eliminating t(z0, u) from the previous two equations gives (24), and an elementary computation gives Equation (25). Singuarities of connected graphs. We have seen in the proof of Theorem 1 that the singularities of the generating function D(x) of cubic networks come from the singularities of T(z). Variable umarks triangles, which is a linear parameter. Hence, by continuity and for usufficiently close to 1, this also holds for the bivariate generating functions of networks. For a given uclose to 1, we let ρ(u) be the dominant singularity of the function E(x, u). Notice that, because of (23), it is also that of C(x, u); there is no cancellation because there is none for u= 1. Remark also that ρ(1) is equal to the constant ρ≈0.3192246062 from Theorem 1. In order to determine ρ(u), we find two equations satisfied by u,ρ(u) and E(ρ(u), u). Then eliminating Ewill give us ρ(u) implicitly in terms of u. Once we have access to ρ(u), an application of Lemma 11 will give the asymptotic normal law with the corresponding moments. Lemma 20. For fixed uclose to 1, E(x, u)admits two dominant singularities given by the two curves ±ρ(u) and such that ρ(1) = ρ. As x→ρ(u)−, we have locally E(x, u) = E0(u) + E2(u)1−x ρ(u)+E3(u)1−x ρ(u)3/2 +. . . , where E0(u),E2(u)and E3(u)are analytic functions. Let x=ρ(u)be the positive dominant singularity of E(x, u)and let E=E(x, u). Then the following two equations hold: x2(1 + E)31+(u−1)x22=27 256,(26) 256(1 + (u−1)x2)2(1 + E)A= 256x2(1 + (u−1)x2)3(E3+ 3E2+ 3E) + B, (27) where A=(u2x4−2ux4+x4−x2−2)2−4x2(1 + (u−1)x2)2E1/2, B= 256(u−1)3x8+ 768(u−1)2x6+ 192(u−1)(3u+ 1)x4+ (1066u−810)x2+ 517. 24 Proof. Similarly to the univariate case, we show that the only source of singularities for E=E(x, u) comes from t=t(x2(1 + E)3,1+(u−1)/(1 + E)3). Furthermore, the singular behaviour of ttransfers directly to that of E. In our case, both statements can be deduced directly from a slightly modified version of [4, Theorem 2.31], in which we now require that |PE(t(τ), E(ρ), ρ, 1)| 6= 0 when u= 1, and that t(z, u) admits a 3/2 singular behaviour locally around u= 1 and z=τ(u), where the τ(u) is the solution of z0in (24). By elimination from the equations in Lemmas 17 and 18, we obtain a polynomial equation P(t, E, x, u) = 0, which has degree 6 in E(it is too big to be displayed here). From there, we check that |PE(t(τ), E(ρ), ρ, 1)| ≈ 7.1818705965. For the second condition, we eliminate V(z) and T4(z) from (7), (20) and z=V(z)(1 −V(z))2to obtain an irreducible polynomial equation Q(t(z, u), z, u) = 0. Using Newton’s polygon algorithm on Q(as it is square-free), we compute the Puiseux expansion of t(z, u) locally around z=τ(u), which is of the form: t(z, u) = t0(u) + t2(u)1−z τ(u)+t3(u)1−z τ(u)3/2 +. . . , where t0(u), t2(u) and t3(u) are analytic functions. Let us finally consider the expressions for H0and H1in Lemma 18. Since the singularities of Emust come from the substitution in t(z, u), the point (z1, u1) = (x2(1 + E)3,1 + (u−1)/(1 + E)3) must be a singular point of t(z, u). The singularities of t(z, u) are given by the relation (24), hence we have: z1(1 + (u1−1)z1)2=x2(1 + E)31 + 1 + (u−1) (1 + E)3−1x2(1 + E)32 =27 256,(28) which is precisely (26). Let us now deduce Equation (27). We first need the evaluation of t(z, u) at the point (z1, u1). This follows directly from (25) and (26) and gives: t(z1, u1) = 32(u−1)x2+ 5 256(1 + (u−1)x2)2. Notice that all the functions, involved in both Lemmas 17 and 18, can be written in terms of E, L and the variables xand u. Solving for Land substituting provides a second equation on E,x, and u. The solution for Lis given by: L(x, u) = x2+ 2 −(u−1)2x4−A 2(1 + (u−1)x2),(29) where Ais an in the statement. It remains finally to write D0,D1,D2in terms of E,L,xand u, then to replace Lwith the expression in (29), and to perform an elementary computation to obtain (27). Proof of Theorem 7. One can eliminate Efrom the system composed of Equations (26) and (27) to obtain a single polynomial equation p(x, u) = 0 in xand u, whose smallest positive solution in xis the singularity ρ(u) of E(x, u). The polynomial phas degree 40 in x2and is too large to be displayed here. We then differentiate p(ρ(u), u) with respect to uand compute the following values (using Maple): ρ0(1) = −0.0389371919, ρ00(1) = 0.0229417852. Alternatively, we can differentiate (26) and (27) and solve the corresponding system involving ρ(1) and ρ0(1), and similarly for ρ00(1). In order to apply Lemma 11, we need to show that E(x, u) is analytic in a ∆-domain at x=ρ(u). By Lemma 20, E(x, u) has an expansion in powers of p1−x/ρ(u) for unear 1. It is hence analytic in a sufficiently small neighborhood of ρ(u) sliced along the ray [ρ(u),∞]. Consider now uin a small neighborhood Uof 1, and take u0∈Ureal with ρ(u0)>|ρ(u)|. By the same argument as in the proof of the univariate case (Theorem 1), E(x, u) is analytic in a ∆-domain at u0. It follows that E(x, u) is analytic in a ∆-domain at ρ(u). Thus, for uin a small neighborhood of 1, we get the estimate [xn]E(x, u) = c(u)·n−5/2ρ(u)−n1 + O(n−1). By a direct application of Lemma 11, we are able to first compute the values ρ0(1) and ρ00(1), then the values of µand λ, as claimed. This concludes the proof of Theorem 7. 25