When structures are almost surely connected

Jason P. Bell Department of Mathematics University of California San Diego La Jolla, CA 92093-0112. USA

                         jbell@math.ucsd.edu

Submitted: June 5, 2000 Accepted: July 20, 2000

Abstract

Let A_{n} denote the number of objects of some type of “size” n, and let C_{n} denote the number of these objects which are connected. It is often the case that there is a relation between a generating function of the C_{n}’s and a generating function of the A_{n}’s. Wright showed that if lim_{n→∞} C_{n}/A_{n} = 1, then the radius of convergence of these generating functions must be zero. In this paper we prove that if the radius of convergence of the generating functions is zero, then lim sup_{n→∞} C_{n}/A_{n} = 1, proving a conjecture of Compton; moreover, we show that lim inf_{n→∞} C_{n}/A_{n} can assume any value between 0 and 1.

1 Introduction

Let A_{n} count objects of some type by their “size” n and let C_{n} count those which are connected. One frequently has either

A(x) = exp(C(x)) or A(x) = exp(∑_{k≥1} \frac{C(x^{k})}{k}),  (1.1)

for exponential generating functions of labeled objects and ordinary generating functions of unlabeled objects, respectively. Let R be the radius of convergence of the power series. Various authors have studied the limiting behavior of C_{n}/A_{n}. In particular, Wright [3] constructed a sequence {C_{n}}_{n≥1} such that lim sup C_{n}/A_{n} = 1 and lim inf C_{n}/A_{n} < 2/3 in both the labeled and unlabeled case. Also, Wright [3], [4] showed that if lim_{n→∞} C_{n}/A_{n} = 1, then R = 0. Compton [1] asked if the converse were true, assuming the limit exists. The following theorem provides an affirmative answer.

Theorem 1 Suppose that either of (1.1) holds then:

• If R = 0, then lim sup_{n→∞} C_{n}/A_{n} = 1.

• For any 0 ≤ l ≤ 1, there exists both labeled and unlabeled objects satisfying (1.1) with R = 0 and lim inf_{n→∞} C_{n}/A_{n} = l.

Combining the first part of the theorem with Wright’s result shows that, if lim_{n→∞} C_{n}/A_{n} = ρ exists, then ρ = 1 if and only if R = 0.

The author would like to thank Ed Bender for helpful advice about the exposition of this paper.

2 Proofs

We require the following simple lemma.

Lemma 1 Suppose p(x) = ∑_{i=1}^{∞} p_{i}x^{i} (p_{1} ≠ 0) is analytic at zero and suppose h(x) = ∑_{i=1}^{∞} h_{i}x^{i} has the property that p(h(x)) = g(x) is a power series that is analytic at zero. Then h(x) is analytic at zero.

Proof. Let p^{−1}(x) be the formal inverse of p. Since p(x) is analytic at zero, we have that p^{−1}(x) is analytic at zero by [2] page 87, Theorem 4.5.1. Hence h(x) = p^{−1}(g(x)) is analytic at zero as required.

We now prove a lemma that will be useful to us.

Lemma 2 Suppose C(x) = ∑_{i=1}^{∞} c_{i}x^{i} is a power series with non-negative coefficients and

p(x) = ∑_{i=1}^{∞} p_{i}x^{i} (p_{1} ≠ 0)

is a power series that is analytic at zero satisfying

p_{n} + αc_{n} ≤ [x^{n}]e^{C(x)}

for some α > 1 and all n ≥ 1. Then C(x) is analytic at zero.

Proof. To prove this, let us first note that if D(x) = ∑_{i=1}^{∞} d_{i}x^{i} is a formal power series that satisfies the equation

p_{n} + αd_{n} = [x^{n}]e^{D(x)}  (2.2)

for all n ≥ 1, then D(x) is analytic. To see this, let us note that equation (2.2) is equivalent to stating that

1 + p(x) + αD(x) = e^{D(x)}  (2.3)

as formal power series. Notice that d_{1} = −p_{1}/(α − 1) ≠ 0 and hence D(x) has a formal inverse D^{−1}(x). Substituting x = D^{−1}(u) into the equation (2.3), we find that

p(D^{−1}(u)) = e^{u} − αu − 1.

Thus by Lemma 1 we have that D^{−1}(u) is analytic at zero. By Lemma 1 we have that D(x) is analytic at zero. We now show that 0 ≤ c_{n} ≤ d_{n} for all n ≥ 1. We prove this by induction on n. Note that for n = 1, we have that p_{1} + αc_{1} ≤ [x]e^{C(x)} = c_{1} and so c_{1} ≤ −p_{1}/(α − 1) = d_{1}. Hence the claim is true when n = 1. Suppose the claim is true for all values less than n. We have

p_{n} + αc_{n} ≤ [x^{n}]e^{C(x)}
= [x^{n}] exp(c_{1}x + c_{2}x^{2} + ⋯ + c_{n}x^{n})
≤ [x^{n}] exp(d_{1}x + d_{2}x^{2} + ⋯ + d_{n}x^{n} + (c_{n} − d_{n})x^{n}),

since c_{k} ≤ d_{k} for k < n. Thus

p_{n} + αc_{n} ≤ [x^{n}] exp(d_{1}x + ⋯ + d_{n}x^{n}) exp((c_{n} − d_{n})x^{n})
= [x^{n}] exp(D(x))(1 + (c_{n} − d_{n})x^{n})
= [x^{n}] exp(D(x)) + c_{n} − d_{n}
= p_{n} + αd_{n} + c_{n} − d_{n}.

Hence (α − 1)c_{n} ≤ (α − 1)d_{n} and so 0 ≤ c_{n} ≤ d_{n} for all n ≥ 1. Since D(x) is analytic at zero, it follows that C(x) is analytic at zero. This completes the proof.

The following theorem implies the first part of Theorem 1. To see this, it suffices to note that

[x^{n}] exp(C(x)) ≤ [x^{n}] exp(∑_{k≥1} \frac{C(x^{k})}{k}).

Theorem 2 Suppose c_{i} ≥ 0 for all i and C(x) = ∑_{i=1}^{∞} c_{i}x^{i} has radius of convergence zero. Let

A(x) = ∑_{i=1}^{∞} a_{i}x^{i} = exp(∑_{j=1}^{∞} C(x^{j})/j).

Then

lim sup_{n→∞} \frac{c_{n}}{a_{n}} = 1.

Proof. Without loss of generality we may assume that c_{1} ≥ 1, as increasing the value of c_{1} can only decrease the values of c_{n}/a_{n} for large n. Suppose

lim sup_{n→∞} \frac{c_{n}}{a_{n}} ≠ 1.

Then there exists λ > 1 and a positive integer N such that

\frac{a_{n}}{c_{n}} > λ for all n > N  (2.4)

Let H(x) = ∑_{i=1}^{∞} h_{i}x^{i} be the power series

H(x) = ∑_{k=1}^{∞} \frac{C(x^{k})}{k} so that c_{n} = ∑_{d|n} \frac{μ(d)h_{n/d}}{d} .

Define the two sets

S_{1} = \{n > N | \frac{a_{n}}{h_{n}} ≥ \frac{1 + λ}{2} \}  (2.5)

and

S_{2} = \{n > N | \frac{a_{n}}{h_{n}} < \frac{1 + λ}{2} \} .  (2.6)

If n ∈ S_{2}, then by (2.4) we must have that c_{n}/h_{n} < (1 + λ)/2λ. Thus

∑_{d|n} \frac{μ(d)h_{n/d}}{d} < \frac{(1 + λ)h_{n}}{2λ} .  (2.7)

But

∑_{d|n} \frac{μ(d)h_{n/d}}{d} = h_{n} + ∑_{{d|n \atop d≠1}} \frac{μ(d)h_{n/d}}{d}

≥ h_{n} − ∑_{{d|n \atop d≠1}} \frac{h_{n/d}}{d} .

Combining this result with (2.7) we find that there exists some divisor d ≠ 1 of n such that h_{n/d}/d > (λ − 1)h_{n}/2d(n)λ. Hence

h_{n}(1 + λ)/2 > a_{n} = [x^{n}]e^{H(x)}
≥ h_{n} + h_{n/d}^{d}/d!
≥ h_{n} + \frac{((λ − 1)dh_{n})^{d}}{(2d(n)λ)^{d}d!}
≥ h_{n} + \frac{(λ − 1)^{d}h_{n}^{d}}{(2nλ)^{d}} .

Solving for h_{n} we find that

h_{n} < (\frac{2nλ (\frac{λ−1}{2})^{1/d}}{λ − 1} )^{d/(d−1)} = O(n^{2})

and so there exists C > 0 such that h_{n} < Cn^{2} for all n ∈ S_{2} ∪ {1, 2, …, N}; that is, all n ∉ S_{1}. Define

p(x) = −\frac{(1 + λ)}{2}(∑_{j=1}^{N} Cj^{2}x^{j} + ∑_{j∈S_{2}} Cj^{2}x^{j}).

Clearly p(x) has a radius of convergence of at least 1 and so it is analytic at zero. Consider the power series p(x) + (1 + λ)H(x)/2. Notice if n ∉ S_{1}, then

[x^{n}] (p(x) + \frac{(1 + λ)}{2}H(x)) = \frac{(1 + λ)}{2}(−Cn^{2} + h_{n})
≤ 0
≤ a_{n}
= [x^{n}] exp(H(x)).

If n ∈ S_{1}, then

[x^{n}] (p(x) + \frac{(1 + λ)}{2}H(x)) = (1 + λ)h_{n}/2 ≤ a_{n} = [x^{n}] exp(H(x)).

Hence we have

[x^{n}] (p(x) + \frac{(1 + λ)}{2}H(x)) ≤ [x^{n}] exp(H(x))

for all n ≥ 1. Moreover when n = 1, p′(0) + \frac{1+λ}{2}h_{1} ≤ h_{1}, and so p′(0) < 0. Hence by Lemma 2, H(x) is analytic at zero. Since 0 ≤ c_{n} ≤ h_{n} for all n, we see that C(x) is also analytic at zero, a contradiction. This completes the proof of the theorem.

We now prove the second part of Theorem 1. The set of all graphs (labeled or unlabeled) provides an example for l = 1 [5]. For l = 0, notice if C(x) = ∑_{n≥1} C_{n}x^{n} is any power series of radius zero having positive integer coefficients and C_{n} = 1 for infinitely many n, then in both the labeled and unlabeled cases we have that

A_{n} ≥ [x^{n}] exp(C(x))
≥ [x^{n}] exp(\frac{x}{1 − x})
≥ [x^{n}]\frac{1}{2!} \frac{x^{2}}{(1 − x)^{2}}
= (n − 1)/2.

Hence

inf_{{n : C_{n}=1}} C_{n}/A_{n} = 0.

Hence to prove the second part of Theorem 1 it suffices to prove the following theorem.

Theorem 3 Given l with 0 < l < 1, there exist power series C(x) = ∑_{i≥1} c_{i}x^{i}, H(x) = ∑_{i≥1} h_{i}x^{i}, and A(x) = ∑_{i≥1} a_{i}x^{i} that satisfy the following:

1. C(x), H(x), and A(x) all have zero radius of convergence;

2. c_{n}, a_{n}, and n!h_{n} are positive integers;

3. A(x) = exp (H(x)) = exp(∑_{j≥1} C(x^{j})/j);

4. lim inf_{n→∞} c_{n}/a_{n} = lim inf_{n→∞} h_{n}/a_{n} = l.

Proof. We recursively define sequences {N_{n}}, and {c_{n}} as follows. We define N_{1} = 0, and c_{1} = 1. For n > 1, we define N_{n} = [x^{n}] ∏_{j=1}^{n−1}(1 − x^{j})^{−c_{j}} and

c_{n} = \{ \begin{matrix}n!N_{n} & if n is even \\ [\frac{N_{n}}{α−1}] + 1 & if n is odd, \end{matrix}

where α = 1/l. Notice N_{n} and c_{n} are positive integers for all n > 1. Notice that if n is even, then c_{n} ≥ n! and so C(x) has zero radius of convergence. Since

[x^{n}] ∏_{j=1}^{∞}(1 − x^{j})^{−c_{j}} = [x^{n}](1 + c_{n}x^{n}) ∏_{j=1}^{n−1}(1 − x^{j})^{−c_{j}}
= c_{n} + N_{n}
= c_{n}(1 + N_{n}/c_{n}),

we have that

1 + ∑_{j=1}^{∞}(1 + N_{j}/c_{j})c_{j}x^{j} = ∏_{j=1}^{∞}(1 − x^{j})^{−c_{j}}

and so

1 + ∑_{j=1}^{∞}(1 + N_{j}/c_{j})c_{j}x^{j} = exp(∑_{k=1}^{∞} C(x^{k})/k).

Hence a_{n} = (1 + N_{n}/c_{n})c_{n}. Notice that

N_{n} = [x^{n}] ∏_{j=1}^{n−1}(1 − x^{j})^{−c_{j}}

≥ [x^{n}] ∏_{j=1}^{n−1}(1 − x^{j})^{−1}
≥ p(n − 1).

Hence N_{n} tends to infinity as n tends to infinity, and so for odd n we have

a_{n}/c_{n} = 1 + \frac{N_{n}}{[N_{n}/(α − 1)] + 1} → α

as n tends to infinity. Moreover, we have that for n even, a_{n}/c_{n} = 1 + 1/n! → 1 as n → ∞. Thus C(x) ∈ ℤ[[x]] is a power series satisfying the conditions of the theorem. Since H(x) = ∑_{j=1}^{∞} C(x^{j})/j, we have that h_{n} = ∑_{d|n} c_{n/d}/d. Clearly n!h_{n} is a positive integer for all n ≥ 1. To complete the proof of the theorem, it suffices to show that lim_{n→∞} h_{n}/c_{n} = 1. To see this, notice that if n > 2, then

N_{n} = [x^{n}] ∏_{j=1}^{n−1}(1 − x^{j})^{−c_{j}} ≥ (1 + x)^{c_{1}}(1 + x^{n−1})^{c_{n−1}} = c_{n−1}c_{1}.

Since c_{1} = 1, N_{n} ≥ c_{n−1} for all n > 1. Thus c_{n} ≥ n!c_{n−1} for even n and c_{n} ≥ c_{n−1}/(α − 1) for odd n. It follows that c_{n} ≥ (n − 1)!c_{n−2}/(α − 1) for all n > 2, and so there is a B > 0 such that c_{n} ≥ B(n − 1)!c_{k} for all k ≤ n/2. Hence we have that for n > 2

h_{n} = c_{n} + ∑_{{d|n \atop d≠1}} c_{n/d}/d

≤ c_{n}(1 + ∑_{{d|n \atop d≠1}} 1/B(n − 1)!)

= c_{n}(1 + o(1)).

This completes the proof of the theorem.

References

[1] K. J. Compton, Some methods for computing component distribution probabilities in relational structures, Discrete Math. 66 (1987) 59–77.

[2] E. Hille, Analytic function theory. Vol. I. Introduction to Higher Mathematics Ginn and Company, Boston (1959).

[3] E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (iii) 17 (1967) 296–304.

[4] E. M. Wright, A relationship between two sequences III, J. London Math. Soc. 43 (1968) 720–724.

[5] E. M. Wright, Asymptotic relations between enumerative functions in graph theory, Proc. London Math. Soc. (iii) 20 (1970) 558–572.