Mireille Bousquet-Mélou
email: mireille.bousquet@labri.fr

Kerstin Weller
email: weller@stats.ox.ac.uk

ASYMPTOTIC PROPERTIES OF SOME MINOR-CLOSED CLASSES OF GRAPHS

Let A be a minor-closed class of labelled graphs, and let Gn be a random graph sampled uniformly from the set of n-vertex graphs of A. When n is large, what is the probability that Gn is connected? How many components does it have? How large is its biggest component? Thanks to the work of McDiarmid and his collaborators, these questions are now solved when all excluded minors are 2-connected.

Using exact enumeration, we study a collection of classes A excluding non-2-connected minors, and show that their asymptotic behaviour may be rather different from the 2-connected case. This behaviour largely depends on the nature of dominant singularity of the generating function C(z) that counts connected graphs of A. We classify our examples accordingly, thus taking a first step towards a classification of minor-closed classes of graphs. Furthermore, we investigate a parameter that has not received any attention in this context yet: the size of the root component. It follows non-gaussian limit laws (beta and gamma), and clearly deserves a systematic investigation.

Introduction

We consider simple graphs on the vertex set {1, . . . , n}. A set of graphs is a class if it is closed under isomorphisms. A class of graphs A is minor-closed if any minor 1 of a graph of A is in A. To each such class one can associate its set E of excluded minors: an (unlabelled) graph is excluded if its labelled versions do not belong to A, but the labelled versions of each of its proper minors belong to A. A remarkable result of Robertson and Seymour states that E is always finite [START_REF] Robertson | Graph minors I-XX[END_REF]. We say that the graphs of A avoid the graphs of E. We refer to [START_REF] Bernardi | Growth constants of minor-closed classes of graphs[END_REF] for a study of the possible growth rates of minor-closed classes.

For a minor-closed class A, we study the asymptotic properties of a random graph G n taken uniformly in A n , the set of graphs of A having n vertices: what is the probability p n that G n is connected? More generally, what is the number N n of connected components? What is the size S n of the root component, that is, the component containing 1? Or the size L n of the largest component?

Thanks to the work of McDiarmid and his collaborators, a lot is known if all excluded graphs are 2-connected: then p n converges to a positive constant (at least 1/ √ e), N n converges in law to a Poisson distribution, n -S n and n -L n converge in law to the same discrete distribution. Details are given in Section 3.

If some excluded minors are not 2-connected, the properties of G n may be rather different (imagine we exclude the one edge graph...). This paper takes a preliminary step towards a classification of the possible behaviours by presenting an organized catalogue of examples.

For each class A that we study, we first determine the generating functions C(z) and A(z) that count connected and general graphs of A, respectively. The minors that we exclude are always connected 2 , which implies that A is decomposable in the sense of Kolchin [START_REF] Kolchin | Random graphs[END_REF]: a graph belongs to A if and only if all its connected components belong to A. This implies that A(z) = exp(C(z)).

Figure 1. A zoo of graphs. Top: the 3-star, the triangle K 3 , the bowtie and the diamond. Bottom: A caterpillar and the 4-spoon (a k-spoon consists of a "handle" formed of k edges, to which a triangle is attached).

We then derive asymptotic results from the values of these series. They are illustrated throughout the paper by pictures of large random graphs, generated using Boltzmann samplers [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]. Under a Boltzmann distribution, two graphs of A having the same size always have the same probability. The most difficult class we study is that of graphs avoiding the bowtie (shown in Figure 1).

Our results make extensive use of the techniques of Flajolet and Sedgewick's book [START_REF] Flajolet | Analytic combinatorics[END_REF]: symbolic combinatorics, singularity analysis, saddle point method, and their application to the derivation of limit laws. We recall a few basic principles in Section 2. We also need and prove two general results of independent interest related to the saddle point method or, more precisely, to Hayman admissibility (Theorems 17 and 18).

Our results are summarized in Table 1. A first principle seems to emerge: the more rapidly C(z) diverges at its radius of convergence ρ, the more components G n has, and the smaller they are. In particular, when C(ρ) converges, then the properties of G n are qualitatively the same as in the 2-connected case (for which C(ρ) always converges [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF]), except that the limit of p n can be arbitrarily small. When C(ρ) diverges, a whole variety of behaviours can be observed, depending on the nature of the singularity of C(z) at ρ: the probability p n tends always to 0, but at various speeds; the number N n of components goes to infinity at various speeds (but is invariably gaussian after normalization); the size S n of the root component and the size L n of the largest component follow, after normalization, non-gaussian limit laws: for instance, a Gamma or Beta law for S n , and for L n a Gumbel law or the first component of a Poisson-Dirichlet distribution. Cases where C(z) converges, or diverges at most logarithmically, are addressed using singularity analysis (Sections 4 and 5), while those in which C(z) diverges faster (in practise, with an algebraic singularity) are addressed with the saddle point method (Sections 7 to 10). Section 6 gathers general results on the saddle point method and Hayman admissibility.

Let us conclude with a few words on the size of the root component. It appears that this parameter, which can be defined for any exponential family of objects, has not been studied systematically yet, and follows interesting (i.e., non-gaussian!) continuous limit laws, after normalization. In an independent paper [START_REF] Bousquet-Mélou | Size of the root component in exponential structures[END_REF], we perform such a systematic study, in the spirit of what Bell et al. [START_REF] Bell | Asymptotics for the probability of connectedness and the distribution of number of components[END_REF] or Gourdon [START_REF] Gourdon | Largest component in random combinatorial structures[END_REF] did for the number of components or the largest component, respectively. This project is also reminiscent of the study of the 2-connected component containing the root vertex in a planar map, which also leads to a non-gaussian continuous limit law, namely an Airy distribution [START_REF] Banderier | Random maps, coalescing saddles, singularity analysis, and Airy phenomena[END_REF]. This distribution is also related to the size of the largest 2-and 3-connected components in various classes of graphs [START_REF] Giménez | Graph classes with given 3-connected components: Asymptotic enumeration and random graphs[END_REF].

"Generatingfunctionology" for graphs

Let E be a finite set of (unlabelled) connected graphs that forms an antichain for the minor order (this means that no graph of E is a minor of another one). Let A be the set of labelled graphs that do not contain any element of E as a minor. We denote by A n the subset of A formed of graphs having n vertices (or size n) and by a n the cardinality of A n . The associated exponential generating function is A(z) = n≥0 a n z n /n!. We use similar notation (c n and C(z))

for the subset C of A consisting of (non-empty) connected graphs. Since the excluded minors are connected, A is decomposable, and

A(z) = exp(C(z)).
Several refinements of this series are of interest, for instance the generating function that keeps track of the number of (connected) components as well:

A(z, u) = G∈A u c(G) z |G| |G|! ,
where |G| is the size of G and c(G) the number of its components. Of course, A(z, u) = exp(uC(z)). 1. Summary of the results: for each quantity N n , S n and L n , we give the order of the expected value (up to a multiplicative constant, except in the last line where constants are exact) and a description (name or density) of the limit law. The examples are ordered according to the speed of divergence of C(z) near its radius ρ. Spoons are defined in Figure 1. As we get lower in the table, the graphs have more components, of a smaller size. The symbol PD (1) (1/4) stands for the first component of a Poisson-Dirichlet distribution of parameter 1/4.

Excluded

We denote by G n a uniform random graph of A n , and by N n the number of its components. Clearly,

P(N n = i) = [z n ]C(z) i i![z n ]A(z) , (1)
where [z n ]F (z) denotes the coefficient of z n in the series F (z). The ith factorial moment of N n is We believe it to be of independent interest (Theorem 18).

E(N n (N n -1) • • • (N n -i + 1)) = [z n ] ∂ i A ∂u i (z, 1) [z n ]A(z) = [z n ]C(z) i A(z) [z n ]A(z
We also study the size c 1 of the root component, which is the component containing the vertex 1. We define accordingly

Ā(z, v) = G∈A,G =∅ v c1(G)-1 z |G|-1 (|G| -1)! .
The choice of |G| -1 instead of |G| simplifies slightly some calculations. Note that Ā(z, 1) = A (z) = C (z)A(z). Denoting by S n the size of the root component in G n , we have

P(S n = k) = c k a n-k n-1 k-1 a n = k n c k k! a n-k (n -k)! n! a n . (2)
Equivalently, the series Ā(z, v) is given by

Ā(z, v) = C (zv)A(z). (3)
The ith factorial moment of S n -1 is

E((S n -1) • • • (S n -i)) = [z n-1 ] ∂ i Ā ∂v i (z, 1) [z n-1 ] Ā(z, 1) = [z n-i-1 ]C (i+1) (z)A(z) n[z n ]A(z) . (4)
Surprisingly, this parameter has not been studied before. Our examples give rise to non-gaussian limit laws (Beta or Gamma, cf. Propositions 14 or 25). In fact, the form (3) of the generating function shows that this parameter is bound to give rise to interesting limit laws, as both the location and nature of the singularity change as v moves from 1-ε to 1+ε. Using the terminology of Flajolet and Sedgewick [19, Sec. IX.11], a phase transition occurs. We are currently working on a systematic study of this parameter in exponential structures [START_REF] Bousquet-Mélou | Size of the root component in exponential structures[END_REF].

Finally, we denote by C [k] (z) the generating function of connected graphs of A of size less than k:

C [k] (z) = k-1 n=1 c n z n n! ,
and study, for some classes of graphs, the size L n of the largest component. We have

P(L n < k) = [z n ] exp(C [k] (z)) [z n ]A(z) . (5)
We use in this paper two main methods for studying the asymptotic behaviour of a sequence (a n ) n given by its generating function A(z). The first one is the singularity analysis of [START_REF] Flajolet | Analytic combinatorics[END_REF]Chap. VI]. Let us describe briefly how it applies, for the readers who would not be familiar with it. Assume that A(z) has a unique singularity of minimal modulus (also called dominant) at its radius of convergence ρ, and is analytic in a ∆-domain, that is, a domain of the form {z : |z| < r, z = ρ and | Arg(z -ρ)| > φ} for some r > ρ and φ ∈ (0, π/2). Assume finally that, as z approaches ρ in this domain,

A(z) = S(z) + O(R(z)),
where S(z) and R(z) are functions belonging to the simple algebraic-logarithmic scale of [START_REF] Flajolet | Analytic combinatorics[END_REF]Sec. VI.2]. Then one can transfer the above singular estimates for the series into asymptotic estimates for the coefficients:

[z n ]A(z) = [z n ]S(z) + O([z n ]R(z)).
Since S and R are simple functions, the asymptotic behaviour of their coefficients is well known, and the estimate of [z n ]A(z) is thus explicit. We use singularity analysis in Sections 3 to 5. The second method we use is the saddle point method. In Section 6 we recall how to apply it, and then use it in Sections 7 to 10.

When dealing directly with sequences rather than generating functions, a useful notion will be that of smoothness: the sequence (f n ) n≥0 is smooth if f n-1 /f n converges as n grows. The limit is then the radius of convergence of the series n f n z n .

Classes defined by 2-connected excluded minors

We assume in this section that at least one minor is excluded, and that all excluded minors are 2-connected. This includes the classes of forests, series-parallel graphs, outer-planar graphs, planar graphs... Many results are known in this case. We recall briefly some of them, and state a new (but easy) result dealing with the size of the root component. The general picture is that the class A shares many properties with the class of forests.

Proposition 1 (The number of graphs -when excluded minors are 2-connected). The generating functions C(z) and A(z) = e C(z) are finite at their (positive) radius of convergence ρ. Moreover, the sequence (a n /n!) n is smooth.

The probability that G n is connected tends to 1/A(ρ), which is clearly in (0, 1). In fact, this limit is also larger than or equal to 1/ √ e. The latter value is reached when A is the class of forests.

The fact that ρ is positive is due to Norine et al. [START_REF] Norine | Proper minor-closed families are small[END_REF], and holds for any proper minor-closed class. The next results are due to McDiarmid [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF] (see also the earlier papers [START_REF] Mcdiarmid | Random planar graphs[END_REF][START_REF] Mcdiarmid | Random graphs from planar and other addable classes[END_REF]). The fact that 1/A(ρ) ≥ 1/ √ e, or equivalently, that C(ρ) ≤ 1/2, was conjectured in [START_REF] Mcdiarmid | Random graphs from planar and other addable classes[END_REF], and then proved independently in [START_REF] Berry | Connectivity for bridge-addable monotone graph classes[END_REF] and [START_REF] Kang | On the connectivity of random graphs from addable classes[END_REF].

Example 2. A basic, but important example is that of forests, illustrated in Figure 2. We have in this case

C(z) = T (z) - T (z) 2 2 ,
where T (z) = ze T (z) counts rooted trees (see for instance [19, p. 132]). The series T , C and A = e C have radius of convergence ρ = 1/e, with the following singular expansions at this point:

T (z) = 1 - √ 2(1 -ze) 1/2 + 2 3 (1 -ze) -11 √ 2 36 (1 -ze) 3/2 +O((1 -ze) 2 ), C(z) = 1 2 -(1 -ze) + 2 √ 2 3 (1 -ze) 3/2 +O((1 -ze) 2 ), A(z) = √ e - √ e(1 -ze) + √ e 2 √ 2 3 (1 -ze) 3/2 +O((1 -ze) 2 ). (6)
The singularity analysis of [19, Chap. VI] applies: the three series are analytic in a ∆-domain, and their coefficients satisfy

t n ∼ n! e n √ 2πn 3/2 , c n ∼ n! e n √ 2πn 5/2
, and a n ∼ √ e c n . We will also consider rooted trees of height less than k (where by convention the tree consisting of a single vertex has height 0). Let T k (z) denote their generating function. Then T 1 (z) = z and for k ≥ 1,

T k+1 (z) = ze T k (z) .
Note that T k (z) is entire.

Note. When all excluded minors are 2-connected, C(ρ) always converges, but the nature of the singularity of C(z) at ρ depends on the class: it is for instance (1 -z/ρ) 3/2 for forests (and more generally, for subcritical classes [START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF]), but (1 -z/ρ) 5/2 for planar graphs. We refer to [START_REF] Giménez | Graph classes with given 3-connected components: Asymptotic enumeration and random graphs[END_REF] for a more detailed discussion that applies to classes that exclude 3-connected minors.

Proposition 3 (Number of components -when excluded minors are 2-connected). The mean of N n satisfies:

E(N n ) ∼ 1 + C(ρ)
and the random variable N n -1 converges in law to a Poisson distribution of parameter C(ρ). That is, as n → ∞,

P(N n = i + 1) → C(ρ) i i!e C(ρ) . (7)
We refer to [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF]Cor. 1.6] for a proof. The largest component is known to contain almost all vertices, and it is not hard to prove that the same holds for the root component. In fact, the tails of the random variables S n and L n are related by the following simple result. Lemma 4. For any class of graphs A, and k < n/2,

P(S n = n -k) = n -k n P(L n = n -k).
Proof. Let us denote by B n the (lexicographically first) biggest component of G n . Its size is thus L n . We have, for n > 2k,

P(S n = n -k) = P(S n = n -k and 1 ∈ B n ) + P(S n = n -k and 1 ∈ B n ) = P(L n = n -k and 1 ∈ B n ) + P(S n = n -k and 1 ∈ B n ) = P(1 ∈ B n |L n = n -k)P(L n = n -k) + P(S n = n -k and 1 ∈ B n ) = n -k n P(L n = n -k).
Indeed, there cannot be two components of size n -k or more. This implies that P(S n = n -k and 1 ∈ B n ) = 0.

Proposition 5 (The root component and the largest component -when excluded minors are 2-connected). The random variables n-S n and n-L n both converge to a discrete limit distribution X given by

P(X = k) = 1 A(ρ) a k ρ k k! .
Proof. By Lemma 4, the two statements are equivalent. The L n result has been proved by McDiarmid [26,Cor. 1.6].

We give an independent proof (of the S n result), as we will recycle its ingredients later for certain classes of graphs that avoid non-2-connected minors. Let k ≥ 0 be fixed. By [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF],

P(S n = n -k) = c n-k a k n-1 k a n = a k k! c n-k a n-k (n -1)!a n-k (n -k -1)!a n .
By Proposition 1, the term c n-k /a n-k , which is the probability that a graph of size n -k is connected, converges to 1/A(ρ). Moreover, the sequence a n /n! is smooth, so that (n-1)!a n-k

(n-k-1)!an converges to ρ k . The result follows.

A more precise result is actually available. Let us call fragment the union of the components that differ from the biggest component B n . Then McDiarmid describes the limit law of the fragment, not only of his size [START_REF] Mcdiarmid | Random graphs from a minor-closed class[END_REF]Thm. 1.5]: the probability that the fragment is isomorphic to a given unlabelled graph H of size k is

1 A(ρ) ρ k aut(H) ,
where aut(H) is the number of automorphisms of H.

When trees dominate: C(z) converges at ρ

Let A be a decomposable class of graphs (for instance, a class defined by excluding connected minors), satisfying the following conditions:

(1) A includes all trees, (2) the generating function D(z) that counts the connected graphs of A that are not trees has radius of convergence (strictly) larger than 1/e (which is the radius of trees). We then say that A is dominated by trees. Some examples are presented below. In this case, the properties that hold for forests (Section 3) still hold, except that the probability c n /a n that G n is connected tends to a limit that is now at most 1/ √ e. We will see that this limit can become arbitrarily small. Proposition 6 (The number of graphs -when trees dominate). Let T (z) be the generating function of rooted trees, given by T (z) = ze T (z) . Write the generating function of connected graphs in the class A as

C(z) = T (z) - T (z) 2 2 + D(z).

The generating function of graphs of

A is A(z) = e C(z) . As n → ∞, c n ∼ n! e n √ 2πn 5/2
and a n ∼ A(1/e)c n .

In particular, the probability that G n is connected tends to 1/A(1/e) = e -1/2-D(1/e) as n → ∞.

Proof. As in Example 2, we use singularity analysis [START_REF] Flajolet | Analytic combinatorics[END_REF]Chap. VI]. By assumption, D(z) has radius of convergence larger than 1/e, and the singular behaviour of C(z) is that of unrooted trees. More precisely, it follows from (6) that, as z approaches 1/e,

C(z) = 1/2 + D(1/e) -(1 -ze)(1 + D (1/e)/e) + 2 √ 2 3 (1 -ze) 3/2 + O((1 -ze) 2 ),
this expansion being valid in a ∆-domain. This gives the estimate of c n via singularity analysis.

For the series A, we find

A(z) = e 1/2+D(1/e) 1 -(1 -ze)(1 + D (1/e)/e) + 2 √ 2 3 (1 -ze) 3/2 + O((1 -ze) 2 ) ,
and the estimate of a n follows.

Proposition 7 (Number of components -when trees dominate). The mean of N n satisfies:

E(N n ) ∼ 1 + C(1/e
) and N n -1 converges in law to a Poisson distribution of parameter C(1/e) (see [START_REF] Bernasconi | On the degree sequences of random outerplanar and seriesparallel graphs[END_REF]).

Proof. We can start from (1) and apply singularity analysis. Or we can apply a ready-to-use result of Bell et al. [4,Thm. 2], which uses the facts (proved in Proposition 6) that the sequences nc n-1 /c n and c n /a n converge.

Proposition 8 (Size of components -when trees dominate). The random variable n-S n converges to a discrete limit distribution X given by

P(X = k) = 1 A(1/e) a k e -k k! ,
where a k and A(z) are given in Proposition 6. The same holds for n -L n .

Proof. The two ingredients used in the proof of Proposition 5 to establish the limit law of n -S n (namely, smoothness of a n /n! and convergence of c n /a n ), still hold here (see Proposition 6). Lemma 4 gives then the law of n -L n .

We now present a collection of classes dominated by trees.

Proposition 9. Let k ≥ 1. Let A be a decomposable class of graphs that includes all trees, and such that all graphs of A avoid the k-spoon (shown in Figure 1). Then A is dominated by trees, and the results of Propositions 6, 7 and 8 hold.

Proof. Clearly, it suffices to prove this proposition when A is exactly the class of graphs avoiding the k-spoon, which we henceforth assume. We partition the set C of connected graphs of A into three subsets: the set C 0 of trees, counted by C 0 = T -T 2 /2 with T ≡ T (z), the set C 1 of unicyclic graphs (counted by C 1 ), and finally the set C 2 containing graphs with at least two cycles (counted by C 2 ). Hence C = T -T 2 /2+C 1 +C 2 . We will prove that C 1 has radius of convergence (strictly) larger than 1/e, and that C 2 is entire.

A unicyclic graph belongs to C if and only if all trees attached to its unique cycle have height less than k. The generating function of cycles is given by: Hence, the basic rules of the symbolic method of [19, Chap. II] give:

Cyc(z) = 1 2 n≥3 z n n = 1 2 log 1 1 -z -z - z 2 2 . ( 8
) v 0 v v j v i P v j P v v 0 v i Q v 0 v P v 0 v P v b v a R (a) (c) (b) (d) Q v a+1 Q P Q P2 P1
C 1 (z) = Cyc(T k ) = 1 2 log 1 1 -T k (z) -T k (z) - T k (z) 2 2 , (9)
where T k counts rooted trees of height less than k and is given in Example 2. Recall from this example that T (z) equals 1 at its unique dominant singularity 1/e. Also, T k (z) < T (z) for all z ∈ [0, 1/e] since T k counts fewer trees than T . In particular, T k (1/e) < 1 and C 1 (z) has radius of convergence larger than 1/e. We now want to prove that C 2 is entire. The (2)-core of a connected graph H is the (possibly empty) unique maximal subgraph of minimum degree 2. It can be obtained from H by deleting recursively all vertices of degree 0 or 1 (or, in a non-recursive fashion, all dangling trees of H). By extension, we call core any connected graph of minimum degree 2. Let C2 denote the set of cores having several cycles and avoiding the k-spoon, and C2 the associated generating function. The inequality C 2 (z) ≤ C2 (T k (z)) holds, coefficient by coefficient, because the core of a graph of C 2 has several cycles and avoids the k-spoon. Since T k is entire, it suffices to prove that C2 is entire. It follows from [START_REF] Bernardi | Growth constants of minor-closed classes of graphs[END_REF]Thm. 3.1] that it suffices to prove that no graph G of C2 contains a path of length 3k -1. So let P = (v 0 , v 1 , . . . , v ) be a path of maximal length in G, and assume that ≥ 3k -1. We will prove that G contains the k-spoon as a minor. Since P is maximal and G is a core, there exist v i and v j , with i ≥ 2 and j ≤ -2, such that the edges {v 0 , v i } and {v j , v } belong to G.

If i = or j = 0, let P be the cycle of G formed of P and the edge {v 0 , v }. Let Q be another cycle of G. If Q contains at most one vertex of P (Figure 3(a)), we find an -spoon by deleting one edge of P , contracting Q into a 3-cycle and one of the paths joining P to Q into a point. If Q contains at least two vertices v a and v b of P , with a < b (Figure 3(b)), we may assume that Q consists of the edges {v a , v a+1 }, . . . , {v b-1 , v b } and of a path Q that only meets P at v a and v b . Let R denote the cycle formed of the path Q and the path (v b , v b+1 , . . . , v , v 0 , . . . , v a }. Then we obtain a p-spoon, with p ≥ 3k/2 -1 ≥ k, by contracting the shortest of the cycles Q and R into a 3-cycle and deleting an edge ending at v a from the other.

Assume now that i < and j > 0. Suppose first that i ≤ j (Figure 3(c)). By symmetry, we may assume that the cycle P1 = (v 0 , . . . , v i ) is shorter than (or equal in length to) the cycle P2 = (v j , . . . , v ). In particular, i ≤ /2. Contract P1 into a 3-cycle, and remove the edge {v j , v } from P2 : this gives a p-spoon with p = -i ≥ /2 ≥ k. Assume now that j < i (Figure 3(d)). Consider the three following paths joining v i and v j :

(v i , v i-1 , . . . , v j ), (v i , v 0 , v 1 , . . . , v j ) and (v i , v i+1 , . . . , v , v j ).
Since the sum of the lengths of these paths is + 2 ≥ 3k + 1, one of them, say (v i , v 0 , v 1 , . . . , v j ), has length at least k + 1. That is, j ≥ k. Delete from this path the edge {v i , v 0 }, and contract the cycle formed by the other two paths into a 3-cycle: this gives a j-spoon, with j ≥ k.

The simplest non-trivial class of graphs satisfying the conditions of Proposition 9 consists of graphs avoiding the 1-spoon. By specializing to k = 1 the proof of that proposition, we find C 1 = Cyc(z) and C 2 = 0 (since no core having several cycles avoids the 2-path). Hence

C(z) = T (z) - T (z) 2 2 + 1 2 log 1 1 -z -z - z 2 2 .
More generally, consider the class A (k) of graphs avoiding the k-spoon, but also the diamond and the bowtie (both shown in Figure 1): excluding the latter two graphs means that no graph of C can have several cycles, so that C 2 = 0. Hence the proof of Proposition 9 immediately gives the following result.

Proposition 10 (No diamond, bowtie or k-spoon). Let k ≥ 1. Let T (z) be the generating function of rooted trees, given by T (z) = ze T (z) , and let T k (z) be the generating function of rooted trees of height less than k, given in Example 2.

Let A (k) be the class of graphs avoiding the diamond, the bowtie and the k-spoon. The generating function of connected graphs of

A (k) is C (k) (z) = T (z) - T (z) 2 2 + D (k) (z)
where

D (k) (z) = 1 2 log 1 1 -T k (z) -T k (z) - T k (z) 2 2 .
The class A (k) is dominated by trees, and the results of Propositions 6, 7 and 8 hold. In particular, the probability that a random graph of

A (k)
n is connected tends to e -C (k) (1/e) as n → ∞. Since T k (1/e) tends to T (1/e) = 1 as k increases, this limit probability tends to 0.

A random graph of A (k)

n is shown in Figure 4 for k = 20 and n = 541. We have also determined the generating function of graphs that avoid the 2-spoon.

Proposition 11 (No 2-spoon). Let T (z) be the generating function of rooted trees, given by T (z) = ze T (z) . The generating function of connected graphs avoiding the 2-spoon is

C(z) = T (z) - T (z) 2 2 + D(z)
where

D(z) = 1 2 log 1 1 -ze z -ze z - z 2 e 2z 2 + z 4 4! + z 2 e 2z e z -1 -z - z 2 4 .
The class of graphs avoiding the 2-spoon is dominated by trees, and the results of Propositions 6, 7 and 8 apply.

Proof. We first follow the proof of Proposition 9: we write

C = T -T 2 /2 + C 1 + C 2 ,
where C 1 is given by ( 9) with T k = T 2 = ze z , and C 2 counts connected graphs having several cycles and avoiding the 2-spoon. Note that C 1 is the first term in the above expression of D(z). Let us now focus on C 2 . In Section 10 below, we study the class of graphs that avoid the bowtie, and in particular describe the cores of this class (Proposition 31). Since the bowtie contains the 2-spoon as a minor, graphs that avoid the 2-spoon avoid the bowtie as well. Hence we will first determine which cores of Proposition 31 have several cycles and avoid the 2-spoon, and then check which of their vertices can be replaced by a small tree (that is, a tree of height 1) without creating a 2-spoon.

Clearly, the cores of Proposition 31 that have several cycles are those of Figures 16, 17 and 18. Among the cores of Figure 16, only K 4 avoids the 2-spoon. Moreover, none of its vertices can be replaced by a non-trivial tree. This gives the term z 4 /4! in D(z). Among the cores of Figures 17 and18, only the ones drawn on the left-hand sides avoid the 2-spoon. In these cores, only the two vertices of degree at least 3 can be replaced by a small tree. The resulting graphs are shown in Figure 5 and give together the contribution

1 2 (ze z ) 2 (e z -1 -z) + 1 2 (ze z ) 2 e z -1 -z - z 2 2
(again an application of the symbolic method of [19, Chap. II]). The proposition follows.

. . . at least two vertices . . .

at least three vertices

Excluding the diamond and the bowtie: a logarithmic singularity

Let A be the class of graphs avoiding the diamond and the bowtie (both shown in Figure 1). These are the graphs whose components have at most one cycle (Figure 6). They were studied a long time ago by Rényi [START_REF] Rényi | On connected graphs[END_REF] and Wright [START_REF] Wright | The number of connected sparsely edged graphs[END_REF], and the following result has now become a routine exercise. Proposition 12 (The number of graphs avoiding a diamond and a bowtie). Let T (z) be the generating function of rooted trees, defined by T (z) = ze T (z) . The generating function of connected graphs of A is

C(z) = T (z) 2 - 3T (z) 2 4 + 1 2 log 1 1 -T (z)
.

The generating function of graphs of

A is A(z) = e C(z) . As n → ∞, c n ∼ n! e n 4n and a n ∼ n! 1 (2e) 1/4 Γ(1/4) e n n 3/4 . ( 10
)
In particular, the probability that G n is connected tends to 0 at speed n -1/4 as n → ∞.

Proof. The expression of C(z) is obtained by taking the limit k → ∞ in Proposition 10. We now estimate c n and a n via singularity analysis [START_REF] Flajolet | Analytic combinatorics[END_REF]Sect. VI.4]. Recall from Example 2 that T (z) has a unique dominant singularity, at z = 1/e, with a singular expansion (6) valid in a ∆-domain. Thus 1/e is also the unique dominant singularity of C(z) and A(z), and we have, in a ∆-domain,

C(z) ∼ 1 4 log 1 1 -ze and A(z) ∼ 1 (2e) 1/4 (1 -ez) 1/4 . ( 11
)
The asymptotic estimates of c n and a n follow.

Proposition 13 (Number of components -no bowtie nor diamond). The mean and variance of N n satisfy:

E(N n ) ∼ log n 4 , V(N n ) ∼ log n 4 ,
and the random variable Nn-log n/4 √ log n/4

converges in law to a standard normal distribution.

Proof. Using (6), the estimate (11) can be refined into

C(z) = 1 4 log 1 1 -ze + λ + O( √ 1 -ze), ( 12
)
where λ is a constant, and the proposition is a direct application of [19, Prop. IX.14, p. 670].

The number of connected components is about 1/4 log n. However, the size of the root component is found to be of order n. More precisely, we have the following result.

Proposition 14 (Size of the root component -no bowtie nor diamond). The normalized variable S n /n converges in distribution to a beta law of parameters α = 1, β = 1/4, with density (1 -x) -3/4 /4 on [0, 1]. In fact, a local limit law holds: for x ∈ (0, 1) and k = xn ,

n P(S n = k) → 1 4 (1 -x) -3/4 .
The convergence of moments holds as well: for i ≥ 0,

E(S i n ) ∼ Γ(5/4)i! Γ(i + 5/4) n i .
Proof. Recall that the existence of a local limit law implies the existence of a global one [START_REF] Billingsley | Convergence of probability measures[END_REF]Thm. 3.3]. Thus it suffices to prove the local limit law. But this is easy, starting from the rightmost expression in (2), and using [START_REF] Bousquet-Mélou | Size of the root component in exponential structures[END_REF].

For the moments, let us start from (4). Our first task is to obtain an estimate of C (i+1) (z) near 1/e. Combining ( 12) and [19, Thm. VI.8, p. 419] gives, for i ≥ 1,

C (i+1) (z) ∼ i! 4 e 1 -ze i+1 .
We multiply this by the estimate [START_REF] Canfield | Central and local limit theorems for the coefficients of polynomials of binomial type[END_REF] of A(z), apply singularity analysis, and finally use [START_REF] Bousquet-Mélou | Size of the root component in exponential structures[END_REF] to obtain the asymptotic behaviour of the ith moment of S n . Since these moments characterize the above beta distribution, we conclude [19, Thm. C.2] that S n /n converges in law to this distribution. We conclude with the law of the size of the largest component, which we derive from general results dealing with components of logarithmic structures [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF]. The following proposition is illustrated by Figure 7.

Proposition 15 (Size of the largest component -no bowtie nor diamond). The normalized variable L n /n converges in law to the first component of a Poisson-Dirichlet distribution of parameter 1/4: for x ∈ (0, 1),

P(L n < xn) → ρ(1/x),
where ρ : R + → [0, 1] is the unique continuous function such that ρ(x) = 1 for x ∈ [0, 1] and for x > 1,

x 1/4 ρ (x) + 1 4 (x -1) -3/4 ρ(x -1) = 0.
The function ρ is infinitely differentiable, except at integer points.

A local limit law also holds: for x ∈ (0, 1) and 1/x ∈ N,

n P(L n = xn ) → (1 -x) -3/4 4x ρ 1 -x x .
Proof of [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF]. We then apply Theorem 6.12 and Theorem 6.8 of [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF]: this gives the convergence in law of L n and the local limit law. The distribution function of the limit law is given by [2, Eq. (5.29)], and the differential equation satisfied by ρ follows from [2, Eq. (4.23)].

Remark. If we push further the singular expansion [START_REF] Corless | On the Lambert W function[END_REF] of C(z), we find a subdominant term in √ 1 -ze, but its influence is never felt in the asymptotics results. We would obtain the same results (with possibly different constants) for any C(z) having a purely logarithmic singularity.

Hayman admissibility and extensions

Our next examples (Sections 7 to 10) deal with examples where C(z) diverges at ρ with an algebraic singularity. This results in A(z) diverging rapidly at ρ. We then estimate a n using the saddle point method -more precisely, with a black box that applies to Hayman Theorem 16. Let A(z) be a power series with real coefficients and radius of convergence ρ ∈ (0, ∞]. Assume that A(r) is positive for r ∈ (R, ρ), for some R ∈ (0, ρ). Let

a(r) = r A (r) A(r) and b(r) = r A (r) A(r) + r 2 A (r) A(r) -r 2 A (r) A(r) 2 .
Assume that the following three properties hold:

H 1 [Capture condition] lim r→ρ a(r) = lim r→ρ b(r) = +∞.
H 2 [Locality condition] For some function θ 0 (r) defined over (R, ρ), and satisfying 0 < θ 0 (r) < π, one has, as r → ρ,

sup |θ|≤θ0(r) A(re iθ ) A(r) e -iθa(r)+θ 2 b(r)/2 -1 → 0. H 3 [Decay condition] As r → ρ, sup |θ|∈[θ0(r),π) A(re iθ ) A(r) b(r) → 0.
We say that A(z) is Hayman admissible. Then the nth coefficient of A(z) satisfies, as n → ∞, Conditions H 2 and H 3 are usually stated in terms of uniform equivalence as r → ρ, but we find the above formulation more explicit.

[z n ]A(z) ∼ A(ζ) ζ n 2πb(ζ) (13
The set of H-admissible series has several useful closure properties [19, Thm. VIII.5, p. 568]. Here is one that we were not able to find in the literature.

Theorem 17. Let A(z) = F (z)G(z) where F (z) and G(z) are power series with real coefficients and radii of convergence 0 < ρ F < ρ G ≤ ∞. Assume that F (z) has non-negative coefficients and is Hayman-admissible, and that G(ρ F ) > 0. Then A(z) is Hayman-admissible.

Proof. Let us first prove that the radius of convergence ρ of A(z) is ρ F . Clearly, ρ ≥ ρ F . Now, suppose ρ > ρ F . Then A(z) is analytic at ρ F . Together with G(ρ F ) > 0 this implies that F (z) = A(z)/G(z) has an analytic continuation at ρ F , which is impossible by Pringsheim's Theorem (since F (z) has non-negative coefficients) [19, Thm. IV.6, p. 240]. Note also that A(r) is positive on an interval of the form [R, ρ) (by continuity of G). Let us now check the three conditions of Theorem 16. We have

a(r) = a F (r) + a G (r), b(r) = b F (r) + b G (r), with a F (r) = r F (r) F (r) and b F (r) = r F (r) F (r) + r 2 F (r) F (r) -r 2 F (r) F (r) 2 ,
and similarly for a G and b G .

H 1 The capture condition holds for A since it holds for F , given that G(ρ) > 0 and ρ G > ρ.

H 2 Choose θ 0 (r) = θ F 0 (r) where θ F 0 (r) is a function for which F (z) satisfies H 2 and H 3 . We have A(re iθ ) A(r) • e -ia(r)θ+θ 2 b(r)/2 = F (re iθ ) F (r) e -ia F (r)θ+θ 2 b F (r)/2 G(re iθ ) G(r) • e -ia G (r)θ+θ 2 b 2 G (r)/2 . (14)
By assumption, F satisfies the locality condition: hence

F (re iθ ) F (r) • e -ia F (r)θ+b F (r)θ 2 /2 = 1 + M (r, θ) (15)
where sup

|θ|≤θ0(r) |M (r, θ)| → 0 (16)
as r → ρ. For r ∈ [R, ρ) and |θ| ≤ θ 0 (r), let us expand log G(re iθ ) in powers of θ:

log G(re iθ ) = log G(r) + iθa G (r) - θ 2 2 b G (r) + θ 3 S(r, θ)
where S(r, θ) is bounded uniformly in a neighborhood of (ρ, 0). We can assume that θ 0 (r) → 0 as r → ρ (see [22, Eq. (12.1)]). Thus

G(re iθ ) G(r) • e -ia G (r)θ+θ 2 b G (r)/2 = e θ 3 S(r,θ) = 1 + N (r, θ) (17)
where sup

|θ|≤θ0(r) |N (r, θ)| → 0 (18)
as r → ρ. Putting together Eqs. ( 14) to [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF], we obtain that A(z) satisfies H 2 . H 3 We have:

A(re iθ ) A(r) b(r) = F (re iθ )G(re iθ ) F (r)G(r) b F (r) + b G (r) ≤ F (re iθ ) F (r) 2b F (r) • G(re iθ ) G(r) for r close to ρ, because b F (r) → ∞ as r → ρ while b G (r) is bounded around ρ.
Also, since G has radius larger than ρ and G(ρ) > 0, the term G(re iθ )/G(r) is uniformly bounded in a neighborhood of the circle of radius ρ. Since by assumption, F (z) satisfies H 3 , this shows that A(z) satisfies it as well.

We will also need a uniform version of Hayman-admissibility for series of the form e uC(z) .

Theorem 18. Let C(z) be a power series with non-negative coefficients and radius of convergence ρ. Assume that A(z) = e C(z) has radius ρ and is Hayman-admissible. Define

b(r) = rC (r) + r 2 C (r) and V (r) = C(r) - (rC (r)) 2 rC (r) + r 2 C (r)
.

Assume that, as r → ρ,

V (r) → +∞, (19)
C(r) V (r) 3/2 → 0, (20) b
(r) 1/ √ V (r) = O(1). ( 21
)
Then A(z, u) := e uC(z) satisfies Conditions (1)-( 6), ( 8) and (9) of [16, Def. 1]. If N n is a sequence of random variables such that

P(N n = i) = [z n ]C(z) i i![z n ]e C(z) ,
then the mean and variance of N n satisfy:

E(N n ) ∼ C(ζ n ), V(N n ) ∼ V (ζ n ), (22)
where ζ n ≡ ζ is the unique solution in (0, ρ) of the saddle point equation ζC (ζ) = n. Moreover, the normalized version of N n converges in law to a standard normal distribution:

N n -E(N n ) V(N n )
→ N (0, 1).

Remark. The set of series covered by this theorem seem to have only a small intersection with the set of series (of the form g(z)F (uf (z))) covered by Section 4 of [START_REF] Drmota | Marking in combinatorial constructions: generating functions and limiting distributions[END_REF].

Proof. With the notation of [16, Def. 1], we have

a(r, u) = c(r, u) = ruC (r) = ua(r), b(r, u) = ruC (r) + r 2 uC (r) = ub(r), ā(r, u) = b(r, u) = uC(r), ε(r) = K V (r) (23)
c(r, 1)(u -1) + O(c(r, 1)(u -1) 2 )) uniformly for r ∈ (0, ρ) and u ∈ [1 -ε(r), 1 + ε(r)].
Since a(r, u) = a(r, 1) + c(r, 1)(u -1), this condition obviously holds. We are thus left with Conditions (2) and (3), which are uniform versions (in u) of the locality and decay conditions H 2 and H 3 defining Hayman admissibility. They can be stated as follows.

H 2 [Uniform locality condition] There exists R ∈ (0, ρ) such that for any K > 0, there exists a function δ(r) defined over (R, ρ), and satisfying 0 < δ(r) < π, such that, as r → ρ,

sup |θ|≤δ(r), |u-1|≤ε(r)
A(re iθ , u) A(r, u) e -iθa(r,u)+θ 2 b(r,u)/2 -1 → 0. A(re iθ , u) A(r, u) b(r, u) → 0.

We begin with H 2 . Since A(z) is H-admissible, let θ 0 (r) be a function for which H 2 (and H 3 ) holds:

A(re iθ ) A(r) e -iθa(r)+θ 2 b(r)/2 = 1 + M (r, θ)

where

M (r) := sup |θ|≤θ0(r) |M (r, θ)| tends to 0 as r → ρ. Then, for u ∈ [1 -ε(r), 1 + ε(r)], A(re iθ , u) A(r, u) e -iθa(r,u)+θ 2 b(r,u)/2 = exp u C(re iθ ) -C(r) -iθa(r) + θ 2 b(r)/2 = (1 + M (r, θ)) u
where we have taken the principal determination of log to define

(1 + M (r, θ)) u = exp(u log(1 + M (r, θ))) (because M (r, θ) is close to 0). Thus sup |θ|≤θ 0 (r) |u-1|≤ε(r) A(re iθ , u) A(r, u) e -iθa(r,u)+θ 2 b(r,u)/2 -1 = sup |θ|≤θ 0 (r) |u-1|≤ε(r) |(1 + M (r, θ)) u -1| ≤ (1 + ε(r))M (r) + O (1 + ε(r))M (r) 2 ,
and this upper bound tends to 0 as r → ρ. This proves H 2 with δ(r) = θ 0 (r).

We finally address H 3 . Since A(z) satisfies the decay condition H 3 , the quantity

N (r, θ) := A(re iθ ) A(r) b(r) satisfies sup |θ|∈[θ0(r),π] |N (r, θ)| → 0 (24)
as r → ρ. We have, for u

∈ [1 -ε(r), 1 + ε(r)], A(re iθ , u) A(r, u) b(r, u) = |N (r, θ)| u b(r) 1-u√ u ≤ |N (r, θ)| 1+ε(r) b(r) ε(r) 1 + ε(r),
and this tends to 0 uniformly for |θ| ∈ [θ 0 (r), π] thanks to ( 24), ( 23), ( 19) and ( 21). As explained in [START_REF] Drmota | Extended admissible functions and Gaussian limiting distributions[END_REF] just below Theorem 2, these eight conditions give the estimates ( 22) of E(N n ) and V(N n ) and imply the existence of a gaussian limit law.

We finish this section with a simple but useful result of products of series [5, Thm. 2].

Proposition 19. Let F (z) =

n f n z n and G(z) = n g n z n be power series with radii of convergence 0 ≤ ρ F < ρ G ≤ ∞, respectively. Suppose that G(ρ F ) = 0 and the sequence

(f n ) n≥0 is smooth. Then [z n ]F (z)G(z) ∼ G(ρ F )f n .

Graphs with bounded components: C(z) is a polynomial

Let C be a finite class of connected graphs, and let A be the class of graphs with connected components in C. Note that A is minor-closed if and only if C itself is minor-closed. This is the case for instance if C is the class of graphs of size at most k. In general, we denote by k the size of the largest graphs of C. We assume that C(z) is aperiodic.

We begin with the enumeration of the graphs of A. The following proposition is a bit more precise than the standard result on exponentials of polynomials [19, Cor. VIII.2, p. 568], since it makes explicit the behaviour of the term b(ζ) occurring in the saddle point estimate [START_REF] Darrasse | Biased Boltzmann samplers and generation of extended linear languages with shuffle[END_REF].

Proposition 20 (The number of graphs with small components). Write the generating function of graphs of C as

C(z) = k i=0 c i i! z i . ( 25
)
The generating function of graphs of A is A(z) = e C(z) . As n → ∞,

a n ∼ n! 1 √ 2πkn A(ζ) ζ n (26)
where ζ ≡ ζ n is defined by ζC (ζ) = n and satisfies

ζ = αn 1/k + β + O(n -1/k ) (27)
with

α = (k -1)! c k 1/k and β = - (k -1)c k-1 kc k . ( 28
)
The probability that G n is connected is of course zero as soon as n > k.

Proof.

ζ = i≥i0 α i n -i/k , (29)
for some integer i 0 and complex coefficients α i . Using Newton's polygon method [19, p. 499], one easily finds i 0 = -1 and the values (28) of the first two coefficients. Since b(r) = rC (r) + r 2 C (r) has leading term kc k r k /(k -1)!, the first order expansion of b

(ζ) reads b(ζ) = kn + O(n (k-1)/k ),
and the asymptotic behaviour of a n follows.

Again, the following proposition is more precise than the statement found, for instance, in [11, Thm. I], because our estimates of E(N n ) and V(N n ) are explicit. Note in particular that E(N n ) ∼ n/k suggests that most components have maximal size k.

Proposition 21 (Number of components -Graphs with small components). Assume that the coefficient c k-1 in (25) is non-zero. The mean and variance of N n satisfy:

E(N n ) ∼ n k , V(N n ) ∼ c k-1 k • k! α k-1 n (k-1)/k ,
where α is given by [START_REF] Mcdiarmid | Random planar graphs[END_REF], and the random variable Nn-E(Nn) √

V(Nn)
converges in law to a standard normal distribution.

Proof. We apply [11, Thm. I] (we can also apply Theorem 18 if k > 3). Still denoting the saddle point by ζ ≡ ζ n , we just have to find estimates of

µ n = C(ζ) and σ 2 n = C(ζ) - (ζC (ζ)) 2 ζC (ζ) + ζ 2 C (ζ)
.

Given [START_REF] Mcdiarmid | On graphs with few disjoint t-star minors[END_REF], we obtain

µ n = n k + c k-1 k! α k-1 n (k-1)/k + O(n (k-2)/k ), ζ 2 C (ζ) = (k -1)n - c k-1 (k -2)! α k-1 n (k-1)/k + O(n (k-2)/k ),
and finally

σ 2 n = µ n - n 2 n + ζ 2 C (ζ) = c k-1 k • k! α k-1 n (k-1)/k + O(n (k-2)/k ).
Since there are approximately n/k components, one expects the size S n of the root component to be k. This is indeed the case, as illustrated in Figure 8.

Proposition 22 (Size of the components -Graphs with small components). The distribution of S n converges to a Dirac law at k:

P(S n = j) → 1 if j = k, 0 otherwise.
The same holds for the size L n of the largest component.

Proof. We combine the second formulation in (2) with the estimate (26) of a n . This gives Observe that most components have size 3, so that the root component is very likely to have size 3.

P(S n = j) ∼ 1 n c j (j -1)! A(ζ n-j ) A(ζ n ) ζ n n ζ n-j n-j .
Clearly, it suffices to prove that this probability tends to 0 if j < k. So let us assume j < k. Since ζ n is increasing with n, it suffices to prove that

1 n ζ n n ζ n-j n-j → 0. (30)
Recall from ( 27) and ( 29) that ζ n admits an expansion of the form

ζ n = αn 1/k + k-1 i=0 n -i/k β i + O (1/n) .
This gives, for some constants γ i ,

n log ζ n = n k log n + n log α + k i=1 γ i n 1-i/k + O(n -1/k ).
Hence

(n -j) log ζ n-j = n -j k log n + (n -j) log α + k i=1 γ i n 1-i/k + O(1).
This gives

n log ζ n -(n -j) log ζ n-j -log n = j -k k log n + O(1),
and (30) follows, since j < k. Since L n ≥ S n , the behaviour of L n is then clear.

Forests of paths or caterpillars: a simple pole in C(z)

Let A be a decomposable class (for instance defined by excluding connected minors), with generating function A(z) = exp(C(z)). Assume that

C(z) = α 1 -z/ρ + D(z), (31)
where D has radius of convergence larger than ρ. Of course, we assume α > 0.

Proposition 23 (The number of graphs -when C has a simple pole). Assume that the above conditions hold, and let β = D(ρ). As n → ∞,

c n ∼ n! αρ -n and a n ∼ n! α 1/4 e α/2+β 2 √ πn 3/4 ρ -n e 2 √ αn . ( 32
)
In particular, the probability that G n is connected tends to 0 at speed n 3/4 e -2 √ αn .

Proof. The asymptotic behaviour of c n follows from [19, Thm. IV.10, p. 258]. To obtain the asymptotic behaviour of a n , we first write

A(z) = F (z)G(z) with F (z) = exp α 1 -z/ρ and G(z) = e D(z) , (33)
where G(z) has radius of convergence larger than ρ. To estimate the coefficients of F , we apply the ready-to-use results of Macintyre and Wilson [25, Eqs. ( 10)-( 14)], according to which, for α, γ > 0 and a non-negative integer k,

[z n ] log 1 1 -z k 1 (1 -z) γ exp α 1 -z ∼ α 1/4 e α/2 2 √ πn 3/4 n α γ/2 log n 2 k e 2 √ αn . ( 34
)
This gives

f n := [z n ]F (z) ∼ α 1/4 e α/2 2 √ πn 3/4 ρ -n e 2 √ αn .
This shows in particular that f n-1 /f n tends to ρ as n → ∞, so that we can apply Proposition 19 to [START_REF] Stanley | Enumerative combinatorics[END_REF] and conclude.

Proposition 24 (Number of components -when C has a simple pole). Assume (31) holds. The mean and variance of N n satisfy:

E(N n ) ∼ √ αn, V(N n ) ∼ √ αn/2,
and the random variable Nn- √ αn (αn/4) 1/4 converges in law to a standard normal distribution. Proof. We apply Theorem 18. The H-admissibility of A(z) follows from Theorem 17, using [START_REF] Stanley | Enumerative combinatorics[END_REF] and the H-admissibility of exp(α/(1 -z/ρ)) (see [19, p. 562]). Conditions ( 19)-( 21) are then readily checked, using

C(r) ∼ α 1 -r/ρ , b(r) ∼ 2α (1 -r/ρ) 3 and V (r) ∼ α 2(1 -r/ρ) .
We thus conclude that the normalized version of N n converges in law to a standard normal distribution. For the asymptotic estimates of E(N n ) and V(N n ), we use [START_REF] Hayman | A generalisation of Stirling's formula[END_REF] with the saddle point estimate

ζ n = ρ -ρ α/n + O(1/n).
Since there are approximately √ n components, one may expect the size S n of the root component to be of the order of √ n.

Proposition 25 (Size of the root component -when C has a simple pole). The normalized variable S n / n/α converges in distribution to a Gamma(2, 1) law of density xe -x on [0, ∞). In fact, a local limit law holds: for x > 0 and k = x n/α ,

n/α P(S n = k) → xe -x .
The convergence of moments holds as well: for i ≥ 0,

E(S i n ) ∼ (i + 1)!(n/α) i/2 . Proof.
For the local (and hence global) limit law, we simply combine ( 2) with [START_REF] Robertson | Graph minors I-XX[END_REF]. For the moments, we start from (4), with

C (i+1) (z) = α(i + 1)! ρ i+1 (1 -z/ρ) i+2 + D (i+1) (z).
Let us first observe that [START_REF] Robertson | Graph minors I-XX[END_REF] implies that a n /n! is smooth. We can thus apply Proposition 19 to the product D (i+1) (z)A(z), which gives We thus have

[z n-i-1 ]D (i+1) (z)A(z) n[z n ]A(z) ∼ D (i+1) (ρ) n a n-i-1 (n -i -1)! n! a n ∼ D (i+1) (ρ) n ρ i → 0.
a n (n -1)! E(S i n ) ∼ [z n-i-1 ] α(i + 1)! ρ i+1 (1 -z/ρ) i+2 exp α 1 -z/ρ + D(z) . (35)
Now [START_REF] Wright | The number of connected sparsely edged graphs[END_REF] gives

[z n-i-1 ] α(i + 1)! ρ i+1 (1 -z/ρ) i+2 exp α 1 -z/ρ ∼ α(i + 1)! α 1/4 e α/2 2 √ πn 3/4 n α i/2+1 ρ -n e 2 √ αn . ( 36
)
In particular, this sequence of coefficients is smooth. Hence by Proposition 19, the asymptotic behaviour of (35) only differs from (36) by a factor e β , where β = D(ρ). Combined with [START_REF] Robertson | Graph minors I-XX[END_REF], this gives the limiting ith moment of S n . Since these moments characterize the above Gamma distribution, we can conclude [19, Thm. C.2] that S n / n/α converges in law to this distribution.

We now present two classes for which C(z) has a simple isolated pole (Figure 9): forests of paths, and forests of caterpillars (a caterpillar is a tree made of a simple path to which leaves are attached; see Figure 1). In forests of paths, the excluded minors are the triangle K 3 and the 3-star. The fact that N n converges in probability to n/2 for this class was stated in [26, p. 587]. For forests of caterpillars, the excluded minors are K 3 and the tree shown in Table 1 (6th line). This class is also considered in [START_REF] Bernardi | Growth constants of minor-closed classes of graphs[END_REF]. It is also the class of graphs of pathwidth 1.

Proposition 26 (Forests of paths or caterpillars). The generating functions of paths and of caterpillars are respectively

C p (z) = z(2 -z) 2(1 -z) and C c (z) = z 2 (e z -1) 2 2(1 -ze z ) + ze z - z 2 2 . ( 37
)
For both series, Condition Proof. The expression of C p (z) is straightforward. One can also write

C p (z) = 1 2(1 -z) + z -1 2 ,
which gives D p (1) = 0. Let us now focus on caterpillars. Let us call star a tree in which all vertices, except maybe one, have degree 1. By a rooted star we mean a star with a marked vertex of maximum degree: hence the root has degree 0 for a star with 1 vertex, 1 for a star with 2 vertices, and at least 2 otherwise. Clearly, there are n rooted stars on n labelled vertices, so that their generating function is

S • (z) = n≥1 z n (n -1)! = ze z .
The generating function of (unrooted) stars is

S(z) = S • (z) - z 2 2 = ze z - z 2
2 (because all stars have only one rooting, except the star on 2 vertices which has two). Now a caterpillar is either a star, or is a (non-oriented) chain of at least two rooted stars, the first and last having at least 2 vertices each. This gives

C(z) = S(z) + (S • (z) -z) 2 2(1 -S • (z)) ,
which is equivalent to the right-hand side of (37).

The series C c (z) is meromorphic on C, with a unique dominant pole at ρ, and its behaviour around this point is easily found using a local expansion of ze z at ρ:

C c (z) = α 1 -z/ρ + β + O (1 -z/ρ) ,
with α and β as in (38).

For forests of paths, we have also obtained the limit law of the size L n of the largest component. It is significantly larger than the root component (

√ n log n instead of √ n).
Proposition 27 (Size of the largest component -forests of paths). In forests of paths, the (normalized) size of the largest component converges in law to a Gumbel distribution: for x ∈ R and as n → ∞,

P L n -n/2 log n n/2 < x → exp - e -x/2 √ 2 .
Proof. We start from [START_REF] Bender | Asymptotic methods in enumeration[END_REF], where k = n/2 (log n + x) (39) and the generating function of paths of size less than k is:

C [k] (z) = z 2 + z -z k 2(1 -z) . ( 40
)
Using a saddle point approach for integrals [19, p. 552], we will find an estimate of

[z n ] exp(C [k] (z)) = 1 2iπ Cr exp(C [k] (z)) dz z n+1 , (41)
where the integration contour is any circle C r of center 0 and radius r < 1.

Let us first introduce some notation: we denote C [k] (z) by K(z), the integrand in (41) by F , and its logarithm by f :

K(z) = C [k] (z), F (z) = exp(K(z)) z n+1 , f (z) = K(z) -(n + 1) log z.
We choose the radius r ≡ r n that satisfies the saddle point equation

F (r) = 0, or equivalently f (r) = 0 or rK (r) = n + 1.
Note that rK (r) increases from 0 to ∞ as r grows from 0 to 1, so that the solution of this equation is unique and simple to approximate via bootstrapping. We find:

r = 1 - 1 √ 2n + e -x/2 4 √ 2 log n n + O 1 n . (42)
Gaussian approximation. Let θ 0 ∈ (0, π). By expanding the function g : θ → f (re iθ ) in the neighbourhood of θ = 0, we find, for |θ| ≤ θ 0 :

f (re iθ ) -f (r) + θ 2 r 2 f (r)/2 ≤ θ 3 0 6 sup |α|≤θ0 g (3) (α) , (43)
with

g (3) (α) = -ire iα f (re iα ) -3ir 2 e 2iα f (re iα ) -ir 3 e 3iα f (re iα ) ≤ K (r) + n + 1 r + 3K (r) + 3 n + 1 r 2 + K (r) + 2
n + 1 r 3 . By combining the expression (40) of K(z) = C [k] (z) and the saddle point estimate (42), we find that K (r) = (n + 1)/r ∼ n, that K (r) ∼ 2 √ 2n 3/2 and finally that K (r) ∼ 12n 2 . This term dominates the above bound on |g (3) (α)|. Hence, if

θ 0 ≡ θ 0 (n) = o(n -2/3 ), (44)
we find, by taking the exponential of (43),

F (re iθ ) ∼ F (r)e -θ 2 r 2 f (r)/2 , uniformly in |θ| ≤ θ 0 .
Completion of the Gaussian integral. We split the integral (41) into two parts, depending on whether |θ| ≤ θ 0 or |θ| ≥ θ 0 . The first part is

θ0 -θ0 F (re iθ ) re iθ dθ 2π ∼ rF (r) 2π θ0 -θ0
e -θ 2 r 2 f (r)/2 e iθ dθ.

As argued above,

r 2 f (r) ∼ K (r) ∼ 2 √ 2n 3/2 . Hence, if we choose θ 0 ≡ θ 0 (n) such that θ 2 0 n 3/2 → ∞ (which is compatible with (44), for instance if θ 0 = n -5/7 , (45)
which we henceforth assume), we obtain θ0 -θ0

F (re iθ ) re iθ dθ 2π ∼ F (r) 2π f (r) θ0r √ f (r) -θ0r √ f (r) e -α 2 /2 e iα/(r √ f (r)) dα ∼ F (r) 2π f (r) R e -α 2 /2 dα ∼ F (r) 2πf (r)
∼ e 1/4 e √ 2n 2 1/4 2 √ πn 3/4 exp - e -x/2 √ 2 (46)
by ( 42).

The second part of the integral can be neglected. The second part of the integral (41) is θ0<|θ|<π F (re iθ ) re iθ dθ 2π , and we want to prove that it is dominated by (46). It suffices to prove that for θ 0 < |θ| < π,

|F (re iθ )| = o F (r) f (r) . (47)
Let us denote z = re iθ and z 0 = re iθ0 . We have

|F (re iθ )| F (r) = | exp(K(z) -K(r))| ≤ exp(|K(z)| -K(r)) = exp z 2 + z -z k 2(1 -z) - r 2 - r -r k 2(1 -r) ≤ exp r + r k 2|1 -z| - r -r k 2(1 -r) ≤ exp r + r k 2|1 -z 0 | - r -r k 2(1 -r) = exp - n 1/14 √ 2 (1 + o(1)) ,
given the values (39), ( 42) and (45) of k, r and θ 0 . Since f (r) ∼ 2 √ 2n 3/2 , we conclude that (47) holds.

Conclusion.

We have now established that the integral (41) is dominated by its first part, and is thus equivalent to (46). To obtain the limiting distribution function, it remains to divide this estimate by a n /n!. The asymptotic behaviour of a n is given by [START_REF] Robertson | Graph minors I-XX[END_REF], with α = 1/2, ρ = 1 and β = 0, and this concludes the proof. Let A be the class of graphs of maximum degree 2, or equivalently, the class of graphs avoiding the 3-star (Figure 10). The connected components of such graphs are paths or cycles. This class differs from those studied in the previous section in that the series C(z) has now, in addition to a simple pole, a logarithmic singularity at its radius of convergence ρ. As we shall see, the logarithm changes the asymptotic behaviour of the numbers a n , but the other results remain unaffected. The proofs are very similar to those of the previous section.

Proposition 28 (The number of graphs of maximum degree 2). The number of connected graphs (paths or cycles) of size n in the class A is c n = n!/2 + (n -1)!/2 for n ≥ 3 (with c 1 = c 2 = 1) and the associated generating function is

C(z) = z(2 -z + z 2 ) 4(1 -z) + 1 2 log 1 1 -z .
The generating function of graphs of A is

A(z) = e C(z) = 1 √ 1 -z exp z(2 -z + z 2 ) 4(1 -z) .
As n → ∞,

a n ∼ n! 1 2 √ eπn 1/2 e √ 2n .
In particular, the probability that G n is connected tends to 0 at speed n 1/2 e - √ 2n as n → ∞.

Proof. Again, the exact results are elementary. To obtain the asymptotic behaviour of a n , we write

A(z) = F (z)G(z) with F (z) = 1 √ 1 -z exp 1 2(1 -z) and G(z) = exp - 1 2 - z 2 4
(48) and combine Proposition 19 with [START_REF] Wright | The number of connected sparsely edged graphs[END_REF].

For the number of components, we find the same behaviour as in the case of a simple pole (Proposition 24 with α = 1/2). We have also determined the expected number of cyclic components.

Proposition 29 (Number and nature of components -Graphs of maximum degree 2). The mean and variance of N n satisfy:

E(N n ) ∼ n/2, V(N n ) ∼ n/8,
and the random variable

Nn- √ n/2
(n/8) 1/4 converges in law to a standard normal distribution. The expected number of cycles in G n is of order (log n)/4.

Proof. We want to apply Theorem 18. To prove that A(z) is Hayman-admissible, we apply Theorem 17 to (48). This reduces our task to proving that F (z) is H-admissible, which is done along the same lines as [19, Ex. VIII.7, p. 562] (see also the footnote of [22, p. 92], and Lemma 1 in [START_REF] Drmota | Marking in combinatorial constructions: generating functions and limiting distributions[END_REF]). Conditions ( 19)-( 21) are readily checked. The asymptotic estimates of E(N n ) and V(N n ) are obtained through [START_REF] Hayman | A generalisation of Stirling's formula[END_REF], using the saddle point estimate

ζ n = 1 -1/ √ 2n + O(1/n).
The bivariate generating function of graphs of A, counted by the size (variable z) and the number of cycles (variable v) is

Ã(z, v) = exp z + z 2 2(1 -z) + v Cyc(z) ,
where Cyc(z) is given by [START_REF] Bernasconi | The degree sequence of random graphs from subcritical classes[END_REF]. By differentiating with respect to v, the expected number of cycles in G n is found to be:

[z n ] Cyc(z)A(z) [z n ]A(z) .
The asymptotic behaviour of [z n ]A(z) = a n /n! has been established in Proposition 28. We determine an estimate of [z n ] Cyc(z)A(z) in a similar fashion, using a combination of Proposition 19 and (34). We find

[z n ] Cyc(z)A(z) ∼ log n 8 √ eπn 1/2 e √ 2n ,
and the result follows.

The size of the root component is still described by Proposition 25, with α = 1/2. The proof is very similar, with now

C (i+1) (z) = i! 2 2 + i -z (1 -z) i+2 - 1 2 1 i=1 ,
where 1 i=1 is 1 if i = 1 and is 0 otherwise.

10. Excluding the bowtie: a singularity in (1 -z/ρ) -1/2

We now denote by A the class of graphs avoiding the bowtie (Figure 11). The following proposition answers a question raised in [START_REF] Mcdiarmid | On graphs with few disjoint t-star minors[END_REF].

Proposition 30 (The generating function of graphs avoiding a bowtie). Let T ≡ T (z) be the generating function of rooted trees, defined by T (z) = ze T (z) . The generating function of connected graphs in the class A is

C(z) = T 2 1 -T + T 2 e T 1 -T + 1 2 log 1 1 -T + T 12 -54 T + 18 T 2 -5 T 3 -T 4 24(1 -T ) . ( 49
)
The generating function of graphs of A is A(z) = e C(z) . This is the most delicate enumeration of the paper. The key point is the following characterization of cores (graphs of minimum degree 2) avoiding the bowtie.

Proposition 31. The cores that avoid the bowtie are:

• the empty graph,

• all cycles,

• K 4 , with one edge possibly subdivided, as shown in Figure 16,

• the graphs of Figures 17 and18. We will first establish a number of properties of cores avoiding a bowtie. Recall that a chord of a cycle C is an edge, not in C, joining two vertices of C. Lemma 32. Let C = (v 0 , v 1 , . . . , v n-1 ) be a cycle in a core G avoiding the bowtie. Let us write v n = v 0 and v n+1 = v 1 . Every chord of C joins vertices that are at distance 2 on C (we say that it is a short chord). Moreover, C has at most two chords. If it has two chords, say {v 0 , v 2 } and {v i , v i+2 }, with

1 ≤ i ≤ n -1 , then v i = v 1 or v i+2 = v 1 .
Proof. If a chord were not short, contracting it (together with some edges of C) would give a bowtie. Figure 12 then proves the second statement, which can be loosely restated as follows: the two chords cross and their four endpoints are consecutive on C.

yes no no

Figure 12. The relative positions of two (short) chords in a cycle. The first two configurations are not valid, as these graphs contain a bowtie (shown with gray/blue edges).

Lemma 33. Let C be a cycle of maximal length in a core G avoiding the bowtie. Let v be an external vertex, that is, a vertex not belonging to C. Then v is incident to exactly two edges, both ending on C. The endpoints of these edges are at distance 2 on C.

Proof. Since G is a core, v belongs to a cycle C . Since G is connected and avoids the bowtie, C shares at least two vertices with C. Thus let P 1 and P 2 be two vertex-disjoint paths (taken from C ) that start from v and end on C without hitting C before. Let v 1 and v 2 be their respective endpoints on C. Then v 1 and v 2 lie at distance at least 2 on C, otherwise C would not have maximal length. Now contracting the path P 1 P 2 into a single edge gives a chord of C. By the previous lemma, this chord must be short, so that v 1 and v 2 are at distance exactly 2. Since C has maximal length, P 1 and P 2 have length 1 each, and thus are edges. Assume now that v has degree at least 3, and let e be a third edge (distinct from P 1 and P 2 ) adjacent to v. Again, e must belong to a cycle, sharing at least two vertices with C, and the same argument as before shows that e ends on C. But then Figure 13 shows that G contains a bowtie. Proof of Propositions 30 and 31. Observe that a graph G avoids the bowtie if and only if its core (defined as its maximal subgraph of degree 2) avoids it. Hence, if C(z) denotes the generating function of non-empty cores avoiding the bowtie, we have

C(z) = T (z) - T (z) 2 2 + C(T (z)). (50)
Using the above lemmas, we can now describe and count non-empty cores avoiding the bowtie.

We start with cores reduced to a cycle: their contribution to C(z) is given by [START_REF] Bernasconi | The degree sequence of random graphs from subcritical classes[END_REF]. We now consider cores G having several cycles. Let C be a cycle of G of maximal length, chosen so that it has the largest possible number of chords. By Lemma 32, this number is 2, 1 or 0.

If C has two chords, it contains all vertices of G (Lemma 34). By Lemma 32 and Figure 12 (right), either all vertices have degree 3 and G = K 4 , or G consists of K 4 where one edge is subdivided (Figure 16). ≥ 0 This gives the generating function

z 4 4! + z 4 4! • 6 • z 1 -z , (51)
where, in the second term, we read first the choice of the 4 vertices of degree 3 forming a K 4 , then the choice of one edge of this K 4 , and finally the choice of a (directed) path placed along this edge. Assume now that C has exactly one chord e. By Lemma 35, all external vertices are adjacent to the endpoints of e. To avoid problems with symmetries, we count separately the cores where C has length 4, or length ≥ 5 (Figure 17). This gives the generating function

z 2 2 (e z -1 -z) + z 2 2 (e z -1) z 2 1 -z . ( 52
)
In the second term, the factor z 2 /(1 -z) accounts for the directed chain of vertices of degree 2 lying on the maximal cycle. Putting this estimate together with (58) and (59), we obtain the estimate of a n /n! given in the proposition.

Proposition 38 (Number of components -no bowtie). The mean and variance of N n satisfy:

E(N n ) ∼ (e -5/4) 2/3 n 1/3 , V(N n ) ∼ 2 3 (e -5/4) 2/3 n 1/3 ,
and the random variable Nn-E(Nn) √ V(Nn)

converges in law to a standard normal distribution.

Proof. We want to apply Theorem 18. By Proposition 40, A(z) is H-admissible. Conditions ( 19)-( 21) are readily checked, using The asymptotic estimates of E(N n ) and V(N n ) are obtained through [START_REF] Hayman | A generalisation of Stirling's formula[END_REF], using the saddle point estimate (56).

C(z) ∼ e -5/4 √ 2 √ 1 -ze , b(r) ∼ 3 √ 2
Since there are approximately n 1/3 components, one may expect the size S n of the root component to be of the order of n 2/3 . More precisely, we have the following result.

Proposition 39 (Size of the root component -no bowtie). The normalized variable (e-5/4) 2/3 S n /(2n 2/3 ) converges in distribution to a Gamma(3/2, 1) law, of density 2 √ xe -x / √ π on [0, ∞). In fact, a local limit law holds: for x > 0 and k = x 2n 2/3 (e-5/4) 2/3 ,

2n 2/3 (e -5/4) 2/3 P(S n = k) → 2 x π e -x .
The convergence of moments holds as well: for i ≥ 0,

E(S i n ) ∼ Γ(i + 3/2) Γ(3/2) 2n 2/3 (e -5/4) 2/3 i .
Proof. The local (and hence global) limit law follows directly from Proposition 37, using [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF]. For the convergence of the moments, we start from (4). We first prove (see Proposition 40 in the appendix) that C (i+1) (z)A(z) is H-admissible. We then apply Theorem 16 to estimate the coefficient of z n in this series (we will replace n ny n -i -1 later). Our calculations mimic those of Proposition 37, but the saddle point equation now reads

ζC (ζ) + ζ C (i+2) (ζ) C (i+1) (ζ) = n, where ζ ≡ ζ (i)
n depends on i and n. Comparing with the original saddle point equation (55), and using the estimate (69) of

C (i) (z), this reads e -5/4 2 √ 2(1 -ζe) 3/2 + 7 + 4i 4(1 -ζe) + O 1 (1 -ζe) 1/2 = n.
This gives the saddle point as

ζ = 1 e - (e -5/4) 2/3 2en 2/3 - 7 + 4i 6en + O(n -4/3 ). (61)
We now want to obtain estimates of

C (i+1) (ζ)A(ζ), ζ n and b i (ζ).
We first derive from (57) that

C(ζ) = (e -5/4) 2/3 n 1/3 + 1 6 log n e -5/4 + 29 24 - 11e 3 - 2i 3 + O(n -1/3 ).
This gives

A(ζ) ∼ e 53 24 -11e 3 -2i 3
(e -5/4) 1/6 n 1/6 exp((e -5/4) 2/3 n 1/3 ).

Moreover, we derive from (69) that

C (i+1) (ζ) ∼ (2i + 1)! 2 i i! e i+1 n 1+2i/3 (e -5/4) 2i/3 . (63)
It then follows from (61) that

ζ n ∼ e -7/6-2i/3 exp -n -(e -5/4) 2/3 n 1/3 /2 . (64)
Finally, (71) and (60) give

b i (ζ) ∼ b(ζ) ∼ 3 (e -5/4) 2/3 n 5/3 .
Putting this estimate together with (62), ( 63) and (64), we obtain We finally replace n by n -i -1 (the only effect is to replace e n+i+1 by e n ), and divide by the estimate of na n /n! given in Proposition 37: this gives the estimate of the ith moment of S n as stated in the proposition, and concludes the proof.

[z n ]C (i+1) (z)A(z) ∼ (2i + 1)! 2 i i! (
11. Final comments and further questions

Random generation

For each of the classes A that we have studied, we have designed an associated Boltzmann sampler, which generates a graph G of A with probability

P(G) = x |G| |G|!A(x) , (65)
where x > 0 is a fixed parameter such that A(x) converges. We refer to [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]Sec. 4] for general principles on the construction of exponential Boltzmann samplers, and only describe how we have addressed certain specific difficulties. Most of them are related to the fact that our graphs are unrooted.

Trees and forests. Designing a Boltzmann sampler for rooted trees is a basic exercise after reading [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]. Note that the calculation of T (x) can be avoided by feeding the sampler directly with the parameter t = T (x), taken in (0, 1]. To sample unrooted trees, a first solution is to sample a rooted tree G and keep it with probability 1/|G|. However, this sometimes generates large rooted trees that are rejected with high probability. A much better solution is presented in [13, Sec. 2.2.1]. In order to obtain an unrooted tree distributed according to (65), one calls the sampler of rooted trees with a random parameter t. The density of t must be chosen to be (1 -t)/C(x) on [0, T (x)], with C(x) = T (x) -T (x) 2 /2. To sample t according to this density, we set t = 1 -1 -2uC(x), where u is uniform in [0, 1]. Again, we actually avoid computing the series C(x) by feeding directly our sampler with the value T (x) ∈ (0, 1]. We use this trick for all classes that involve the series T (x).

To obtain large forests (Figure 2), we actually sample forests with a distinguished vertex; that is, a rooted tree plus a forest [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]Sec. 6.3].

Paths, cycles and stars. The sequence operator of [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]Sec. 4] produces directed paths, while we need undirected paths. Let u be uniform on [0, 1]. Our generator generates the one-vertex path if u < x/C p (x), where C p (x) is given by (37), and otherwise generates a path of length 2 + Geom(x). An alternative is to generate a directed path, and reject it with probability 1/2 if its size is at least 2.

Although the cycle operator of [START_REF] Duchon | Boltzmann samplers for the random generation of combinatorial structures[END_REF]Sec. 4] generates oriented cycles, this does not create a similar problem for our non-oriented cycles: indeed, a cycle of length at least 3 has exactly two possible orientations.

Designing a Boltzmann sampler ΓRS for rooted stars is elementary. For unrooted stars, we simply call ΓRS, but reject the star with probability 1/2 if it has size 2 (because the only star with two rootings has size 2).

Graphs avoiding the bowtie. This is the most complex of our algorithms, because the generation of connected graphs involves 7 different cases (see the proof of Proposition 30). There is otherwise no particular difficulty. We specialize this algorithm to the generation of graphs avoiding the 2-spoon (Proposition 11). However, the probability to obtain a forest is about 0.95, and thus there is no point in drawing a random graph of this class.

The graphs shown in the paper have been drawn with the graphviz software.

The nature of the dominant singularities of C(z)

This is clearly a crucial point, as the probability that G n is connected and the quantities N n and S n seem to be directly correlated to it (see the summary of our results in Table 1). This raises the following question: is it possible to describe an explicit correlation between the properties of the excluded minors and the nature of the dominant singularities of C(z)? For instance, it is known that C(ρ) is finite when all excluded minors are 2-connected, but Section 4 shows that this happens as well with some non-2-connected excluded minors. Which excluded minors give rise to a simple pole in C(z) (as in caterpillars)? or to a logarithmic singularity (as for graphs with no bowtie nor diamond), or to a singularity in (1 -z/ρ) -1/2 (as for graphs with no bowtie)? Some classes for which C(z) has a unique dominant pole of high order are described in the next subsection.

More examples and predictions

Our examples, as well as a quick analysis, lead us to predict the following results when C(z) has a unique dominant singularity and a singular behaviour of the form (1 -z/ρ) -α , with α > 0:

• the mean and variance of the number N n of components scale like n α/(1+α) , and N n admits a gaussian limit law after normalization, • the mean of S n scales like n 1/(1+α) , and S n , normalized by its expectation, converges to a Gamma distribution of parameters α + 1 and 1.

The second point is developed in [START_REF] Bousquet-Mélou | Size of the root component in exponential structures[END_REF]. To confirm these predictions one could study the following classes, which yield series C(z) with a high order dominant pole. Fix k ≥ 2, and consider the class A (k) of forests of degree at most k, in which each component has at most one vertex of degree ≥ 3. This means that the components are stars with long rays and "centers" of degree at most k. It is not hard to see that

C (k) (z) = z + z 2 2(1 -z) + k i=3
z i+1 i!(1 -z) i , so that C k has a pole of order k (for k ≥ 3). The case k = 2 corresponds to forests of paths (Section 8). The limit case k = ∞ (forests of stars with long rays) looks interesting, with a very fast divergence of C at 1:

C (∞) (z) = z exp z 1 -z - z 2 2(1 -z) 2 .
We do not dare any prediction here.

Other parameters

We have focussed in this paper on certain parameters that are well understood when all excluded minors are 2-connected. But other parameters -number of edges, size of the largest 2connected component, distribution of vertex degrees -have been investigated in other contexts, that sometimes intersect the study of minor-closed classes [START_REF] Bernasconi | The degree sequence of random graphs from subcritical classes[END_REF][START_REF] Bernasconi | On the degree sequences of random outerplanar and seriesparallel graphs[END_REF][START_REF] Drmota | Asymptotic study of subcritical graph classes[END_REF][START_REF] Drmota | Degree distribution in random planar graphs[END_REF][START_REF] Giménez | Graph classes with given 3-connected components: Asymptotic enumeration and random graphs[END_REF]. When specialized to the theory of minor-closed classes, these papers generally assume that all excluded minors are 2-connected, sometimes even 3-connected.

Clearly, it would not be hard to keep track of the number of edges in our enumerative results. Presumably, keeping track of the number of vertices of degree d for any (fixed) d would not be too difficult either. This may be the topic of future work. The size of the largest component clearly needs a further investigation as well.

Acknowledgements. KW would like to thank Colin McDiarmid for many inspiring and helpful discussions as well as for constant support. We also thank Philippe Duchon and Carine Pivoteau for their help with Boltzmann samplers, Nicolas Bonichon for a crash course on the Graphviz software, Jean-François Marckert for pointing out the relevance of [START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF] and finally Bruno Salvy for pointing out Reference [START_REF] Macintyre | Operational methods and the coefficients of certain power series[END_REF].

We also thank the referees for their careful and detailed reports.

¡ £

Appendix: Hayman-admissibility for bowties Proposition 40. Let C(z) and A(z) be the series given in Proposition 30. Then the series A(z) and C (i+1) (z)A(z) are H-admissible, for any i ≥ 1.

Proof. We begin with the series A(z). Recall the analytic properties of T (z), listed at the beginning of the proof of Proposition 37. The capture condition H 1 is readily checked. In fact, for some constant M . For any z of modulus r < 1/e, we have |1 -re| ≤ |1 -ze|, and we can bound the first factor above by 1. Also, it is not hard to prove that 1/ √ 1 -ze is a decreasing function of θ ∈ (0, π). Hence, denoting z 0 = re iθ0 : Let us now consider the series A i (z) := C (i+1) (z)A(z), for i ≥ 1. It is easy to prove by induction on i that for i ≥ 1, Let us now prove that A i (z) satisfies H 2 with the same value of θ 0 as for A(z) (that is, θ 0 = (1 -re) 6/5 ). Thanks to (70-71) we have, for |θ| ≤ θ 0 and uniformly in θ, e -iθai(r)+θ 2 bi(r)/2 = e -iθa(r)+θ 2 b(r)/2 1 + O((1 -re) 1/5 ) .

C (i) (z) = (

Figure 2 .

 2 Figure 2. A random forest of size n = 1165. It has two connected components.

Figure 3 .

 3 Figure 3. A core having several cycles and avoiding the k-spoon cannot contain a path of length 3k -1.

Figure 4 .

 4 Figure 4. A random graph of size n = 541 avoiding the diamond, the bowtie and the 20-spoon.

Figure 5 .

 5 Figure 5. Graphs with several cycles avoiding the 2-spoon.

Figure 6 .

 6 Figure 6. A random graph of size n = 859 avoiding the diamond and the bowtie.

Figure 7 .

 7 Figure 7. The distribution function P(L n < m) for n = 100. The first plot shows the change of regime at m = n/2, the second the change at m = n/3, the third the change at m = n/4.

  -admissible (or H-admissible) functions. Let us first recall what this black box does [19, Thm. VIII.4, p. 565].

)

  where ζ ≡ ζ n is the unique solution in (R, ρ) of the saddle point equation ζA (ζ) = nA(ζ).

  for a fixed constant K. Condition (1) of[START_REF] Drmota | Extended admissible functions and Gaussian limiting distributions[END_REF] Def. 1] holds for R = ρ, any ζ > 0 and any R 0 ∈ [0, ρ): indeed, the series A(z, u) is analytic for |z| < ρ and u ∈ C, and A(z, 1) is positive on [0, ρ). Conditions (8) and (9) are nothing but our assumptions[START_REF] Flajolet | Analytic combinatorics[END_REF] and[START_REF] Giménez | Graph classes with given 3-connected components: Asymptotic enumeration and random graphs[END_REF]. Condition (4) is that b(r) → +∞ as r → ρ: this holds because A is Hayman admissible. Condition[START_REF] Bender | Asymptotic methods in enumeration[END_REF] requires that b(r, u) ∼ b(r, 1) for r → ρ, uniformly for u ∈ [1 -ε(r), 1 + ε(r)]: this holds because b(r, u)/b(r, 1) = u and ε(r) → 0 as r → ρ. Condition (6) requires that a(r, u) = a(r, 1) +

H 3 [

 3 Uniform decay condition] As r → ρ, sup |θ|∈[δ(r),π) |u-1|≤ε(r)

Figure 8 .

 8 Figure 8. A random graph of size n = 1171 with component size at most 3.Observe that most components have size 3, so that the root component is very likely to have size 3.

Figure 9 .

 9 Figure 9. A random forest of paths of size n = 636 (left) and a forest of caterpillars of size n = 486 (right).

( 31 ) 3 4

 313 is satisfied and Propositions 23, 24 and 25 hold. For paths we have ρ = 1, α = 1/2 and β := D(ρ) = 0. For caterpillars, ρ 0.567 is the only real such that ρe ρ = 1, α = (1 -ρ) 2 2(1 + ρ) 0.06 and β = ρ 10 + 3 ρ -4 ρ 2 -ρ

Figure 10 . 9 .

 109 Figure 10. A random graph of size n = 1034 avoiding the 3-star.

Figure 11 .

 11 Figure 11. A random graph of size n = 758 avoiding the bowtie.

Figure 13 .

 13 Figure 13. A cycle C with an external vertex v of degree at least 3. The cycle shown in gray/blue has a chord that is not short, the contraction of which gives a bowtie.

Figure 14 .v 1 v 2 Figure 15 .

 14215 Figure 14. A cycle C with (a) two chords and an external vertex v (b) one chord and an external vertex v.

Figure 16 .

 16 Figure 16. K 4 with a subdivided edge.

Figure 17 . 3 (e - 5 / 4 )

 17354 Figure 17. A maximal cycle with one chord e and external vertices.

  (e -5/4) 8(1 -ze) 5/2 and V (r)

e - 5 / 4 ) 1 /6 e 19

 54119

a(r) = rC (r) ∼ e - 5 /4 2 √ 2 ( 1 -

 5221 re) 3/2 and b(r) = rC (r) + r 2 C (r) ∼ 3 √ 2(e -5/4) 8(1 -re) 5/2 .(66)Let us now prove H 2 . By Taylor's formula applied to the function f : θ → C(re iθ ), we have, for r ∈ (0, 1/e) and θ ∈ [-θ 0 , θ 0 ]:C(re iθ ) -C(r) -iθa(r) + θ 2 b(r)/2 ≤ |θ 3 0 |/6 sup |α|≤θ0 |f (3) (α)| with f (3) (α) = -ire iα C (re iα ) -3ir 2 e 2iα C (re iα ) -ir 3 e 3iα C (re iα ) ≤ rC (r) + 3r 2 C (r) + r 3 C (r) ∼ κ (1 -re) 7/2as r → 1/e, for some constant κ. Hence, if we take θ 0 ≡ θ 0 (r) = o((1 -re) 7/6 ), then sup |θ|≤θ0(r)A(re iθ ) A(r) e -iθa(r)+θ 2 b(r)/2 -1 = e o(1) -1 → 0 as r → 1/e. Thus H 2 holds for such values of θ 0 . We now takeθ 0 (r) = (1 -re) 6/5 ,(67)and want to prove that H 3 also holds.Recall that C(z) is analytic on C \ [1/e, ∞), and let us isolate in C(z) the part that diverges at z = 1/e: is uniformly bounded on {|z| < 1/e}. Hence, writing z = re iθ , we have sup |θ|∈[θ0,π) A(z) A(r) b(r) ≤ M sup |θ|∈[θ0,π)

1 - 1 -

 11 But as r → 1/e, the choice (67) of θ 0 implies that c √ re) 1/10 + o(1).Condition H 3 now follows, using the estimate (66) of b(r).

1 ( 1 - 2 = b(r) + O 1 ( 1 -

 11211 2i)!(e -5/4)e i 4 i √ 2i!(1 -ze) i+1/2 + O ze) i . (69) This can be proved either from the expression of C(z) given in Proposition 30, or by starting from the singular expansion (68) of C(z) and applying [19, Thm. VI.8, p. 419].Recall the behaviour (66) of the functions a(r) and b(r) associated with A(z). It follows, with obvious notation, that as r → 1/e,a i (r) = a(r) + r C (i+2) (r) C (i+1) (r) = a(r) + O 1 1 -re(70)andb i (r) = b(r) + r C (i+2) (r) C (i+1) (r) + r 2 C (i+3) (r) C (i+1) (r) -r 2 C (i+2) (r) C (i+1) (r) re) 2(71)both tend to infinity. Thus H 1 holds.

  Several general results provide a limit law for N n if C(z) satisfies certain conditions: for instance the results of Bell et al.[START_REF] Bell | Asymptotics for the probability of connectedness and the distribution of number of components[END_REF] that require C(z) to converge at its radius of convergence; or the exp-log schema of [19, Prop. IX.14, p. 670], which requires C(z) to diverge with a logarithmic singularity (see also the closely related results of[START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF] on logarithmic structures). We use these results when applicable, and prove a new result of this type, based on Drmota et al.'s notion of extended Hayman admissibility, which applies when C(z) diverges with an algebraic singularity.

) .

  . A decomposable class of graphs A is an assembly in the sense of[START_REF] Arratia | Logarithmic combinatorial structures: a probabilistic approach[END_REF] Sec. 2.2]. In particular, it satisfies the conditioning relation [2, Eq. (3.1)]: conditionally to the total size being n, the numbers C that count connected components of size i, for 1 ≤ i ≤ n, are independent. When A is the class of graphs avoiding the diamond and the bowtie, the estimate (10) of c n tells us that this assembly is logarithmic in the sense of [2, Eq. (2.15)]: indeed, [2, Eq. (2.16)] holds with m i = c i , y = e and θ = 1/4. Our random variable L n coincides with the random variable L

	(n)
	i
	(n)
	1

Both authors were partially supported by a CNRS-Oxford collaboration scheme (CNRS/John Fell Oxford University Press Research fund, 2012).

1 obtained by contracting or deleting some edges, removing some isolated vertices and discarding loops and

Assume finally that C has no chord. By Lemma 36, all external vertices are adjacent to the same points of C. Again, we treat separately the cases where C has length 4, or length ≥ 5 (Figure 18). This gives the generating function Putting together the contributions ( 8), (51), ( 52) and (53) gives the value of C(z) (the generating function of cores) from which we obtain the series C(z) using (50).

We now derive asymptotic results from Proposition 30.

Proposition 37 (The asymptotic number of graphs avoiding the bowtie). As n → ∞,

Proof. Let us first recall that the series T (z) has radius of convergence 1/e, and can be continued analytically on the domain D := C \ [1/e, +∞). In fact, T (z) = -W (-z), where W is the (principle branch of the) Lambert function [START_REF] Corless | On the Lambert W function[END_REF]. The singular behaviour of T (z) near 1/e is given by [START_REF] Bernardi | Growth constants of minor-closed classes of graphs[END_REF]. Moreover, the image of D by T avoids the half-line [1, +∞).

It thus follows from the expression (49) of C(z) that C(z) and A(z) are analytic in the domain D. Moreover, we derive from (6) that, as z approaches 1/e in a ∆-domain,

The above estimate of c n then follows from singularity analysis. We now embark with the estimation of a n . We first prove (see Proposition 40 in the appendix) that A(z) is H-admissible. We then apply Theorem 16. The saddle point equation reads ζC (ζ) = n. Using the singular expansion (6) of T (z), and a similar expansion for T (z), this reads

This gives the saddle point as

We now want to obtain estimates of the values A(ζ), ζ n and b(ζ) occurring in Theorem 16.

Refining (54) into

we find C(ζ) = (e -5/4)

and Condition H 2 holds for A i since it holds for A.

Finally, since C(z) has non-negative coefficients, we have C (i+1) (z) ≤ C (i+1) (r) for z = re iθ . Thus the fact that A i (z) satisfies H 3 follows from the fact that A(z) satisfies H 3 , together with b i (r) ∼ b(r).