Printer Friendly

Blocks in constrained random graphs with fixed average degree.

1 Introduction

In the early 60's Erdos and Renyi (5) introduced the random graph [G.sub.n,M], which is obtained by adding M random edges to an initially empty graph with n labeled vertices. Since then, the [G.sub.n,M] has been studied extensively, and in the meanwhile there have been thousands of papers devoted to the analysis of its typical properties. One property that has been of particular interest is the evolution of [G.sub.n,M]. Of course, when M = 0 then [G.sub.n,M] is just the empty graph, and when M = ([??]) then [G.sub.n,M] is the complete graph--but are there critical values in between where interesting changes happen? The answer is yes, and many such critical values of M have been discovered. Let us mention here only an example (the famous "phase transition"), and we refer the reader to the excellent monograph (3) of Bollobas for many other exciting results. Let M = cn. If c < 1, then [G.sub.n,M] has with high probability (i) connected components of size O(log n). On the other hand, if c > 1, then the largest connected component of [G.sub.n,M] containts whp [THETA](n) vertices, and the second largest component contains only O(log n) vertices. In other words, the connectivity structure of [G.sub.n,M] changes dramatically when we "pass" the critical value c =1.

Much less is known if we turn our attention to graph classes with structural constraints, like for example planar graphs. How different does a random planar graph with 3/2n edges look like from a random planar graph with 5/2n edges? In (11) the authors Gerke, McDiarmid, Steger and Weissl showed that for all m = [cn], where 1 < c < 3, a random planar graph with m edges contains linearly many copies of any given planar graph. Moreover, they showed that the probability of connectedness is bounded away from 0 and 1. Except of these results we currently have only very sparse information about how the evolution of a random planar graph does look like, and how random planar graphs with fixed average degree typically behave.

The goal of this paper is to present a unified analytic framework, which allows us to make precise statements about random graphs with fixed average degree drawn from a specified graph class. Our framework includes specifically the classes of labeled outerplanar, series-parallel, and planar graphs, and more generally every class for which we have sufficient information about the generating function enumerating this class. The parameter that we will study here is the block structure. Denote for any graph G by 6(^; G) the number of blocks, i.e. maximal biconnected subgraphs, that contain exactly I vertices in G, and abbreviate [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, denote by /6(G) the number of vertices in the largest block of G. Let C be a graph class, and let [C.sub.n,m] be a random graph from C with n vertices and m edges. We shall show that whp Cn m belongs to one of the following categories, which differ vastly in complexity:

* lb([C.sub.n,m]) [~.sub.n] cn, where c = c(C) > 0 is given explicitly, and the second largest block contains [n.sup.[alpha]] vertices, where [alpha] = [alpha](C) < 1 (where x [~.sub.n] y means x = (1 + o(1))y for large n), or

* lb([C.sub.n,m]) = O(log n).

Moreover, we will show sharp concentration results for the quantities b(l; [C.sub.n,m]) for all 2 [less than or equal to] l [less than or equal to] n. As a corollary we will obtain that for all c [member of] (1,3) random planar graphs with [cn] edges belong to the first category, while random outerplanar and series-parallel graphs with fixed average degree belong to the second category. Finally, we will demonstrate that there are graph classes such that there a exists a critical density co where the category to which a random graph with cn edges belongs to is different for c > [c.sub.o] and c < [c.sub.o]. We shall discuss this and related issues in more detail later.

Before we present our results in detail we need a technical definition. For any set C of complex numbers and any [delta] > 0 let N(C, [delta] ) be the set of all complex numbers that are closer than [delta] to some point of C. We shall say that a function F(x, y) is of algebraic type for y in a compact subset S of (0, + [infinity]) if there exist [delta] > 0 and 0 < [theta] 6 < [pi]/2 such that

F(x,y) = P(x,y) + [(1 - x / [rho](y)).sup.[alpha]] x (g(y) + E (x,y)), (1)

where

* P(x, y) is a polynomial,

* g(y) is analytic in N(S, [delta]), and g(y) [not equal to] 0,

* [rho](y) has continuous third partial derivatives in N(S, [delta]), and [alpha] [not member of] Z [less than or equal to] 0,

* E(x, y) is analytic in [DELTA] \ {[rho](y)} and E(x, y) = o(1) as x [right arrow] [rho](y) uniformly for all y [member of] N(S, [delta]),

where

[DELTA] A = {z : [absolute value of z] [less than or equal to] [rho](y) + [delta] 6, [absolute value of arg(z - [rho](y))] [greater than or equal to] - [theta]}.

Functions of the algebraic type are commonly encountered in modern analytic combinatorics, and the above assumptions, although quite technical, are needed to unfold the full power of the available machinery. We refer the reader to Flajolet's and Sedgewick's book (7) for an excellent treatment and numerous applications. All functions that we shall consider in this work are of algebraic type.

The following definition describes precisely the graph classes that will be of interest in this paper, and is a generalization of a similar definition in (13).

Definition 1 Let C be a class of labeled connected graphs and let B [subset] C be the class of biconnected graphs in C. The class C is called nice if it has the following two properties.

(i) Let C [member of] C and B [member of] B. Then the graph obtained by identifying any vertex of C with any vertex from B is in C. Moreover, all graphs in C \ B can be constructed in such a way. Finally, the graph consisting of a single isolated vertex is in C.

(ii) Let B(x, y) be the exponential generating function enumerating the graphs in C, where x marks the vertices, and y marks the edges. Then [partial derivative] / [partial derivative]x B(x, y) is of algebraic type for y [member of] [0, + [infinity]), where we will write R(y) := [rho](y), [[alpha].sub.B] := a, and [g.sub.B] (y) := g(y).

The following statement says that the egf enumerating a nice class is also of algebraic type. We will use it without any further reference.

Proposition 1 Let C be a nice class, and let SC be a subinterval of [S.sub.B] such that for all y [member of] [S.sub.C] it holds R(y)B" (R(y), y) [not member of] 1. Then x [partial derivative] / [partial derivative]x C (x, y) is of algebraic type in SC.

In the proposition above we show that [partial derivative] / [partial derivative]x C (x, y), which is the exponential generating function enumerating vertex-rooted graphs from C, is of algebraic type. We do this solely for technical convenience (instead of making a similar statement for C(x, y)): in what follows, we will study asymptotic properties of random graphs from [C.sub.n], which do not depend on the root label. Hence, as there are exactly n distinct ways to root each graph in [C.sub.n], any random variable defined on rooted graphs from [C.sub.n] will be identically distributed with the corresponding random variable defined on graphs from [C.sub.n].

Let us define some important notation that we shall use in the remainder of the paper without any further reference. We will denote by R, [rho] the singularities of [partial derivative] / [partial derivative] x B(x, y) and x [partial derivative] / [partial derivative]x C(x, y), and by [[alpha].sub.B], [alpha] the critical exponents of the corresponding singular expansions (see (1)). Finally, we will write [g.sub.B] ,g for the function g in the definition (1), for [partial derivative]x B (x, y) respectively x [partial derivative] / partial derivative]x C (x, y).

In order to formulate our main result we need one additional technical definition. For any function f (u) we will write [[partial derivative].sub.u]f(u) = d/du f(u). Given a such a function f (u), which is analytic at u = 1 and assumed to satisfy f (1) [not equal to] 0, we set

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

Theorem 1 Let C be a nice class. Suppose that for all [beta] [member of] [S.sub.C]

* v([[rho].sub.[beta]]) [not equal to] 0, where [[rho].sub.[beta](y): = [rho]([beta]y) and

* [[rho].sub.[beta](1) < [absolute value of [[rho].sub.[beta]](u)] for all u [member of] {z | [absolute value of z] = 1 z [not member of] N (S, [[delta]}

Let m = [??]-[beta] [rho]'([beta])/[rho]([beta]) n + [beta]g' ([beta])/[g([beta])[??], and let [C.sub.n, m] be a random graph from [C.sub.n, m]. Let c([beta]) = R([beta])B"(R([beta]), [beta]).

Then the following is true with high probability.

(I) If c([beta]) > 1 then let 0 < [tau]([beta]) < R([beta]) be given by [tau]B"([tau],[beta]) = 1, and set [xi](([beta]) = [tau]([beta])/R([beta]).

Then we have for all [epsilon] > 0:

1. lb([C.sub.n, m]) [less than or equal to] ([absolute value of [alpha]] + [epsilon]) [log.sub.1/[xi]([beta])] n.

2. b(l; [C.sub.n,m) ~ [b.sub.l]n for all 2 [less than or equal to] l [less than or equal to] (1 - [epsilon]) [log.sub.1 / [xi]([beta]) n, where

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

3. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

(II) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (4)

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (5)

Let us discuss a few implications of the theorem above. Exploiting the results in (12) we obtain as a corollary the following result for random planar graphs with fixed average degree.

Corollary 1 Let [P.sub.n,m] be a graph drawn uniformly at random from the set of all labeled connected planar graphs with n vertices and m edges, where m = [cn] and c [member of] (1,3). Then [P.sub.n,m] is with high probability of type (II).

By applying the results in (2) we obtain statements about random outerplanar and series-parallel graphs.

Corollary 2 Let [O.sub.n,m] be a graph drawn uniformly at random from the set of all labeled connected outerplanar graphs with n vertices and m edges, where m = [cn] and c [member of] (1,2). Then [O.sub.n,m] is with high probability of type (I). The same is true for random series-parallel graphs.

One natural question that arises in the context of Theorem 1 is the following: is there a nice graph class such that there a exists a critical density [c.sub.0] where the type of a random graph with cn edges is different for c > [c.sub.0] and c < [c.sub.0]? The following result gives an affirmative answer.

Theorem 2 Let B be the class of biconnectedplanar graphs, and set [??] = B [union] {[K.sub.8]}, where [K.sub.8] is the complete graph with 8 vertices. Then the class C in which every graph contains blocks only from B is nice, and there is a [c.sub.0] [approximately equal to] 3.9995 such that

* if c > [c.sub.0], then [[??].sub.n[cn]] is with high probability of type (I),

* if c < [c.sub.0], then [[??].sub.n[cn]] is with high probability of type (II).

In fact, classes with two critical densities can be constructed, such that the type is different in each two neighboring intervals. We do not give the explicit construction here, but these graph classes seem to be very artificial. This raises the following questions. First, are there graph classes with arbitrarily many critical densities? And second, are there natural classes with more than one critical density? The definition of the term "natural" is of course a matter of taste--a possible candidate would be to require the class to be hereditary, i.e., closed under taking subgraphs.

Remark The discussion in this paper can easily be adapted to cover an even wider class of functions. Following (10), we say that a function is of algebraic-logarithmic type, if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where, in addition to the properties of (1), [alpha](y) and [beta](y) have continuous third partial derivatives in N(S, [delta]). With a little more technical work, and using the local limit theorems provided in (10), a more general version of Theorem 1 can be proved. We leave the straightforward but tedious details to the reader.

Notation We shall fix some additional notation that we will use throughout without further reference. Let G be any graph. We will denote by [v.sub.G] the number of vertices in G, and by [e.sub.G] the number of edges in G. Moreover, for a graph class C we will denote by [C.sup.*] the class that contains vertex-rooted graphs from C, i.e., pairs (C, v), where C e C, and v is a vertex of C. Finally, we will denote by [C.sub.*](x, y) the egf for [C.sup.*], i.e., [C.sup.*](x,y) = x [partial derivative] / [partial derivative]x C(x,y).

2 Preliminaries

In this section we collect some well-known facts and make some observations that we will exploit later. The following theorem gives us information about the coefficients of algebraico-logarithmic functions.

Theorem 3 ((6)) Let F (x, y) be as in (1). Then, uniformly for y [member of] N (S, [delta]),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where [GAMMA](z) = [[integral].sup.[infinity].sub.0] [t.sup.z-1] [e.sup.-t] dt denotes the Gamma-function.

The next statement describes an important combinatorial property of nice graph classes, and is taken from (13). Let us introduce some notation first. We denote by Z the graph class consisting just of one graph that contains a single labeled vertex. For two graph classes X and Y, we write "G = X x Y" if there is a 1-1 correspondence between the graphs in G and the class formed by the cartesian product of X and Y, followed by a relabeling step, so as to guarantee that all labels are distinct for an object in X x Y. Moreover, Set(X) is the class in which every graph can be represented by set of graphs in X. Finally, the class X o Y consists of all graphs that are obtained from graphs from X, where each vertex is replaced by a graph from Y. This set of combinatorial operators (cartesian product, set, and substitution) appears frequently in modern theories of combinatorial analysis (4; 7), as well as in systematic approaches to random generation of combinatorial objects (4; 8). For a very detailed description of these operators and numerous applications we refer to (7) and further references therein.

Lemma 1 Let C be a graph class having property (i) of Definition 1. Then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

2.1 Central & Local Limit Theorems

Let ([p.sub.n,k])n>1] be a sequence of discrete probability distributions with mean [[mu].sub.n] and standard deviation an. We say that the [p.sub.n,k] obey a central limit theorem (CLT) if there is a sequence [[epsilon].sub.n] [right arrow] 0 such that

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

Note that a central CLT gives us very precise information about the (cumulative) distribution of the sequences [p.sub.n,k]. However, in general it fails to give us information about the individual probabilities. In this case we are interested in a local limit theorem (LLT), which shows pointwise convergence. More precisely, the sequence ([p.sub.n,k)n [greater than or equal to] 1] is said to obey a LLT if there is a sequence [[epsilon].sub.n] [right arrow] 0 such that

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

The statement below provides us with a CLT in a general setting, that is commonly encountered in the context of analytic combinatorics.

Theorem 4 (7, Theorem IX.8) Let ([X.sub.n)n [greater than or equal to]1] be a sequence of discrete random variables supported by N, with associated probability generating functions [p.sub.n](u). Assume that, uniformly in a fixed complex neighborhood [OMEGA] of 1, for sequences [[beta].sub.n], [[kappa].sub.n] [right arrow] + [infinity], there holds

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where A(u), B(u) are analytic at u = 1, and A(1) = B(1) = 1. Moreover, assume that v(B)[not equal to] 0. Then, [X.sub.n] satisfies a CLT with [[epsilon].sub.n] = O([[kappa].sup.-1.sub.n] + [[beta].sup.1/2.sub.n]), and

[mu].sub.n] = [[beta].sub.n]m(B)+ m(A) + O([[kappa].sup.-1.sub.n])

[[sigma].sup.2.sub.n] = [[beta].sub.n] b(B) + v(A)+ O([[kappa].sup.-1.sub.n]).

Under a very light additional technical assumption, a similar LLT theorem can be shown. This assumption will be fulfilled in all our applications, and is typical in the context of analytic combinatorics.

Theorem 5 (7, Theorem IX.14) Suppose that a random variable satisfies all conditions of Theorem 4. Moreover, assume the existence of a uniform bound

[absolute value of [p.sub.n](u)][less than or equal to] [K.sup.-[beta].sub.n] (8)

for some K > 1 and all u [member of] {[absolute value of z] = 1 | z [not member of] [OMEGA]}. Then, [X.sub.n] satisfies a LLT with [[mu].sub.n], [[sigma].sub.n] and [[epsilon].sub.n] as given in Theorem 4.

2.2 Bounding Tail Probabilities

In our proofs we will often bound the probability that certain random variables assume values far away from their expectation. The next lemma states the well-known Chernoff bounds.

Lemma 2 Let X be a binomially distributed variable. Then, for every 0 < [epsilon] < 1 we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The same bounds are true for Poisson distributed random variables. Lemma 3 Lemma 2 is true when X is distributed like a Poisson variable.

3 Sampling & Asymptotics

Let C be a nice graph class such that [C.sup.*] (x, y) is of algebraic type in a compact set S [subset or equal to] (0, + [infinity]). Recall that for every fixed y [member of] S the quantity [rho](y) denotes the singularity of [C.sup.*] (x, y). Set

[[lambda].sub.c] (y) = B'([C.sup.*]([rho](y),y),y), (9)

where B(x, y) is the exponential generating function enumerating the biconnected graphs in C. Note that a priori it is not clear whether [[lambda].sub.c] (y) exists for all y [member of] S. However, as we shall argue later, the existence is an inherent property of nice classes. Moreover, let [GAMMA]B'(x, y) be a randomized algorithm that generates graphs from B' according to the following distribution:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], (10)

provided that B'(x, y) exists. The above distribution is called the Boltzmann distribution (or Gibbs distribution), and was introduced in the context of the random generation of combinatorial objects by Douchon, Flajolet, Louchard and Schaeffer in 2004, see (4). With this notation consider the following algorithm.
[LAMBDA][C.sup.*] (3) : [gamma] [left arrow] a single node r
                        k [left arrow] Po([[lambda].sub.c]([beta])) (*)
                        for j = 1,..., k
                          [gamma]' [left arrow][GAMMA]B'([C.sup.*]
                            ([rho]([beta]),([beta]), ([beta]), discard
                            the labels of [gamma]'                 (**)
                          [gamma] [left arrow] merge [gamma] and
                            [gamma] at their roots
                        for each vertex v [not equal to] r of [gamma]
                          [gamma].sub.v] [right arrow] [GAMMA][C.sup.*]
                            ([beta]), discard the labels of [[gamma].
                            sub.v]
                        replace all nodes v = [not equal to] of [gamma]
                          with [[gamma].sub.v]
                        return [gamma], where the vertices are labeled
                          uniformly at random


A similar version of this algorithm, for the special case [beta] = 1, was studied already in (13). There the authors determined the number of blocks in random graphs with constraints, but they did not consider any restriction on the average degree. Here we are interested in general [beta], which makes the analysis more involved. The following lemma will be one of the main tools in our analysis, and says that with some reasonable probability the algorithm above will output a graph from [C.sup.*.sub.n,m], for a very specific m = m([beta]).

Lemma 4 Let C be a nice graph class satisfying the assertions of Theorem 1. For any [beta] [member of] [S.sub.C] there is a c > 0 such that

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

Proof: The proof consists of three parts. First, we will show that [GAMMA][C.sup.*] is well-defined for any [beta] [member of] [S.sub.C], i.e., we will show that [[lambda].sub.c]([beta]) and B'([C.sup.*]([rho]([beta]), [beta]), [beta]) exist. Second, we argue that for any [gamma] [member of] [C.sup.*]

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

Finally, we show that there is a constant C > 0 such that

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

Putting all three facts together proves then the statement. To see the first claim, apply Lemma 1 and note that [psi](u) = [ue.sup.-B'(u,y)] is the functional inverse of [C.sup.*](x, y). Let R(y) be the singularity of B'(x, y). By the Analytic and Singular Inversion Lemmas in (7, Lemma IV.2 and IV.3), for any y [member of] [S.sub.c], the singularity of [C.sup.*](x, y) depends on whether [psi](u) is strictly monotone:

* if there is a unique 0 < [tau] (y) < R(y) such that [psi]'([tau](y)) = 0, or equivalently, [tau](y)B"([tau](y),y) = 1, then [rho](y) = ^(t(y)) and [C.sup.*]([rho](y),y) = [tau](y).

* Otherwise, [psi] is strictly monotone in [0, R(y)), and then [rho](y) = [psi](R(y)) = R(y)[e.sup.-B'(R(y)>y)]. Moreover, we have in this case R(y)B"(R(y),y) [less than or equal to] 1 and [C.sup.*] (p(y), y) = R(y).

Note that in both cases we have [C.sup.*]([rho](y),y) < [infinity]. Moreover, in the first case we obviously have [C.sup.*](p(y),y) < R(y), which implies that AC(y) and B'([C.sup.*]([rho](y),y),y) are well-defined. Finally, in the second case we have that B"(R(y), y) < [infinity], as R(y) > 0. But then, also B'(R(y), y) < [infinity] is true, which implies that also in this case [[lambda].sub.c](y) and B'([C.sup.*]([rho](y), y), y) are well-defined. This completes the proof of the first part.

The identity (12) follows directly from the composition rules for Boltzmann samplers in (9) and (4), and the decomposition of nice classes provided in Lemma 1. To prove (13) consider the function Cp (x, y) = [C.sup.*](x, [beta]y), and note that for any y such that [[beta]y [member of] [S.sub.c] its singularity is given by [[rho].sub.[beta]](y) = [rho]([beta]y). Now, consider a random variable X with probability generating function

[p.sub.n](u) =[[x.sup.n][C.sub.[beta]](x,u) / [[x.sup.n][C.sub.[beta]](x,1]),

and note that

[[u.sup.s]][p.sub.n](u) = Pr[X = s] = [absolute value of [C.sup.*.sub.n,s] 1 / n! x [[beta].sup.s] / [x.sup.n][C.sub.[beta]] (x,1). (14)

In the remainder we will estimate [[u.sup.s]][p.sub.n](u) and [[x.sup.n]][C.sub.[beta]](x, 1) directly, which will yield (13). By applying Theorem 3 we obtain uniformly for u such that [[beta].sub.u] [member of] [S.sub.c]

[P.sub.n](u) ~ g([beta]u) / g([beta])[([[rho].sub.[beta]](1) / [[rho].sub.[beta]](u)).sup.n.]

Note that the assertions of Theorem 4 are fulfilled, if we choose A(u) = g([beta]u) / g([beta]), B(u) = [[rho].sub.[beta](1) / [[rho].sub.[beta](u) and [[kappa].sub.n] = [omega](1), due to our assumptions. Moreover, from our assumptions follows that [[absolute value of [[rho].sub.[beta](u)] = [absolute value of [rho]([[beta]u)] > [rho]([beta]) = [[rho].sub.beta]](1) for u [member of] {z | [absolute value of z] = 1,z [member of] N(S, [delta])}, and we may infer that there is a K > 1 such that for all such u

[P.sub.n](u) < [K.sup.-n].

All in all, the assertions of Theorem 5 are fulfilled, and we may conclude that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where

E [X] = nm(B) + m(A) + o(1) = -[beta][rho]'([beta]) / [rho]([beta])n + [beta]g'([beta]) / g([beta])+ o(1),

and [[sigma].sub.n] = Var [[X.sub.n]] = nb(B) + b(A). This calculations determine the left-hand side of (14). Moreover, by applying Theorem 3 to the expansion of [C.sub.[beta]] (x, 1) = [C.sup.*](x, [beta]) we readily obtain that there is a constant C' > 0 such that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

By plugging this and the above estimate for Pr [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] into (14) we obtain (13).

The following lemma is essentially taken from (13), where the special case [beta] = 1" was considered. As the proof is completely analogous, we refer the reader to (13). Before we state it let us introduce a little additional notation. We follow an approach first used in (14; 1) and consider a sampler that simulates an execution of [GAMMA][C.sup.*]. Observe that VC* makes twice a random choice: first, when it chooses a random value according to a Poisson distribution in the line marked with (*), and second, when it calls VB' in the line marked with (**). We now consider an algorithm that takes as input a sequence of non-negative integers and a sequence of graphs from B' and uses them instead of making the random choices. More precisely, let K be an infinite sequence of numbers in [N.sub.0], and let B' be an infinite sequence of graphs from B'. Then the algorithm [GAMMA][C.sup.*]([beta]; K, B'), which simulates the execution of [GAMMA][C.sup.*] by using the next unused value from the provided lists, generates obviously every graph from [C.sup.*] with the same probability as [GAMMA][C.sup.*], provided that the values in K and the graphs B' are generated independently and according to the appropriate probability distributions. In the sequel we will therefore assume that the notation [GAMMA][C.sup.*]([beta]) in fact denotes the sampler [GAMMA][C.sup.*]([beta]; K, B'), where we often will omit the lists (K, B').

Lemma 5 Let K = {[k.sub.1], [k.sub.2], ... } bean infinite sequence of non-negative integers and let B' = {[B'.sub.1], [B'.sub.2],...} be an infinite sequence of graphs from B'. Suppose that [GAMMA][C.sup.*]([beta]; K, B') used the first n values in K and the first m graphs in B' to generate a graph [gamma] [member of] [C.sup.*]. Then the following statements are true.

(1) n = [absolute value of [gamma].

(2) m = [summation].sup.n.sub.j] = 1] [k.sub.j].

(3) m = [summation].sub.l][greater than or equal to]2] b(l; [gamma]).

(4) For any l [greater than or equal to] 2 we have that b(l; [gamma]) = [absolute value of [less than or equal to] i [less than or equal to] m] [absolute value of B'.sub.i]| = l - 1].

4 Blocks With l Vertices in [C.sub.n,m]

Let [C.sub.n,m] be a graph with n vertices and m edges, drawn uniformly at random from [C.sub.n,m], where C is nice. First, we apply Lemma 5 to deduce some information on the number of not too "large" blocks.

Lemma 6 Let C be a nice class satisfying the assertions of Theorem 1. Let [beta] [member of] [S.sub.c], n [member of] N, and set m = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Moreover, let 0 < [epsilon] = [epsilon](n) < 1. For t [greater than or equal to] 2 define the quantities

[b.sub.l] = [[x.sup.l-1]]B'(x, [beta])* [[eta].sup.l-1] and [l.sub.0] = [l.sub.0](n,[epsilon]) = max {l | [b.sub.e] n [greater than or equal to] 50[[epsilon].sup.-2] [alpha] log n} .

Then we have for all 2 [less than or equal to] l [less than or equal to] [l.sub.0] and sufficiently large n

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

Proof: The proof is similar to the proof of the analogous lemma in (13, Lemma 3.1); the sole difference is that we have to deal here with the fixed number of edges. We give this proof in full detail.

Let l [member of] [2, [l.sub.0]] and let S [subset] [C.sub.n,m] denote the set of labeled graphs in [C.sub.n,m] whose number of blocks of size t is not in the interval (1 [+ or -] [epsilon]) [b.sub.l]n. Using Lemma 4 we obtain that there exists a constant [??] > 0 such that for all large enough n we have

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

We write S = [S.sub.1] [union] [S.sub.2], where [S.sub.1] contains all graphs that satisfy [[summation].sub.l[greater than or equal to]2] b(l;G) [not member of] (1 [+ or -] [epsilon]/3)[[lambda].sub.C]([beta])n, and [S.sub.2] = S\[S.sub.1]. By using Lemma 5, statements (1)-(3), the event "[GAMMA][C.sup.*] [member of] [S.sub.1] and [GAMMA][C.sup.*] [member of] [C.sup.*.sub.n,m]" implies that the sum of n independent variables distributed like Po([[lambda].sub.C]([beta])) is not in (1 [+ or -] [epsilon]/3)[[lambda].sub.C]([beta])n. But this probability is easily seen to be less than [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], by applying Lemma 3.

Moreover, again by Lemma 5, this time Statement (4), the event "[GAMMA][C.sup.*] [member of] [S.sub.2] and [GAMMA][C.sup.*] [member of] [C.sup.*.sub.n,m]" implies that a sequence of N = (1 [+ or -] [epsilon]/3) [[lambda].sub.C]([beta])n independent random graphs, which are drawn from B' according to the distribution (10) with parameters x = [C.sup.*]([rho](beta), [beta]) = [eta] and y = [beta], contains less than (1 - [epsilon])[b.sub.l]n or more than (1 + [epsilon])[b.sub.l]n graphs with l - 1 non-virtual vertices. The probability that a single such random graph has exactly l - 1 non-virtual vertices is precisely

[t.sub.l] := [[x.sup.l-1]] B'(x, [beta]) x [[eta].sup.l-1]/B'([eta], [beta]). (17)

Hence, by applying the Chernoff bounds from Lemma 2 we deduce that the number of graphs with l - 1 non-virtual vertices among N independently drawn random graphs is less than (1 - [epsilon]/3)[t.sub.l]N or more than (1 - [epsilon]/3)[t.sub.l]N with probability at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. The proof completes with N [member of] (1 [+ or -] [epsilon]/3)[[lambda].sub.C]([beta])n, as [GAMMA][C.sup.*] [member of] [S.sub.2], and the assumptions on [l.sub.0] and [epsilon].

Lemma 7 Let C be a nice class satisfying the assertions of Theorem 1. Let [beta] [member of] [S.sub.C], n [member of] N, and set m = [??]- [beta][rho]'([beta])/[rho]([beta])n + [beta]g'([beta])/g([beta])[??]. Moreover, let 0 < [epsilon] = [epsilon] (n) < 1. For l [greater than or equal to] 1 and [delta] > 1 define the quantities

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Set [l.sub.0] = [l.sub.0]([delta]) = max {l | [b.sub.l[delta]n [greater than or equal to] 50[[epsilon].sup.- 2][[alpha][alpha].sub.B] log n}. If R([beta])B"(R([beta]), [beta]) < 1, then we have for all 1 << l [less than or equal to] [l.sub.0] and sufficiently large n for a graph [C.sub.n,m] drawn uniformly at random from [C.sub.n,m]

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Proof: Note that R([beta])B"(R([beta]), [beta]) < 1 implies that [eta] = R([beta]) (see e.g. the discussion after (13)), and that d. Now, by using exactly the same arguments as in Lemma 6 we can prove the first claim; the sole modification has to be made in (17), where we use [t.sub.l] = [b.sub.l,[delta]] instead. To see the second claim we apply Theorem 3 to the singular expansion of B', and use straightforward Euler-McLaurin summation.

Lemma 8 Let C be a nice class satisfying the assertions of Theorem 1. Let [beta] [member of] [S.sub.C], n [member of] N, and set m = [??]- [beta][rho]'([beta])/[rho]([beta])n + [beta]g'([beta])/g([beta])[??]. If R([beta])B"(R([beta]), [beta]) < 1, then for sufficiently large n we have asymptotically almost surely for a graph [C.sub.n,m] drawn uniformly at random from [C.sub.n,m] that lb([C.sub.n,m]) ~ c([beta])n, where

c([beta]) = 1 - R([beta])B"(R([beta]), [beta]).

Moreover, let [[omega].sub.n] be a function satisfying [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, for all [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] we have b(l; [C.sub.n,m]) = 0.

Proof: The proof proceeds in two steps: first, apply Lemmas 6 and 7 to count the number of vertices in blocks with size at most [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Then, show by tedious but straightforward counting that the most probable case is that the remaining vertices form exactly one block. The details are similar to the details in the proof of Lemma 3.4 in (13), and are omitted due to space limitations.

5 Graph Classes With Critical Densities

In this section we shall prove Corollary 1 and Theorem 2. Let us recall a few basic facts from (12). Let B(x, y) be the egf enumerating biconnected labeled planar graphs, and let C(x, y) be the egf enumerating labeled connected planar graphs. In (12) the authors showed that B'(x, y) and [C.sup.*](x, y) are of the algebraic type for y [member of] (0, [infinity]), where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and they also gave explicit expressions for R(y), [B.sub.2](y), [B.sub.4](y) and [B.sub.5](y). Moreover, they showed that ((12, Claim 2)) for all y [member of] (0, [infinity]) it holds R(y)B"(R(y), y) = 2[B.sub.4](y)/R(y) < 1. With those facts at hand Corollary 1 follows immediately.

Now we turn to the proof of Theorem 2. Recall that we set [??] = B [union] {[K.sub.8]}. Note that the singularity of [??]C(x, y) is the same as the singularity of B(x, y), i.e., R(y). Observe that

R(y)[??]"(R(y),y) = 2[B.sub.4](y)R(y) + R[(y).sup.7] [y.sup.28]/6!

Using the explicit expressions for all involved functions we readily obtain that for y e (0, y0) it holds R(y)[??]"(R(y),y) < 1, while for y [member of] ([y.sub.0], [infinity]) we have R(y)B"(R(y),y) > 1, where [y.sub.0] [approximately equal to] 25.671. Moreover, for y [member of] (0, [y.sub.0]) we have that

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII],

where the [[??].sub.i](y) are given as functions of the [B.sub.i](y) and R(y), and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. Additionally, for y [member of] ([y.sub.0], [infinity]) we obtain by applying Theorem VI.6 in (7)

[[??].sup.*] (x, y) ~ R(y) - [[??].sub.1](y) [(1 - x/[[rho].sub.2](y)).sup.1/2],

where [[rho].sub.2](y) = [tau](y)[e.sup.-B'([pi](y),y)], 0 < [tau](y) < R(y) is given by the solution of [tau](y)[??]"([tau](y), y) = 1, and [[??].sub.1](y) is analytically given. To obtain [c.sub.0] we determine [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. All numerical calculations performed in this section can be easily performed with MAPLE.

References

[1] N. Bernasconi, K. Panagiotou, and A. Steger. On properties of random dissections and triangulations. In SODA '08: Proceedings of the 19th annual ACM-SIAM symposium on Discrete algorithms, pages 132-141, 2008.

[2] M. Bodirsky, O. Gimenez, M. Kang, and M. Noy. Enumeration and limit laws for series-parallel graphs. European J. Combin., 28(8):2091-2105, 2007.

[3] B. Bollobas. Random Graphs. Cambridge University Press, 2001.

[4] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann samplers for the random generation of combinatorial structures. Combin. Probab. Comput., 13(4-5):577-625, 2004.

[5] P. Erdos and A. Renyi. On the evolution of random graphs. Mag. Tud. Akad. Mat. Kut. Int. Koozl., 5:17-61, 1960.

[6] P. Flajolet and A. Odlyzko. Singularity analysis of generating functions. SIAM J. Disc. Math., 3(2):216-240, 1990.

[7] P. Flajolet and R. Sedgewick. Analytic combinatorics. web edition, 811+xii pages (available from the authors web sites). To be published in 2008 by Cambridge University Press.

[8] P. Flajolet, P. Zimmerman, and B. Van Cutsem. A calculus for the random generation of labelled combinatorial structures. Theoret. Comput. Sci., 132(1-2):1-35, 1994.

[9] E. Fusy. Quadratic exact-size and linear approximate-size random generation of planar graphs. In 2005 International Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AD, pages 125-138 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2005.

[10] Z. Gao and L. B. Richmond. Central and local limit theorems applied to asymptotic enumeration. IV. Multivariate generating functions. J. Comput. Appl. Math., 41(1-2):177-186, 1992.

[11] S. Gerke, C. McDiarmid, A. Steger, and A. Weissl. Random planar graphs with n nodes and a fixed number of edges. In SODA '05: Proceedings of the 16th annual ACM-SIAM symposium on Discrete algorithms, pages 999-1007, Philadelphia, PA, USA, 2005.

[12] O. Gimenez and M. Noy. The number of planar graphs and properties of random planar graphs. In 2005 International Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AD, pages 147-156 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2005.

[13] K. Panagiotou and A. Steger. Maximal biconnected components in random planar graphs. To appear in: Proceedings of the 20th Annual ACM-SIAMSymposium on Discrete Algorithms (SODA 09), 2009.

[14] K. Panagiotou and A. Weissl. Properties of random graphs via boltzmann samplers. In 2007 International Conference on Analysis of Algorithms, Discrete Math. Theor. Comput. Sci. Proc., AH, pages 159-168 (electronic). Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2007.

Konstantinos Panagiotou

Max-Planck-Institute for Informatics, 66119 Saarbrucken, Germany

(i) whp, with probability tending to 1 when n [right arrow] [infinity]
COPYRIGHT 2009 DMTCS
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2009 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Panagiotou, Konstantinos
Publication:DMTCS Proceedings
Article Type:Report
Geographic Code:4EUGE
Date:Jan 1, 2009
Words:6612
Previous Article:Combinatorics of positroids.
Next Article:Noncrossing partitions and the shard intersection order.
Topics:

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