Connectedness, classes, and cycle index

E. A. Bender, P. J. Cameron, A. M. Odlyzko and L. B. Richmond

Center for Communications Research 4320 Westerra Court San Diego, CA 92121 U.S.A.

School of Mathematical Sciences Queen Mary and Westfield College Mile End Road London E1 4NS U.K.

AT&T Bell Laboratories 600 Mountain Avenue Murray Hill, NJ 07974-0636 U.S.A.

Department of Combinatorics and Optimization Faculty of Mathematics University of Waterloo Waterloo, Ontario N2L 3G1 Canada

Abstract

This paper begins with the observation that half of all graphs containing no induced path of length 3 are disconnected. We generalize this in several directions. First, we give necessary and sufficient conditions (in terms of generating functions) for the probability of connectedness in a suitable class of graphs to tend to a limit strictly between zero and one. Next we give a general framework in which this and related questions can be posed, involving operations on classes of finite structures. Finally, we discuss briefly an algebra associated with such a class of structures, and give a conjecture about its structure.

1 Introduction

The class of graphs containing no induced path of length 3 has many remarkable properties, stemming from the following well-known observation. Recall that an induced subgraph of a graph consists of a subset S of the vertex set together with all edges contained in S.

Proposition 1.1 Let G be a finite graph with more than one vertex, containing no induced path of length 3. Then G is connected if and only if its complement is disconnected.

Proof: It is trivial that the complement of a disconnected graph is connected. Moreover, since P_{3} is self-complementary, the property of containing no induced P_{3} is self-complementary. So let G be a minimal counterexample: thus, G and \overline{G} are connected but, for any vertex v, either G − v or \overline{G} − v is disconnected. Choose a vertex v and assume, without loss, that G − v is disconnected. Then v is joined to a vertex in each component of G − v. Since \overline{G} is connected, there is a vertex x′ not joined to v (in G). Let w′ be a neighbour of v in the component C of G − v containing x′. Then there is a path from w′ to x′ in C, and hence an edge wx such that w ∼ v, x ≁ v. If u is a neighbour of v in a different component of G − v, then {u, v, w, x} induces P_{3}, contrary to assumption.

The particular view of this result we will take here is that a random P_{3}-free graph on more than one vertex is connected with probability \frac{1}{2}. This leads to the general question: in which classes of graphs, having good notions of “connectedness” and “induced substructure”, does it hold that the probability of connectedness of a random n-vertex graph in the class tends to a limit p, with 0 < p < 1, as n → ∞? There are two questions here, since we could take either labelled or unlabelled structures.

One example is the class of forests of rooted trees, where the limiting probability of connectedness is 1/e = 0.3679 … for the labelled structures, and 1/2.997 … = 0.3367 … for the unlabelled structures. (The latter holds because there is a natural bijection between forests of rooted trees on n vertices, and rooted trees on n + 1 vertices; and 2.997 … is the exponential constant in the asymptotic formula for the number of unlabelled trees: see Otter [11]. For the labelled case, see Rényi [15].

There is no need to restrict ourselves to graphs. The probability of connectedness of a random N-free poset tends to (\sqrt{5} − 1)/2, in both the labelled and the unlabelled case (El-Zahar [4]; see also Stanley [18]). (Incidentally, there is no simple explanation for why the golden ratio appears here, nor for why the answer is the same in the labelled and unlabelled case.)

Contrary to what Proposition 1.1 might suggest, this question turns out to have little to do with the detailed structure of the class, but involves the rate of growth of the number of n-element structures. This will be analysed in Section 2, where we show that a sufficient condition can be expressed in terms of convergence and smoothness properties of the generating function.

The relation between connected and arbitrary structures has several analogues, such as that between partial and total structures, or between reduced and arbitrary structures in a class whose members have a natural “congruence” relation (where a structure is reduced if the congruence is equality). These are best described in terms of two kinds of composition of classes of finite structures, “multiplication” and “substitution”, defined in Section 3. The behaviour of generating functions under these operations is expressed in terms of a cycle index function, described in Section 4. The final section defines a graded algebra based on a class of structures, and gives a conjecture on this algebra and a structure theorem under additional hypotheses.

2 Convergence and smoothness

Let A be a class of graphs or other structures which has a notion of “connectedness”; let C denote the class of connected structures in A. We assume that every member of A can be expressed uniquely as a disjoint union of members of C, and that any disjoint union of members of C is in A. Let c_{n} and C_{n} be the numbers of unlabelled and labelled structures in C, and a_{n} and A_{n} the corresponding numbers for A. (We assume that c_{0} = C_{0} = 0, a_{0} = A_{0} = 1.) As is usual in enumeration theory, we use exponential generating functions C(z) = ∑_{n=0}^{∞} C_{n}z^{n}/n! and A(z) = ∑_{n=0}^{∞} A_{n}z^{n}/n! for labelled structures, and ordinary generating functions c(z) = ∑_{n=0}^{∞} c_{n}z^{n} and a(z) = ∑_{n=0}^{∞} a_{n}z^{n} for unlabelled structures. (This notation will be used throughout this section.) With our assumptions, we have

A(z) = exp(C(z)),  (1)
a(z) = exp (∑_{n=1}^{∞} \frac{c(z^{n})}{n}) = ∏_{n=1}^{∞}(1 − z^{n})^{−c_{n}}.  (2)

(See Wright [19]; we will derive these well-known equations in Section 5.) Now the probability of connectedness of a random n-element structure in A is c_{n}/a_{n} in the unlabelled case, or C_{n}/A_{n} in the labelled case. So the general question is: What conditions on the sequence (C_{n}) or (c_{n}) guarantee that C_{n}/A_{n} or c_{n}/a_{n} tends to a limit strictly between zero and one as n → ∞, where A_{n} and a_{n} are defined by the formulae above?

Similar questions were first considered by Wright [19], who proved the following.

Theorem 2.1 If c_{n} ≥ 0 for all n, then c_{n}/a_{n} → 1 if and only if

(a) c(x) has radius of convergence 0, and (b) ∑_{s=1}^{n−1} h_{s}h_{n−s} = o(h_{n}), where h_{n} may be either c_{n} or a_{n}.

The same holds for C_{n} and A_{n}.

In Cameron [2], it was conjectured that a necessary and sufficient condition for the probability of connectedness to tend to a limit strictly between zero and one is that the appropriate generating function has finite radius of convergence R and converges at z = R, and that its coefficients satisfy some “smoothness” condition. In this section, we prove a result of this form. First, we observe that the convergence condition is necessary.

Theorem 2.2 Suppose that, with the above notation, C(z) has finite non-zero radius of convergence R, and that C(z) is unbounded on its circle of convergence. Then lim inf_{n→∞} C_{n}/A_{n} = 0. The analogous result holds also for c(z) and a(z).

Proof: Consider the labelled case, and suppose that C_{n} > δA_{n} for all n, where δ > 0. Then C(z) > δ(A(z) − 1) for 0 ≤ z ≤ R, and so C(z) > δ(exp(C(z) − 1) as z → R. This is clearly impossible if C(R) is divergent. If C(R) is convergent, then C(z) is uniformly convergent for |z| = R.

The argument in the unlabelled case is similar.

Here is an example. Take a finite alphabet Q, with |Q| = q, and let A consist of all finite words in Q. An induced substructure is taken to be a (not necessarily consecutive) subword. (This example can be recast as a relational structure, where a word on n letters is regarded as n-set which is totally ordered and is partitioned into q subsets corresponding to the elements of Q.) A Lyndon word is one which is lexicographically smaller than any proper cyclic shift of itself. Now it can be shown that any word can be expressed uniquely as the concatenation, in lexicographically decreasing order, of Lyndon words. Thus, taking “disjoint union” to mean concatenation in decreasing order, we are in the general situation of this section. In this case, a_{n} (the number of words of length n) is equal to q^{n}, while c_{n} (the number of Lyndon words of length n) is given by the well-known formula

c_{n} = \frac{1}{n} ∑_{d|n} μ(d)q^{n/d} ∼ \frac{q^{n}}{n} .

We see directly that the radii of convergence of a(z) and c(z) are equal to 1/q, and that both series diverge at 1/q; also

c_{n}/a_{n} ∼ 1/n → 0.

Furthermore, because words are totally ordered, we have C_{n} = n!c_{n} and A_{n} = n!a_{n}, so also C_{n}/A_{n} → 0.

In addition, some smoothness condition on the coefficients is required to ensure that lim inf(C_{n}/A_{n}) = lim sup(C_{n}/A_{n}) (or the analogous condition for c_{n}/a_{n}). An example to show this was given in Cameron [2]. We give two alternative definitions of “smoothness” which will work. In the analysis that follows, the arguments in the unlabelled and labelled cases are virtually identical. So we speak of the functions c(z) and a(z), but C(z) and A(z) may be substituted.

The first smoothness condition we consider is Hayman admissibility, defined in Hayman [8] or Odlyzko [10]. Rather than give the definition here, we quote a theorem of Hayman which frequently allows an easy proof of Hayman admissibility for generating functions in combinatorial situations.

Theorem 2.3 (Hayman) Let f(z) and g(z) be admissible for |z| < R, R ≤ ∞. Let h(z) be analytic in |z| < R and real for real z. Let p(z) be a polynomial with real coefficients.

(i) If the coefficients a_{n} of the Taylor series of exp(p(z)) are positive for all sufficiently large n, then exp(p(z)) is Hayman admissible for all z.

(ii) exp(f(z)) and f(z)g(z) are admissible for in |z| < R.

(iii) If, for some η > 0 and R_{1} < r < R,

max_{|z|=r} |h(z)| = O(f(r)^{1−η}),

then f(z) + h(z) is H-admissible in |z| < R. In particular, f(z) + p(z) is H-admissible in |z| < R and, if the leading coefficient of p(z) is positive, then p(f(z)) is H-admissible in |z| < R.

Hayman [8] proved the following theorem:

Theorem 2.4 Let f(z) = ∑ f_{n}z^{n} be Hayman-admissible in |z| < R. Let

a(r) = \frac{rf′(r)}{f(r)},
b(r) = ra′(r) = \frac{rf′(r)}{f(r)} + \frac{r^{2}f′′(r)}{f(r)} − (r \frac{f′(r)}{f(r)})^{2} .

Then

f_{n} ∼ (2πb(r_{n}))^{−1/2}f(r_{n})r_{n}^{−n} as n → ∞,

where r_{n} is defined uniquely for sufficiently large n by a(r_{n}) = n. Furthermore, for all ϵ > 0, we have r_{n} → R, f(r_{n}) → ∞, and b(r_{n}) = o(f(r_{n})^{ϵ}) as n → ∞.

The first result of this section is:

Theorem 2.5 Let c(x) be the generating function for the unlabelled (or labelled) connected structures in a class and let 0 < R ≤ ∞ be the radius of convergence of c(x). If exp(c(x)) is admissible, then c(x) → ∞ diverges as x → R and the probability of connectedness of an unlabelled (or labeled) structure goes to 0 as n → ∞.

Proof: In the unlabeled case, a_{n} is at least as large as the coefficient of x^{n} in exp(c(x)). Hence it suffices to work with f(x) = exp(c(x)) in both the labeled and unlabeled cases and show that c_{n}/a_{n} → 0.

The divergence of f(x), and hence c(x), at x = R follows from f(r_{n}) → ∞ in Theorem 2.4.

We have

f_{n} ∼ (2πb(r_{n}))^{−1/2} exp(c(r_{n}))r_{n}^{−n}
> exp((1 − ϵ)c(r_{n}))r_{n}^{−n}
> Mc(r_{n})c(r_{n})r_{n}^{−n}
≥ M log(f(r_{n}))c_{n},

where the last inequality follows from the fact that a sum of nonnegative terms is at least as large as a single term. Since f(r_{n}) → ∞, the proof is complete.

The other smoothness condition we impose on c(x) is satisfaction of the Flajolet–Odlyzko singularity analysis [6]. See [10], Section 11, for the definition of a function of slow variation at ∞, and for the definition of the region Δ. Flajolet and Odlyzko showed:

Theorem 2.6 Suppose that c(x) has a unique singularity at R on its circle of convergence, that the radius of convergence of h(x) exceeds R, that L(u) is a function of slow variation at ∞, and that

c(x) − h(x) ∼ (R − x)^{α}L(1/(R − x))

as x → R in Δ, where α is not a non-negative integer. Then

c_{n} ∼ \frac{R^{−n}n^{−α−1}L(n)}{Γ(α)}

as n → ∞.

Remark. A similar result is proved in [6] when α is a non-negative integer: Γ(α) must be replaced by a suitable constant.

Remark. If α < 0 and

L(u) = (log u)^{β_{1}}(log log u)^{β_{2}} ⋯,

then exp(c(x)) is admissible (Hayman [8]), and we can use Theorem 2.5. We now come to the other result of this section:

Theorem 2.7 Suppose that C(x) satisfies the hypotheses of Theorem 2.6. A necessary and sufficient condition for the probability of connectedness of labelled structures in the class to have a limit strictly between 0 and 1 is that C(x) converge at R.

Suppose that c(x) satisfies the hypotheses of Theorem 2.6 and has radius of convergence R < 1. A necessary and sufficient condition for the probability of connectedness of unlabelled structures in the class to have a limit strictly between 0 and 1 is that C(x) converge at R.

Proof: From Theorem 2.1, we cannot have c_{n}/a_{n} → 1 if R > 0.

Suppose c(R) diverges (that is, if α ≤ 0). As in the proof of Theorem 2.5, it suffices to consider a(x) = exp(c(x)). We have

a_{n} = [x^{n}] exp(c(x))
≥ [x^{n}]c(x)^{2}/2
∼ r^{−n}n^{−2α−1}L(n)^{2}/Γ(2α),

and the result follows.

Suppose now that c(x) is convergent at x = R. Then, in Δ, we have

c(x) − h(x) ∼ (R − x)^{α}L(1/(R − x)),

where α > 0 and h(x) is analytic in |x| < R + δ for some δ > 0. Note that h(R) = c(R). In the labelled case, as x → R in Δ,

a(x) − e^{h(x)} ∼ e^{h(R)}(R − x)^{α}L(1/(R − x)),

and we conclude that

a_{n} ∼ e^{h(R)}c_{n},

so that c_{n}/a_{n} → e^{−h(R)} = e^{−c(R)} as n → ∞. The unlabelled case is similar provided R < 1.

For example, Cayley’s Theorem for the number T_{n} of labelled trees on n vertices, combined with Stirling’s approximation, shows that

T_{n}/n! ∼ Cn^{−5/2}e^{n}.

It is known that T (z) = ∑ T_{n}z^{n}/n! satisfies the hypotheses of Theorem 2.7, and we conclude that the probability of connectedness of a random forest tends to a limit strictly between zero and one. In fact the limit is 1/\sqrt{e} (Rényi [15]).

It remains to prove that various natural classes of graphs satisfy “smoothness” conditions of the types described above. We pose the following problems. If C is a class of finite graphs, let X (C) denote the class of finite graphs containing no induced subgraph isomorphic to a member of C. Note that, if every member of C is connected, then a graph lies in X (C) if and only if all its connected components do, so the analysis of this section applies (if the appropriate growth and smoothness conditions can be shown).

(a) Is it true that, if C is finite, then the probability of connectedness of labelled or unlabelled graphs in X (C) tends to a limit?

(b) Is it true that P_{3} is the only finite connected graph H such that, in X ({H}), the limiting probability of connectedness is strictly between 0 and 1?

3 Operations on classes

In this section, we propose a general framwork in which a number of questions like the probability of connectedness can be posed and studied. We work in the context of a class A of finite structures, which is closed under isomorphism and closed under taking induced substructures. Thus A may be the set of models of a universal theory in a first-order relational language. (We allow the language to have infinitely many relation symbols, but require that there are only finitely many n-element structures in A (up to isomorphism), for each n. As in the preceding section, we let a_{n} and A_{n} be the numbers of unlabelled and labelled n-element structures in A, and use the ordinary generating function ∑_{n=0}^{∞} a_{n}z^{n} for the sequence (a_{n}), and the exponential generating function ∑_{n=0}^{∞} A_{n}z^{n}/n! for (A_{n}). We assume that a_{0} = A_{0} = 1.

Following Fraïssé [7], the age of a countable structure M is the class of all finite structures embeddable in M as induced substructures. Among structures satisfying our assumptions, ages are characterised by the joint embedding property: given A, B ∈ A, there exists C ∈ A containing both A and B as induced substructures.

We will frequently make use of the class S of sets (without any structure). We have S_{n} = s_{n} = 1 for all n; so S(z) = exp(z), s(z) = 1/(1−z). Other simple classes are T , the total orders, with t_{n} = 1, T_{n} = n!, t(z) = T (z) = 1/(1−z); and the class P of permutations, with P_{n} = n!, p_{n} = p(n) (the partition function), P (z) = 1/(1 − z), p(z) = ∏_{n=1}^{∞} 1/(1 − z^{n}). (Two permutations are isomorphic if and only if they are conjugate in the symmetric group, so the number of unlabelled permutations of an n-set is the number of partitions of n.)

Now we define two operations on classes of structures as follows. Let A, B be classes. Then the operation of multiplication produces the class A×B, defined as follows: a structure in the class with point set X consists of a partition of X into two parts Y, Z (possibly empty), with an A-structure on Y and a B-structure on Z.

Proposition 3.1 If C = A × B, then C(z) = A(z)B(z) and c(z) = a(z)b(z).

For example, if D is the class of derangements (permutations with no fixed points), then P = D × S, from which we obtain the exponential generating function for derangement numbers: D(z) = 1/((1 − z) exp(z)).

The operation of substitution of B into A produces the class A[B−1], defined as follows: a structure in the class on the point set X consists of a partition of X into an arbitrary number of non-empty parts, a B-structure on each part, and an A-structure on the set of parts. The −1 in the notation is intended to suggest that we remove the empty structure from B before performing the substitution.

Proposition 3.2 If C = A[B − 1], then C(z) = A(B(z) − 1).

The function c(z) cannot be determined from a(z) and b(z) alone, as we see in the next section.

For example, if C denotes the class of cyclic orders, then the cycle decomposition of a permutation can be expressed as P = S[C − 1], so that P (z) = S(C(z)−1), in agreement with the values calculated above for P (z) and S(z) and the fact that C(z) = 1 − log(1 − z) (from C_{n} = (n − 1)! for n ≥ 1).

Now let A be a class of graphs closed under disjoint unions, and let C be the class of connected graphs in A. We have A = S[C − 1]. So the problem of the probability of connectedness is an instance of the following more general problem:

Problem: Suppose that A is obtained from B and C by some operation such as multiplication or substitution. Under what conditions does it hold that C_{n}/A_{n} or c_{n}/a_{n} tends to a limit strictly between zero and one?

We give two further examples.

If A = S × C, then A-structures can be regarded as partial C-structures, consisting of a set with a C-structure on a subset. For example, if A is a class of graphs closed under adding isolated vertices, and C is the class of members of A with no isolated vertices, then this relation holds. So our question would be: When does it occur that the proportion of partial structures which are total tends to a limit between zero and one? This is discussed in Cameron [2].

Suppose that A = C[S−1]. Then an A-structure carries a natural equivalence relation or congruence ≡, such that if a relation holds for an n-tuple of points, then it remains true if some or all of the points are replaced by equivalent ones. With this interpretation, C is the class of reduced structures, those in which the relation ≡ is just equality. For example, in a suitable class A of graphs, set v ≡ w if v and w have the same neighbour sets; a graph is reduced if different vertices have different neighbour sets. Now our question is: When does it occur that the proportion of structures which are reduced tends to a limit between zero and one?

4 Cycle index

It is possible, following Joyal [9], to define a cycle index of a class of structures such that the generating functions for labelled and unlabelled structures defined above are specialisations of it. Its behaviour under multiplication and substitution can also be described.

Recall that the cycle index z(g) of a permutation g on n letters is the monomial in indeterminates s_{1}, …, s_{n} given by

z(g) = s_{1}^{c_{1}(g)}s_{2}^{c_{2}(g)} ⋯,

where c_{i}(g) is the number of cycles of length i in the cycle decomposition of g. If G is a permutation group on n letters, the cycle index of G is the average of the cycle indices of its elements:

Z(G) = \frac{1}{|G|} ∑_{g∈G} z(g).

Now if G is a class of finite permutation groups, containing only finitely many members of degree n for each n, we define the cycle index of G by Z(G) = ∑_{G∈G} Z(G). (This is a formal power series in infinitely many indeterminates; but the assumption guarantees that each monomial occurs only finitely often in the sum.)

This definition can be extended in two ways. First, let A be a class of structures, as in the preceding section. We define its cycle index to be Z(A) = Z({Aut(A) : A ∈ A}), where each unlabelled structure in A is used once in the sum. Now the generating functions for A are specializations of the cycle index. If Φ is a formal power series, we let Φ(s_{i} ← t_{i}) be the result of making the substitution t_{i} for s_{i} for all i. Some conditions are required in general in order that this is well-defined. For example, if the t_{i} are formal power series in one indeterminate z, it suffices that t_{i} has no term of degree less than i.

Proposition 4.1 (i) A(z) = Z(A)(s_{i} ← z^{i}).

(ii) a(z) = Z(A)(s_{1} ← z, s_{i} ← 0 for i > 1).

The cycle index behaves as follows under multiplication and substitution:

Proposition 4.2 (i) Z(A × B) = Z(A)Z(B).

(ii) Z(A[B − 1]) = Z(A)(s_{i} ← t_{i} − 1), where t_{i} = Z(B)(s_{j} ← s_{ij}).

¿From the second part of this proposition, we obtain the missing formula for the generating function for unlabelled structures in A[B − 1]:

Proposition 4.3 If C = A[B − 1], then c(z) = Z(A)(s_{i} ← b(z^{i}) − 1).

For the class S we have

Z(S) = exp (∑_{n=1}^{∞} \frac{s_{n}}{n} ) .

¿From this, the formula of Section 2 relating connected and arbitrary graphs in a class closed under taking disjoint unions follows.

The other extension is to a class of infinite permutation groups. A permutation group G on a set X is called oligomorphic if the number of orbits of G on the set of n-tuples of points of X is finite for all n. See Cameron [1] for an account of these groups.

Clearly, the previous definition of the cycle index of an infinite permutation group makes no sense. However, an oligomorphic permutation group G has a socalled modified cycle index Z̃(G), defined as follows. Choose representatives for the orbits of G on finite subsets of X. (By assumption, there are only finitely many of each size.) For each representative Y, let G(Y) be the permutation group induced on Y by its setwise stabiliser in G. Then Z̃(G) is defined to be the cycle index of this collection of finite permutation groups.

The relationship with the preceding is as follows. A structure M is said to be homogeneous if any isomorphism between finite substructures of M extends to an automorphism of M. Examples of homogeneous structures include the pentagon, the rational numbers ℚ (as ordered set), and the random graph or Rado’s graph [5], [14]. A theorem of Fraïssé [7] characterizes the ages of countable homogeneous structures. In particular, a class A of structures satisfying our conditions (that is, closed under isomorphism and under induced substructures and containing only finitely many n-element structures up to isomorphism) is the age of a countable homogeneous structure if and only if it satisfies the amalgamation property: if B, C ∈ A have isomorphic substructures A, A′ respectively, then there is a structure D ∈ A in which B and C can be embedded in such a way that the substructures are identified or “glued together” according to the isomorphism.

Proposition 4.4 Let M be a countable homogeneous structure with automorphism group G and age A. Then

(i) the number of orbits of G on n-element subsets is equal to the number of unlabelled n-element structures in A;

(ii) the number of orbits of G on n-tuples of distinct elements is equal to the number of labelled n-element structures in A;

(iii) Z̃(G) = Z(A).

This result gives a covenient translation between ages satisfying the amalgamation property and oligomorphic permutation groups. Under this translation, multiplication and substitution of ages correspond to the direct product (in its intransitive action) and the wreath product (in its imprimitive action) of permutation groups.

5 Algebras

In this section, a graded algebra is associated with a class of finite structures. We make a conjecture about its structure, and give a structure theorem under additional hypotheses. See Cameron [3] for more details of the latter.

Let A be a class of finite structures satisfying our usual conditions (closed under isomorphism and under induced substructures, and containing only finitely many n-element structures up to isomorphism). For each n, let V_{n} denote the ℚ-vector space of all isomorphism-invariant rational functions on the set of nelement structures in A. Thus, dim(V_{n}) = a_{n}; a basis for V_{n} consists of the characteristic functions of the isomorphism classes of n-element structures.

We define

Alg(A) = ⨁_{n=0}^{∞} V_{n},

and define a product as follows. Take f ∈ V_{n}, g ∈ V_{m}. Then fg is the function in V_{n+m} whose value on the (n + m)-element structure X ∈ A is given by

(fg)(X) = ∑_{{Y ⊆X \atop |Y |=n}} f(Y)g(X \ Y).

This multiplication is extended linearly to the whole of Alg(A). The algebra is easily seen to be commutative and associative. An element of Alg(A) is said to be homogeneous of degree n if it is contained in V_{n}.

The construction behaves well with respect to multiplication of classes:

Proposition 5.1

Alg(A × B) = Alg(A) ⊗_{ℚ} Alg(B).

For A = S, we have dim(V_{n}) = 1 for all n, and in fact Alg(S) is a polynomial algebra in one variable, the generator being the function in V_{1} taking the value 1 on all singleton sets.

Conjecture: Suppose that A has the following property: for any A, B ∈ A, there exists C ∈ A in which A and B can be embedded as disjoint substructures. Then Alg(A) is an integral domain (i.e., has no divisors of zero).

We make some remarks about this conjecture. First, the condition is clearly necessary. For, if A and B cannot be embedded disjointly in any A-structure, then f_{A}f_{B} = 0, where f_{A} is the characteristic function of the isomorphism class of A. Also, the condition is a strengthening of the joint embedding property; so a class A satisfying it is the age of a countably infinite structure M. In this case, Alg(A) is a subalgebra of the reduced incidence algebra of the poset of finite subsets of M (Rota [17]).

If a graded algebra is a polynomial algebra generated by homogeneous elements, then the relation between the sequence enumerating the polynomial generators by degree and the sequence of dimensions of the homogeneous components is identical to the relation between the sequences enumerating unlabelled conneced and arbitrary structures, met with at the start of Section 2. This observation motivates the following result, taken from Cameron [3].

Theorem 5.2 Let A be a class of structures. Suppose that A possesses

(i) a subclass of “connected” structures;

(ii) a partial order ≤ of “involvement” on the set of n-element structures for each n;

(iii) a commutative and associative “composition” ∘ such that |A ∘ B| = |A| + |B|.

Assume:

(i) Any structure in A is uniquely the composition of connected structures.

(ii) If A ∈ A is partitioned into substructures A_{1}, A_{2}, …, then A_{1}∘A_{2}∘⋯ ≤ A.

Then Alg(A) is a polynomial algebra generated by the characteristic functions of the isomorphism classes of connected structures in A.

The conditions of the theorem are satisfied when A is the class of all graphs; we take “connected” to have its usual meaning, “involvement” to mean “spanning subgraph”, and “composition” to be “disjoint union”. A more unusual example involves the words considered in Section 2. As there, a word is “connected” if it is a Lyndon word (smaller than any proper cyclic shift of itself); “involvement” is lexicographic order, reversed; and “composition” is concatenation in lexicographically decreasing order. Now the hypotheses of the Theorem are satisfied. The algebra Alg(A) is the shuffle algebra, which occurs in the theory of free Lie algebras (see Reutenauer [16]), and which was shown to be a polynomial algebra by Radford [13].

References

[1] P. J. Cameron, Oligomorphic Permutation Groups, London Math. Soc. Lecture Notes 152, Cambridge University Press, Cambridge, 1990.

[2] P. J. Cameron, On the probability of connectedness, Discrete Math., submitted.

[3] P. J. Cameron, The algebra of an age, in preparation.

[4] M. H. El-Zahar, Enumeration of ordered sets, pp. 327–352 in Algorithms and Order (ed. I. Rival), Kluwer, Dordrecht, 1989.

[5] P. Erdős and A. Rényi, Asymmetric graphs, Acta Math. Acad. Sci. Hungar. 14 (1963), 295–315.

[6] P. Flajolet and A. M. Odlyzko, Singularity analysis of generating function, SIAM J. Discrete Math. 3 (1990), 216–240.

[7] R. Fraïssé, Sur certains relations qui généralisent l’ordre des nombres rationnels, C. R. Acad. Sci. Paris 237 (1953), 540–542.

[8] W. K. Hayman, A generalisation of Stirling’s formula, J. Reine Angew. Math. 196 (1956), 67–95.

[9] A. Joyal, Une théorie combinatoire des séries formelles, Advances Math. 42 (1981), 1–82.

[10] A. M. Odlyzko, Asymptotic enumeration methods, pp. 1063–1229 in Handbook of Combinatorics (ed. R. Graham, M. Grötschel and L. Lovász), Elsevier, Amsterdam, 1995.

[11] R. Otter, The number of trees, Ann. Math. (2) 49 (1948), 583–599.

[12] G. Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math. 68 (1937), 145–254.

[13] D. E. Radford, A natural ring basis for the shuffle algebra and an application to group schemes, J. Algebra 58 (1979), 432–454.

[14] R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340.

[15] A. Rényi, Some remarks on the theory of trees, Publ. Math. Inst. Hungar. Acad. Sci. 4 (1959), 73–85.

[16] C. Reutenauer, Free Lie Algebras, Oxford University Press, Oxford, 1994.

[17] G.-C. Rota, On the foundations of combinatorial theory, I: Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie 2 (1964), 340–368.

[18] R. P. Stanley, Enumeration of posets generated by disjoint unions and ordinal sums, Proc. Amer. Math. Soc. 45 (1974), 295–299.

[19] E. M. Wright, A relationship between two sequences, I, Proc. London Math. Soc. (3) 17 (1967), 296–304; II, ibid. (3) 17 (1967), 547–552; III, J. London Math. Soc. (1) 43 (1968), 720–724.