The Probability of Connectedness

Edward A. Bender

Department of Mathematics, University of California, San Diego

Algorithms Seminar

November 2, 1998

[summary by Bruno Salvy]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

A graph is a set of connected components. Graphs of various kinds are obtained by imposing constraints on these components. If cn is the number of different components of size n and an the number of graphs of size n, then cn/an is the probability that a graph selected uniformly at random among all graphs of size n is connected. The aim of this work is to study to what extent structural properties of the sequence {cn} make it possible to determine the asymptotic probability of connectedness (as the size n tends to infinity).

The asymptotic properties of cn/an are closely related to properties of the generating functions of these sequences. Two cases are to be considered. In the labelled case, the generating functions under study are
A(x)=
 
å
n³0
an
xn
n!
,     C(x)=
 
å
n³0
cn
xn
n!
and they are connected by
A(x)=exp(C(x)).     (1)
In the unlabelled case, the generating functions are
A(x)=
 
å
n³0
anxn ,     C(x)=
 
å
n³0
cnxn
and they are connected by
A(x)=exp ( C(x)+C(x2)/2+C(x3)/3+··· ) .     (2)
(See for instance [3] for a proof.) From the asymptotic point of view, these two identities are sufficiently close to make most of the proofs go through from one case to the other, with technical complications in the unlabelled case.
Example 1   General labelled rooted trees with n vertices are counted by nn-1. The exponential generating function is the tree function T(z) defined by
T(z)=zexp(T(z)).
The corresponding forests have generating function exp(T(z))=T(z)/z. The dominant singularity of T(z) is exp(-1) where the singularity is of square root type. Singularity analysis then shows that the asymptotic probability of connectedness is exp(-1).

Let R be the radius of convergence of the series C(x). In the unlabelled case, since the cn are integers, R£ Rmax=1, while Rmax=¥ in the labelled case. It is useful to distinguish three situations: R=0, C converges at R, or C diverges at R (which can be infinite). Defining
r
 
l
=
 
liminf
n®¥
cn/an ,     ru=
 
limsup
n®¥
cn/an,
the aim of this work is to study when rl=ru and to show as much as possible of Table 1.
  possible values for (rl,ru)
R=0 [0,1]×{1}
C divergent at R {0}×[0,1]
C convergent at R [0,1)×(0,1] with rl£ru

Table 1: Conjectured possibilities for (rl,ru)

A first result in this area is the following.
Theorem 1  [[5]]   A necessary and sufficient condition for asymptotic connectedness (rl=ru=1) is that R=0 and
n-1
å
i=1
hihn-i=o(hn)     (3)
where hn is any of an or cn.
Note that (3) is satisfied with hn=an if and only if it is satisfied with hn=cn.
Example 2  General undirected graphs with n vertices are enumerated by an=2n(n-1)/2 which accounts for all choices of edges. The theorem shows that cn~ an.
The remainder of this summary is devoted to proving parts of Table 1.

1   It is Always Possible that rl=0 and ru=1

This is shown by constructing an ad hoc sequence cn which is 1 for most n and very large at rare points. Then an tends to infinity so that rl=0 and ru=1 because for those large cn, an~ cn.

This idea might extend to obtain 0=rl<ru<1 by taking more frequent large cn in order to break the last equivalence.

2   Divergent Case: rl=0

This is a result of [4], which is proved as follows. If there exists d>0 such that cn>d an for all n sufficiently large, then we get for 0£ z<R
C(z)>d e
C(z)(+···)
 
+P(z),
where P is a polynomial and the dots indicate more positive terms that are present in the unlabelled case. In both cases, this inequality implies that C is convergent at R.

3   Convergent Case: ru>0 and rl<1

The second inequality is a consequence of Wright's theorem.

The first one can be proved as follows in the labelled case. Differentiating (1) and extracting coefficients yields
an
n!
=
1
n
n
å
k=0
k
ck
k!
an-k
(n-k)!
.
If cn=o(an), then cutting the sum at n1/2 and using ck£ ak in the first part shows that
[xn]A(x)=o([xn]A(x)2),
which implies divergence of A at R.

4   When rl=ru

The result is that every time (r,r) is present in Table 1, then there are sequences an and cn of nonnegative integers making this happen. The first two lines of the table are dealt with by exhibiting appropriate examples: general labelled graphs for the first one; partitions of sets for the other one in view of the asymptotics of Bell numbers.

In the convergent case, an important tool is the following theorem.
Theorem 2   In the convergent case, if lim cn-1/cn exists (then it is R) and åk=wn-wckcn-k=o(cn) for any w(n)®¥, then rl=ru=1/A(R).
We first show how this theorem is used to prove that every rÎ(0,1) is reached in the labelled case. The principle is to construct a sequence of generating functions C[i](x) such that the coefficients j![xj]C[i](x) are nonnegative integers for 0£ j<i and the value of lim an[i]/cn[i] is r. Start with
C[0](x)=aå
(x/R)n
n2
.
Then by the theorem, r=exp(-ap2/6), which fixes a. To construct C[k+1] from C[k], the coefficient of k!xk is replaced by its integer part, and the coefficient of xk+1 is increased to keep r unchanged. The increase is at most R-1/k! which is sufficiently small compared to its original value so that the conditions of the theorem still hold. Therefore the limit C[¥] also satisfies the theorem. A similar argument gives the unlabelled case.

Proof.[Proof of the theorem] In the labelled case, the hypothesis is used in an induction on d to obtain the following asymptotic estimates and bounds on cn(d)=[xn]C(x)d: The conclusion follows from there by extracting the coefficient of xn in A(x)=åC(x)d/d!.

A proof in the unlabelled case is given in [2].


5   Conclusion

Many properties related to connectedness can be deduced from very little information on the counting sequence of the connected components. Much more than indicated here is known if extra smoothness conditions on the sequence are satisfied. Also, results regarding the limiting distribution are known. We refer to [2] for details. Still, a large part of Table 1 remains unproved, mostly regarding the existence of structures with the announced (rl,ru).

References

[1]
Bender (E. A.), Cameron (P. J.), Odlyzko (A. M.), and Richmond (L. B.). -- Connectedness, classes and cycle index. Combinatorics, Probability and Computing, vol. 8, 1999, pp. 31--43.

[2]
Bender (Edward A.), Cameron (Peter J.), and Richmond (L. Bruce). -- Asymptotics for the probability of connectedness and the distribution of number of components, 1999. Preprint.

[3]
Bergeron (F.), Labelle (G.), and Leroux (P.). -- Combinatorial species and tree-like structures. -- Cambridge University Press, Cambridge, 1998, xx+457p. Translated from the 1994 French original by Margaret Readdy, With a foreword by Gian-Carlo Rota.

[4]
Cameron (Peter J.). -- On the probability of connectedness. Discrete Mathematics, vol. 167/168, 1997, pp. 175--187.

[5]
Wright (E. M.). -- A relationship between two sequences. Proceedings of the London Mathematical Society, vol. 17, 1967, pp. 296--304.
This document was translated from LATEX by HEVEA.