Printer Friendly

Asymptotic properties of some minor-closed classes of graphs.

1 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 of a graph of A is in A. To each such class one can associate a 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 [19].

For a minor-closed class A, we study the asymptotic properties of a random graph [G.sub.n] taken uniformly in [A.sub.n], the set of graphs of A having n vertices: what is the probability [p.sub.n] that [G.sub.n] is connected? More generally, what is the number [N.sub.n] of connected components? What is the size [S.sub.n] of the root component, that is, the component containing the vertex 1? Or the size [L.sub.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.sub.n] converges to constant larger than 1/[square root of e], [N.sub.n] converges in law to a Poisson distribution, n - [S.sub.n] and n - [L.sub.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.sub.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. We refer to [7] for more examples, complete proofs and Boltzmann samplers for our classes of graphs.

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, which implies that A is decomposable: a graph belongs to A if and only if all its connected components belong to A. In particular, A(z) = exp(C(z)). Our exact and asymptotic results make extensive use of the techniques of Flajolet and Sedgewick's book [11]: 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, but then we only sketch the proofs, at best. We also need and prove two general results of independent interest related to the saddle point method (Theorems 3 and 4).

Our results are summarized in Table 1. A first dichotomy emerges: when C(z) is finite at its radius of convergence [rho], the properties of A are qualitatively the same as in the 2-connected case (for which C([rho]) is known to converge), except that the limit of [p.sub.n] can be arbitrarily small (Section 8). When C([rho]) diverges, a whole variety of behaviours can be observed, depending on the nature of the singularity of C(z) at [rho] (Sections 5 to 7): the probability [p.sub.n] tends to 0 at various speeds; the number [N.sub.n] of components goes to infinity at various speeds (but is invariably gaussian after normalization); the size [S.sub.n] of the root component follows, after normalization, non-gaussian limit laws (gamma or beta). We only study the size [L.sub.n] of the largest component in a few cases. Much remains to be done in this direction.

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. We are currently working on such a systematic study, in the spirit of what Bell et al. [4] and Gourdon [13] did for the number of components and the largest component, respectively. This project is also reminiscent of the study of the 2-connected root component in a planar map [3], which also leads to non-gaussian limit laws.

2 Generating functionology for graphs

Let E be a finite set of (unlabelled) connected graphs that forms an antichain with respect to the minor order. Let A be the set of labelled graphs that do not contain any element of E as a minor. By [A.sub.n] we denote the subset of A formed of graphs having n vertices and by [a.sub.n] the cardinality of [A.sub.n]. The associated exponential generating function (g.f.) is A(z) = [[summation].sub.n [greater than or equal to] 0][a.sub.n][z.sup.n]/n!. We use similar notation ([c.sub.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 g.f. that keeps track of the number of (connected) components as well:

A(z,u) = [summation over (G[member of]A)][u.sup.c(G)] [[z.sup.[absolute value of G]]/[absolute value of G]!] = exp(uC(z)),

where [absolute value of G] is the size of G (the number of its vertices) and c(G) the number of its components. We denote by [N.sub.n] the number of components in a (uniform) random graph [G.sub.n] of [A.sub.n]. Clearly,

p([N.sub.n] = i) = [[z.sup.n]]C[(z).sup.i]/i![[z.sup.n]]A(z) and E([N.sub.n]([N.sub.n] - 1) ... ([N.sub.n] - i + 1)) = [[z.sup.n]]C[(z).sup.i]A(z)/[[z.sup.n]]A(z). (1)

Several general results provide a limit law for [N.sub.n] if C(z) satisfies certain conditions: for instance the results of Bell et al. [4] that require C(z) to converge at its radius; or the exp-log schema of [11, Prop. IX.14, p. 670], which requires C(z) to have a logarithmic singularity. We use them when applicable, and prove a new result of this type, which applies when C(z) diverges with an algebraic singularity (Theorem 4).

We also study the size r(G) of the root component (the component containing the vertex 1). Let

[bar.A](z,v) = [summation over (G[member of]A,G[not equal to]0)][v.sup.r(G)- 1][[z.sup.[absolute value of G] - 1]/([absolute value of G] - 1)!] = C'(zv)A(z). (2)

The choice of [absolute value of G] - 1 instead of [absolute value of G] slightly simplifies some calculations. Note that [bar.A](z, 1) = A'(z). Denoting by [S.sub.n] the size of the root component in [G.sub.n], we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. (3)

Surprisingly, this parameter has not been studied before. Our examples lead to non-gaussian limit laws (gamma or beta, cf. Propositions 7 or 12). In fact, the form (2) 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 to 1 - [epsilon] to 1 + [epsilon]. Using the terminology of [11, Sec. IX.11], a phase transition occurs. We are currently working on a systematic study of this parameter for exponential objects.

3 Classes defined by 2-connected excluded minors

We assume here that the class A excludes at least one minor, and that all excluded minors are 2-connected. This includes the class of forests, series-parallel graphs, planar graphs, and many more. Many results are known in this case. The general picture is that A shares many properties with the class of forests.

Proposition 1 The series C(z) and A(z) = [e.sup.C(z)] are finite at their (positive) radius of convergence [rho]. Moreover, the sequence [([a.sub.n]/n!).sub.n] is smooth, meaning that n[a.sub.n- 1]/[a.sub.n] tends to [rho] as n grows.

The probability that [G.sub.n] is connected tends to 1/A([rho]), which is clearly in (0,1). In fact, this limit is also larger than or equal to 1/[square root of [epsilon]]. This value is reached when A is the class of forests.

The fact that [rho] > 0 is due to Norine et al. [18], and holds for any proper minor-closed class. The next results are due to McDiarmid [16]. The fact that 1/A([rho]) [greater than or equal to] 1/[square root of [epsilon]], or equivalently, that C([rho]) [less than or equal to] 1/2, was proved independently in [1] and [14].

For forests, all results are well-know (see for instance [11, p. 132]). We have C(z) = T(z) - T[(z).sup.2]/2, where T(z) = z[e.sup.T(z)] counts rooted trees. The series T, C and A have radius [rho] = 1/e, and A([rho]) = [square root of [epsilon]].

The nature of the singularity of C(z) at [rho] depends on the class: [(1 - z/[rho]).sup.3/2] for forests (and more generally, for subcritical minor-closed classes [8]), but [(1 - z/[rho]).sup.5/2] for planar graphs. We refer to [12] for a more detailed discussion that applies to classes that exclude 3-connected minors.

Proposition 2 The random variable [N.sub.n] - 1 converges in law to a Poisson distribution of parameter C([rho]):

p([N.sub.n] = i + 1) [right arrow] C[([rho]).sup.i]/i![e.sup.C([rho])].

The random variables n - [L.sub.n] and n - [S.sub.n] both converge to a discrete limit distribution X given by

P(X = k) = [1/A([rho])][[a.sub.k][[rho].sup.k]/k!]].

Proof: The first two results (on [N.sub.n] and [L.sub.n]) are due to McDiarmid [16, Cor. 1.6]. The third one is in fact equivalent to the second (the root component is, with high probability, the largest one), but we give here an independent proof, as we will recycle its ingredients later for some classes of graphs that avoid non-2-connected minors. Let k [greater than or equal to] 0 be fixed. By (3),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By Proposition 1, the term [c.sub.n-k]/[a.sub.n-k], which is the probability that [G.sub.n-k] is connected, converges to 1/A([rho]). Moreover, the sequence [a.sub.n]/n! is smooth, so that (n- 1)![a.sub.n-k]/(n-k-1)![a.sub.n] converges to [[rho].sup.k]. The result follows. []

4 General tools: Hayman admissibility and extensions

We consider in Sections 5 to 7 minor-closed classes of graphs such that C(z) diverges at its radius of convergence [rho]. This often results in A(z) diverging rapidly at [rho], and leads us to estimate [a.sub.n] using the saddle point method, or rather, a black box that applies to Hayman-admissible (or H-admissible) series: see [11, Thm. VIII.4, p. 565]. These series have useful closure properties [ibid., p. 568]. Here is one that we did not find in the literature.

Theorem 3 Let A(z) = F(z)G(z) where F(z) and G(z) are power series with real coefficients and radii of convergence 0 < [[rho].sub.F] < [[rho].sub.G] [less than or equal to] [infinity]. Assume that F(z) has non-negative coefficients and is H-admissible, and that G([[rho].sub.F]) > 0. Then A(z) is H-admissible.

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

Theorem 4 Let C(z) be a power series with non-negative coefficients and radius of convergence p. Assume A(z) = [e.sup.C(z)] has radius p and is H-admissible. Define

b(r)= rC'(r) + [r.sup.2]C"(r) and V(r) = C(r) - [[(rC'(r)).sup.2]/[rC'(r) + [r.sup.2]C"(r)]].

Assume that, as r [right arrow] [rho],

V(r) [right arrow] +[infinity], C(r)/V[(r).sup.3/2] [right arrow] 0, b[(r).sup.1/[square root of V(r)]] = O(1). (5)

Then A(z,u) := [e.sup.uC(z)] satisfies Conditions (1)-(6), (8) and (9) of [10, Def. 1]. If [N.sub.n] is a sequence of random variables such that

P([N.sub.n] = i) = [[z.sup.n]]C[(z).sup.i]/i![[z.sup.n]][e.sup.C(z)],

then the mean and variance of [N.sub.n] satisfy:

E([N.sub.n]) ~ C([[zeta].sub.n]), V([N.sub.n]) ~ V([[zeta].sub.n]), (6)

where [zeta] = [[zeta].sub.n] is the unique solution in (0, [rho]) of the saddle point equation [zeta]C'([zeta]) = n. Moreover, the normalized random variable [[N.sub.n] - E([N.sub.n])]/[square root of V([N.sub.n])] converges in law to a standard normal distribution.

Proof: We carefully check the eight conditions (the only that do not come for free are (2) and (3)). As explained in [10] just below Theorem 2, they give the estimates (6) of E([N.sub.n]) and V([N.sub.n]) and imply the existence of a gaussian limit law. []

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

Proposition 5 Let F(z) = [[summation].sub.n][f.sub.n][z.sup.n] and G(z) = [[summation].sub.n][g.sub.n][z.sup.n] be power series with radii of convergence 0 [less than or equal to] [[rho].sub.F] < [[rho].sub.G] [less than or equal to] [infinity], respectively. Suppose that G([[rho].sub.F]) [not equal to] 0 and [f.sub.n-1]/[f.sub.n] approaches a limit (which is necessarily [[rho].sub.F]) as n [right arrow] [infinity]. Then [[z.sup.n]]F(z)G(z) ~ G([[rho].sub.F])[f.sub.n].

5 Forests of paths or caterpillars: a simple pole

Let A be a decomposable class (for instance defined by excluding connected minors), with g.f. A(z) = exp(C(z)). Assume that C(z) has a unique dominant singularity [rho], which is an isolated simple pole:

C(z) = [[alpha]/[1 - [z/[rho]]]] + D(z), where D([rho]) = [beta] (7)

and D has radius of convergence strictly larger than [rho]. Of course, we assume [alpha] > 0.

Proposition 6 If the above conditions hold, then, as n [right arrow] [infinity],

[c.sub.n] ~ n![alpha][[rho].sup.-n] and [a.sub.n] ~ n![[[alpha].sub.1/4][e.sup.[alpha]/2+[beta]]/2[square root of [pi]][n.sup.3/4]][[rho].sup.-n][e.sup.2[square root of [alpha]n]]. (8)

In particular, the probability that [G.sub.n] is connected tends to 0 at speed [n.sup.3/4][e.sup.2[square root of [alpha]n]].

Proof: The asymptotic behaviour of [c.sub.n] follows from [11, Thm. IV.10, p. 258]. For [a.sub.n], we first write

A(z) = F(z)G(z) with F(z) = exp([alpha]/[1 - [z/[rho]]]) and G(z) = [e.sup.D(z)], (9)

where G(z) has radius strictly larger than [rho]. To estimate the coefficients of F, we apply the ready-to-use results of Macintyre and Wilson [15, Eqs. (10)-(14)], according to which, for [alpha] > 0 and [gamma] [greater than or equal to] 0,

[[z.sup.n]][1/[(1 - z).sup.[gamma]]]exp([alpha]/[1 - z]) ~ [[[alpha].sup.1/4][e.sup.[alpha]/2]/2[square root of [pi]][n.sup.3/4]][(n/[alpha]).sup.[gamma]/2][e.sup.2[square root of [alpha]n]]. (10)

This gives

[f.sub.n] := [[z.sup.n]]F(z) ~ [[[alpha].sup.1/4][e.sup.[alpha]/2]/2[square root of [pi]][n.sup.3/4]][[rho].sup.-n][e.sup.2[square root of [alpha]n]].

In particular, [f.sub.n-1]/[f.sub.n] tends to [rho], so that we can apply Proposition 5 to (9) and conclude. []

Proposition 7 Assume (7) holds.

1 . The mean and variance of [N.sub.n] satisfy:

E([N.sub.n]) ~ [square root of [alpha]n], V([N.sub.n]) ~ [square root of [alpha]n]/2, (11)

and the random variable [[N.sub.n] - [square root of [alpha]n]]/[([alpha]n/4).sup.1/4] converges in law to a standard normal distribution.

2. For i [greater than or equal to] 0, the ith moment of [S.sub.n] satisfies, as n [right arrow] [infinity],

E([S.sup.i.sub.n]) ~ (i + 1)![(n/[alpha]).sup.i/2].

Consequently, the normalized variable [S.sub.n]/[square root of (n/[alpha])] converges in distribution to a gamma(2) law, of density x[e.sup.-x] on [0, [infinity]). A local limit law also holds: for x > 0 and k = [x[square root of (n/[alpha])]],

[square root of (n/[alpha])]P([S.sub.n] = k) ~ x[e.sup.-x].

Proof: 1. We apply Theorem 4. The H-admissibility of A(z) follows from Theorem 3, using (9) and the H-admissibility of exp([alpha]/(1 - z/[rho])) (see [11, p. 562]). Conditions (5) are then readily checked, using

C(r) ~ [alpha]/[1 - [z/[rho]]], b(r) ~ 2[alpha]/[(1 - [z/[rho]]).sup.3] and V(r) ~ [alpha]/2(1 - [z/[rho]]).

We thus conclude that the normalized version of [N.sub.n] converges in law to a standard normal distribution. For (11), we use (6) with the saddle point estimate [[zeta].sub.n] = [rho] - [rho][square root of ([alpha]/n)] + O(1/n).

2. We apply (3), with

[C.sup.(i+1)](z) = [[alpha](i + 1)!/[[rho].sup.i+1][(1 - [z/[rho]]).sup.i+2]] + [D.sup.(i+1)](z). (12)

As in the proof of Proposition 6, we combine Proposition 5, (9) and (10) to obtain

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Combined with (8), this gives the limiting ith moment of [S.sub.n]. Since these moments characterize the above gamma distribution, we conclude [11, Thm. C.2] that [S.sub.n]/[square root of (n/[alpha])] converges in law to this distribution.

For the local limit law, we simply combine the first part of (3) with (8). []

We now apply these results to two classes for which C(z) has a simple pole: 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).

Proposition 8 The generating functions of paths and of caterpillars are respectively

[C.sub.p](z) = z(2-z)/2(1-z) and [C.sub.c](z) = [[z.sup.2][([e.sup.z]- 1).sup.2]/2(1-z[e.sup.z])] + z[e.sup.z] - [[z.sup.2]/2].

For both series, Condition (7) is satisfied and Propositions 6 and 7 hold. For paths we have [rho] = 1, [alpha] = 1/2 and [beta] = 0. For caterpillars, [rho] [equivalent] 0.567 is the only real such that [rho][e.sup.[rho]] = 1,

[alpha] = [[(1-[rho]).sup.2]/2(1+[rho])] [equivalent] 0.06 and [beta] = [rho](10 + 3[rho] - 4[[rho].sup.2] - [[rho].sup.3])/4[(1 + [rho]).sup.2] [equivalent] 0.59.

For forests of paths, we have also studied the size [L.sub.n] of the largest component.

Proposition 9 In forests of paths, the size of the largest component converges to a Gumbel distribution:

P([[[L.sub.n] - [square root of (n/2)]log n]/[square root of (n/2)]] < x) [right arrow] exp(-[e.sup.x/2]/[square root of 2]).

Proof: The generating function of paths of size less than k is [C.sup.[k]](z) = z/2 + (z - [z.sup.k])/(2(1 - z)). We then use Cauchy's formula and a saddle point approach. []

Graphs with maximal degree 2: a simple pole plus a logarithm. Let A be the class of graphs avoiding the 3-star. The connected components of such graphs are paths and cycles. The series C(z) has now, in addition to a simple pole, a logarithmic singularity at its radius. The logarithm changes the asymptotic behaviour of the numbers [a.sub.n], but the other results remain unaffected. The proofs are very similar to the above ones.

Proposition 10 The generating function of connected graphs of A is

C(z) = [z(2 - z + [z.sup.2])/4(1 - z)] + [1/2]log [1/[1 - z]].

The generating function of graphs of A is A(z) = [e.sup.C(z)]. We have, for large n,

[c.sub.n] = [n!/2] + [(n-1)!/2] and [a.sub.n] ~ n![1/2[square root of e[pi]][n.sup.1/2]][e.sup.[square root of 2n]].

In particular, the probability that [G.sub.n] is connected tends to 0 at speed [n.sub.1/2][e.sup.-[square root of 2n]].

The number of components and the size of the root component behave as in Proposition 7, with [alpha] = 1/2.

6 Excluding the diamond and the bowtie: a logarithm dominates

Let A be the class of graphs avoiding the diamond and the bowtie (shown in Figure 1). The connected components are trees or unicyclic graphs, and have been counted a long time ago by Wright [20].

Proposition 11 Let T (z) = z[e.sup.T(z)] be the g.f. of rooted trees. The g.f. of connected graphs of A is

C(z) = [T/2] - [3[T.sup.2]/4] + [1/2]log [1/[1 - T]].

The generating function of graphs of A is A(z) = [e.sup.C(z)]. As n [right arrow] [infinity],

[c.sub.n] ~ n![[e.sup.n]/4n] and [a.sub.n] ~ n![1/[(2e).sup.1/4][GAMMA](1/4)][[e.sup.n]/[n.sup.3/4]]. (13)

In particular, the probability that [G.sub.n] is connected tends to 0 at speed [n.sup.-1/4] as n [right arrow] [infinity].

Proof: A connected graph of A is either an (unrooted) tree (with g.f. T - [T.sup.2]/2), or consists of a cycle, in which each vertex is replaced by a rooted tree. The generating function of cycles is

Cyc(z) = [1/2][summation over (n [greater than or equal to] 3)][[z.sup.n]/n] = [1/2](log [1/[1 - z]] - z - [[z.sup.2]/2]), (14)

and this gives the expression of C(z). We then estimate [c.sub.n] and [a.sub.n] via singularity analysis [11, VI.4]. []

Proposition 12 1. The mean and variance of Nn satisfy E([N.sub.n]) ~ V([N.sub.n]) ~ log n/4, and the random variable [[N.sub.n] - log [n/4]]/[square root of log [n/4]] converges in law to a standard normal distribution.

2. For i [greater than or equal to] 0, the ith moment of [S.sub.n] satisfies, as n [right arrow] [infinity],

E([S.sup.i.sub.n]) ~ [[GAMMA](5/4)i!/[GAMMA](i + 5/4)][n.sup.i].

Consequently, the normalized variable [S.sub.n]/n converges in distribution to a beta law, ofdensity [(1 - x).sup.-3/4]/4 on [0,1]. A local limit law also holds: for x [member of] (0,1) and k = [xn],

nP([S.sub.n] = k) ~ [1/4][(1 - x).sup.-3/4].

3. The normalized variable [L.sub.n]/n converges in law to the first component of a Poisson-Dirichlet distribution ofparameter 1 /4.

Proof: Once the singular expansion of C(z) is obtained, the first result follows from [11, Prop. IX.14, p. 670]. To study the moments of [S.sub.n], we apply (3). Using T(z) = z[e.sup.T(z)], we obtain, for i [greater than or equal to] 1,

[C.sup.(i+1)](z) ~ [i!/4][(e/[1 - ze]).sup.i+1].

The estimate of the th moment of [S.sub.n] then follows again from singularity analysis. Since these moments characterize the above beta distribution, we conclude [11, Thm. C.2] that [S.sub.n]/n converges in law to this distribution. For the local limit law, we start from (3), and use (13).

Finally, the third result follows from general results on logarithmic structures [2]. []

Remark. A subdominant term in [square root of (1 - ze)] occurs in the expansion of C(z), but has no influence on the asymptotic results. They would be the same (with possibly different constants) for any C(z) having a purely logarithmic singularity.

7 Excluding the bowtie: a singularity in [(1 - z/[rho]).sup.-1/2]

We now denote by A the class of graphs avoiding the bowtie (shown in Figure 1).

Proposition 13 Let T(z) = z[e.sup.T(z)] be the g.f. of rooted trees. The g.f. of connected graphs in A is

C(z) = [[T.sup.2](1 - T + [T.sup.2])[e.sup.T]/[1 - T]] + [1/2]log (1/[1 - T]) + [T(12 - 54T + 18[T.sup.2] - 5[T.sup.3] - [T.sup.4])/24(1 - T)].

As n [right arrow] [infinity],

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: This is the most delicate enumeration result of the paper. We have

C(z)= T(z) - T[(z).sup.2]/2 + [bar.C](T(z)),

where [bar.C](z) counts graphs with minimal degree 2 avoiding the bowtie. After studying the properties of these graphs, we conclude that they are either cycles, or [K.sub.4] with one edge possibly replaced by a chain of vertices of degree 2, or the graphs of Figure 2. Counting these various classes gives [bar.C](z), and thus C(z). []

Proposition 14 1. The mean and variance of [N.sub.n] satisfy:

E([N.sub.n]) ~ [(e - [5/4]).sup.2/3][n.sup.1/3], V([N.sub.n]) ~ [2/3][(e - [5/4]).sup.2/3][n.sup.1/3],

and the random variable [[N.sub.n] - E([N.sub.n])]/[square root of V([N.sub.n])] converges in law to a standard normal distribution.

2. For i [greater than or equal to] 0, the ith moment of [S.sub.n] satisfies, as n [right arrow] [right arrow],

E([S.sup.i.sub.n]) ~ [[GAMMA](i + [3/2])/[GAMMA](3/2)][(2[n.sup.2/3]/[(e - [5/4]).sup.2/3]).sup.i].

Consequently, the normalizedvariable [(e - [5/4]).sup.2/3][S.sub.n]/(2[n.sup.2/3]) converges in distribution to a gamma(3/2) law, of density 2[square root of x][e.sup.-x]/[square root of [pi]] on [0, [infinity]). A local limit law also holds: for x > 0 and k = [x[2[n.sup.2/3]/[(e - [5/4]).sup.2/3]]],

[2[n.sup.2/3]/[(e - [5/4]).sup.2/3]]P([S.sub.n] = k) ~ 2[square root of (x/[pi])][e.sup.-x].

8 When trees dominate: C(z) converges at [rho]

Let A be a decomposable class of graphs (for instance, a class defined by excluding connected minors) with set of components C. Assume that C contains all trees (counted by T - [T.sup.2]/2), and that

C(z)= T(z) - T[(z).sup.2]/2 + D(z), (15)

where D(z) has radius strictly larger than 1/e (the radius of T). We 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 limit of [c.sub.n]/[a.sub.n] is now smaller than 1/[square root of e].

Proposition 15 Assume A is dominated by trees. As n [right arrow] [infinity],

[c.sub.n] ~ n![[e.sup.n]/[square root of 2[pi]][n.sup.5/2]] and [a.sub.n] ~ A(1/e)[c.sub.n].

In particular, the probability that [G.sub.n] is connected tends to 1/A(1/e) = [e.sup.-1/2-D(1/e)].

The asymptotic behaviours of [N.sub.n], [L.sub.n] and [S.sub.n] are described by Proposition 2, with [rho] = 1/e.

Proof: The asymptotic behaviours of [c.sub.n] and [a.sub.n] are obtained via singularity analysis. For [N.sub.n], we can either start from (1) and apply singularity analysis, or use directly [4, Thm. 2]. For [S.sub.n], the two ingredients used in the proof of Proposition 2, namely smoothness of [a.sub.n]/n! and convergence of [c.sub.n]/[a.sub.n], still hold here. For [L.sub.n], we use the fact that the root component is with high probability the biggest one. []

We now give examples where trees dominate.

Proposition 16 Let k [greater than or equal to] 1. Let A be a minor-closed class of graphs containing all trees, but not the k-spoon (shown in Figure 1). Then A is dominated by trees, and the results of Proposition 15 apply.

Proof: We partition the set C of connected graphs of A into three subsets: the set of trees, counted by T - [T.sup.2]/2, the set [C.sub.1] of unicyclic graphs (counted by [C.sub.1]), and finally the set [C.sub.2] containing graphs with at least two cycles (counted by [C.sub.2]). We prove that [C.sub.1] has radius strictly larger than 1/e, and that [C.sub.2] is entire. []

Proposition 17 Let [T.sub.k] be the g.f. of rooted trees of height less than k. That is, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] with [T.sub.1] = z. Let [A.sup.(k)] be the class of graphs avoiding the diamond, the bowtie and the k-spoon. Then (15) holds with

D(z) [equivalent to] [D.sup.(k)](z) = [1/2](log [1/[1 - [T.sub.k](z)]] - [T.sub.k](z) - [[T.sub.k][(z).sup.2]/2]).

The class [A.sup.(k)] is dominated by trees, and Proposition 15 applies. In particular, the probability that a random graph of [A.sup.(k).sub.n] is connected tends to [1/[A.sup.(k)]](1/e) as n [right arrow] [infinity]. This value tends to 0 as k increases.

By specializing the proof of Proposition 13, we have also counted graphs avoiding the 2-spoon.

Proposition 18 The g.f. of connected graphs avoiding the 2-spoon satisfies (15) with

D(z) = [1/2] (log [1/[1 - z[e.sup.z]]] - z[e.sup.z] - [[z.sup.2][e.sup.2z]/2]) + [[z.sup.4]/4!] + [z.sup.2][e.sup.2z]([e.sup.z] - 1 - z - [[z.sup.2]/4]).

9 Final comments

The nature of the dominant singularities of C(z) is clearly a central parameter of the class, as the quantities [N.sub.n] and [S.sub.n] seem to depend largely on it (see Table 1). Is it possible to determine the nature of this singularity from the properties of the excluded minors? For instance, C([rho]) is finite when all excluded minors are 2-connected, but Section 8 shows that this happens as well with non- 2-connected minors. Which excluded minors give rise to a simple pole in C(z)? to a logarithmic singularity? to a singularity in [(1 - [z/[rho]]).sup.-1/2]?

Other parameters. We have focussed on certain parameters that are well understood for 2-connected excluded minors. But others have been investigated in different contexts: the number of edges, the size of the largest 2-connected component, the distribution of vertex degrees [6, 8, 9, 12]. When specialized to the theory of minor-closed classes, these papers generally assume that all excluded minors are (at least) 2-connected. Including (some of) these parameters in our results may be the topic of future work.

Acknowledgements. KW would like to thank C. McDiarmid for many inspiring discussions as well as for constant support. We also thank J.-F. Marckert and B. Salvy for pointing out Refs. [2] and [15].

References

[1] L. Addario Berry, C. McDiarmid, and B. Reed. Connectivity for bridge-addable monotone graph classes. Combin. Probab. Comput., 21(6):803-815, 2012. ArXiv:1110.0009.

[2] R. Arratia, A. D. Barbour, and S. Tavare. Logarithmic combinatorial structures: a probabilistic approach. EMS Monographs in Mathematics. European Mathematical Society (EMS), Zurich, 2003.

[3] C. Banderier, P. Flajolet, G. Schaeffer, and M. Soria. Random maps, coalescing saddles, singularity analysis, and Airy phenomena. Random Structures Algorithms, 19(3-4):194-246, 2001.

[4] J. P. Bell, E. A. Bender, P. J. Cameron, and L. B. Richmond. Asymptotics for the probability of connectedness and the distribution of number of components. Electron. J. Combin., 7:RP 33, 2000.

[5] E. A. Bender. Asymptotic methods in enumeration. SIAMRev., 16:485-515, 1974.

[6] N. Bernasconi, K. Panagiotou, and A. Steger. The degree sequence of random graphs from subcritical classes. Combin. Probab. Comput., 18(5):647-681, 2009.

[7] M. Bousquet-Melou and K. Weller. Asymptotic properties of some minor-closed classes of graphs. ArXiv:1303.3836, 2013.

[8] M. Drmota, E. Fusy, M. Kang, V. Kraus, and J. Rue. Asymptotic study of subcritical graph classes. SIAMJ. Discrete Math., 25(4):1615-1651, 2011.

[9] M. Drmota, O. Gimenez, and M. Noy. Degree distribution in random planar graphs. J. Combin. Theory Ser. A, 118(7):2102-2130, 2011.

[10] M. Drmota, B. Gittenberger, and T. Klausner. Extended admissible functions and Gaussian limiting distributions. Math. Comp., 74(252):1953-1966 (electronic), 2005.

[11] P. Flajolet and R. Sedgewick. Analytic combinatorics. Cambridge Univ. Press, Cambridge, 2009.

[12] O. Gimenez, M. Noy, and J. Rue. Graph classes with given 3-connected components: Asymptotic enumeration and random graphs. Random Structures Algorithms, to appear.

[13] X. Gourdon. Largest component in random combinatorial structures. Discrete Math., 180(1-3):185-209, 1998.

[14] M. Kang and K. Panagiotou. On the connectivity of random graphs from addable classes. J. Combin. Theory Ser. B, 103(2):306-312, 2013.

[15] A. J. Macintyre and R. Wilson. Operational methods and the coefficients of certain power series. Math. Ann., 127:243-250, 1954.

[16] C. McDiarmid. Random graphs from a minor-closed class. Combin. Probab. Comput., 18(4):583-599, 2009.

[17] C. McDiarmid, A. Steger, and D. J. A. Welsh. Random planar graphs. J. Combin. Theory Ser. B, 93(2):187-205, 2005.

[18] S. Norine, P. Seymour, R. Thomas, and P. Wollan. Proper minor-closed families are small. J. Combin. Theory Ser. B, 96(5):754-757, 2006.

[19] N. Robertson and P.D. Seymour. Graph minors I-XX. J. Combin. Theory Ser. B, 1983-2004.

[20] E. M. Wright. The number of connected sparsely edged graphs. J. Graph Th., 1(4):317-330, 1977.

Mireille Bousquet-Melou (1), ([dagger]) and Kerstin Weller (2)

(1) CNRS, LaBRI, UMR 5800, University de Bordeaux, 351 cours de la Liberation, 33405 Talence Cedex, France

(2) Department of Statistics, University of Oxford, 1 South Parks Road, Oxford, OX1 3TG, United Kingdom

([dagger]) Both authors were partially supported by a CNRS-Oxford collaboration scheme, 2012
COPYRIGHT 2013 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2013 Gale, Cengage Learning. All rights reserved.

 
Article Details
Printer friendly Cite/link Email Feedback
Author:Bousquet-Melou, Mireille; Weller, Kerstin
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUUK
Date:Jan 1, 2013
Words:5809
Previous Article:Kazhdan-Lusztig polynomials of boolean elements.
Next Article:EL-labelings and canonical spanning trees for subword complexes.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters