# The profile of relations *.

Abstract

Le profil d'une structure relationelle R est la fonction [[phi].sub.R] qui compte pour chaque entier n le nombre de ses sous-structures a n elements, les sous-structures isomorphes etant identifiees. Dans cet expose, je donne quelques exemples, notamment des exemples venant des groupes, et presente quelques faits frappants concernant le comportement des profils. J'indique le role joue par quelques notions de la theorie de l'ordre et de la combinatoire (eg belordre, algebre ordonnee, theoreme de Ramsey) dans l'etude du profil. Comme illustration, je montre que le profil d'une structure relationnelle R dont l'age est inepuisable et de hauteur au plus [omega](k + 1) satisfait l'inegalite [EXPRESSION MATHEMATIQUE NON REPRODUCIBLE EN ASCII.] pour tout entier n. Les recherches en cours suggerent de voir le profil d'une structure relationnelle R comme la fonction de Hilbert d'une algebre graduee associee a R; un exemple est l'algebre d'un age, inventee par P.J. Cameron. Je presente la solution d'une conjecture de Cameron sur l'integrite de l'algebre d'un age, ainsi que quelques progres recents faits avec Y.Boudabbous et N.Thiery sur la conjecture que la serie generatrice associee a un profil est une fraction rationnelle lorsque ce profil est borne par un polynome (et la structure a un noyau fini).

AMS Subject Classification: 03 C13, 03 C52, 05 A16, 05 C30, 20 B27.

Keywords: Relational structures, ages, counting functions, oligomorphic groups, age algebra, Ramsey theorem, well quasi ordering, cellular graphs, tournaments.

1 Introduction

This paper is a survey about the properties of a combinatorial function, the profile of a relational structure. I present a collection of results, some old, going back to 1971, some new, some published, some unpublished, and -in order to give to the reader a flavor of the techniques- I detail some proofs. An overview of results is given in Section 2. It is organized around two striking properties of the profile, namely: the profile of an infinite relational structure R is non decreasing and, provided that the arity of relations constituting R is bounded or the kernel of R is finite, its growth rate is either polynomial or faster than every polynomial. As observed by P.J.Cameron, the Hilbert function of the algebra of invariants of a finite group is a profile. This suggests that the generating series associated to a profile could be a rational fraction whenever the profile is bounded by a polynomial (and the relational structure has a finite kernel). I present a positive solution obtained jointly with N. Thiery for the class of relational structures admitting a finite decomposition into monomorphic components. As an illustration, I present the characterization of tournaments with polynomial profile obtained with Y. Boudabbous. A graded algebra, the age algebra, was associated by P.J Cameron to a relational structure R in such a way that its Hilbert function is the profile of R. This algebra and its role are presented in Section 3. The solution of a conjecture of Cameron on the integrity of the age algebra is also presented. These two sections contain very few detailed proofs. Some combinatorial tools needed for the study of the profile are presented in Section 4. An outline of the proof that the growth rate of a profile is either polynomial or faster than every polynomial is given (see Theorem 4.30). One of its ingredients is proved, namely the fact that the profile of a relational structure R whose age is inexhaustible and of height at most (k + 1) satisfies the inequality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every non-negative integer n (Theorem 4.28).

The work presented here benefited from discussions and collaborations with several colleagues. I am pleased to thank them. I am particularly pleased to mention Y. Boudabbous, M. Sobrani and N. Thiery. Without them, the paper would have been different.

This paper is an outgrowth of a paper presented at the conference in honor of Claude Benzaken, in Grenoble, in september 2002. Since then, its content was presented to several audiences, eg in Caracas, Kingston, St Denis de la Reunion, Calgary, Tampere, Sfax and, last but not the least, in Hammamet, March 2006, at the annual meeting of the "Societe Mathematique de Tunisie". I thank the organizers for offering me this opportunity, the incentive to write this paper and for their warm hospitality.

2 Overview

2.1 Definitions and Simple Examples

A relational structure is a realization of a language whose non-logical symbols are predicates. This is a pair R := (E, [([[rho].sub.i]).sub.i [member of] I]) made of a set E and of a family of [m.sub.i]-ary relations [[rho].sub.i] on E. The set E is the domain or base of R. The family [mu] := [([m.sub.i]).sub.i[member of]I] is the signature of R. The substructure induced by R on a subset A of E, simply called the restriction of R to A, is the relational structure [R.sub.[up arrow]A] := (A, [([A.sup.[m.sub.i]] [intersection] [[rho].sub.i]).sub.i[member of]I]). Notions of isomorphism and local isomorphism from a relational structure to an other one are defined in a natural way as well as the notion of isomorphic type (see Section 4 for undefined notions). In the sequel, [tau](R) stands for the isomorphic type of a relational structure R and [[OMEGA].sub.[mu]] stands for the set of isomorphic types of finite relational structures with signature [mu].

The profile of R is the function [[phi].sub.R] which counts for every integer n the number [[phi].sub.R](n) of substructures of R induced on the n-element subsets, isomorphic substructures being identified.

Clearly, this function only depends upon the set A(R) of finite substructures of R considered up to an isomorphism, a set introduced by R. Fraisse under the name of age of R (see [14]).

If the signature [mu] is finite (in the sense that I is finite), there are only finitely many relational structures with signature [mu] on an n-element domain, hence [[phi].sub.R](n) is necessarily an integer for each integer n. In order to capture examples coming from algebra and group theory, we cannot preclude I to be infinite. But then, [[phi].sub.R](n) could be an infinite cardinal. As far as we will be concerned by the behavior of [[phi].sub.R], we will exclude this case. Indeed, we have:

Fact 1. Let n < |E|. Then

[[phi].sub.R](n) [less than or equal to] (n + 1)[[phi].sub.R](n + 1) (2.1)

In particular:

If [[phi].sub.R](n) is infinite then [[phi].sub.R](n + 1) is infinite too and [[phi].sub.R](n) = [[phi].sub.R](n + 1). (2.2)

Inequality (2.1) follows from a simple counting argument. Let [[E].sup.n] be the set of n-element subsets of E, A[(R).sub.n] := {[tau]([R.sub.[up arrow]F]) : F [member of] [[E].sup.n]} and [[E].sup.n+1], A[(R).sub.n+1] be the sets defined in a similar way. Let [GAMMA] := {([tau]([R.sub.[up arrow]F]), [tau] ([R.sub.[up arrow]F[union]{x}])) : F [member of] [[E].sup.n] and x [member of] E F}. We have trivially [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Item (2) follows immediately.

Hence, except in very few occasions, mentioned in the text, we make the assumption that [[phi].sub.R] is integer valued, no matter how large I is. With this assumption, profiles of relational structures with bounded signature are profiles of relational structures with finite signature, structures that R. Fraisse call multirelations, a fact that we record for further use.

Fact 2. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure of signature [mu] := [([m.sub.i]).sub.i[member of]I] and let n be a non-negative integer.

1. If [[phi].sub.R](n) is an integer there is a finite subset I' of I (whose size is bounded by a function of n and [[phi].sub.R](n)) such that the local isomorphisms of R and of its reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) which are defined on the n-element subsets of E are the same, hence [[phi].sub.R](n) = [[phi].sub.[R.sup.[up arrow]I']](n).

2. If in addition [mu] is bounded above by n, that is max [mu] := max{[m.sub.i] : i [member of] I} [less than or equal to] n, one may choose I' such that [[phi].sub.R] = [[phi].sub.[R.sup.[up arrow]I']].

Several counting functions are profiles. Here is some simple minded examples.

1. The binomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Let R := ([??],[less than or equal to], [u.sub.1],..., [u.sub.k]) where = is the natural order on the set [??] of rational numbers, [u.sub.1],..., [u.sub.k] are k unary relations which divide [??] into k + 1 intervals. Then [[phi].sub.R](n) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

2. The exponential n [??] [k.sup.n]. Let R := ([??],=, [u.sub.1],..., [u.sub.k]), where again [u.sub.1],..., [u.sub.k] are k unary relations, but which divide [??] into k "colors" in such a way that between two rational numbers all colors appear. Then [[phi].sub.R](n) = [k.sup.n].

3. The factorial n [??] n!. Let R := (Q,[less than or equal to], [less than or equal to]'), where [less than or equal to]' is an other linear order on [??] such a way that the finite restrictions induce all possible pairs of two linear orders on a finite set (eg take for [less than or equal to]' an order with the same type as the natural order on the set N of non-negative integers). Then [[phi].sub.R](n) = n!

4. The partition function which counts the number p(n) of partitions of the integer n. Let R := ([??], n) be the infinite path on the integers whose edges are pairs {x, y} such that y = x + 1. Then [[phi].sub.R](n) = p(n). The determination of its asymptotic growth is a famous achievement, the difficulties encountered to prove that p(n) [??] 1/4[square root of 3n][e.sup.[pi][square root of 2n/3]] (Hardy and Ramanujan, 1918) suggest some difficulties in the general study of profiles.

An important class of functions comes from permutation groups. The orbital profile of a permutation group G acting on a set E is the function [[theta].sub.G] which counts for each integer n the number, possibly infinite, of orbits of the n-element subsets of E. As it is easy to see, [[theta].sub.G] is the profile of some relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) on E. In fact, as it is easy to see:

Lemma 2.1. For every permutation groupGacting on a set E there is a relational structure R on E such that:

1. Every isomorphism f from a finite restriction of R onto an other extends to an automorphism of R.

2. AutR = [bar.G] where[bar.G] is the topological adherence of G into the symmetric group [??](E), equipped with the topology induced by the product topology on [E.sup.E], E being equipped with the discrete topology.

Structures satisfying condition 1) are called homogeneous (or ultrahomogeneous). They are now considered as one of the basic objects of model theory. Ages of such structures are called Fraisse classes after their characterization by R.Fraisse[13]. In many cases, I is infinite, even if [[theta].sub.G](n) is finite. Groups for which [[theta].sub.G](n) is always finite are said oligomorphic by P.J.Cameron. The study of their profile is whole subject by itself [5]. Their relevance to model theory stems from the following result of Ryll-Nardzewski [46].

Theorem 2.2. Let G acting on a denumerable set E and R be a relational structure such that AutR = [bar.G]. Then G is oligomorphic if and only if the complete theory of R is [[??].sub.0]-categorical.

2.2 A Sample of Results

2.2.1 The Profile Grows

Inequality (1) given in the previous subsection can be substantially improved:

Theorem 2.3. If R is a relational structure on an infinite set then [[phi].sub.R] is non-decreasing.

This result was conjectured with R.Fraisse [15]. We proved it in 1971; the proof--for a single relation- appeared in 1971 in R.Fraisse's book [16], Exercise 8 p. 113; the general case was detailed in [37]. The proof relies on Ramsey theorem [45]. We give it in 2.5.4.

More is true:

Theorem 2.4. If R is a relational structure on a set E having at least 2n + k elements then [[phi].sub.R](n) [less than or equal to] [[phi].sub.R](n + k).

Meaning that if |E| := m then [[phi].sub.R] increases up to m/2; and, for n [greater than or equal to] m/2 the value in n is at least the value of the symmetric of n w.r.t. m/2.

The result is a straightforward consequence of the following property of incidence matrices.

Let n, k, m be three non-negative integers and E be an m-element set. Let [M.sub.n,n+k] be the matrix whose rows are indexed by the n-element subsets P of E and columns by the n + k-element subsets Q of E, the coefficient [a.sub.P,Q] being equal to 1 if P [[subset].bar] Q and equal to 0 otherwise.

Theorem 2.5. If 2n + k [less than or equal to] m then [M.sub.n,n+k] has full row rank (over the the field of rational numbers).

With this result the proof of Theorem 2.4 goes as follows:

We suppose that [[phi].sub.R](n + k) is finite (otherwise, from Fact 1, the stated inequality holds). Thus, we may suppose also that E is finite (otherwise, for each isomorphic type [tau] of n + k-element restriction of R we select a subset Q of E such that [R.sub.[up arrow]Q] has type [tau] and we replace E by the union of the Q's). We consider the matrix whose rows are indexed by the isomorphic types [tau] of the restrictions of R to the n-element subsets of E and columns by the n-element subsets P of E, the coefficient [a.sub.[tau],P] being equal to 1 if [R.sub.[up arrow]P] has type [tau] and equal to 0 otherwise. Trivially, this matrix has full row rank, hence if we multiply it (from the left) with [M.sub.n,n+k] the resulting matrix has full row rank. Thus, there are [phi](n) linearly independent colums. These columns being distinct, the restrictions of R to the corresponding (n + k)-element subsets have different isomorphic types, hence [[phi].sub.R](n) = [[phi].sub.R](n + k).

We proved Theorem 2.4 in 1976 [32]. The same conclusion was obtained first for orbits of finite permutation groups by Livingstone and Wagner, 1965 [25], and extended to arbitrary permutation groups by Cameron, 1976 [3]. His proof uses the dual version of Theorem 2.5. Later on, he discovered a nice translation in terms of his age algebra. We present it in 3.2.

Theorem 2.5 is in W.Kantor 1972 [23], with similar results for affine and vector subspaces of a vector space. Over the last 30 years, it as been applied and rediscovered many times; recently, it was pointed out that it appeared in a 1966 paper of D.H.Gottlieb [20]. Nowadays, this is one of the fundamental tools in algebraic combinatorics. A proof, with a clever argument leading to further developments, was given by Fraisse in the 1986 edition of his book, Theory of relations, see [14].

2.2.2 Jumps in the Growth of the Profile

Infinite relational structures with profile constant, equal to 1, were called monomorphic and characterized by R. Fraisse who proved that they where chainable. Later on, those with profile bounded, called finimorphic, were characterized as almost chainable [15]. We present these characterizations in 2.5.3. Beyond bounded profiles, and provided that the relational structures satisfy some mild conditions, there are jumps in the behavior of the profiles: eg. no profile grows as log n or nlog n.

Let [phi]. : [??] [right arrow] [??] and [psi] : [??] [right arrow] [??]. Recall that [phi] = O([psi]) and [psi] grows as fast as [phi] if [phi](n) [less than or equal to] a[psi](n) for some positive real number a and n large enough. We say that [phi] and [psi] have the same growth if [phi] grows as fast as [psi] and [psi] grows as fast as [phi]. The growth of [phi] is polynomial of degree k if [phi] has the same growth as n [??] [n.sup.k]; in other words there are positive real numbers a and b such that [an.sup.k] [less than or equal to] [phi] [less than or equal to] [bn.sup.k] for n large enough. Note that the growth of [phi] is as fast as every polynomial if and only if [lim.sub.n[right arrow]+[infinity][phi](n)/[n.sup.k]] = +[infinity] for every non negative integer k.

Theorem 2.6. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure. The growth of [[phi].sub.R] is either polynomial or as fast as every polynomial provided that either the signature [mu] := [([[rho].sub.i]).sub.i[member of]I] is bounded or the kernel K(R) of R is finite.

The kernel of R is the set K(R) of x [member of] E such that A([R.sub.[up arrow]E\{x}]) [not equal to] A(R). Relational structures with empty kernel are those for which their age has the disjoint embedding property, meaning that two arbitrary members of the age can be embedded into a third in such a way that their domains are disjoint [34]. In Fraisse's terminology, ages with the disjoint embedding property are said inexhaustible and relational structures whose age is inexhaustible are said age-inexhaustible. We will say that relational structures with finite kernel are almost age-inexhaustible (1).

At this point, enough to know that the kernel of any relational structure which encodes an oligomorphic permutation group is finite (this fact immediate: if R encodes a permutation groupGacting on a set E then K(R) is the set union of the orbits of the 1-element subsets of E which are finite. Since the number of these orbits is at most [[theta].sub.G](1), if G is oligomorphic then K(R) is finite).

Corollary 2.7. The orbital profile of an oligomorphic group is either polynomial or faster than every polynomial.

Groups with orbital profile equal to 1 were described by P.Cameron in 1976 [3]. From his characterization, Cameron obtained that the growth rate of an orbital profile is ultimately constant, or it grows as fast as a linear function with slope 1/2.

For groups, and graphs, there is a much more precise result than Theorem 2.6. It is due to Macpherson, 1985 [27].

Theorem 2.8. The profile of a graph or a permutation groups grows either as a polynomial or as fast as [f.sub.[epsilon]], where [f.sub.[espsilon]](n) = [e.sup.[n.sup.1/2-[epsilon]]], this for every [epsilon] > 0.

Note that the [f.sub.[epsilon]] are somewhat similar to the partition function. Such growth cannot be prevented. Indeed, the partition function is the orbital profile of the automorphim group of an equivalence relation having infinitely many classes, all being infinite. Such a group is imprimitive. In fact, according to Macpherson 1987 [28]:

Theorem 2.9. If G is primitive then either [[theta].sub.G](n) = 1 for all n [member of] [??], or [[theta].sub.G](n) > [c.sup.n] for all n [member of] N, where c := [2.sup.1/5] - [??].

Some hypotheses on R are needed in Theorem 2.6, indeed

Theorem 2.10. For every non-decreasing and unbounded map [phi] : [??] [right arrow] [??], there is a relational structure R such that [[phi].sub.R] is unbounded and eventually bounded above by [phi].

More is true.

Let f : [??] [right arrow] [??] be a non-decreasing map such that 1 [less than or equal to] f(n) [less than or equal to] n + 1 for all n [member of] [??]. Let A := {n : f(n') < f(n + 1) for all n' < n + 1}. Let R := ([??], [([[rho].sub.n]).sub.n[member of]A]) in which each [[rho].sub.n] is n + 1-ary, with ([x.sub.1],..., [x.sub.n+1]) [member of] [[rho].sub.n] if and only if {[x.sub.1],..., [x.sub.n+1]} = {0,..., n}. Then [[phi].sub.R] = f.

The reader will notice that if f is unbounded then the signature of R is unbounded and also the kernel of R is infinite (equal to [??]).

The hypothesis about the kernel is not ad hoc. As it turns out, if the growth of the profile of a relational structure with a bounded signature is bounded by a polynomial then its kernel is finite(cf. Theorem 2.12 and Theorem 4.30).

An outline of the proof of Theorem 2.6 is given in the last section of the paper.

Theorems 2.6 and 2.10 were obtained in 1978 [33]. Theorem 2.10 and a part of Theorem 2.6 appear in [37], with a detailed proof showing that the growth of unbounded profiles of relational structures with bounded signature is at least linear. The notion of kernel is in [33], see also [34], [37], and [36] Lemme IV-3.1 p. 37.

2.3 Polynomial Growth

It is natural to ask:

Problem 1. If the profile of a relational structure R with finite kernel has polynomial growth, is [[phi].sub.R](n) [??] [cn.sup.k'] for some positive real c and some non-negative integer k'?

The problem was raised by P.J.Cameron for the special case of orbital profiles [5]. Up to now, it is unsolved, even in this special case.

An example, pointed out by P.J.Cameron, [5], suggests that a stronger property holds.

Let G' be the wreath product G' := G[??][[??].sub.[omega]] of a permutation group G acting on {1,..., k} and of [[??].sub.[omega]], the symmetric group on [omega]. Looking at G' as a permutation group acting on E' := {1,..., k} x [omega], then - as observed by Cameron-[[theta].sub.G'] is the Hilbert function [h.sub.Inv(G)] of the subalgebra Inv(G) of [??][[x.sub.1],..., [x.sub.k]] consisting of polynomials in the k indeterminates [x.sub.1],..., [x.sub.k] which are invariant under the action of G. The value of [h.sub.Inv(G)](n) is, by definition, the dimension dim([Inv.sub.n](G)) of the subspace of homogeneous polynomials of degree n. As it is well known, the Hilbert series of Inv(G),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a rational fraction of the form

P(x)/(1 - x) ... (1 - [x.sup.k]) (2.3)

with P(0) = 1, P(1) > 0, and all coefficients of P being non negative integers.

Problem 2. Find an example of a permutation group G' acting on a set E with no finite orbit, such that the orbital profile of G' has polynomial growth, but is not the Hilbert function of the invariant ring Inv(G) associated with a permutation group G acting on a finite set.

Let us associate to a relational structure R whose profile takes only finite values its generating series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Problem 3. If R has a finite kernel and [[phi].sub.R] is bounded above by some polynomial, is the series [H.sub.[phi]R] a rational fraction of the form

P(x)/(1 - x)(1 - [x.sup.2]) ... (1 - [x.sup.k])

with P [member of] [??][x]?

Under the hypothesis above we do not know if [H.sub.[phi]R] is a rational fraction.

It is well known that if a generating function is of the form P(x)/(1-x)(1-[x.sup.2]) ... (1-[x.sup.k]) then for n large enough, an is a quasi-polynomial of degree k', with k' [less than or equal to] k - 1, that is a polynomial [a.sub.k'](n)[n.sup.k'] + ... + [a.sub.0](n) whose coefficients [a.sub.k'](n),..., [a.sub.0](n) are periodic functions. Hence, a subproblem is:

Problem 4. If R has a finite kernel and [[phi].sub.R] is bounded above by some polynomial, is [[phi].sub.R](n) a quasi-polynomial for n large enough?

Remark 2.11. Since the profile is non-decreasing, if [[phi].sub.R](n) is a quasi-polynomial for n large enough then [a.sub.k'](n) is eventually constant. Hence the profile has polynomial growth in the sense that [[phi].sub.R](n) ~ [cn.sup.k'] for some positive real c and k' [member of] [??]. Thus, in this case, Problem 1 has a positive solution.

In the theory of languages, one of the basic results is that the generating series of a regular language is a rational fraction (see [1]). This result is not far away from our considerations. Indeed, if A is a finite alphabet, with say k elements, and [A.sup.*] is the set of words over A, then each word can be viewed as a finite chain coloured by k colors and [A.sup.*] can be viewed as the age of the relational structure made of the chain [??] of rational numbers divided into k colors in such a way that, between two distinct rational numbers, all colors appear. This structure was Example (2) in Subsection 1.1.

Problem 5. Does the members of the age of a relational structure with polynomial growth can be coded by words forming a regular language?

Problem 6. Extend the properties of regular languages to subsets of [[OMEGA].sub.[mu]].

2.4 Morphology of Relational Structures with Polynomial Growth

We only have a partial description of relational structures with polynomial growth.

Let us say that a relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is almost multichai-nable if there is a finite subset F of E and an enumeration [([a.sub.x,y]).sub.(x,y)[member of]VxL] of the elements of E \ F by a set V x L, where V is finite and L is a linearly ordered set, such that for every local isomorphism f of L the map ([1.sub.V], f) extended by the identity on F is a local isomorphism of R (the map ([1.sub.V], f) is defined by ([1.sub.V], f)(x, y) := (x, f (y))).

Note that if L is infinite, K(R), the kernel of R, is a subset of F. Thus we have:

Fact 3. An almost multichainable relational structure has a finite kernel.

The notion of almost multichainability was introduced in [33] and appeared in [36, 34]. It seems to be a little bit hard to swallow. The special case |V| = 1, for which the linear order L can be defined on E F, is discussed in more details in 2.5.3.

The profile of an almost multichainable relational structure is not necessarily bounded above by a polynomial (see the last two examples given in Examples 2.13).

Problem 7. If the profile of an almost multichainable relational structure is not bounded above by a polynomial, does his profile has exponential growth? Is the generating series a rational fraction?

Theorem 2.12. If the profile of a relational structure R with bounded signature or finite kernel is bounded above by a polynomial then R is almost multichainable.

For a proof, see Section 4, Theorem 4.30.

There are two cases, in fact opposite cases, for which the profile of an almost multichainable relational structure is bounded above by a polynomial.

1. Case 1. ([1.sub.V], f) extended by the identity on F is an automorphism of R for every permutation f of L.

2. Case 2. For every family [([f.sub.x]).sub.x[member of]V] of local isomorphisms of L, the map [union]{[f.sub.x] : x [member of] V} extended by the identity on F is a local isomorphism of f (the map [union]{[f.sub.x] : x [member of] V} associates (x, [f.sub.x](y)) to (x, y)).

A relational structure for which there are F and [([a.sub.x,y]).sub.(x,y)[member of]VxL] such that Case 1 holds is cellular. This notion was introduced by Schmerl [47]. We illustrate it below. Relational structures for which case 2 holds are illustrated in subsection 2.5.

2.4.1 The Case of Graphs

A directed graph is a pair G := (E, [rho]) where [rho] is a binary relation on E. Ordered sets and tournaments are special case of directed graphs. We will use the term graph if [rho] is irreflexive and symmetric. In this case [rho] is identified with the set E of pairs {x, y} of members of E such that x[rho]y, G is identified with (E, E); the members of E and E are the vertices and edges of G. We denote by V (G), resp. E(G), the set of vertices, resp. edges, of G.

In terms of profile, the class of graphs provides interesting examples.

Examples 2.13. 1. [[phi].sub.G](n) is constant, equal to 1, for every n [less than or equal to] |V(G)|, if and only if [[phi].sub.G](2) [less than or equal to] 1, that is G is a clique or an independent set (trivial).

2. [[phi].sub.G] is bounded if and only if G is "almost constant" in the Fraisse's terminology, that is there is a finite subset [F.sub.G] of vertices such that two pairs {x, y} and {x', y'} of vertices having the same intersection on [F.sub.G] are both edges or both non-edges. This fact is an immediate consequence of Theorem 2.25.

3. If G is the direct sum of infinitely many edges, or the direct sum [K.sub.[omega]] [direct sum] [K.sub.[omega]] of two infinite cliques, then [[phi].sub.G](n) = [n/2] + 1, whereas [H.sub.[phi]G] = 1/(1-x)(1-[x.sup.2]).

4. Let G be the direct sum [K.sub.(1,[omega])] [direct sum] [[bar.K].sub.[omega]] of an infinite wheel and an infinite independent set, or the direct sum [K.sub.[omega]] [direct sum] [[bar.K].sub.[omega]] of an infinite clique and an infinite independent set. Then [[phi].sub.G](n) = n. Hence [H.sub.[phi]G] = 1 + x/[(1-x).sup.2], that we may write 1-x- [x.sup.2]/[(1-x).sup.2], as well as 1+[x.sup.3]/(1-x)(1-[x.sup.2]).

5. Let G be the direct sum of infinitely many k-element cliques or the direct sum of k infinite cliques. Then [[phi].sub.G](n) = [p.sub.k](n) [??] [n.sup.k-1]/(k-1)!k! and [H.sub.[phi]G] = 1/(1-x) ... (1- [x.sup.k]).

6. If G is either the direct sum of infinitely many infinite cliques -or an infinite path- then [[phi].sub.G](n) = p(n) the partition function.

7. Let C := (E, [less than or equal to]) be a chain and [K.sub.C,1/2] be the graph whose vertex set is 2 x E and the edge set is {{(0, i), (1, j)} : i < j in C}. Such a graph is an half-complete bipartite graph. If C is infinite, then [2.sup.n-2] [less than or equal to] [[phi].sub.[K.sub.C, 1/2]](n) [less than or equal to] [2.sup.n-1] [27], hence its growth is exponential. In fact, one can check that: [H.sub.[K.sub.C,1/2]] = 1-2x- [x.sup.2]+3[x.sup.3]-[x.sup.4]/(1-x)(1-2x)(1-2[x.sup.2]) = 1 + x + 2[x.sup.2] + 3[x.sup.3] + 6[x.sup.4] + 10[x.sup.5] + 20[x.sup.6] + 36[x.sup.7] + 72[x.sup.8] + 136[x.sup.9] + O([x.sup.10]).

8. Let [[??].sub.C,1/2] be the graph obtained from [K.sub.C,1/2] by adding all possible edges between vertices of the form (1, i), for i [member of] E. Then [[phi].sub.[[??].sub.C,1/2]](n) = [2.sup.n-1].

Theorem 2.14. The profile of a graph is bounded by a polynomial if and only if this graph is cellular.

A straightforward computation shows that the profile of a cellular graph is bounded by a polynomial. The converse follows directly from Theorem 2.12 and Lemma 2.15 below. A self-contained proof will hopefully appear in a joint work with S. Thomasse and R. Woodrow. Lemma 2.15. The growth of the profile of almost multichainable graph which is not cellular is at least exponential

Indeed, let G be an almost multichainable graph. The sets F, V and L which appear in the definition of the almost multichainability of G satisfy the following conditions: F,V are finite, V(G) = F [union] V x L and:

{a, (x, i)} [member of] E(G) if and only if {a, (x, j)} [member of] E(G) (2.4)

for all a [member of] F, x [member of] V, j [member of] L

{(x, i), (y, j)} [member of] E(G) if and only if {(x, i'), (y, j ')} [member of] E(G) (2.5)

for all x, y [member of] V, i, j, i', j' [member of] L such that i[rho]j and i'[rho]j' where [rho] is either the equality relation on L or the strict order < on L.

If G is not cellular then there is some permutation f of L such that ([1.sub.V], f) extended by the identity on F is not an automorphism of G. The map f does not preserve the order on L, hence, there are [i.sub.0], [j.sub.0] [member of] L and x, y [member of] V such that {(x, [i.sub.0]), (y, [j.sub.0])} [member of] E(G) and {(x, [j.sub.0]), (y, [i.sub.0])} [??] E(G).

Let H := [G.sub.[up arrow]{x,y}xL]. This graph is multichainable, hence it is entirely determined by the edges belonging to [[{x, y}x{[i.sub.0], [j.sub.0]}].sup.2]\{(x, [j.sub.0]), (y, [j.sub.0])}. There are 16 possible graphs. But, if L is infinite, these graphs yield only two distinct ages, namely the age of [K.sub.C,1/2] and the age of [[??].sub.C,1/2], two graphs described in (7) and (8) of Examples 2.13. Hence, they yield at most two distinct profiles. Their growth rates, as computed in Examples 2.13, are exponential, hence the growth rate of [[phi].sub.G] is at least exponential as claimed.

We do not know if Problem 1 has a positive answer for cellular graphs. Problem 3 has a positive answer for a special class of relational structures described in the following subsection.

2.5 Relational Structures Admitting a Finite Monomorphic Decomposition

A monomorphic decomposition of a relational structure R is a partition P of E into blocks such that for every integer n, the induced structures on two n-elements subsets A and A' of E are isomorphic whenever the intersections A[intersection]B and A'[intersection]B over each block B of P have the same size.

This notion was introduced with N. Thiery [42].

If an infinite relational structure R has a monomorphic decomposition into finitely many blocks, whereof k are infinite, then the profile is bounded by some polynomial, whose degree itself is bounded by k - 1. Indeed, as one may immediately see:

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

where r is the cardinality of the union of the finite blocks.

One can say more:

Theorem 2.16 ([42]). Let R be an infinite relational structure R with a monomorphic decomposition into finitely many blocks ([E.sub.i], i [member of] X), k of which being infinite. Then, the generating series [H.sub.[phi]R] is a rational fraction of the form:

P(x)/(1 - x)(1 - [x.sup.2]) ... (1 - [x.sup.k]).

Corollary 2.17 ([42]). Let R a relational structure as above, then [[phi].sub.R] has a polynomial growth and in fact [[phi].sub.R](n) ~ [an.sup.k'] for some positive real a, some non-negative integer k'.

Recently, with N. Thiery, we proved:

Lemma 2.18. If k is the least number of infinite blocks that a monomorphic decomposition of R may have then [[phi].sub.R](n) ~ [an.sup.k-1].

The proof idea of Theorem 2.16 is this. To each subset A of size n

of E, we associate the monomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

where [d.sub.i](A) = |A [intersection] [E.sub.i]| for all i in X. Obviously, A is isomorphic to B whenever [x.sup.d(A)] = [x.sup.d(B)]. The shape of a monomial [x.sup.d] = [PI] [x.sup.[d.sub.i].sub.i] is the partition obtained by sorting decreasingly ([d.sub.i], i [member of] X). We define a total order on monomials by comparing their shape w.r.t. the degree reverse lexicographic order, and breaking ties by the usual lexicographic order on monomials w.r.t. some arbitrary fixed order on X. If [tau] [member of] A(R) its leading monomial lm([tau]) is the maximum of the monomials [x.sup.d(A)] where [R.sub.[up arrow]A] has isomorphic type [tau]. If S is subset of X, set [x.sub.S] := 1 if S = [empty set] and [x.sub.S] := [[PI].sub.i[member of]S] [x.sub.i] otherwise. We may write every monomial m (distinct from 1) as a product [PI][([x.sub.[S.sub.1]]).sup.[m.sub.1]] ... [([x.sub.[S.sub.k]]).sup.[m.sub.k]] for a unique sequence C := ([empty set] [??] [S.sub.1] [??] ... [S.sub.r] [subset.bar] X) of non-empty subsets of X. This sequence is the chain support of m. To such a sequence C, we associate the set [lm.sub.C] of leading monomials with chain support C. We prove that one can realize [lm.sub.C] as the linear basis of some ideal of a polynomial ring, so that the generating series of [lm.sub.C] is realized as an Hilbert series. From this, one concludes easily that [H.sub.[phi]R] has the same form.

The key property of leading monomials in this proof is this lemma:

Lemma 2.19 ([42]). Let m be a leading monomial, and S [subset] X be a layer of m. Then, either [d.sub.i] = |[E.sub.i]| for some i in S, or [mx.sub.S] is again a leading monomial.

The proof of this result relies on Proposition 2.20 below for which we introduce the following definition. Let R be a relational structure on E; a subset B of E is a monomorphic part of R if for every integer n and every pair A, A' of n-element subsets of E the induced structures on A and A' are isomorphic whenever A \ B = A' \ B.

Proposition 2.20 ([42]). 1. For every x [member of] E, the set-union R(x) of all the monomorphic parts of R containing x is a monomorphic part, the largest monomorphic part of R containing x.

2. The largest monomorphic parts form a monomorphic decomposition of R of which every monomorphic decomposition of R is a refinement.

We will call canonical the decomposition of R into maximal monomorphic parts. This decomposition has the least possible number of parts.

Despite the apparent simplicity of relational structures admitting a finite monomorphic decomposition, there are many significant examples.

2.5.1 Relational Structures which are Categorical for Their Age

A relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is categorical for its age if every R' having the same age than R is isomorphic to R. It was proved in [22] that for a relational structure with a finite signature, this happens just in case E is at most denumerable and can be divided into finitely many blocks such that every permutation of E which preserves each block is an automorphism of R.

These structures may occur in some interesting areas. For a simple minded example, let G' := G[??][[??].sub.[omega]] be the wreath product of a permutation group G acting on {1,..., k} and of [[??].sub.[omega]], the symmetric group on [omega]. As we have noticed, the orbital profile of G' is the Hilbert function of the algebra of invariants of G. Now, the group G' is the automorphism group of a relational structure R which is categorical for its age. Among the possible R' take R' := (E', [([[bar.[rho]].sub.i]).sub.i[member of]I]) where [[bar.[rho]].sub.i] := {(([x.sub.1],[m.sub.1]),..., ([x.sub.[n.sub.i]],[m.sub.[n.sub.i]])) : ([x.sub.1],..., [x.sub.[n.sub.i]]) [member of] [[rho].sub.i], ([m.sub.1],..., [m.sub.[n.sub.i]]) [member of] [[??].sup.{1,..., [n.sub.i]}}, R := ({1,..., k}, [([[rho].sub.i]).sub.i[member of]I]) is a relational structure containing the equality relation and having signature [mu] := [([n.sub.i])[member of]I] such that AutR = G. Such an R' decomposes into k monomorphic components, namely the sets [E'.sub.i], 1 [less than or equal to] i < k (where [E'.sub.i] := {(i, m) : m [member of] [??]}).

2.5.2 Quasi-Symmetric Polynomials

Let [x.sub.1],..., [x.sub.k] be k-indeterminates and [n.sub.1],..., [n.sub.l] be a sequence of non-negative integers, 1 [less than or equal to] l [less than or equal to] k. The polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a quasi-monomial of degree n, where n =: [n.sub.1] + ... + [n.sub.l]. The vector space spanned by the quasi-monomials forms the space [QS.sub.k] of quasi-polynomials as introduced by I. Gessel. As in the example above, the Hilbert series of [QS.sub.k+1] is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

As shown by F. Bergeron, C. Retenauer, see [18], this series is a rational fraction of the form [P.sub.k]/(1-x)(1-[x.sup.2]) ... (1-[x.sup.k]) where the coefficients [P.sub.k] are non negative. Let R be the poset product of a k-element chain by a denumerable antichain. More formally, R := (E, [rho]) where E := {1,..., k} x [??] and [rho] := {((i, n), (j, m)) [member of] E such that i [less than or equal to] j}. Each isomorphic type of an n-element restriction may be identified to a quasi-polynomial, hence the generating series associated to the profile of R is the Hilbert series defined above. Since R decomposes into k monomorphic components, the rationality of this series is a special case of Theorem 2.16. The reason for which the coefficients of this fraction are non-negative was elucidated only recently by Garsia and Wallach [18]. They proved that [QS.sub.k] is Cohen-Macaulay.

2.5.3 Monomorphic Relational Structures, Chainability and Extensions

We present here the origin of the notion of relational structure admitting a monomorphic decomposition into finitely many blocks.

According to R.Fraisse who introduced this notion in 1954 in his thesis, a relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) for which [[phi].sub.R](n) = 1 for every n [less than or equal to] |E| is monomorphic.

Example 2.21. There are eight kinds of monomorphic directed graphs, four made of reflexive directed graphs, four made of irreflexive graphs. For the reflexive ones, there are the chains, the reflexive cliques, the antichains, plus the 3-element oriented reflexive cycle. Whereas, for the irreflexive ones, there are the acyclic (oriented) graphs, the cliques, the independent sets, and the 3-element oriented irreflexive cycle.

Fraisse gave a characterization of infinite monomorphic relational structures by means of his notion of chainability:

A relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is chainable if there is a linear ordering [less than or equal to] on E such that every local isomorphism of L := (E, [less than or equal to]) is a local isomorphism of R.

Since chains are monomorphic, chainable relational structures are also monomorphic. The converse does not hold, as shown by a 3-element cycle. Fraisse proved that it holds if the structure is infinite.

Theorem 2.22. An infinite relational structure is monomorphic if and only if it is chainable.

His proof, given for relational structures of finite signature, was based on Ramsey's theorem [45] and the compactness theorem of first order logic. The extension to arbitrary signature requires an other application of the compactness theorem (for a detailed proof, see [37]).

We give the proof idea, in the setting of a generalization of the monomorphy and chainability notions.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure and F be a subset of E. The relational structure R is F-monomorphic if for every non-negative integer n and every A, A' [member of] [[E\F].sup.n] there is an isomorphism from [R.sub.[up arrow]A] onto [R.sub.[up arrow]A'] which extends by the identity on F to an isomorphism of [R.sub.A[union]F] onto [R.sub.A'[union]F']. This relational structure is F-chainable if there is a linear order [less than or equal to] on E \ F such that every local isomorphism of L := (E \ F, [less than or equal to]), once extended by the identity on F, is a local isomorphism of R. This relational structure is almost monomorphic, resp. almost chainable, if it is F-monomorphic, resp. F-chainable for some finite subset F of E.

From Ramsey's theorem, Fraisse deduced the following lemma.

Lemma 2.23. Let R be a relational structure with domain E and F be a finite subset of E. If the signature of R is finite then there is an infinite subset E' of E containing F on which the restriction R' := [R.sub.[up arrow]E'] is F-chainable.

Then he applied the compactness theorem of first order logic (in a weaker form, given by his "coherence lemma"). Indeed, from Lemma 2.23 above, if a monomorphic relational structure R of finite signature is infinite, it contains an infinite induced substructure R' which is chainable. Since R is monomorphic, each finite substructure of R is isomorphic to some finite substructure of R', hence is chainable. The compactness theorem insures that R is chainable. As said, this conclusion holds if the signature is arbitrary.

Theorem 2.22 has the following strenghtening.

Theorem 2.24. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure, E' be a subset of E and F := E' \ E. Let us consider the following properties

(i) R is F-chainable;

(ii) R is F-monomorphic;

(iii) E' is a monomorphic part of R.

Then (i) [??] (ii) [??] (iii). If E' is infinite then (ii) [??] (i). If E' is infinite and E' is a monomorphic component of R then (iii) [member of] (ii).

For these implications, one considers first the case for which the signature and F are finite. Then, one applies Lemma 2.23 and the compactness theorem of first order logic. The general case follows by another application of the compactness theorem.

This yields:

Theorem 2.25. For a relational structure, the following properties are equivalent:

(i) The profile of R is bounded by some integer.

(ii) R has a monomorphic decomposition into finitely many blocks, at most one being infinite.

(iii) R is almost chainable.

(iv) R is almost monomorphic.

Theorem 2.25 above was proved (without Item (ii)) in [15] for finite signature and in [37] for arbitrary signature. Theorem 2.3 was proved afterward.

From Theorem 2.3 and Theorem 2.25, it follows that a relational structure R has a monomorphic decomposition into finitely many blocks, at most one being infinite, if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

where [b.sub.1],..., [b.sub.l] re non negative integers.

With this elementary fact in hands, it was not so hard to conjecture the extension given in Theorem 2.16.

2.5.4 An illustration: a proof of Theorem 2.3

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure. Suppose E be infinite. Let n be a non negative integer. We claim that [[phi].sub.R](n) [less than or equal to] [[phi].sub.R](n + 1).

Case 1. [[phi].sub.R](n) is infinite. Then, as stated in Fact 1, [[phi].sub.R](n) = [[phi].sub.R](n + 1) as claimed.

Case 2. [[phi].sub.R](n) is finite. We reduce the claim to the case of an almost monomorphic relational structure.

Claim 1. There is some finite subset I' of I and some infinite subset E' of E such that the reduct R' := [R.sup.[up arrow]I'.sub.[up arrow]E'] is almost monomorphic and [[phi].sub.R'](n) = [[phi].sub.R](n).

Proof of Claim 1. According to (1) of Fact 2, there is some finite subset I' of I such that the reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) satisfies [[phi].sub.[R.sup.[up arrow]I']](n) = [[phi].sub.R](n). Let m := [[phi].sub.[R.sup.[up arrow]I']](n). Select [F.sub.1],... [F.sub.m] in [[E].sup.n] such that the restrictions [R.sup.[up arrow]I'.sub.[up arrow][F.sub.1]],..., [R.sup.[up arrow]I'.sub.[up arrow][F.sub.m]] are pairwise non-isomorphic. Set F := [F.sub.1] [union] ... [union] [F.sub.m]. According to Lemma 2.23, there is an infinite subset E' of E containing F such that the restriction R' := [R.sup.[up arrow]I'.sub.[up arrow].sub.E']] is F-chainable. This restriction is almost monomorphic. From our construction, [[phi].sub.R'](n) = m. This proves Claim 1.

Claim 2. If an infinite relational structure R' := (E', [([[rho].sub.i]).sub.i[member of]I']) is almost monomorphic then [[phi].sub.R'] is non-decreasing.

Proof of Claim 2. Let F be a finite subset of E' such that R' is F-monomorphic. Let n be a non-negative integer. Let m := [[phi].sub.R'](n) and let [[tau].sub.1],..., [[tau].sub.m] be the isomorphic types of the n-element restrictions of R'. Select [F.sub.1],..., [F.sub.m] such that for each i, 1 [less than or equal to] i [less than or equal to] m, [R'.sub.[up arrow][F.sub.i]] has type [[tau].sub.i] and |F [intersection] [F.sub.i]| is minimum. Pick x [member of] E' \(F[union] [F.sub.1][union] ... [union][F.sub.m]) and set [F'.sub.i] := [F.sub.i] [union]{x} for i, 1 = i = m. We claim that the restrictions [R'.sub.[up arrow][F'.sub.1]],..., [R'.sub.[up arrow][F'.sub.m]] are pairwise non-isomorphic, from which the inequality [[phi].sub.R'](n) [less than or equal to] [[phi].sub.R'](n + 1) will follow. Indeed, suppose that there is some isomorphism f from [R'.sub.[up arrow][F.sub.i]] onto [R'.sub.[up arrow][F.sub.j]]. With no loss of generality, we may suppose |[F.sub.i] [intersection] F| [greater than or equal to] |[F.sub.j] [intersection] F|. Then f(x) [??] F, otherwise [R'.sub.[up arrow][F".sub.j]], where [F".sub.j] := [F'.sub.j] \ {f (x)}, has type [[tau].sub.i] and |[F".sub.j] intersection] F| < |[F.sub.i] [intersection] F|, contradicting the choice of [F.sub.i] [member of] Hence f(x) [member of] [F'.sub.j] F. Since R' is F-monomorphic, the restriction [R'.sub.[up arrow][F.sub.j]\{f(x)}] and [R'.sub.[up arrow][F'.sub.j]]\{x} are isomorphic. Since their types are respectively [[tau].sub.i] and [[tau].sub.j], we have i =

2.5.5 Directed Graphs

Monomorphic decompositions can be easily described in the case of directed graphs.

For that we recall that a subset A [[subset].bar] V(G) of a a directed graph is autonomous if for every x, x' [member of] A, y [??] A, the following two conditions holds:

(x, y) [member of] E(G) if and only if (x', y) [member of] E(G)

(y, x) [member of] E(G) if and only if (y, x') [member of] E(G).

The empty set, the one-element subsets of V(G) and V(G) itself are autonomous. If there are no others, G is prime.

We also recall that, if a directed graph G is a lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], indexed by a directed graph D, then provided that there are pairwise disjoint, the V([G.sub.i]) form a partition of V(G) into automomous subsets. Conversely, if the vertex set V(G) of directed graph G is partionned into autonomous subsets, then G is the lexicographical sum of the directed graphs induced on the blocks of the partition.

Theorem 2.26. Let G be a directed graph. Then G has a finite monomorphic decomposition if and only if G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], indexed by a finite directed graph D, each [G.sub.i] being one of six kinds: an oriented acyclic graph, a clique, an independent set, a chain, a reflexive clique, or an antichain. Moreover, if G decomposes into such a sum with all the V([G.sub.i])'s non-empty and if D contains no 2-element autonomous subset, then both the monomorphic components of G and the V([G.sub.i])'s wich are infinite coincide.

Proof. Let W be a monomorphic component of G. If W is infinite then [G.sub.[up arrow]W] is of one of the six kinds mentionned in Theorem 2.26. Moreover, as it follows from implication (iii) [member of] (i) of Theorem 2.24, W is autonomous. Hence, if G has a finite monomorphic decomposition, the partition of V(G) into the infinite blocks of the canonical decomposition of G and of the singletons of the remainder is a partition into autonomous sets, each of one of these six kinds. If G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], each one of these six kinds and if a monomorphic component W contains some V([G.sub.i]) with V([G.sub.i]) infinite then W = V([G.sub.i]). Otherwise, since W is one of the six kinds above and W is autonomous, the set A := {j [member of] V(D) : [V.sub.j] [member of] W} is autonomous and D'A is of one of these six kind. Since D is finite, it contains a 2-element autonomous subset.

In the later case, Lemma 2.18 yields:

Corollary 2.27. If G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of non-empty directed graphs [G.sub.i], indexed by a finite directed graph D, each [G.sub.i] being either an oriented acyclic graph, a clique, an independent set, a chain, a reflexive clique, or an antichain and if D contains no 2-element autonomous subset then [[phi].sub.G](n) ~ [an.sup.k-1] where k is the number of infinite [G'.sub.i]s.

A prime directed graph D with |V(D)| [greater than or equal to] 3 cannot contain a 2-element autonomous subset. Since there are prime directed graphs of arbitrarily large size, Corollary 2.27 yields examples of directed graphs of polynomial growth of degree k for every non negative integer k.

2.5.6 Tournaments

The monomorphic tournaments are the acyclic ones and the 3-element cycle. Hence from Theorem 2.26, a tournament has a finite monomorphic decomposition if and only if it is a lexicographical sum of acyclic tournaments indexed by a finite tournament. We may reformulate this in a simpler form.

An acyclic component of a tournament T is a subset of V(T) which is maximal w.r.t. inclusion among the acyclic autonomous subsets of V(T). Clearly, every acyclic autonomous subset is contained into an acyclic component. As it is easy to see, the acyclic components of a tournament form a partition of its vertex set. It follows that a tournament is a lexicographical sum of acyclic tournaments indexed by a finite tournament if and only if it has only finitely many acyclic components.

With Y.Boudabbous [2], we identified twelve infinite tournaments and proved that an infinite tournament T is a finite lexicographical sum of acyclic tournaments if and only if T embeds none of these tournaments. The growth of the profile of each of these tournaments being exponential, we deduced from Theorem 2.16 andLemma2.18 the following dichotomy result.

Theorem 2.28. [2] The growth of the profile of a tournament T is either polynomial, in which case T is a lexicographic sum of acyclic tournaments indexed by a finite tournament, or it is at least exponential.

There are prime tournaments of arbitrarily large finite size, hence, according to Corollary 2.27 there are tournaments of arbitrarily large polynomial growth. We give below some examples of small growth.

Examples 2.29. 1. If T is an acyclic tournament, then [[phi].sub.T](n) = 1 for every integer n, n [less than or equal to] |T|. Conversely, if |T| [not equal to] 3 and [[phi].sub.T](3) = 1 then T is acyclic.

Let [omega] be the tournament made of the integers, with the strict ordering, that is [omega]:= ([??], {(p, q) [member of] [[??].sup.2] : p < q}), and let * be its dual. Note that according to the theorem of Ramsey, every infinite tournament contains a subtournament which is isomorphic to [omega] or to [[omega].sup.*].

Let [C.sub.3] := ({0, 1, 2}, {(0, 1), (1, 2), (2, 0)}) be the 3-element cycle. For i := 1, 2, 3, let [T.sub.i] be the tournament obtained by replacing i vertices of [C.sub.3] by [omega].

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

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

4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

The profile of tournaments goes largely beyond polynomials. For an example of exponential profile, let [C.sub.3.[omega]] be the lexicographical sum of infinitely many copies of [C.sub.3]. Then the generating serie of the profile is [H.sub.[[phi].sub.[C.sub.3.[omega]]]] = 1/1-x-[x.sup.3] hence the profile is exponential (see sequence A000930 in Encyclopedia of integer sequences (URL: http://www.research.att.com).).

3 The Age Algebra of Cameron

P. J. Cameron [5, 6] associates to A(R), the age of a relational structure R, its age algebra, a graded commutative algebra [??].A(R) over a field [??] of characteristic zero. He shows that if [[phi].sub.R] takes only finite values, then the dimension of [??].A[(R).sub.n], the homogeneous component of degree n of [??].A(R), is [[phi].sub.R](n). Hence, in this case, the generating series of the profile is simply the Hilbert series of [??].A(R).

P.J Cameron mentions several interesting examples of algebras which turn to be age algebras. The most basic one is the shuffle algebra on the set [A.sup.*] of words on a finite alphabet A [26]. Indeed, as mentionned at the end of Subsection 2.3, [A.sup.*] is the age of the relational structure ([??], [([U.sub.a]).sub.a[member og]A]) where the [U.sub.a]'s are unary relations forming a coloring of [??] into distinct colors, in such a way that between two distinct rational numbers, all colors appear. And the shuffle algebra is isomorphic to the age algebra of ([??], [([U.sub.a]).sub.a[member of]A]).

There are several reasons to associate a graded algebra to an age. We will examine some in the next subsections. For the ease of our discussion, we recall the presentation of the age algebra via the set algebra (see [8]).

3.1 The Set Algebra

Let E be a set and let [[E].sup.<[omega]] be the set of finite subsets of E (including the empty set [empty set]). Let [??] be a field and [[??].sup.[[E].sup.<[omega]]] be the set of maps f : [[E].sup.<[omega]] [right arrow] [??]. Endowed with the usual addition and scalar multiplication of maps, this set is a vector space over [??]. Let f, g [member of] [[??].sup.[[E].sup.<[omega]]] and Q [member of] [[E].sup.<[omega]]. Set

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

. With this operation added, the above vector space becomes a [??]-algebra. This algebra is commutative and it has a unit, denoted by 1. This is the map taking the value 1 on the empty set and the value 0 everywhere else. The set algebra is the subalgebra made of the maps such that f (P) = 0 for every P [member of] [[E].sup.<[omega]] with |P| large enough. This algebra is graded, the homogeneous component of degree n being made of maps which take the value 0 on every subset of size different from n.

Let = be an equivalence relation on [[E].sup.<[omega]]. A map f : [[E].sup.<[omega]] [right arrow] [??] is [equivalent to]-invariant, or briefly, invariant, if f is constant on each equivalence class. Invariant maps form a subspace of the vector space [[??].sup.[[E].sup.<[omega]]]. We give a condition which insure that they form a subalgebra too.

An equivalence relation on [[E].sup.<[omega]] is hereditary if every pair D, D' of equivalent elements satisfies the following conditions:

1. |D| = |D'| = d for some d.

2. |{X [[subset].bar] D : X = B}| = |{X [[subset].bar] D' : X [equivalent to] B}| for every B [[subset].bar] E

Hereditary equivalence where introduced in [39].

With N.Thiery, we proved:

Proposition 3.1. Let = be an hereditary equivalence relation on [[E].sup.<[omega]]. Then the product of two invariant maps is invariant. Thus the set of invariant maps f : [[E].sup.<[omega]] [right arrow] [??] form a subalgebra of [[??].sup.[[E].sup.<[omega]]].

Let R be a relational structure with domain E. Set F [equivalent to][sub.R] F' for F, F' [member of] [[E].sup.<[omega]] if the restrictions R [sub.[up arrow]F] and R [sub.[up arrow]F'] are isomorphic. The resulting equivalence on [[E].sup.<[omega]] is hereditary. Let [??].A(R) be the intersection of the subalgebra of [[??].sup.[[E].sup.<[omega]]] made of invariant maps with the set algebra. This is a graded algebra, the age algebra of Cameron.

The name comes from the fact that this algebra depends only upon the age of R. Indeed, if R' is a relational structure with domain E' such that A(R') = A(R) then [??].A(R') identifies to [??].A(R). To see that, associates first to every indicator function [[chi].sub.S] of an equivalence class S for [equivalent to][sub.R] the indicator function [[chi].sub.S'] of the equivalence class S' for [equivalent to][sub.R'] such that [R.sub.[up arrow]P] is isomorphic to [R'.sub.[up arrow]P'] for some P [member of] S and some P' [member of] S'. Next associate to every linear combination (finite or not) of indicator function the linear combination, with the same coefficients, of their images.

If [[phi].sub.R] takes only integer values, [??].A(R) identifies with the set of (finite) linear combinations of members of A(R). This explain the fact that, in this case, [[phi].sub.R](n) is the dimension of the homogeneous component of degree n of [??].A(R). In a special case, we have

Theorem 3.2. [42] If R has a monomorphic decomposition into finitely many blocks [E.sub.1],..., [E.sub.k], all infinite, then the age algebra [??].A(R) is a polynomial algebra, isomorphic to a subalgebra [??][[[x.sub.1],..., [x.sub.k]].sup.R] of [??][[x.sub.1],..., [x.sub.k]], the algebra of polynomials in the indeterminates [x.sub.1],..., [x.sub.k].

3.2 Behavior of the Profile

In the frame of its age algebra, Cameron gave the following proof of the fact that the profile does not decrease.

Let R be a relational structure on a set E, let e := [[summation].sub.P[member of][[E].sup.1]] P (that we could view as the sum of isomorphic types of the one-element restrictions of R) and U be the subalgebra generated by e. Members of U are of the form [[lambda].sub.m][e.sup.m] + ... + [[lambda].sub.1]e + [[lambda].sub.0]1 where 1 is the isomorphic type of the empty relational structure and [[lambda].sub.m],..., [[lambda].sub.0] are in [??]. Hence U is graded, with [U.sub.n], the homogeneous component of degree n, equals to [??].[e.sup.n].

Theorem 3.3. If R is infinite then for every u [member of] [??].A(R), eu = 0 if and only if u = 0

This innocent looking result implies that [[phi].sub.R] is non decreasing. Indeed, the image of a basis of [??].A[(R).sub.n] by multiplication by [e.sub.m] is an independent subset of [??].A[(R).sub.n+m].

3.3 Finite generation

If a graded algebra A is finitely generated, then, since A is a quotient of the polynomial ring [??][[x.sub.1],..., [x.sub.k]], its Hilbert function is bounded above by a polynomial. In fact, as it is well known, its Hilbert series is a fraction of form P(x)/[(1-x).sup.d], thus of the form given in (2.3) of subsection 2.3. Moreover, one can choose a numerator with non-negative coefficients whenever the algebra is Cohen-Macaulay. Due to Problem 3, one could be tempted to conjecture that these sufficient conditions are necessary in the case of age agebras. Indeed, from Theorem 3.3 one deduces easily:

Theorem 3.4. The profile of R is bounded if and only if [??].A(R) is finitely generated as a module over U. In particular, if one of these equivalent conditions holds, then [??].A(R) is finitely generated

But this case is exceptional. Indeed, on one hand, as we have mentionned in 2.5.6, there are tournaments whose profile has arbitrarily large polynomial growth rate. On an other hand, with N.Thiery we proved:

Theorem 3.5. The age algebra of a tournament is finitely generated if and only if the profile is bounded.

The argument is simple and illustrates the above notions. Let T be a tournament. Suppose that [[phi].sub.T] is bounded, then by Theorem 3.4, [??].A(T) is finitely generated. Conversely, suppose that [??].A(T) is finitely generated. Then, as mentionned in the introduction of this subsection, [[phi].sub.T] is bounded above by a polynomial. Apply Theorem 2.28. Necessarily, T is a lexicographical sum of acyclic tournaments indexed by a finite tournament, a fact that we may write T = [[summation].sub.i[member of]D] [A.sub.i], where each [A.sub.i] is an acyclic tournament and D is a finite tournament. If [[phi].sub.T] is not bounded by a constant then, as one can easily see, D contains a 3-element subset A := {i, j, k} such [D.sub.[up arrow]A] is a cycle and [A.sub.j] and [A.sub.k] are infinite. Pick an element [a.sub.i] [member of] [A.sub.i], set E' := {[a.sub.i]} [union] [A.sub.j] [union] [A.sub.k] and set T' := [T.sub.[up arrow]E'] [member of] Since T' is an induced substructure of T, the algebra [??].A(T') is a quotient of [??].A(T). Thus, with our hypothesis that [??].A(T) is finitely generated, [??].A(T') must be finitely generated too. Let us see that this is not the case. Indeed, notice that if T' is an arbitrary infinite tournament then in the age algebra [??].A(T') we have [e.sup.n] = n!([a.sub.n] + [b.sub.n]) where an is the isomorphic type of an acyclic tournament on n vertices and [b.sub.n] is the sum of isomorphic types of induced subtournaments of T' on n vertices which contain a triangle. It follows then that every element x [member of] [??].A(T') is a sum x := a(x) + u(x) where a(x) is a linear combination of types, each containing a cycle, and u(x) [member of] U. Thus, if [g.sub.1],..., [g.sub.k], 1 generate [??].A(T') then a([g.sub.1]),..., a([g.sub.k]), e generate it also. We apply this fact to our tournament T'. Since T' does not contain two disjoint cycles, we have a([g.sub.i])a([g.sub.j]) = 0 for every 1 [less than or equal to] i, j [less than or equal to] k. Thus, a([g.sub.1]),..., a([g.sub.k]), 1 generate [??].A(T) as a module over U. According to Theorem 3.4, [[phi].sub.T'](n) is bounded. But, A(T') = A([T.sub.2]) where [T.sub.2] is the example given in Item 3 of Examples 2.29. Hence according to the computation given there, [[phi].sub.T'](n) = n - 2 for n [greater than or equal to] 4. This gives a contradiction. Thus [[phi].sub.T] must be bounded by a constant, as claimed.

3.4 The Behavior of the Hilbert Function; a Conjecture of Cameron

Cameron [9] made an important observation about the behavior of the Hilbert fonction.

Theorem 3.6. Let A be a graded algebra over an algebraically closed field of characteristic zero. If A is an integral domain the values of the Hilbert function [h.sub.A] satisfy the inequality

[h.sub.A](n) + [h.sub.A](m) - 1 = [h.sub.A](n + m) (3.2)

for all non-negative integers n and m.

In 1981, he made the conjecture that if R codes a permutation groups with no finite orbits then the age algebra over C is an integral domain [4] (see also [8] p. 86). I solved it positively in 2002 in a slightly more general setting:

Theorem 3.7. Let R be a relational structure with possibly infinitely many non isomorphic types of n-element substructures. If the kernel of R is empty, then [??].A(R) is an integral domain.

Since the kernel of a relational structure R encoding a permutation group G is the union of its finite orbits, if G has no finite orbit, the kernel of R is empty. Thus from this result, [??].A(R) is an integral domain, as conjectured by Cameron.

At the core of the solution is this lemma:

Lemma 3.8. Let m, n be two non negative integers. There is an integer t such that for every set E, every field K with characteristic zero, every pair of maps f : [[E].sup.m] [right arrow] [??], g : [[E].sup.n] [right arrow] [??], if fg(Q) := [[summation].sub.P[member of][[Q].sup.m]] f(P)g(Q \ P) = 0 for every Q [member of] [[E].sup.m+n] but f and g are not identically zero, then f and g are zero on [[E S].sup.m] and [[E \ S].sup.n] where S is a finite subset of E with size at most t

If the age is inexhaustible, then in order to prove that there is no zero divisor, the only part of the lemma we need to apply is the assertion that S is finite.

The fact that S can be bounded independently of f and g, and the value of the least upper bound [tau] (n, m), seem to be of independent interest. The only exact value we know is [tau](1, n) = 2n, a fact which amounts to a weighted version of Theorem 2.5. Our existence proof of [tau](m, n) yields astronomical upper bounds. For example, it gives [tau](2, 2) [less than or equal to] 4[R.sup.2.sub.k](4) + 1, where k := [5.sup.56] and [R.sup.2.sub.k](4) is the Ramsey number equals to the least integer p such that for every colouring of the pairs of {1,..., p} into k colors there are four integers whose all pairs have the same colour. The only lower bound we have is [tau](2, 2) [greater than or equal to] 7 and more generally [tau](m, n) = (m + 1)(n + 1) - 2. We cannot preclude a extremely simple upper bound for [tau](m, n), eg quadratic in n + m.

For example, our 1971 proof of Theorem 2.3 consisted to show that [[phi].sub.R](n) = [[phi].sub.R](n+1) provided that E is large enough, the size of E being bounded by some Ramsey number, whereas, according to Theorem 2.5, 2n + 1 suffices [32].

Our proof of Lemma 3.8 is built on the integrity of the age algebra of infinite multichainable relational structures and Ramsey's theorem. Here is a sketch (details will appear in [43]). We reduce the first part to the integrity of a shuffle algebra. For this, let R be a multichainable relational structure and let V and L, with L infinite, as in 2.4. Consider the vector space over [??] spanned by the words whose letters are non-empty subsets of a finite set V, the shuffle u[??]v of two words u and v being the sum of all words w which are the disjoint union of one occurrence of u and one occurrence of v (eg if V := {a, b} then {a}{b} = {a}{b} + {b}{a} + {a, b}). Using a lexicographical order, one can show that the resulting algebra is an integral domain [44]. This algebra is the age algebra of a relational structure M of a special form: the product of a relational structure on V by an infinite chain L (see subsection 4.5). Since the isomorphic classes of R contain those of M, the age algebra of R is an integral domain.

Next, we consider a pair f, g of maps as in Lemma 3.8, we suppose m [less than or equal to] n and that the subsets S for which the conclusion of the lemma holds are "large" (that is |S| = [mu](m, n) where [mu](m, n) is a number depending on [tau](m, n - 1), [tau](m - 1, n), and r(n + m) := [R.sup.n.sub.k](m + n), where k := [5.sup.s] and s := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. We observe then that there are at least r(m + n) pairwise disjoint m + n-element subsets [V.sub.0],..., [V.sub.i],..., [V.sub.r(m+n)]-1 of E, each satisfying f([P.sub.i])g([V.sub.i] \ [P.sub.i]) [not equal to] 0 for some [P.sub.i] [member of] [[[V.sub.i]].sup.m]. Supposing that the union E' of these subsets is the product of an m + n element set V by a r(m + n)-element chain L', we encode the action of f and g on E' by a relational structure R' made of a m-uniform hypergraph and a n-uniform hypergraph whose hyperedges are coloured in at most four colors. Dividing the m + n-element subsets of L' into equivalence classes, Ramsey's theorem provides a m + n-element subchain L" such that the isomorphic classes of [R'.sub.|VxL"] contains those of the product of V by L". From the fact that the shuffle algebra built on V is an integral domain we deduce that either the restriction of f to [[V x L"].sup.m] or the restriction of g to [[V x L"].sup.n] vanishes. But this is not the case. Hence S cannot be large.

3.5 Initial segments of an age and ideals of a ring

As stated in Theorem 2.12, if the profile of a relational structure R, with bounded signature or finite kernel, has a polynomial growth, then it is almost multichainable. As we will see in Theorem 4.19, if a relational structure R is almost multichainable, its age A(R), ordered by embeddability, is well-quasi-ordered, that is every final segment of A(R) is finitely generated, which amounts to the fact that the collection F(A(R)) of final segments of A(R) is noetherian, w.r.t. the inclusion order (see subsection 4.3). Final segments play for posets the same role than ideals for rings. Noticing that an age algebra is finitely generated if and only if it is noetherian, we are lead to have a closer look at the relationship between the basic objects of the theory of relations and of ring theory, particularly ages and ideals.

We mention the following result which will be incorporated into a joint paper with N.Thiery.

Proposition 3.9. Let A be the age of a relational structure R such that the profile of R takes only finite values and [??].A be its age algebra. If A' is an initial segment of A then:

(i) The vector subspace J := [??].(A\A') spanned by A\A' is an ideal of [??].A. Moreover, the quotient of [??].A by J is a ring isomorphic to the ring [??].A'.

(ii) If this ideal is irreducible then A' is a subage of A.

(iii) This is a prime ideal if and only if A' is an inexhaustible age.

The proof of Item (i) and Item (ii) are immediate. The proof of Item (iii) is essentially based on Theorem 3.7.

According to Item (i), F(A) embeds into the collection of ideals of [??].A). Consequently:

Corollary 3.10. If an age algebra is finitely generated then the age is well-quasi-ordered by embeddability.

Problem 8. How the finite generation of an age algebra translates in terms of embeddability between members of the age?

4 Tools for Classifying Profiles

Beside graded algebras, Hilbert series and rudimentary algebraic geometry, the tools we use to classify profiles can be divided into the following categories:

--Orders, well-founded orders, well-quasi-orders;

--Ramsey Theorem;

--Compactness theorem;

--Combinatorial properties of the kernel.

In this section, we show the role of these tools in the proof of Theorem 2.6 and Theorem 2.12. For reader convenience, we record in the first subsection below some notions and notations we are using in this paper.

4.1 Basic Notions, Relational Structures, Embeddability and Ages

We use standard set-theoretical notations. If E is a set, |E| denotes its cardinality. If n is an integer, [[E].sup.n] denotes the set of n-element subsets of E; whereas [E.sup.n] denotes the set of n-tuples of elements of E. An n-ary relation on E is any subset n of [E.sup.n]. As said in subsection 2.1, a pair R := (E, [([[rho].sub.i]).sub.i[member of]I]) made of a set E and of a family of mi-ary relations [[rho].sub.i] on E is a relational structure of signature [mu] := [([m.sub.i]).sub.i[member of]I]. If I' is a subset of I, the relational structure [R.sup.I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) is a reduct of R.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) and R' := (E', [([[rho]'.sub.i).sub.i[member of]I]) be two relational structures of the same signature [mu] := [([m.sub.i]).sub.i[member of]I].

A map f : E [right arrow] E' is an isomorphism from R onto R' if

1. f is bijective,

2. ([x.sub.1],..., [x.sub.[m.sub.i]]) [member of] [[rho].sub.i] if and only if (f ([x.sub.1]),..., f([x.sub.[m.sub.i]])) [member of] [[rho]'.sub.i] for every ([x.sub.1],..., [x.sub.[m.sub.i]]) [member of] [E.sup.[m.sub.i]], i [member of] I.

A map f from a subset A of E onto a subset A' of E' is a local isomorphism or a local embedding of R into R' if f is an isomorphism from [R.sub.[up arrow]A] onto [R'.sub.[up arrow]A']. If A = E, this is an embedding from R into R'.

We say that R is isomorphic, resp. embeddable, to R', resp. into R', and we write R [congruent to] R', resp. R [less than or equal to] R', if there is an isomorphism, resp. an embedding, from R onto R', resp. into R'. Clearly, R is embeddable into R' if and only if R is isomorphic to some restriction of R'. To each relational structure R one may associate an isomorphic type [tau](R), in such a way that R [congruent to] R' if and only if [tau](R) = [tau](R'). The collection of isomorphic types of finite relational structures of signature [mu] is a set, that we denote [[OMEGA].sub.[mu]]. The embeddability relation is a quasi-order on the class of relational structures of signature [mu]. It induces a quasi-order on the class of their isomorphic types. On the set [[OMEGA].sub.[mu]] this is an ordering.

The age of a relational structure R is the set A(R) of isomorphic types of the restrictions of R to the finite subsets of its domain.

Ages can be (almost) characterized in terms of ordered sets (posets). Let us recall that if P is a poset, an initial segment of P is a subset I such that x [member of] P, y [member of] I and x [less than or equal to] y imply x [member of] I. An ideal is a non-empty initial segment which is up-directed, that is x, y [member of] I imply x, y [less than or equal to] z for some z [member of] I.

The following characterization is essentially due to R. Fraisse 1954 (see [14]).

Lemma 4.1. a) Let R be a relational structure of arity [mu] and size [kappa], then A(R), the age of R, is an ideal of [[OMEGA].sub.[mu]], whose size is at most e if [kappa] is infinite and [2.sup.[kappa]] otherwise; b) Conversely, let C be an ideal of [[OMEGA].sub.[mu]]; if C is countable, then C is the of age a countable [mu]-ary relational structure.

In particular:

c) If [mu] is finite, then a subset C of [[OMEGA].sub.[mu]] is the age of a [mu]-ary relational structure if and only if C is an ideal of [[OMEGA].sub.[mu]].

The equivalence stated in c) does not hold without some condition on [mu]. An example was obtained with C. Delhomme and mentionned in [40], see [11] for other examples and further developments.

Still, [[OMEGA].sub.[mu]] is an age -and the largest one. As a poset, it decomposes into levels, the levels of a poset P being defined inductively by the formula [P.sub.n] := Min(P \ [union]{[P.sub.n'] : n' < n}). The n-th level is the set of isomorphic types of relational structures on n elements. The same holds for the age of a relational structure R, hence the profile [[phi].sub.R](n) is simply the function which assign to each n the number of elements of the n-th level of A(R) (in the general theory of posets, the numbers of elements of the levels of a poset P are the Whitney numbers- of the second kind- of P). In the study of their growth, we have only to consider profiles taking finite values. Hence, according to the above characterization, our study is about ideals of [[OMEGA].sub.[mu]], each one with finite levels. A characterization in order-theoretical terms, of these ideals eludes us, the study of the profile is just a bare approach.

4.2 The Height Function on a Well-Founded Poset, the Height of an age and its Relation with the Profile

Let P be a poset; P is well-founded if every non-empty subset A of P contains some minimal element a (that is there is no b [member of] A with b < a). The height function on a poset P associates to an element x [member of] P an ordinal number h(x, P) is such a way that:

h(x, P) := Sup{h(y, P) + 1 : y < x}

The ordinal h(x, P) is the height of x in P.

With this definition, h(x, P) = 0 if and only if x is minimal in P; also h(x, P) is defined if and only if [down arrow] x := {y [less than or equal to] P : y [less than or equal to] x} is well-founded.

Let A be an ideal of [[OMEGA].sub.[mu]] and let J(A) be the set of ideals included into A. The height of A, denoted by H(A), is the height of A in J(A). With this definition, H(A) = n with n < [omega], if and only if A = A(R) for some R on n elements. Furthermore, H(A) = [omega] if and only if A is infinite and every ideal properly included into A is finite.

The characterization of ideals of height is given by the following result:

Theorem 4.2 ([37]). Let A be an ideal of [[OMEGA].sub.[mu]]. Then the following properties are equivalent:

(i) H(A) = [omega].

(ii) A is the age of an infinite monomorphic relational structure R (that is [[phi].sub.R](n) = 1 for all n).

(iii) A is the age of an infinite chainable relational structure.

The essential part is the implication (i) [??] (iii). For that, observe that A is countable. Hence, from Lemma 4.1 b), A is the age of some countable relational structure R. From Theorem 2.23 and Compactness theorem of first order logic, R is chainable.

This generalizes:

Theorem 4.3 ([37]). Let A be an ideal of [[OMEGA].sub.[mu]]. Then the following properties are equivalent:

(i) H(A) = [omega] + p, for some p < [omega].

(ii) A is the age of an infinite relational structure with a bounded profile.

(iii) A is the age of an infinite almost chainable relational structure.

This result opens the road for proving Theorem 2.6. Indeed, as it will appear at the end of this section:

Theorem 4.4. If R has a finite kernel then the growth of [[phi].sub.R] is polynomial of degree k if and only if A(R) has an height and H(A(R)) = [omega](k + 1) + p for some integer p.

At this point, we are still far away of a proof. More tools are needed.

4.3 Well-Quasi-Ordering, Higman Theorems, Very-Well-Quasi-Ordered Classes

A poset P is well-quasi-ordered, in brief w.q.o., if every non-empty subset contains finitely many minimal elements(this number being non-zero). A final segment F of a poset P is finitely generated if for some finite subset K of P, F equals the set [up arrow] K := {y [member of] P : x [less than or equal to] y for some x [member of] K}.

A basic result due to Higman [21] is the following.

Theorem 4.5. For a poset P, the following properties are equivalent:

1. P is w.q.o.

2. P contains no infinite strictly descending chain and no infinite antichain.

3. Every final segment of P is finitely generated.

4. The set I (P) ordered by inclusion and made of initial segments of P is well-founded.

Corollary 4.6. If an ideal A of [[OMEGA].sub.[mu]] is w.q.o. then J(A) is well-founded, hence H(A) is defined.

Non-w.q.o posets for which the collection of ideals is well-founded abund. Not a single example of non-w.q.o age whose the collection of subages is well-founded as been discovered yet.

With Zorn lemma, one may observe that if a poset P is not w.q.o. it contains some final segment F which is not finitely generated and maximal w.r.t. inclusion. If follows that its complement P \ F is w.q.o.

This fact applies nicely to [[OMEGA].sub.[mu]]. For that, let us mention that a bound of a relational structure R is any relational structure S on a finite set F such that S does not embed into R but [S.sub.-x] := [S.sub.[up arrow]F\{x}] embeds into R for every x [member of] F. A bound of an initial segment C of [[OMEGA].sub.[mu]] is any minimal element of [[OMEGA].sub.[mu]] \ C. Clearly, the bounds of A(R) are the isomorphic types of the bounds of R.

Lemma 4.7. If an initial segment C of [[OMEGA].sub.[mu]] is level finite and is not w.q.o., then it contains an ideal which has infinitely many bounds in C.

Let us recall that a word is a finite sequence of letters and that a word u is a subword of a word w if u can be obtained from w by erasing some letters of w. We have the following theorem of Higman [21].

Theorem 4.8. The set [A.sup.*] made of words on a finite alphabet A is w.q.o. with respect to the subword ordering.

A class C of relational structures is very-well-quasi-ordered, in short v.w.q.o., if for every integer m the class [C.sub.m] made of R [member of] C added of m unary relations is w.q.o for the embeddability relation We will need the following result.

Theorem 4.9. Let C be a class of finite relational structures, then:

1. C is v.w.q.o iff [down arrow] C, its downward closure, is v.w.q.o.

2. If [down arrow] C is v.w.q.o. then all the ages it contains are almost inexhaustible.

3. If [down arrow] C is v.w.q.o. and all of its members have the same finite signature [mu] then it has only finitely many bounds [31].

An other important result on w.q.o. is this (see [50] for the first part, [10] for the second). Theorem 4.10. If a poset P is w.q.o. then all the linear extensions of P are well-ordered and there is one having the largest possible order type.

This largest order type, denoted [tau](P), is the ordinal length of P.

Lemma 4.11 ([10]). If A is an alphabet made of k letters then [tau]([A.sub.*) = [[omega].sup.[[omega].sup.k-1]].

The computation for ages (see [41], [49]) yields:

Theorem 4.12. If J(A(R)) is w.q.o then [tau](A(R)) = [[omega].sup.a] x q where [alpha] is such that [omega] x [alpha] [less than or equal to] H(A(R)) < [omega] x ([alpha] + 1) and q is the number of ages included into A(R) whose height is between [omega] x [alpha] and [omega] x ([alpha] + 1).

4.4 Kernel, Almost Inexhaustibility, Height and Profile

Most of the properties of the kernel (defined in subsection 2.2.2)are based on the following simple lemma (see [34] for finite signature and 3 of Lemma 2.12 of [40] for the general case).

Lemma 4.13. A([R.sub.[up arrow]E\{a}]) = A(R) [??] A([R.sub.[up arrow]E\{a,b}]) = A([R.sub.[up arrow]E\{b}]) for all a, b [member of] E

From this lemma, one immediately gets the following:

Corollary 4.14. A relational structure R has an empty kernel if and only if its age A(R) has the disjoint embedding property.

Instead of saying that an age has the disjoint embedding property, we say that it is inexhaustible. We say that a relational structure R is age-inexhaustible if K(R) is empty and almost age-inexhaustible if K(R) is finite.

Lemma 4.15. Let A be an infinite inexhaustible age. Then:

1. For every age A' included into A there is an infinite strictly increasing sequence of ages included into A such that

A' = [A.sub.0] [subset] ... [subset] [A.sub.n] [sunset] ...

2. The height of A, is a limit ordinal, provided that it is defined.

See Proposition 4.7 of [40]. Notice that the converse of (2) does not hold in general, a fact which causes some complications.

The relationship between almost inexhaustibility and inexhaustibility is based upon properties of reductions.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure and F be a subset of E. A reduction of R over F is a relational structure M := (E \ F, [([[tau].sub.j).sub.j[member of]J]) such that the local automorphisms of M are precisely the restrictions of local isomorphisms of R fixing F pointwise.

Lemma 4.16. Let R be a relational structure, K(R) be its kernel, r := |K(R)|, and M be a reduction of R over K(R). If K(R) is finite then:

1. K(M) is empty.

2. H(A(R)) = H(A(M)) + p, for some integer p, if and only if one of these heights exists.

3. [[phi].sub.R](n) [less than or equal to] [2.sup.r] [[phi].sub.S](n) and [[phi].sub.S](n) = a[[phi].sub.R](n + k) for some a [member of] [[??].sup.*.sub.+], k [member of] [??], and all n [member of] [??].

Item 1 is special case of Theorem 20 [19]. Item 2 is a special case of Theorem 4.6 of [40]. Item 3 can be proved in the same way as Theorem 21 of [19].

The growth of a map [phi] : [??] [right arrow] [??] is invariant under translation if [phi] and its translate n [right arrow] [phi](n+1) have the same growth. In this case, [phi] is bounded by an exponential function. Clearly, polynomial functions are invariant under translation. Under the hypotheses of Lemma 4.16 we get from Item (3):

Corollary 4.17. [[phi].sub.R] is bounded by a polynomial of degree k, resp. has polynomial growth of degree k, iff [[phi].sub.M] is bounded by a polynomial of degree k, resp. has polynomial growth of degree k.

This tells us that in order to prove that the growth of the profile of a relational structure with finite kernel is polynomial it suffices to prove that the growth of a reduction over its kernel is polynomial.

4.5 Product of a Finite Relational Structure by a Chain

Let S := (V, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure of signature [mu] and L := (D, [less than or equal to]) be a chain. A relational structure R of signature [mu] is a product of S and L, denoted by S [crosss product] L, if it satisfies the following conditions.

(a) The domain is V x D.

(b) For every y [member of] D, the map x [right arow] (x, y) is an isomorphism from S into R.

(c) For each local isomorphism f of L, the map ([1.sub.V], f) which to (x, y) associates (x, f(y)) is a local isomorphism of R.

If |V| = 1, this reduces to say that every local isomorphism of L is a local isomorphism of R. As we have said, a relational structure is chainable if there is such a chain defined on its domain.

In this context, a relational structure is almost multichainable, resp. almost chainable, if its kernel is finite and a reduction over its kernel is a multiple of a finite, resp. a one-element, relational structure by a chain.

A relational structure M freely interprets a relational structure R on the same set if each local isomorphism of M is a local isomorphism of R. Clearly, if a relational structure M is almost multichainable, every relational structure freely interpretable by M has the same property. In fact, an almost multichainable relational structure is freely interpretable by an almost multichainable relational structure of a special form:

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be an almost multichainable relational structure; let F and V be two finite sets, L := (D, [less than or equal to]) be a chain such that E = F [union] V x D and every local isomorphism of f extended by the identity on F and D induces a local isomorphism of R. Let r := |F|, m := |V|, [a.sub.1],..., [a.sub.r], resp. [v.sub.1],..., [v.sub.m], be an enumeration of the members of F, resp. of V. Set M := (E, [A.sub.1],..., [A.sub.r], [V.sub.1],... [V.sub.m], Eq, W) be the relational structure in which [A.sub.1],..., [A.sub.r] and [V.sub.1],..., [V.sub.m] are unary relations, [A.sub.i] := {[a.sub.i]} for i = 1,..., r, [V.sub.i] := {i} x D, Eq is an equivalence relation defined by (u, v) [member of] Eq if either u = v or u = (x, y) and v = (x', y), W is an order defined by (u, v) [member of] W if either u = v or u = (x, y), v = (x', y') and y < y' in L.

Clearly, M interprets R. This relational structure has a finite signature. The fact that an almost multichainable relational structures is freely-interpretable by a relational structure with finite signature allows to use the compactness theorem of first order logic. This yields:

Proposition 4.18. If a relational structure R is almost multichainable then every relational structure R' such that A(R') [[subset].bar] A(R) is also almost multichainable.

Proof. Let M as above which interprets freely R. If some relational structure R' verifies A(R') [[subset].bar] A(R) then, since the signature of M is finite, the compactness theorem yields some relational structure M' such that A(M') [[subset].bar] A(M) and M' interprets freely R'. The multirelation M is almost multichainable. It is easy to see that M' is almost multichainable too. Hence R' is almost multichainable too. '

Theorem 4.19. Let A be the age of an almost multichainable relational structure. Then:

1. A is very well-quasi-ordered;

2. H(A) < [[omega].sup.[omega]].

Proof. Let R such that A(R) = A. Let R' be a reduction over K(R). Then R' is the product S [cross prodcuct] L of a finite relational structure S by a chain L. Let V be the domain of S, m := |V|, D be the domain of L and M be the multirelation interpreting R'.

(1) In order to prove that A is v.w.q.o. it suffices to prove that A(M) is v.w.q.o. For that, we consider the alphabet A whose letters are the non-empty subsets of V (that is A = [??](V) \ {[empty set]}). We order A by inclusion; we extend this order to an order, compatible with the concatenation of words, on [A.sup.*], the set of words over A. With this ordering [A.sup.*] is isomorphic to A(M). Thus from Theorem 4.8, A(M) is w.q.o. and in fact v.w.q.o.

(2) Since M interprets R' we have [tau](A(R')) [less than or equal to] [tau](A(M)). We also have [tau](A(M)) [less than or equal to] o([A.sup.*]) and, since |A| = [2.sup.m] - 1, we have o([A.sup.*]) = [[omega].sup.[[omega].sup.[2.sup.m]- 2]] from Lemma 4.11. Thus, o(R') [less than or equal to] [[omega].sup.[[omega].sup.[2.sup.m]-2]]. Theorem 4.12 yields H(A(R')) [less than or equal to] [[omega].sup.[2.sup.m]-1]. From this inequality, Lemma 4.16 yields H(A) < [[omega].sup.[2.sup.m]-1] + [omega].

Combining (1) of Theorem 4.19 and (3) of Theorem 4.9, we get:

Theorem 4.20. An almost multichainable relational structure having a finite signature has only finitely many bounds.

For the special case of chainable relations this conclusion was obtained by C.Frasnay in 1965 [17] by means of his theory of indicative groups. Atruly reamarkable consequence also due to Frasnay is that for every integer m there is an integer f (m) such that a monomorphic relational structure with signature bounded by m and size at least f (m) is chainable (see Chapter 13 of [14]).

Lemma 4.21 ([34]). Let R' be a relational structure and L be a chain with at least two elements. Then the kernel of R' is empty if and only if there is a product R" := R' [cross product] L such that A(R") = A(R').

Corollary 4.22. The age A of a denumerable relational structure with empty kernel is the union of an infinite sequence

[A.sub.0] [[subset].bar] [A.sub.1] [[subset].bar] ... [[subset].bar] [A.sub.n] [[subset].bar] ...

where each [A.sub.n] is the age of a product of some S [member of] [A.sub.n] by an infinite chain.

Proof. Let R' be a denumerable relational structure such that A(R') = A and L be an infinite chain. According to Lemma 4.21, there is a product R" := R' [cross product] L such that A(R") = A. Let [F.sub.0] [[subset].bar] ... [[subset].bar] [F.sub.n] [[subset].bar] ... be an non-decreasing sequence of finite subsets of the domain E' of R' whose union is E'. Let [R".sub.n] := [R".sub.[up arrow][F.sub.n]xL] and [A.sub.n] := A([R".sub.n]) for n [member of] [??]. The sequence [A.sub.n],..., [A.sub.n],.... is non-decreasing and A = [[union].sub.n[member of]N] [A.sub.n].

Proposition 4.23. If the age A of a denumerable relational structure is inexhaustible then

--Either A is the age of a multichainable relational structure and H(A) < [[omega].sup.2].

--Or for every integer k, A contains the age [A.sub.k] of an almost multichainable relational structure such that H([A.sub.k]) = [omega].(k + 1).

Proof.

Claim. Either A is the age of a multichainable relational structure or for every integer k it contains the age [A.sub.k] of a multichainable relational structure such that H([A.sub.k]) [greater than or equal to] [omega].(k + 1). Proof of the claim. Apply Corollary 4.22. If the sequence

[A.sub.0] [[subset].bar] [A.sub.1] [[subset].bar] ... [[subset].bar] [A.sub.n] [[subset].bar] ...

is eventually constant, then A = [A.sub.[n.sub.0]] for some non-negative integer [n.sub.0]. Let [S.sub.[n.sub.0]] := [R'.sub.[up arrow][F.sub.[n.sub.0]]] and R := [R".sub.[n.sub.0] = [R".sub.[up arrow][F.sub.[n.sub.0]]xL]. Then R is a product of [S.sub.[n.sub.0]] by L. If this sequence is not eventually constant, it contains an infinite subsequence which is strictly increasing, say:

[A.sub.[n.sub.0]] [subset] ... [subset] [A.sub.[n.sub.i]] [subset] ...

Since [R".sub.[n.sub.i]] is a product of product of [S.sub.[n.sub.i]] by L, its kernel is empty, that is [A.sub.[n.sub.i]] is inexhaustible. Hence, from (1) of Lemma 4.15 there is a strictly increasing sequence of ages between [A.sub.[n.sub.k-1]] and [A.sub.[n.sub.k]]. Since [R".sub.[n.sub.i]] is multichainable, [A.sub.[n.sub.k]] has an height. It follows that H([A.sub.[n.sub.k]]) [greater than or equal to] [omega].(k + 1).

Now, suppose that A is the age of a multichainable relational structure. Then H(A) is defined. If H(A) < [[omega].sup.2], the conclusion of the proposition holds. If H(A) [greater than or equal to] [[omega].sup.2], then for every k, A contains an age [A.sub.k] of height [omega].(k + 1). According to Proposition 4.18, [A.sub.k] is the age of an almost multichainable relational structure. Suppose that A is not the age of a multichainable relational structure. Let k be an integer. According to our claim, A contains the age [A.sub.k] of an almost multichainable relational structure such that H([A.sub.k]) = [omega].(k + 1). Let A' [[subset].bar] [A.sub.k] be an age of height [omega].(k + 1). According to Proposition 4.18, A is the age of an almost multichainable relational structure. This proves the proposition.

For relational structures with finite signature we have a similar result with a more intricate proof.

Theorem 4.24. Let A be the age of infinite relational structure R with finite signature.

1. If H(A) < [[omega].sup.2] then R is an almost multiple of a finite relation by a chain; in particular, R has a finite kernel.

2. If A has no height then A contains some age of height [[omega].sup.2] (and, in fact, ages of height [[omega].sup.2] + p for every integer p).

The proof is given below for relational structures made of binary or unary relations; beyond, the proof is quite involved.

Proof. (1)We argue by induction on the height. Let [alpha], [omega] [less than or equal to] [alpha] < [[omega].sup.2]. Suppose that Property (1) holds for every age A such that [omega] [less than or equal to] H(A) < [alpha]. Let A be an age with H(A) = [alpha].

Let R such that A(R) = A. First, K(R), the kernel of R, is finite. Indeed, let x [member of] K(R). We have A([R.sub.-x]) [??] A. Hence, from the induction hypothesis, A([R.sub.-x]) is the age of an almost multiple of a finite relation by a chain. According to Theorem 4.19, A([R.sub.-x]) is very well-quasi-ordered. Since R is made of binary and unary relations, it follows that A(R) is very-well-quasi-ordered too. From (2) of Theorem 4.9, K(R) is finite. Let R' be a reduction of R over K(R). Let n, p < [omega] such that [alpha] = [omega]n + p. According to (2) of Lemma 4.16, we have H(A(R')) = [omega]n and K(R') = [empty set]. Apply Proposition 4.23.

(2)If A has no height then A is not w.q.o., hence it contains some age A' which is w.q.o. and has infinitely many bounds in A (Lemma 4.7). Being w.q.o., A' has an height. If H(A') < [[omega].sup.2], then from (1) A' is the age of an almost multiple of a finite relation by a chain, hence is v.w.q.o. But according to (3) of Theorem 4.9, it cannot have infinitely many bounds, a contradiction. Hence H(A') [greater than or equal to] [[omega].sup.2].

4.6 Profile of Almost Multichainable Relational Structures

Let A be the age of a product R := S [cross product] L with S := (V , [([[rho].sub.i]).sub.i[member of]I]) [member of] A. Let J be a non-empty initial segment of [??](V). Let [F.sub.J]:= {F [member of] [[V x E].sup.<[omega]] : [F.sup.-1](y) [member of] J for every y [member of] E}. Let [A.sub.J] := {[tau]([S.sub.[up arow]F]) : F [member of] [F.sub.J]}.

Lemma 4.25. (i) The age AJ is inexhaustible.

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.];

(iii) [A.sub.[??](V)] = A.

Let J be a non-empty initial segment of [??](V) which is minimal w.r.t. inclusion such that [A.sub.J] = A. Let V' be a maximal element of J [member of] Let m' := |V'| and J' := J {V'}. Note that if J' = [empty set] then A is the age of a chainable relation, in which case its profile is 1.

Given an integer p, let [A.sub.p] := {[tau]([S.sub.[up arrow]F]) : F [member of] [F.sub.J] and |{i : [F.sup.-1](i) = V'}| [less than or equal to] p}.

Lemma 4.26. 1. [A.sub.p] is an age for every p < [omega].

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

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

4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

5. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. In other words, if [p.sub.0] is minimum such that [A.sub.[p.sub.0]] [not equal to] [A.sub.0] then [A.sub.p] [??] [A.sub.p+1] for every p [greater than or equal to] [p.sub.0].

6. For each p [greater than or equal to] [p.sub.0], the kernel of any relation with age [A.sub.p] has m'.p elements.

Proof. Sketch. We may suppose that L is the chain [??] of rational numbers. In the product V x [??], we select a subset X made of "slices" F x {r} with F [member of] J and r [member of] [??], in such a way that between two rational all possible slices appear. Obviously A([R.sub.[up arrow]X]) = A. Let [X.sub.p] obtained by deleting from X all slices of the form V' x {r} except p such slices. Then A([R.sub.[up arrow][X.sub.p]]) = [A.sub.p]. To obtain that, for p larger than some non-negative integer [p.sub.0], K([R.sub.[up arrow][X.sub.p]]) is made of these p slices, apply Lemma 4.13.

Lemma 4.27. Let A be the age of a product R := S [cross product] L with S := (V , [([[rho].sub.i]).sub.i[member of]I]) [member of] A. If H(A) = [omega](k + 1) then [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. for every integer n.

Proof. Induction on k. We apply Lemma 4.26. For p < [omega], we denote by [R.sub.p] a relational structure with age [A.sub.p], by [R'.sub.p] a reduction over its kernel and by [A'.sub.p] its age. We have :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] ...

Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

that is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

With Pascal identity this yields:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

According to (1) of Lemma 4.16 we have H([A.sub.p]) = H([A'.sub.p]) + [n.sub.p] for some [n.sub.p] < [omega] Hence H([A'.sub.p]) [less than or equal to] [omega]k. Via the inductive hypothesis, [[phi].sub.[R'.sub.p]](n) [less than or equal to] [[phi].sub.[omega]k](n) for every n and every p. This yields:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We get the following result mentioned in the introduction.

Theorem 4.28. If the age A of a denumerable relational structure R is inexhaustible and its height H(A) is at most [omega](k + 1) then [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every integer n.

Proof. We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Since A is inexhaustible, (1) of Lemma 4.16 tells us that p = 0. According to Proposition 4.23 there is some R having age A which is a product of some S [member of] A by a chain. According to Lemma 4.27, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every integer n. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], the desired conclusion follows.

Lemma 4.29. Let A be the age of a product R := S [cross product] L with S := (V, [([[rho].sub.i]).sub.i[member of]I]) [member of] A. If H(A) = [omega](k + 1) then [[phi].sub.R] grows at least as a polynomial of degree k.

For the proof of this counterpart of Lemma 4.27 fix an increasing sequence [([A.sub.i]).sub.i[less than or equal to]k] of sub-ages of A such that H([A.sub.i]) = [omega].(i + 1). Then show that increasing sequences [([T.sub.i]).sub.i[less than or equal to]k], [T.sub.i] [member of] [A.sub.i] \ [A.sub.i-1], |[T.sub.k]| = n, yields O([n.sup.k]) distinct types. With this we obtain:

Theorem 4.30. Let R := (E, [([[rho].sub.i]).sub.i[member of]I])) be a relational structure. If the signature of R is bounded or R has a finite kernel then either R is almost multichainable and H(A(R)) = [omega](k + 1) + p -in which case [[phi].sub.R] grows as a polynomial of degree k- or [[phi].sub.R] grows faster than every polynomial.

Proof. Suppose that the kernel K(R) of R is finite. Let R' be a reduction over K(R). If A(R') has an height, then according to (2) of Lemma 4.16, A(R) too and H(A(R)) = H(A(R')) + p for some non-negative integer p. If H(A(R')) = [omega](k + 1) < [[omega].sup.2], then R' is multichainable (Proposition 4.23), hence R is almost multichainable, and [[phi]'.sub.R] grows as a polynomial of degree k (Lemma 4.27 and Lemma 4.29). According to Corollary 4.17, [[phi].sub.R] grows as a polynomial of degree k too. If A(R') has no height or contains an age of height [[omega].sup.2], then for every non-negative integer k it contains the age of an almost multichainable relational structure of height [omega](k + 1) (Proposition 4.23). Hence, according to Lemma 4.29, [[omega].sub.R'] grows faster than every polynomial and, via Corollary 4.17, [[phi].sub.R] too. If K(R) is infinite, then, with our hypothesis, the signature is bounded. Suppose that I is finite. It follows from Theorem 4.24 that A(R) contains ages of height [omega](k + 1) for every non negative integer k, hence [[phi].sub.R] grows faster than every polynomial. If I is infinite, then since the signature is bounded by some integer m, there is some finite subset I' such that the reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) has the same profile as [[phi].sub.R] (Fact 2), thus this case reduces to the previous one.

Theorem 2.6, Theorem 2.12 and Theorem 4.4 are immediate consequences of this result. In the case of a relational structure with empty kernel, Theorem 4.4 has a more precise form. With the help of Lemma 4.27 we get the following result announced in [35]:

Theorem 4.31. If the age of a relational structure R is inexhaustible and [[phi].sub.R] has polynomial growth of degree k then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for every integer n.

We conclude this tour with the following:

Problem 9. Is the profile of a relational structure R bounded by some exponential whenever the age of R is very-well-quasi-ordered under embeddability?

* Dedicated to Roland Fraisse, at the occasion of his 86th birthday.

(1) In order to agree with the Fraisse's terminology, we disagree with the terminology of our papers, in which inexhaustibility, resp. almost inexhaustibility, is used for relational structures with empty, resp. finite, kernel, rather than for their ages.

References

[1] J. Berstel, C. Retenauer, Les series rationnelles et leurs langages. Etudes et recherches en Informatique. Masson, Paris, 1984, 132 pp.

[2] Y. Boudabbous, M. Pouzet, The morphology of infinite tournaments. Application to the growth of their profile. Oct. 2005, Revised Nov. 2006. 20 pp.

[3] P.J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 48 (1976), pp. 127-139.

[4] P.J. Cameron, Orbits of permutation groups on unordered sets. II. J. London Math. Soc. 23(2) (1981), pp. 249-264.

[5] P.J. Cameron, Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990.

[6] P.J. Cameron, The algebra of an age. In Model theory of groups and automorphism groups (Blaubeuren, 1995), pages 126-133. Cambridge Univ. Press, Cambridge, 1997.

[7] P.J. Cameron, Sequences realized by oligomorphic permutation groups. J. Integer Seq. 3(1), Article 00.1.5, 1 HTML document (electronic), 2000.

[8] P.J. Cameron, Some counting problems related to permutation groups. Discrete Math. 225(1-3) (2000), pp. 77-92. Formal power series and algebraic combinatorics (Toronto, ON, 1998).

[9] P.J. Cameron, On an algebra related to orbit-counting. J. Group Theory 1(2) (1998), pp. 173-179.

[10] D.H.J. de Jongh and R. Parikh, Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math. 39(3) (1977), pp. 195-207.

[11] C. Delhomme, M. Pouzet, N. Sauer, G. Sagi, Representation of ideals of relational structures, preprint, Calgary, July 2006, 18pp. http://arxiv.org/math.CO/0607725

[12] R. Fraisse, Sur quelques classifications des systemes de relations, These, Paris (1953), Alger-Math. 1 (1954), pp. 35-182.

[13] R. Fraisse, Sur l'extension aux relations de quelques proprietes des ordres, Ann. Sci. Ecole Norm. Sup. 71 (1954), pp. 361-388.

[14] R. Fraisse, Theory of relations. Second edition, North-Holland Publishing Co., Amsterdam, 2000.

[15] R. Fraisse and M. Pouzet, Interpretabilite d'une relation pour une chaine. C. R. Acad. Sci. Paris Ser. A-B 272 (1971), pp. 1624-1627.

[16] R. Fraisse, Cours de logique mathematique. Tome 1: Relation et formule logique. Gauthier-Villars Editeur, Paris, 1971.

[17] C. Frasnay, Quelques problemes combinatoires concernant les ordres totaux et les relations monomorphes. These. Paris. Annales Institut Fourier Grenoble 15 (1965), pp. 415-524.

[18] A.M. Garsia and N.Wallach, Qsym over Sym is free. J. of Comb. Theory, Series A 104 (2003), pp. 217-263.

[19] P. Gibson, M. Pouzet, and R. Woodrow, Relational Structures Having Finitely Many Full-cardinality Restrictions. Discrete Mathematics 291 (2005), pp. 115-134.

[20] D.H. Gottlieb, A class of incidence matrices, Proc. Amer. Math. Soc. 17 (1966), pp. 1233-1237.

[21] G. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) (1952), pp. 326-336.

[22] I.M. Hodkinson, H.D. Macpherson, Relational structures determined by their finite induced substructures. J. Symbolic Logic 53(1) (1988), pp. 222-230.

[23] W.M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), pp. 315-318.

[24] J.B. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept. J. Com. Th. 13 (1972), pp. 297-305.

[25] D. Livingstone, A. Wagner, Transitivity of finite permutation groups on unordered sets. Math. Z. 90 (1965), pp. 393-403.

[26] M. Lothaire, Combinatorics on words. Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, U.K. 1997.

[27] H.D. Macpherson, Growth rates in infinite graphs and permutation groups. J. London Math. Soc. 35(2) (1987), pp. 276-286.

[28] H.D. Macpherson, Permutation groups of rapid growth. Proc. London Math. Soc. 51(2) (1985), pp. 285-294.

[29] H.D. Macpherson, M. Pouzet, and R.E.Woodrow, Countable structures of a given age. The Journal of Symbolic Logic 57 (1992), pp. 992-1010.

[30] E.C. Milner, Basic wqo- and bqo-theory. In Graphs and order, I.Rival Ed. (Banff, Alta., 1984), pages 487-502. Reidel, Dordrecht, 1985.

[31] M. Pouzet, Un belordre d'abritement et ses rapports avec les bornes d'une multirelation. Comptes rendus Acad. Sci. Paris 274(A) (1972), pp. 1677-1680.

[32] M. Pouzet, Application d'une propriete combinatoire des parties d'un ensemble aux groupes et aux relations. Math. Z. 150(2) (1976), pp. 117-134.

[33] M. Pouzet, Sur la theorie des relations. These d'etat, Universite Claude-Bernard, Lyon 1, pp. 78-85, 1978.

[34] M. Pouzet, Relation minimale pour son age. Z. Math. Logik Grundlag. Math. 25 (1979), pp. 315-344.

[35] M. Pouzet, The asymptotic behavior of a class of counting functions. Combinatorics 79 Part 2. M.DEZA and I.G.ROSENBERG Eds., Annals of Discrete Math. 9 (1980), pp. 223-224.

[36] M. Pouzet, Relation impartible. Dissertationnes 103 (1981), pp. 1-48.

[37] M. Pouzet, Application de la notion de relation presque-enchainable au denombrement des restrictions finies d'une relation. Z. Math. Logik Grundlag. Math. 27(4) (1981), pp. 289-332.

[38] M. Pouzet, Applications of well quasi-ordering and better quasi-ordering. In Graphs and order (Banff, Alta., 1984), pages 503-519. Reidel, Dordrecht, 1985.

[39] M. Pouzet and I.G. Rosenberg, Sperner properties for groups and relations, Europ. J. Combinatorics 7 (1986), pp. 349-370.

[40] M. Pouzet and M. Sobrani, Sandwiches of ages. Ann. Pure Appl. Logic 108(3) (2001), pp. 295-326.

[41] M. Pouzet and M. Sobrani, Ordinal invariants of an age. Preprint, 2002.

[42] M. Pouzet and N. Thiery, Some relational structures with polynomial growth and their associated algebras. May 10th, 2005, 19pages, presented at FPSAC for the 75 birthday of A.Garsia. http://arxiv.org/math.CO/0601256.

[43] M. Pouzet,When the orbit algebra of group is an integral domain? Proof of a Cameron's conjecture. Manuscript, Oct. 2002.

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

[45] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), pp. 264-286.

[46] C. Ryll-Nardzewski, On categoricity in power [less than or equal to] [[??].sub.a]. Bull. Acad. Pol. Sci. Ser. Math. Astr. Phys. 7 (1959), pp. 545-548.

[47] J. Schmerl, Coinductive [[??].sub.0]-categorical theories The Journal of Symbolic Logic 55 (1990), pp. 1130-1137.

[48] R.P. Stanley, Enumerative combinatorics. Volume 1, Wadsworth--Brooks/Cole Advanced Books and Software, Belmont, Calif. 1986.

[49] M. Sobrani, Sur les ages de relations et quelques aspects homologiques des constructions D+M. These de Doctorat d'etat, Universite S.M. Ben Abdallah-Fez, Fez, 2002.

[50] E.S. Wolk, Partially well-ordered sets and partial ordinals. Fun. Math. 60 (1967), pp. 175-185.

MAURICE POUZET ([dagger])

Probabilites-Combinatoire-Statistique,

Universite Claude-Bernard Lyon1, Domaine de Gerland,

bat. recherche, 50 Avenue Tony Garnier,

69365 Lyon cedex 07, France

([dagger]) E-mail address: pouzet@univ-lyon1.fr

Le profil d'une structure relationelle R est la fonction [[phi].sub.R] qui compte pour chaque entier n le nombre de ses sous-structures a n elements, les sous-structures isomorphes etant identifiees. Dans cet expose, je donne quelques exemples, notamment des exemples venant des groupes, et presente quelques faits frappants concernant le comportement des profils. J'indique le role joue par quelques notions de la theorie de l'ordre et de la combinatoire (eg belordre, algebre ordonnee, theoreme de Ramsey) dans l'etude du profil. Comme illustration, je montre que le profil d'une structure relationnelle R dont l'age est inepuisable et de hauteur au plus [omega](k + 1) satisfait l'inegalite [EXPRESSION MATHEMATIQUE NON REPRODUCIBLE EN ASCII.] pour tout entier n. Les recherches en cours suggerent de voir le profil d'une structure relationnelle R comme la fonction de Hilbert d'une algebre graduee associee a R; un exemple est l'algebre d'un age, inventee par P.J. Cameron. Je presente la solution d'une conjecture de Cameron sur l'integrite de l'algebre d'un age, ainsi que quelques progres recents faits avec Y.Boudabbous et N.Thiery sur la conjecture que la serie generatrice associee a un profil est une fraction rationnelle lorsque ce profil est borne par un polynome (et la structure a un noyau fini).

AMS Subject Classification: 03 C13, 03 C52, 05 A16, 05 C30, 20 B27.

Keywords: Relational structures, ages, counting functions, oligomorphic groups, age algebra, Ramsey theorem, well quasi ordering, cellular graphs, tournaments.

1 Introduction

This paper is a survey about the properties of a combinatorial function, the profile of a relational structure. I present a collection of results, some old, going back to 1971, some new, some published, some unpublished, and -in order to give to the reader a flavor of the techniques- I detail some proofs. An overview of results is given in Section 2. It is organized around two striking properties of the profile, namely: the profile of an infinite relational structure R is non decreasing and, provided that the arity of relations constituting R is bounded or the kernel of R is finite, its growth rate is either polynomial or faster than every polynomial. As observed by P.J.Cameron, the Hilbert function of the algebra of invariants of a finite group is a profile. This suggests that the generating series associated to a profile could be a rational fraction whenever the profile is bounded by a polynomial (and the relational structure has a finite kernel). I present a positive solution obtained jointly with N. Thiery for the class of relational structures admitting a finite decomposition into monomorphic components. As an illustration, I present the characterization of tournaments with polynomial profile obtained with Y. Boudabbous. A graded algebra, the age algebra, was associated by P.J Cameron to a relational structure R in such a way that its Hilbert function is the profile of R. This algebra and its role are presented in Section 3. The solution of a conjecture of Cameron on the integrity of the age algebra is also presented. These two sections contain very few detailed proofs. Some combinatorial tools needed for the study of the profile are presented in Section 4. An outline of the proof that the growth rate of a profile is either polynomial or faster than every polynomial is given (see Theorem 4.30). One of its ingredients is proved, namely the fact that the profile of a relational structure R whose age is inexhaustible and of height at most (k + 1) satisfies the inequality [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every non-negative integer n (Theorem 4.28).

The work presented here benefited from discussions and collaborations with several colleagues. I am pleased to thank them. I am particularly pleased to mention Y. Boudabbous, M. Sobrani and N. Thiery. Without them, the paper would have been different.

This paper is an outgrowth of a paper presented at the conference in honor of Claude Benzaken, in Grenoble, in september 2002. Since then, its content was presented to several audiences, eg in Caracas, Kingston, St Denis de la Reunion, Calgary, Tampere, Sfax and, last but not the least, in Hammamet, March 2006, at the annual meeting of the "Societe Mathematique de Tunisie". I thank the organizers for offering me this opportunity, the incentive to write this paper and for their warm hospitality.

2 Overview

2.1 Definitions and Simple Examples

A relational structure is a realization of a language whose non-logical symbols are predicates. This is a pair R := (E, [([[rho].sub.i]).sub.i [member of] I]) made of a set E and of a family of [m.sub.i]-ary relations [[rho].sub.i] on E. The set E is the domain or base of R. The family [mu] := [([m.sub.i]).sub.i[member of]I] is the signature of R. The substructure induced by R on a subset A of E, simply called the restriction of R to A, is the relational structure [R.sub.[up arrow]A] := (A, [([A.sup.[m.sub.i]] [intersection] [[rho].sub.i]).sub.i[member of]I]). Notions of isomorphism and local isomorphism from a relational structure to an other one are defined in a natural way as well as the notion of isomorphic type (see Section 4 for undefined notions). In the sequel, [tau](R) stands for the isomorphic type of a relational structure R and [[OMEGA].sub.[mu]] stands for the set of isomorphic types of finite relational structures with signature [mu].

The profile of R is the function [[phi].sub.R] which counts for every integer n the number [[phi].sub.R](n) of substructures of R induced on the n-element subsets, isomorphic substructures being identified.

Clearly, this function only depends upon the set A(R) of finite substructures of R considered up to an isomorphism, a set introduced by R. Fraisse under the name of age of R (see [14]).

If the signature [mu] is finite (in the sense that I is finite), there are only finitely many relational structures with signature [mu] on an n-element domain, hence [[phi].sub.R](n) is necessarily an integer for each integer n. In order to capture examples coming from algebra and group theory, we cannot preclude I to be infinite. But then, [[phi].sub.R](n) could be an infinite cardinal. As far as we will be concerned by the behavior of [[phi].sub.R], we will exclude this case. Indeed, we have:

Fact 1. Let n < |E|. Then

[[phi].sub.R](n) [less than or equal to] (n + 1)[[phi].sub.R](n + 1) (2.1)

In particular:

If [[phi].sub.R](n) is infinite then [[phi].sub.R](n + 1) is infinite too and [[phi].sub.R](n) = [[phi].sub.R](n + 1). (2.2)

Inequality (2.1) follows from a simple counting argument. Let [[E].sup.n] be the set of n-element subsets of E, A[(R).sub.n] := {[tau]([R.sub.[up arrow]F]) : F [member of] [[E].sup.n]} and [[E].sup.n+1], A[(R).sub.n+1] be the sets defined in a similar way. Let [GAMMA] := {([tau]([R.sub.[up arrow]F]), [tau] ([R.sub.[up arrow]F[union]{x}])) : F [member of] [[E].sup.n] and x [member of] E F}. We have trivially [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Item (2) follows immediately.

Hence, except in very few occasions, mentioned in the text, we make the assumption that [[phi].sub.R] is integer valued, no matter how large I is. With this assumption, profiles of relational structures with bounded signature are profiles of relational structures with finite signature, structures that R. Fraisse call multirelations, a fact that we record for further use.

Fact 2. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure of signature [mu] := [([m.sub.i]).sub.i[member of]I] and let n be a non-negative integer.

1. If [[phi].sub.R](n) is an integer there is a finite subset I' of I (whose size is bounded by a function of n and [[phi].sub.R](n)) such that the local isomorphisms of R and of its reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) which are defined on the n-element subsets of E are the same, hence [[phi].sub.R](n) = [[phi].sub.[R.sup.[up arrow]I']](n).

2. If in addition [mu] is bounded above by n, that is max [mu] := max{[m.sub.i] : i [member of] I} [less than or equal to] n, one may choose I' such that [[phi].sub.R] = [[phi].sub.[R.sup.[up arrow]I']].

Several counting functions are profiles. Here is some simple minded examples.

1. The binomial coefficient [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Let R := ([??],[less than or equal to], [u.sub.1],..., [u.sub.k]) where = is the natural order on the set [??] of rational numbers, [u.sub.1],..., [u.sub.k] are k unary relations which divide [??] into k + 1 intervals. Then [[phi].sub.R](n) = [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

2. The exponential n [??] [k.sup.n]. Let R := ([??],=, [u.sub.1],..., [u.sub.k]), where again [u.sub.1],..., [u.sub.k] are k unary relations, but which divide [??] into k "colors" in such a way that between two rational numbers all colors appear. Then [[phi].sub.R](n) = [k.sup.n].

3. The factorial n [??] n!. Let R := (Q,[less than or equal to], [less than or equal to]'), where [less than or equal to]' is an other linear order on [??] such a way that the finite restrictions induce all possible pairs of two linear orders on a finite set (eg take for [less than or equal to]' an order with the same type as the natural order on the set N of non-negative integers). Then [[phi].sub.R](n) = n!

4. The partition function which counts the number p(n) of partitions of the integer n. Let R := ([??], n) be the infinite path on the integers whose edges are pairs {x, y} such that y = x + 1. Then [[phi].sub.R](n) = p(n). The determination of its asymptotic growth is a famous achievement, the difficulties encountered to prove that p(n) [??] 1/4[square root of 3n][e.sup.[pi][square root of 2n/3]] (Hardy and Ramanujan, 1918) suggest some difficulties in the general study of profiles.

An important class of functions comes from permutation groups. The orbital profile of a permutation group G acting on a set E is the function [[theta].sub.G] which counts for each integer n the number, possibly infinite, of orbits of the n-element subsets of E. As it is easy to see, [[theta].sub.G] is the profile of some relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) on E. In fact, as it is easy to see:

Lemma 2.1. For every permutation groupGacting on a set E there is a relational structure R on E such that:

1. Every isomorphism f from a finite restriction of R onto an other extends to an automorphism of R.

2. AutR = [bar.G] where[bar.G] is the topological adherence of G into the symmetric group [??](E), equipped with the topology induced by the product topology on [E.sup.E], E being equipped with the discrete topology.

Structures satisfying condition 1) are called homogeneous (or ultrahomogeneous). They are now considered as one of the basic objects of model theory. Ages of such structures are called Fraisse classes after their characterization by R.Fraisse[13]. In many cases, I is infinite, even if [[theta].sub.G](n) is finite. Groups for which [[theta].sub.G](n) is always finite are said oligomorphic by P.J.Cameron. The study of their profile is whole subject by itself [5]. Their relevance to model theory stems from the following result of Ryll-Nardzewski [46].

Theorem 2.2. Let G acting on a denumerable set E and R be a relational structure such that AutR = [bar.G]. Then G is oligomorphic if and only if the complete theory of R is [[??].sub.0]-categorical.

2.2 A Sample of Results

2.2.1 The Profile Grows

Inequality (1) given in the previous subsection can be substantially improved:

Theorem 2.3. If R is a relational structure on an infinite set then [[phi].sub.R] is non-decreasing.

This result was conjectured with R.Fraisse [15]. We proved it in 1971; the proof--for a single relation- appeared in 1971 in R.Fraisse's book [16], Exercise 8 p. 113; the general case was detailed in [37]. The proof relies on Ramsey theorem [45]. We give it in 2.5.4.

More is true:

Theorem 2.4. If R is a relational structure on a set E having at least 2n + k elements then [[phi].sub.R](n) [less than or equal to] [[phi].sub.R](n + k).

Meaning that if |E| := m then [[phi].sub.R] increases up to m/2; and, for n [greater than or equal to] m/2 the value in n is at least the value of the symmetric of n w.r.t. m/2.

The result is a straightforward consequence of the following property of incidence matrices.

Let n, k, m be three non-negative integers and E be an m-element set. Let [M.sub.n,n+k] be the matrix whose rows are indexed by the n-element subsets P of E and columns by the n + k-element subsets Q of E, the coefficient [a.sub.P,Q] being equal to 1 if P [[subset].bar] Q and equal to 0 otherwise.

Theorem 2.5. If 2n + k [less than or equal to] m then [M.sub.n,n+k] has full row rank (over the the field of rational numbers).

With this result the proof of Theorem 2.4 goes as follows:

We suppose that [[phi].sub.R](n + k) is finite (otherwise, from Fact 1, the stated inequality holds). Thus, we may suppose also that E is finite (otherwise, for each isomorphic type [tau] of n + k-element restriction of R we select a subset Q of E such that [R.sub.[up arrow]Q] has type [tau] and we replace E by the union of the Q's). We consider the matrix whose rows are indexed by the isomorphic types [tau] of the restrictions of R to the n-element subsets of E and columns by the n-element subsets P of E, the coefficient [a.sub.[tau],P] being equal to 1 if [R.sub.[up arrow]P] has type [tau] and equal to 0 otherwise. Trivially, this matrix has full row rank, hence if we multiply it (from the left) with [M.sub.n,n+k] the resulting matrix has full row rank. Thus, there are [phi](n) linearly independent colums. These columns being distinct, the restrictions of R to the corresponding (n + k)-element subsets have different isomorphic types, hence [[phi].sub.R](n) = [[phi].sub.R](n + k).

We proved Theorem 2.4 in 1976 [32]. The same conclusion was obtained first for orbits of finite permutation groups by Livingstone and Wagner, 1965 [25], and extended to arbitrary permutation groups by Cameron, 1976 [3]. His proof uses the dual version of Theorem 2.5. Later on, he discovered a nice translation in terms of his age algebra. We present it in 3.2.

Theorem 2.5 is in W.Kantor 1972 [23], with similar results for affine and vector subspaces of a vector space. Over the last 30 years, it as been applied and rediscovered many times; recently, it was pointed out that it appeared in a 1966 paper of D.H.Gottlieb [20]. Nowadays, this is one of the fundamental tools in algebraic combinatorics. A proof, with a clever argument leading to further developments, was given by Fraisse in the 1986 edition of his book, Theory of relations, see [14].

2.2.2 Jumps in the Growth of the Profile

Infinite relational structures with profile constant, equal to 1, were called monomorphic and characterized by R. Fraisse who proved that they where chainable. Later on, those with profile bounded, called finimorphic, were characterized as almost chainable [15]. We present these characterizations in 2.5.3. Beyond bounded profiles, and provided that the relational structures satisfy some mild conditions, there are jumps in the behavior of the profiles: eg. no profile grows as log n or nlog n.

Let [phi]. : [??] [right arrow] [??] and [psi] : [??] [right arrow] [??]. Recall that [phi] = O([psi]) and [psi] grows as fast as [phi] if [phi](n) [less than or equal to] a[psi](n) for some positive real number a and n large enough. We say that [phi] and [psi] have the same growth if [phi] grows as fast as [psi] and [psi] grows as fast as [phi]. The growth of [phi] is polynomial of degree k if [phi] has the same growth as n [??] [n.sup.k]; in other words there are positive real numbers a and b such that [an.sup.k] [less than or equal to] [phi] [less than or equal to] [bn.sup.k] for n large enough. Note that the growth of [phi] is as fast as every polynomial if and only if [lim.sub.n[right arrow]+[infinity][phi](n)/[n.sup.k]] = +[infinity] for every non negative integer k.

Theorem 2.6. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure. The growth of [[phi].sub.R] is either polynomial or as fast as every polynomial provided that either the signature [mu] := [([[rho].sub.i]).sub.i[member of]I] is bounded or the kernel K(R) of R is finite.

The kernel of R is the set K(R) of x [member of] E such that A([R.sub.[up arrow]E\{x}]) [not equal to] A(R). Relational structures with empty kernel are those for which their age has the disjoint embedding property, meaning that two arbitrary members of the age can be embedded into a third in such a way that their domains are disjoint [34]. In Fraisse's terminology, ages with the disjoint embedding property are said inexhaustible and relational structures whose age is inexhaustible are said age-inexhaustible. We will say that relational structures with finite kernel are almost age-inexhaustible (1).

At this point, enough to know that the kernel of any relational structure which encodes an oligomorphic permutation group is finite (this fact immediate: if R encodes a permutation groupGacting on a set E then K(R) is the set union of the orbits of the 1-element subsets of E which are finite. Since the number of these orbits is at most [[theta].sub.G](1), if G is oligomorphic then K(R) is finite).

Corollary 2.7. The orbital profile of an oligomorphic group is either polynomial or faster than every polynomial.

Groups with orbital profile equal to 1 were described by P.Cameron in 1976 [3]. From his characterization, Cameron obtained that the growth rate of an orbital profile is ultimately constant, or it grows as fast as a linear function with slope 1/2.

For groups, and graphs, there is a much more precise result than Theorem 2.6. It is due to Macpherson, 1985 [27].

Theorem 2.8. The profile of a graph or a permutation groups grows either as a polynomial or as fast as [f.sub.[epsilon]], where [f.sub.[espsilon]](n) = [e.sup.[n.sup.1/2-[epsilon]]], this for every [epsilon] > 0.

Note that the [f.sub.[epsilon]] are somewhat similar to the partition function. Such growth cannot be prevented. Indeed, the partition function is the orbital profile of the automorphim group of an equivalence relation having infinitely many classes, all being infinite. Such a group is imprimitive. In fact, according to Macpherson 1987 [28]:

Theorem 2.9. If G is primitive then either [[theta].sub.G](n) = 1 for all n [member of] [??], or [[theta].sub.G](n) > [c.sup.n] for all n [member of] N, where c := [2.sup.1/5] - [??].

Some hypotheses on R are needed in Theorem 2.6, indeed

Theorem 2.10. For every non-decreasing and unbounded map [phi] : [??] [right arrow] [??], there is a relational structure R such that [[phi].sub.R] is unbounded and eventually bounded above by [phi].

More is true.

Let f : [??] [right arrow] [??] be a non-decreasing map such that 1 [less than or equal to] f(n) [less than or equal to] n + 1 for all n [member of] [??]. Let A := {n : f(n') < f(n + 1) for all n' < n + 1}. Let R := ([??], [([[rho].sub.n]).sub.n[member of]A]) in which each [[rho].sub.n] is n + 1-ary, with ([x.sub.1],..., [x.sub.n+1]) [member of] [[rho].sub.n] if and only if {[x.sub.1],..., [x.sub.n+1]} = {0,..., n}. Then [[phi].sub.R] = f.

The reader will notice that if f is unbounded then the signature of R is unbounded and also the kernel of R is infinite (equal to [??]).

The hypothesis about the kernel is not ad hoc. As it turns out, if the growth of the profile of a relational structure with a bounded signature is bounded by a polynomial then its kernel is finite(cf. Theorem 2.12 and Theorem 4.30).

An outline of the proof of Theorem 2.6 is given in the last section of the paper.

Theorems 2.6 and 2.10 were obtained in 1978 [33]. Theorem 2.10 and a part of Theorem 2.6 appear in [37], with a detailed proof showing that the growth of unbounded profiles of relational structures with bounded signature is at least linear. The notion of kernel is in [33], see also [34], [37], and [36] Lemme IV-3.1 p. 37.

2.3 Polynomial Growth

It is natural to ask:

Problem 1. If the profile of a relational structure R with finite kernel has polynomial growth, is [[phi].sub.R](n) [??] [cn.sup.k'] for some positive real c and some non-negative integer k'?

The problem was raised by P.J.Cameron for the special case of orbital profiles [5]. Up to now, it is unsolved, even in this special case.

An example, pointed out by P.J.Cameron, [5], suggests that a stronger property holds.

Let G' be the wreath product G' := G[??][[??].sub.[omega]] of a permutation group G acting on {1,..., k} and of [[??].sub.[omega]], the symmetric group on [omega]. Looking at G' as a permutation group acting on E' := {1,..., k} x [omega], then - as observed by Cameron-[[theta].sub.G'] is the Hilbert function [h.sub.Inv(G)] of the subalgebra Inv(G) of [??][[x.sub.1],..., [x.sub.k]] consisting of polynomials in the k indeterminates [x.sub.1],..., [x.sub.k] which are invariant under the action of G. The value of [h.sub.Inv(G)](n) is, by definition, the dimension dim([Inv.sub.n](G)) of the subspace of homogeneous polynomials of degree n. As it is well known, the Hilbert series of Inv(G),

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a rational fraction of the form

P(x)/(1 - x) ... (1 - [x.sup.k]) (2.3)

with P(0) = 1, P(1) > 0, and all coefficients of P being non negative integers.

Problem 2. Find an example of a permutation group G' acting on a set E with no finite orbit, such that the orbital profile of G' has polynomial growth, but is not the Hilbert function of the invariant ring Inv(G) associated with a permutation group G acting on a finite set.

Let us associate to a relational structure R whose profile takes only finite values its generating series

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

Problem 3. If R has a finite kernel and [[phi].sub.R] is bounded above by some polynomial, is the series [H.sub.[phi]R] a rational fraction of the form

P(x)/(1 - x)(1 - [x.sup.2]) ... (1 - [x.sup.k])

with P [member of] [??][x]?

Under the hypothesis above we do not know if [H.sub.[phi]R] is a rational fraction.

It is well known that if a generating function is of the form P(x)/(1-x)(1-[x.sup.2]) ... (1-[x.sup.k]) then for n large enough, an is a quasi-polynomial of degree k', with k' [less than or equal to] k - 1, that is a polynomial [a.sub.k'](n)[n.sup.k'] + ... + [a.sub.0](n) whose coefficients [a.sub.k'](n),..., [a.sub.0](n) are periodic functions. Hence, a subproblem is:

Problem 4. If R has a finite kernel and [[phi].sub.R] is bounded above by some polynomial, is [[phi].sub.R](n) a quasi-polynomial for n large enough?

Remark 2.11. Since the profile is non-decreasing, if [[phi].sub.R](n) is a quasi-polynomial for n large enough then [a.sub.k'](n) is eventually constant. Hence the profile has polynomial growth in the sense that [[phi].sub.R](n) ~ [cn.sup.k'] for some positive real c and k' [member of] [??]. Thus, in this case, Problem 1 has a positive solution.

In the theory of languages, one of the basic results is that the generating series of a regular language is a rational fraction (see [1]). This result is not far away from our considerations. Indeed, if A is a finite alphabet, with say k elements, and [A.sup.*] is the set of words over A, then each word can be viewed as a finite chain coloured by k colors and [A.sup.*] can be viewed as the age of the relational structure made of the chain [??] of rational numbers divided into k colors in such a way that, between two distinct rational numbers, all colors appear. This structure was Example (2) in Subsection 1.1.

Problem 5. Does the members of the age of a relational structure with polynomial growth can be coded by words forming a regular language?

Problem 6. Extend the properties of regular languages to subsets of [[OMEGA].sub.[mu]].

2.4 Morphology of Relational Structures with Polynomial Growth

We only have a partial description of relational structures with polynomial growth.

Let us say that a relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is almost multichai-nable if there is a finite subset F of E and an enumeration [([a.sub.x,y]).sub.(x,y)[member of]VxL] of the elements of E \ F by a set V x L, where V is finite and L is a linearly ordered set, such that for every local isomorphism f of L the map ([1.sub.V], f) extended by the identity on F is a local isomorphism of R (the map ([1.sub.V], f) is defined by ([1.sub.V], f)(x, y) := (x, f (y))).

Note that if L is infinite, K(R), the kernel of R, is a subset of F. Thus we have:

Fact 3. An almost multichainable relational structure has a finite kernel.

The notion of almost multichainability was introduced in [33] and appeared in [36, 34]. It seems to be a little bit hard to swallow. The special case |V| = 1, for which the linear order L can be defined on E F, is discussed in more details in 2.5.3.

The profile of an almost multichainable relational structure is not necessarily bounded above by a polynomial (see the last two examples given in Examples 2.13).

Problem 7. If the profile of an almost multichainable relational structure is not bounded above by a polynomial, does his profile has exponential growth? Is the generating series a rational fraction?

Theorem 2.12. If the profile of a relational structure R with bounded signature or finite kernel is bounded above by a polynomial then R is almost multichainable.

For a proof, see Section 4, Theorem 4.30.

There are two cases, in fact opposite cases, for which the profile of an almost multichainable relational structure is bounded above by a polynomial.

1. Case 1. ([1.sub.V], f) extended by the identity on F is an automorphism of R for every permutation f of L.

2. Case 2. For every family [([f.sub.x]).sub.x[member of]V] of local isomorphisms of L, the map [union]{[f.sub.x] : x [member of] V} extended by the identity on F is a local isomorphism of f (the map [union]{[f.sub.x] : x [member of] V} associates (x, [f.sub.x](y)) to (x, y)).

A relational structure for which there are F and [([a.sub.x,y]).sub.(x,y)[member of]VxL] such that Case 1 holds is cellular. This notion was introduced by Schmerl [47]. We illustrate it below. Relational structures for which case 2 holds are illustrated in subsection 2.5.

2.4.1 The Case of Graphs

A directed graph is a pair G := (E, [rho]) where [rho] is a binary relation on E. Ordered sets and tournaments are special case of directed graphs. We will use the term graph if [rho] is irreflexive and symmetric. In this case [rho] is identified with the set E of pairs {x, y} of members of E such that x[rho]y, G is identified with (E, E); the members of E and E are the vertices and edges of G. We denote by V (G), resp. E(G), the set of vertices, resp. edges, of G.

In terms of profile, the class of graphs provides interesting examples.

Examples 2.13. 1. [[phi].sub.G](n) is constant, equal to 1, for every n [less than or equal to] |V(G)|, if and only if [[phi].sub.G](2) [less than or equal to] 1, that is G is a clique or an independent set (trivial).

2. [[phi].sub.G] is bounded if and only if G is "almost constant" in the Fraisse's terminology, that is there is a finite subset [F.sub.G] of vertices such that two pairs {x, y} and {x', y'} of vertices having the same intersection on [F.sub.G] are both edges or both non-edges. This fact is an immediate consequence of Theorem 2.25.

3. If G is the direct sum of infinitely many edges, or the direct sum [K.sub.[omega]] [direct sum] [K.sub.[omega]] of two infinite cliques, then [[phi].sub.G](n) = [n/2] + 1, whereas [H.sub.[phi]G] = 1/(1-x)(1-[x.sup.2]).

4. Let G be the direct sum [K.sub.(1,[omega])] [direct sum] [[bar.K].sub.[omega]] of an infinite wheel and an infinite independent set, or the direct sum [K.sub.[omega]] [direct sum] [[bar.K].sub.[omega]] of an infinite clique and an infinite independent set. Then [[phi].sub.G](n) = n. Hence [H.sub.[phi]G] = 1 + x/[(1-x).sup.2], that we may write 1-x- [x.sup.2]/[(1-x).sup.2], as well as 1+[x.sup.3]/(1-x)(1-[x.sup.2]).

5. Let G be the direct sum of infinitely many k-element cliques or the direct sum of k infinite cliques. Then [[phi].sub.G](n) = [p.sub.k](n) [??] [n.sup.k-1]/(k-1)!k! and [H.sub.[phi]G] = 1/(1-x) ... (1- [x.sup.k]).

6. If G is either the direct sum of infinitely many infinite cliques -or an infinite path- then [[phi].sub.G](n) = p(n) the partition function.

7. Let C := (E, [less than or equal to]) be a chain and [K.sub.C,1/2] be the graph whose vertex set is 2 x E and the edge set is {{(0, i), (1, j)} : i < j in C}. Such a graph is an half-complete bipartite graph. If C is infinite, then [2.sup.n-2] [less than or equal to] [[phi].sub.[K.sub.C, 1/2]](n) [less than or equal to] [2.sup.n-1] [27], hence its growth is exponential. In fact, one can check that: [H.sub.[K.sub.C,1/2]] = 1-2x- [x.sup.2]+3[x.sup.3]-[x.sup.4]/(1-x)(1-2x)(1-2[x.sup.2]) = 1 + x + 2[x.sup.2] + 3[x.sup.3] + 6[x.sup.4] + 10[x.sup.5] + 20[x.sup.6] + 36[x.sup.7] + 72[x.sup.8] + 136[x.sup.9] + O([x.sup.10]).

8. Let [[??].sub.C,1/2] be the graph obtained from [K.sub.C,1/2] by adding all possible edges between vertices of the form (1, i), for i [member of] E. Then [[phi].sub.[[??].sub.C,1/2]](n) = [2.sup.n-1].

Theorem 2.14. The profile of a graph is bounded by a polynomial if and only if this graph is cellular.

A straightforward computation shows that the profile of a cellular graph is bounded by a polynomial. The converse follows directly from Theorem 2.12 and Lemma 2.15 below. A self-contained proof will hopefully appear in a joint work with S. Thomasse and R. Woodrow. Lemma 2.15. The growth of the profile of almost multichainable graph which is not cellular is at least exponential

Indeed, let G be an almost multichainable graph. The sets F, V and L which appear in the definition of the almost multichainability of G satisfy the following conditions: F,V are finite, V(G) = F [union] V x L and:

{a, (x, i)} [member of] E(G) if and only if {a, (x, j)} [member of] E(G) (2.4)

for all a [member of] F, x [member of] V, j [member of] L

{(x, i), (y, j)} [member of] E(G) if and only if {(x, i'), (y, j ')} [member of] E(G) (2.5)

for all x, y [member of] V, i, j, i', j' [member of] L such that i[rho]j and i'[rho]j' where [rho] is either the equality relation on L or the strict order < on L.

If G is not cellular then there is some permutation f of L such that ([1.sub.V], f) extended by the identity on F is not an automorphism of G. The map f does not preserve the order on L, hence, there are [i.sub.0], [j.sub.0] [member of] L and x, y [member of] V such that {(x, [i.sub.0]), (y, [j.sub.0])} [member of] E(G) and {(x, [j.sub.0]), (y, [i.sub.0])} [??] E(G).

Let H := [G.sub.[up arrow]{x,y}xL]. This graph is multichainable, hence it is entirely determined by the edges belonging to [[{x, y}x{[i.sub.0], [j.sub.0]}].sup.2]\{(x, [j.sub.0]), (y, [j.sub.0])}. There are 16 possible graphs. But, if L is infinite, these graphs yield only two distinct ages, namely the age of [K.sub.C,1/2] and the age of [[??].sub.C,1/2], two graphs described in (7) and (8) of Examples 2.13. Hence, they yield at most two distinct profiles. Their growth rates, as computed in Examples 2.13, are exponential, hence the growth rate of [[phi].sub.G] is at least exponential as claimed.

We do not know if Problem 1 has a positive answer for cellular graphs. Problem 3 has a positive answer for a special class of relational structures described in the following subsection.

2.5 Relational Structures Admitting a Finite Monomorphic Decomposition

A monomorphic decomposition of a relational structure R is a partition P of E into blocks such that for every integer n, the induced structures on two n-elements subsets A and A' of E are isomorphic whenever the intersections A[intersection]B and A'[intersection]B over each block B of P have the same size.

This notion was introduced with N. Thiery [42].

If an infinite relational structure R has a monomorphic decomposition into finitely many blocks, whereof k are infinite, then the profile is bounded by some polynomial, whose degree itself is bounded by k - 1. Indeed, as one may immediately see:

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

where r is the cardinality of the union of the finite blocks.

One can say more:

Theorem 2.16 ([42]). Let R be an infinite relational structure R with a monomorphic decomposition into finitely many blocks ([E.sub.i], i [member of] X), k of which being infinite. Then, the generating series [H.sub.[phi]R] is a rational fraction of the form:

P(x)/(1 - x)(1 - [x.sup.2]) ... (1 - [x.sup.k]).

Corollary 2.17 ([42]). Let R a relational structure as above, then [[phi].sub.R] has a polynomial growth and in fact [[phi].sub.R](n) ~ [an.sup.k'] for some positive real a, some non-negative integer k'.

Recently, with N. Thiery, we proved:

Lemma 2.18. If k is the least number of infinite blocks that a monomorphic decomposition of R may have then [[phi].sub.R](n) ~ [an.sup.k-1].

The proof idea of Theorem 2.16 is this. To each subset A of size n

of E, we associate the monomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

where [d.sub.i](A) = |A [intersection] [E.sub.i]| for all i in X. Obviously, A is isomorphic to B whenever [x.sup.d(A)] = [x.sup.d(B)]. The shape of a monomial [x.sup.d] = [PI] [x.sup.[d.sub.i].sub.i] is the partition obtained by sorting decreasingly ([d.sub.i], i [member of] X). We define a total order on monomials by comparing their shape w.r.t. the degree reverse lexicographic order, and breaking ties by the usual lexicographic order on monomials w.r.t. some arbitrary fixed order on X. If [tau] [member of] A(R) its leading monomial lm([tau]) is the maximum of the monomials [x.sup.d(A)] where [R.sub.[up arrow]A] has isomorphic type [tau]. If S is subset of X, set [x.sub.S] := 1 if S = [empty set] and [x.sub.S] := [[PI].sub.i[member of]S] [x.sub.i] otherwise. We may write every monomial m (distinct from 1) as a product [PI][([x.sub.[S.sub.1]]).sup.[m.sub.1]] ... [([x.sub.[S.sub.k]]).sup.[m.sub.k]] for a unique sequence C := ([empty set] [??] [S.sub.1] [??] ... [S.sub.r] [subset.bar] X) of non-empty subsets of X. This sequence is the chain support of m. To such a sequence C, we associate the set [lm.sub.C] of leading monomials with chain support C. We prove that one can realize [lm.sub.C] as the linear basis of some ideal of a polynomial ring, so that the generating series of [lm.sub.C] is realized as an Hilbert series. From this, one concludes easily that [H.sub.[phi]R] has the same form.

The key property of leading monomials in this proof is this lemma:

Lemma 2.19 ([42]). Let m be a leading monomial, and S [subset] X be a layer of m. Then, either [d.sub.i] = |[E.sub.i]| for some i in S, or [mx.sub.S] is again a leading monomial.

The proof of this result relies on Proposition 2.20 below for which we introduce the following definition. Let R be a relational structure on E; a subset B of E is a monomorphic part of R if for every integer n and every pair A, A' of n-element subsets of E the induced structures on A and A' are isomorphic whenever A \ B = A' \ B.

Proposition 2.20 ([42]). 1. For every x [member of] E, the set-union R(x) of all the monomorphic parts of R containing x is a monomorphic part, the largest monomorphic part of R containing x.

2. The largest monomorphic parts form a monomorphic decomposition of R of which every monomorphic decomposition of R is a refinement.

We will call canonical the decomposition of R into maximal monomorphic parts. This decomposition has the least possible number of parts.

Despite the apparent simplicity of relational structures admitting a finite monomorphic decomposition, there are many significant examples.

2.5.1 Relational Structures which are Categorical for Their Age

A relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is categorical for its age if every R' having the same age than R is isomorphic to R. It was proved in [22] that for a relational structure with a finite signature, this happens just in case E is at most denumerable and can be divided into finitely many blocks such that every permutation of E which preserves each block is an automorphism of R.

These structures may occur in some interesting areas. For a simple minded example, let G' := G[??][[??].sub.[omega]] be the wreath product of a permutation group G acting on {1,..., k} and of [[??].sub.[omega]], the symmetric group on [omega]. As we have noticed, the orbital profile of G' is the Hilbert function of the algebra of invariants of G. Now, the group G' is the automorphism group of a relational structure R which is categorical for its age. Among the possible R' take R' := (E', [([[bar.[rho]].sub.i]).sub.i[member of]I]) where [[bar.[rho]].sub.i] := {(([x.sub.1],[m.sub.1]),..., ([x.sub.[n.sub.i]],[m.sub.[n.sub.i]])) : ([x.sub.1],..., [x.sub.[n.sub.i]]) [member of] [[rho].sub.i], ([m.sub.1],..., [m.sub.[n.sub.i]]) [member of] [[??].sup.{1,..., [n.sub.i]}}, R := ({1,..., k}, [([[rho].sub.i]).sub.i[member of]I]) is a relational structure containing the equality relation and having signature [mu] := [([n.sub.i])[member of]I] such that AutR = G. Such an R' decomposes into k monomorphic components, namely the sets [E'.sub.i], 1 [less than or equal to] i < k (where [E'.sub.i] := {(i, m) : m [member of] [??]}).

2.5.2 Quasi-Symmetric Polynomials

Let [x.sub.1],..., [x.sub.k] be k-indeterminates and [n.sub.1],..., [n.sub.l] be a sequence of non-negative integers, 1 [less than or equal to] l [less than or equal to] k. The polynomial

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

is a quasi-monomial of degree n, where n =: [n.sub.1] + ... + [n.sub.l]. The vector space spanned by the quasi-monomials forms the space [QS.sub.k] of quasi-polynomials as introduced by I. Gessel. As in the example above, the Hilbert series of [QS.sub.k+1] is defined as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

As shown by F. Bergeron, C. Retenauer, see [18], this series is a rational fraction of the form [P.sub.k]/(1-x)(1-[x.sup.2]) ... (1-[x.sup.k]) where the coefficients [P.sub.k] are non negative. Let R be the poset product of a k-element chain by a denumerable antichain. More formally, R := (E, [rho]) where E := {1,..., k} x [??] and [rho] := {((i, n), (j, m)) [member of] E such that i [less than or equal to] j}. Each isomorphic type of an n-element restriction may be identified to a quasi-polynomial, hence the generating series associated to the profile of R is the Hilbert series defined above. Since R decomposes into k monomorphic components, the rationality of this series is a special case of Theorem 2.16. The reason for which the coefficients of this fraction are non-negative was elucidated only recently by Garsia and Wallach [18]. They proved that [QS.sub.k] is Cohen-Macaulay.

2.5.3 Monomorphic Relational Structures, Chainability and Extensions

We present here the origin of the notion of relational structure admitting a monomorphic decomposition into finitely many blocks.

According to R.Fraisse who introduced this notion in 1954 in his thesis, a relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) for which [[phi].sub.R](n) = 1 for every n [less than or equal to] |E| is monomorphic.

Example 2.21. There are eight kinds of monomorphic directed graphs, four made of reflexive directed graphs, four made of irreflexive graphs. For the reflexive ones, there are the chains, the reflexive cliques, the antichains, plus the 3-element oriented reflexive cycle. Whereas, for the irreflexive ones, there are the acyclic (oriented) graphs, the cliques, the independent sets, and the 3-element oriented irreflexive cycle.

Fraisse gave a characterization of infinite monomorphic relational structures by means of his notion of chainability:

A relational structure R := (E, [([[rho].sub.i]).sub.i[member of]I]) is chainable if there is a linear ordering [less than or equal to] on E such that every local isomorphism of L := (E, [less than or equal to]) is a local isomorphism of R.

Since chains are monomorphic, chainable relational structures are also monomorphic. The converse does not hold, as shown by a 3-element cycle. Fraisse proved that it holds if the structure is infinite.

Theorem 2.22. An infinite relational structure is monomorphic if and only if it is chainable.

His proof, given for relational structures of finite signature, was based on Ramsey's theorem [45] and the compactness theorem of first order logic. The extension to arbitrary signature requires an other application of the compactness theorem (for a detailed proof, see [37]).

We give the proof idea, in the setting of a generalization of the monomorphy and chainability notions.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure and F be a subset of E. The relational structure R is F-monomorphic if for every non-negative integer n and every A, A' [member of] [[E\F].sup.n] there is an isomorphism from [R.sub.[up arrow]A] onto [R.sub.[up arrow]A'] which extends by the identity on F to an isomorphism of [R.sub.A[union]F] onto [R.sub.A'[union]F']. This relational structure is F-chainable if there is a linear order [less than or equal to] on E \ F such that every local isomorphism of L := (E \ F, [less than or equal to]), once extended by the identity on F, is a local isomorphism of R. This relational structure is almost monomorphic, resp. almost chainable, if it is F-monomorphic, resp. F-chainable for some finite subset F of E.

From Ramsey's theorem, Fraisse deduced the following lemma.

Lemma 2.23. Let R be a relational structure with domain E and F be a finite subset of E. If the signature of R is finite then there is an infinite subset E' of E containing F on which the restriction R' := [R.sub.[up arrow]E'] is F-chainable.

Then he applied the compactness theorem of first order logic (in a weaker form, given by his "coherence lemma"). Indeed, from Lemma 2.23 above, if a monomorphic relational structure R of finite signature is infinite, it contains an infinite induced substructure R' which is chainable. Since R is monomorphic, each finite substructure of R is isomorphic to some finite substructure of R', hence is chainable. The compactness theorem insures that R is chainable. As said, this conclusion holds if the signature is arbitrary.

Theorem 2.22 has the following strenghtening.

Theorem 2.24. Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure, E' be a subset of E and F := E' \ E. Let us consider the following properties

(i) R is F-chainable;

(ii) R is F-monomorphic;

(iii) E' is a monomorphic part of R.

Then (i) [??] (ii) [??] (iii). If E' is infinite then (ii) [??] (i). If E' is infinite and E' is a monomorphic component of R then (iii) [member of] (ii).

For these implications, one considers first the case for which the signature and F are finite. Then, one applies Lemma 2.23 and the compactness theorem of first order logic. The general case follows by another application of the compactness theorem.

This yields:

Theorem 2.25. For a relational structure, the following properties are equivalent:

(i) The profile of R is bounded by some integer.

(ii) R has a monomorphic decomposition into finitely many blocks, at most one being infinite.

(iii) R is almost chainable.

(iv) R is almost monomorphic.

Theorem 2.25 above was proved (without Item (ii)) in [15] for finite signature and in [37] for arbitrary signature. Theorem 2.3 was proved afterward.

From Theorem 2.3 and Theorem 2.25, it follows that a relational structure R has a monomorphic decomposition into finitely many blocks, at most one being infinite, if and only if

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.],

where [b.sub.1],..., [b.sub.l] re non negative integers.

With this elementary fact in hands, it was not so hard to conjecture the extension given in Theorem 2.16.

2.5.4 An illustration: a proof of Theorem 2.3

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure. Suppose E be infinite. Let n be a non negative integer. We claim that [[phi].sub.R](n) [less than or equal to] [[phi].sub.R](n + 1).

Case 1. [[phi].sub.R](n) is infinite. Then, as stated in Fact 1, [[phi].sub.R](n) = [[phi].sub.R](n + 1) as claimed.

Case 2. [[phi].sub.R](n) is finite. We reduce the claim to the case of an almost monomorphic relational structure.

Claim 1. There is some finite subset I' of I and some infinite subset E' of E such that the reduct R' := [R.sup.[up arrow]I'.sub.[up arrow]E'] is almost monomorphic and [[phi].sub.R'](n) = [[phi].sub.R](n).

Proof of Claim 1. According to (1) of Fact 2, there is some finite subset I' of I such that the reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) satisfies [[phi].sub.[R.sup.[up arrow]I']](n) = [[phi].sub.R](n). Let m := [[phi].sub.[R.sup.[up arrow]I']](n). Select [F.sub.1],... [F.sub.m] in [[E].sup.n] such that the restrictions [R.sup.[up arrow]I'.sub.[up arrow][F.sub.1]],..., [R.sup.[up arrow]I'.sub.[up arrow][F.sub.m]] are pairwise non-isomorphic. Set F := [F.sub.1] [union] ... [union] [F.sub.m]. According to Lemma 2.23, there is an infinite subset E' of E containing F such that the restriction R' := [R.sup.[up arrow]I'.sub.[up arrow].sub.E']] is F-chainable. This restriction is almost monomorphic. From our construction, [[phi].sub.R'](n) = m. This proves Claim 1.

Claim 2. If an infinite relational structure R' := (E', [([[rho].sub.i]).sub.i[member of]I']) is almost monomorphic then [[phi].sub.R'] is non-decreasing.

Proof of Claim 2. Let F be a finite subset of E' such that R' is F-monomorphic. Let n be a non-negative integer. Let m := [[phi].sub.R'](n) and let [[tau].sub.1],..., [[tau].sub.m] be the isomorphic types of the n-element restrictions of R'. Select [F.sub.1],..., [F.sub.m] such that for each i, 1 [less than or equal to] i [less than or equal to] m, [R'.sub.[up arrow][F.sub.i]] has type [[tau].sub.i] and |F [intersection] [F.sub.i]| is minimum. Pick x [member of] E' \(F[union] [F.sub.1][union] ... [union][F.sub.m]) and set [F'.sub.i] := [F.sub.i] [union]{x} for i, 1 = i = m. We claim that the restrictions [R'.sub.[up arrow][F'.sub.1]],..., [R'.sub.[up arrow][F'.sub.m]] are pairwise non-isomorphic, from which the inequality [[phi].sub.R'](n) [less than or equal to] [[phi].sub.R'](n + 1) will follow. Indeed, suppose that there is some isomorphism f from [R'.sub.[up arrow][F.sub.i]] onto [R'.sub.[up arrow][F.sub.j]]. With no loss of generality, we may suppose |[F.sub.i] [intersection] F| [greater than or equal to] |[F.sub.j] [intersection] F|. Then f(x) [??] F, otherwise [R'.sub.[up arrow][F".sub.j]], where [F".sub.j] := [F'.sub.j] \ {f (x)}, has type [[tau].sub.i] and |[F".sub.j] intersection] F| < |[F.sub.i] [intersection] F|, contradicting the choice of [F.sub.i] [member of] Hence f(x) [member of] [F'.sub.j] F. Since R' is F-monomorphic, the restriction [R'.sub.[up arrow][F.sub.j]\{f(x)}] and [R'.sub.[up arrow][F'.sub.j]]\{x} are isomorphic. Since their types are respectively [[tau].sub.i] and [[tau].sub.j], we have i =

2.5.5 Directed Graphs

Monomorphic decompositions can be easily described in the case of directed graphs.

For that we recall that a subset A [[subset].bar] V(G) of a a directed graph is autonomous if for every x, x' [member of] A, y [??] A, the following two conditions holds:

(x, y) [member of] E(G) if and only if (x', y) [member of] E(G)

(y, x) [member of] E(G) if and only if (y, x') [member of] E(G).

The empty set, the one-element subsets of V(G) and V(G) itself are autonomous. If there are no others, G is prime.

We also recall that, if a directed graph G is a lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], indexed by a directed graph D, then provided that there are pairwise disjoint, the V([G.sub.i]) form a partition of V(G) into automomous subsets. Conversely, if the vertex set V(G) of directed graph G is partionned into autonomous subsets, then G is the lexicographical sum of the directed graphs induced on the blocks of the partition.

Theorem 2.26. Let G be a directed graph. Then G has a finite monomorphic decomposition if and only if G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], indexed by a finite directed graph D, each [G.sub.i] being one of six kinds: an oriented acyclic graph, a clique, an independent set, a chain, a reflexive clique, or an antichain. Moreover, if G decomposes into such a sum with all the V([G.sub.i])'s non-empty and if D contains no 2-element autonomous subset, then both the monomorphic components of G and the V([G.sub.i])'s wich are infinite coincide.

Proof. Let W be a monomorphic component of G. If W is infinite then [G.sub.[up arrow]W] is of one of the six kinds mentionned in Theorem 2.26. Moreover, as it follows from implication (iii) [member of] (i) of Theorem 2.24, W is autonomous. Hence, if G has a finite monomorphic decomposition, the partition of V(G) into the infinite blocks of the canonical decomposition of G and of the singletons of the remainder is a partition into autonomous sets, each of one of these six kinds. If G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of directed graphs [G.sub.i], each one of these six kinds and if a monomorphic component W contains some V([G.sub.i]) with V([G.sub.i]) infinite then W = V([G.sub.i]). Otherwise, since W is one of the six kinds above and W is autonomous, the set A := {j [member of] V(D) : [V.sub.j] [member of] W} is autonomous and D'A is of one of these six kind. Since D is finite, it contains a 2-element autonomous subset.

In the later case, Lemma 2.18 yields:

Corollary 2.27. If G is a finite lexicographical sum [[summation].sub.i[member of]D] [G.sub.i] of a family of non-empty directed graphs [G.sub.i], indexed by a finite directed graph D, each [G.sub.i] being either an oriented acyclic graph, a clique, an independent set, a chain, a reflexive clique, or an antichain and if D contains no 2-element autonomous subset then [[phi].sub.G](n) ~ [an.sup.k-1] where k is the number of infinite [G'.sub.i]s.

A prime directed graph D with |V(D)| [greater than or equal to] 3 cannot contain a 2-element autonomous subset. Since there are prime directed graphs of arbitrarily large size, Corollary 2.27 yields examples of directed graphs of polynomial growth of degree k for every non negative integer k.

2.5.6 Tournaments

The monomorphic tournaments are the acyclic ones and the 3-element cycle. Hence from Theorem 2.26, a tournament has a finite monomorphic decomposition if and only if it is a lexicographical sum of acyclic tournaments indexed by a finite tournament. We may reformulate this in a simpler form.

An acyclic component of a tournament T is a subset of V(T) which is maximal w.r.t. inclusion among the acyclic autonomous subsets of V(T). Clearly, every acyclic autonomous subset is contained into an acyclic component. As it is easy to see, the acyclic components of a tournament form a partition of its vertex set. It follows that a tournament is a lexicographical sum of acyclic tournaments indexed by a finite tournament if and only if it has only finitely many acyclic components.

With Y.Boudabbous [2], we identified twelve infinite tournaments and proved that an infinite tournament T is a finite lexicographical sum of acyclic tournaments if and only if T embeds none of these tournaments. The growth of the profile of each of these tournaments being exponential, we deduced from Theorem 2.16 andLemma2.18 the following dichotomy result.

Theorem 2.28. [2] The growth of the profile of a tournament T is either polynomial, in which case T is a lexicographic sum of acyclic tournaments indexed by a finite tournament, or it is at least exponential.

There are prime tournaments of arbitrarily large finite size, hence, according to Corollary 2.27 there are tournaments of arbitrarily large polynomial growth. We give below some examples of small growth.

Examples 2.29. 1. If T is an acyclic tournament, then [[phi].sub.T](n) = 1 for every integer n, n [less than or equal to] |T|. Conversely, if |T| [not equal to] 3 and [[phi].sub.T](3) = 1 then T is acyclic.

Let [omega] be the tournament made of the integers, with the strict ordering, that is [omega]:= ([??], {(p, q) [member of] [[??].sup.2] : p < q}), and let * be its dual. Note that according to the theorem of Ramsey, every infinite tournament contains a subtournament which is isomorphic to [omega] or to [[omega].sup.*].

Let [C.sub.3] := ({0, 1, 2}, {(0, 1), (1, 2), (2, 0)}) be the 3-element cycle. For i := 1, 2, 3, let [T.sub.i] be the tournament obtained by replacing i vertices of [C.sub.3] by [omega].

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

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

4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

The profile of tournaments goes largely beyond polynomials. For an example of exponential profile, let [C.sub.3.[omega]] be the lexicographical sum of infinitely many copies of [C.sub.3]. Then the generating serie of the profile is [H.sub.[[phi].sub.[C.sub.3.[omega]]]] = 1/1-x-[x.sup.3] hence the profile is exponential (see sequence A000930 in Encyclopedia of integer sequences (URL: http://www.research.att.com).).

3 The Age Algebra of Cameron

P. J. Cameron [5, 6] associates to A(R), the age of a relational structure R, its age algebra, a graded commutative algebra [??].A(R) over a field [??] of characteristic zero. He shows that if [[phi].sub.R] takes only finite values, then the dimension of [??].A[(R).sub.n], the homogeneous component of degree n of [??].A(R), is [[phi].sub.R](n). Hence, in this case, the generating series of the profile is simply the Hilbert series of [??].A(R).

P.J Cameron mentions several interesting examples of algebras which turn to be age algebras. The most basic one is the shuffle algebra on the set [A.sup.*] of words on a finite alphabet A [26]. Indeed, as mentionned at the end of Subsection 2.3, [A.sup.*] is the age of the relational structure ([??], [([U.sub.a]).sub.a[member og]A]) where the [U.sub.a]'s are unary relations forming a coloring of [??] into distinct colors, in such a way that between two distinct rational numbers, all colors appear. And the shuffle algebra is isomorphic to the age algebra of ([??], [([U.sub.a]).sub.a[member of]A]).

There are several reasons to associate a graded algebra to an age. We will examine some in the next subsections. For the ease of our discussion, we recall the presentation of the age algebra via the set algebra (see [8]).

3.1 The Set Algebra

Let E be a set and let [[E].sup.<[omega]] be the set of finite subsets of E (including the empty set [empty set]). Let [??] be a field and [[??].sup.[[E].sup.<[omega]]] be the set of maps f : [[E].sup.<[omega]] [right arrow] [??]. Endowed with the usual addition and scalar multiplication of maps, this set is a vector space over [??]. Let f, g [member of] [[??].sup.[[E].sup.<[omega]]] and Q [member of] [[E].sup.<[omega]]. Set

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

. With this operation added, the above vector space becomes a [??]-algebra. This algebra is commutative and it has a unit, denoted by 1. This is the map taking the value 1 on the empty set and the value 0 everywhere else. The set algebra is the subalgebra made of the maps such that f (P) = 0 for every P [member of] [[E].sup.<[omega]] with |P| large enough. This algebra is graded, the homogeneous component of degree n being made of maps which take the value 0 on every subset of size different from n.

Let = be an equivalence relation on [[E].sup.<[omega]]. A map f : [[E].sup.<[omega]] [right arrow] [??] is [equivalent to]-invariant, or briefly, invariant, if f is constant on each equivalence class. Invariant maps form a subspace of the vector space [[??].sup.[[E].sup.<[omega]]]. We give a condition which insure that they form a subalgebra too.

An equivalence relation on [[E].sup.<[omega]] is hereditary if every pair D, D' of equivalent elements satisfies the following conditions:

1. |D| = |D'| = d for some d.

2. |{X [[subset].bar] D : X = B}| = |{X [[subset].bar] D' : X [equivalent to] B}| for every B [[subset].bar] E

Hereditary equivalence where introduced in [39].

With N.Thiery, we proved:

Proposition 3.1. Let = be an hereditary equivalence relation on [[E].sup.<[omega]]. Then the product of two invariant maps is invariant. Thus the set of invariant maps f : [[E].sup.<[omega]] [right arrow] [??] form a subalgebra of [[??].sup.[[E].sup.<[omega]]].

Let R be a relational structure with domain E. Set F [equivalent to][sub.R] F' for F, F' [member of] [[E].sup.<[omega]] if the restrictions R [sub.[up arrow]F] and R [sub.[up arrow]F'] are isomorphic. The resulting equivalence on [[E].sup.<[omega]] is hereditary. Let [??].A(R) be the intersection of the subalgebra of [[??].sup.[[E].sup.<[omega]]] made of invariant maps with the set algebra. This is a graded algebra, the age algebra of Cameron.

The name comes from the fact that this algebra depends only upon the age of R. Indeed, if R' is a relational structure with domain E' such that A(R') = A(R) then [??].A(R') identifies to [??].A(R). To see that, associates first to every indicator function [[chi].sub.S] of an equivalence class S for [equivalent to][sub.R] the indicator function [[chi].sub.S'] of the equivalence class S' for [equivalent to][sub.R'] such that [R.sub.[up arrow]P] is isomorphic to [R'.sub.[up arrow]P'] for some P [member of] S and some P' [member of] S'. Next associate to every linear combination (finite or not) of indicator function the linear combination, with the same coefficients, of their images.

If [[phi].sub.R] takes only integer values, [??].A(R) identifies with the set of (finite) linear combinations of members of A(R). This explain the fact that, in this case, [[phi].sub.R](n) is the dimension of the homogeneous component of degree n of [??].A(R). In a special case, we have

Theorem 3.2. [42] If R has a monomorphic decomposition into finitely many blocks [E.sub.1],..., [E.sub.k], all infinite, then the age algebra [??].A(R) is a polynomial algebra, isomorphic to a subalgebra [??][[[x.sub.1],..., [x.sub.k]].sup.R] of [??][[x.sub.1],..., [x.sub.k]], the algebra of polynomials in the indeterminates [x.sub.1],..., [x.sub.k].

3.2 Behavior of the Profile

In the frame of its age algebra, Cameron gave the following proof of the fact that the profile does not decrease.

Let R be a relational structure on a set E, let e := [[summation].sub.P[member of][[E].sup.1]] P (that we could view as the sum of isomorphic types of the one-element restrictions of R) and U be the subalgebra generated by e. Members of U are of the form [[lambda].sub.m][e.sup.m] + ... + [[lambda].sub.1]e + [[lambda].sub.0]1 where 1 is the isomorphic type of the empty relational structure and [[lambda].sub.m],..., [[lambda].sub.0] are in [??]. Hence U is graded, with [U.sub.n], the homogeneous component of degree n, equals to [??].[e.sup.n].

Theorem 3.3. If R is infinite then for every u [member of] [??].A(R), eu = 0 if and only if u = 0

This innocent looking result implies that [[phi].sub.R] is non decreasing. Indeed, the image of a basis of [??].A[(R).sub.n] by multiplication by [e.sub.m] is an independent subset of [??].A[(R).sub.n+m].

3.3 Finite generation

If a graded algebra A is finitely generated, then, since A is a quotient of the polynomial ring [??][[x.sub.1],..., [x.sub.k]], its Hilbert function is bounded above by a polynomial. In fact, as it is well known, its Hilbert series is a fraction of form P(x)/[(1-x).sup.d], thus of the form given in (2.3) of subsection 2.3. Moreover, one can choose a numerator with non-negative coefficients whenever the algebra is Cohen-Macaulay. Due to Problem 3, one could be tempted to conjecture that these sufficient conditions are necessary in the case of age agebras. Indeed, from Theorem 3.3 one deduces easily:

Theorem 3.4. The profile of R is bounded if and only if [??].A(R) is finitely generated as a module over U. In particular, if one of these equivalent conditions holds, then [??].A(R) is finitely generated

But this case is exceptional. Indeed, on one hand, as we have mentionned in 2.5.6, there are tournaments whose profile has arbitrarily large polynomial growth rate. On an other hand, with N.Thiery we proved:

Theorem 3.5. The age algebra of a tournament is finitely generated if and only if the profile is bounded.

The argument is simple and illustrates the above notions. Let T be a tournament. Suppose that [[phi].sub.T] is bounded, then by Theorem 3.4, [??].A(T) is finitely generated. Conversely, suppose that [??].A(T) is finitely generated. Then, as mentionned in the introduction of this subsection, [[phi].sub.T] is bounded above by a polynomial. Apply Theorem 2.28. Necessarily, T is a lexicographical sum of acyclic tournaments indexed by a finite tournament, a fact that we may write T = [[summation].sub.i[member of]D] [A.sub.i], where each [A.sub.i] is an acyclic tournament and D is a finite tournament. If [[phi].sub.T] is not bounded by a constant then, as one can easily see, D contains a 3-element subset A := {i, j, k} such [D.sub.[up arrow]A] is a cycle and [A.sub.j] and [A.sub.k] are infinite. Pick an element [a.sub.i] [member of] [A.sub.i], set E' := {[a.sub.i]} [union] [A.sub.j] [union] [A.sub.k] and set T' := [T.sub.[up arrow]E'] [member of] Since T' is an induced substructure of T, the algebra [??].A(T') is a quotient of [??].A(T). Thus, with our hypothesis that [??].A(T) is finitely generated, [??].A(T') must be finitely generated too. Let us see that this is not the case. Indeed, notice that if T' is an arbitrary infinite tournament then in the age algebra [??].A(T') we have [e.sup.n] = n!([a.sub.n] + [b.sub.n]) where an is the isomorphic type of an acyclic tournament on n vertices and [b.sub.n] is the sum of isomorphic types of induced subtournaments of T' on n vertices which contain a triangle. It follows then that every element x [member of] [??].A(T') is a sum x := a(x) + u(x) where a(x) is a linear combination of types, each containing a cycle, and u(x) [member of] U. Thus, if [g.sub.1],..., [g.sub.k], 1 generate [??].A(T') then a([g.sub.1]),..., a([g.sub.k]), e generate it also. We apply this fact to our tournament T'. Since T' does not contain two disjoint cycles, we have a([g.sub.i])a([g.sub.j]) = 0 for every 1 [less than or equal to] i, j [less than or equal to] k. Thus, a([g.sub.1]),..., a([g.sub.k]), 1 generate [??].A(T) as a module over U. According to Theorem 3.4, [[phi].sub.T'](n) is bounded. But, A(T') = A([T.sub.2]) where [T.sub.2] is the example given in Item 3 of Examples 2.29. Hence according to the computation given there, [[phi].sub.T'](n) = n - 2 for n [greater than or equal to] 4. This gives a contradiction. Thus [[phi].sub.T] must be bounded by a constant, as claimed.

3.4 The Behavior of the Hilbert Function; a Conjecture of Cameron

Cameron [9] made an important observation about the behavior of the Hilbert fonction.

Theorem 3.6. Let A be a graded algebra over an algebraically closed field of characteristic zero. If A is an integral domain the values of the Hilbert function [h.sub.A] satisfy the inequality

[h.sub.A](n) + [h.sub.A](m) - 1 = [h.sub.A](n + m) (3.2)

for all non-negative integers n and m.

In 1981, he made the conjecture that if R codes a permutation groups with no finite orbits then the age algebra over C is an integral domain [4] (see also [8] p. 86). I solved it positively in 2002 in a slightly more general setting:

Theorem 3.7. Let R be a relational structure with possibly infinitely many non isomorphic types of n-element substructures. If the kernel of R is empty, then [??].A(R) is an integral domain.

Since the kernel of a relational structure R encoding a permutation group G is the union of its finite orbits, if G has no finite orbit, the kernel of R is empty. Thus from this result, [??].A(R) is an integral domain, as conjectured by Cameron.

At the core of the solution is this lemma:

Lemma 3.8. Let m, n be two non negative integers. There is an integer t such that for every set E, every field K with characteristic zero, every pair of maps f : [[E].sup.m] [right arrow] [??], g : [[E].sup.n] [right arrow] [??], if fg(Q) := [[summation].sub.P[member of][[Q].sup.m]] f(P)g(Q \ P) = 0 for every Q [member of] [[E].sup.m+n] but f and g are not identically zero, then f and g are zero on [[E S].sup.m] and [[E \ S].sup.n] where S is a finite subset of E with size at most t

If the age is inexhaustible, then in order to prove that there is no zero divisor, the only part of the lemma we need to apply is the assertion that S is finite.

The fact that S can be bounded independently of f and g, and the value of the least upper bound [tau] (n, m), seem to be of independent interest. The only exact value we know is [tau](1, n) = 2n, a fact which amounts to a weighted version of Theorem 2.5. Our existence proof of [tau](m, n) yields astronomical upper bounds. For example, it gives [tau](2, 2) [less than or equal to] 4[R.sup.2.sub.k](4) + 1, where k := [5.sup.56] and [R.sup.2.sub.k](4) is the Ramsey number equals to the least integer p such that for every colouring of the pairs of {1,..., p} into k colors there are four integers whose all pairs have the same colour. The only lower bound we have is [tau](2, 2) [greater than or equal to] 7 and more generally [tau](m, n) = (m + 1)(n + 1) - 2. We cannot preclude a extremely simple upper bound for [tau](m, n), eg quadratic in n + m.

For example, our 1971 proof of Theorem 2.3 consisted to show that [[phi].sub.R](n) = [[phi].sub.R](n+1) provided that E is large enough, the size of E being bounded by some Ramsey number, whereas, according to Theorem 2.5, 2n + 1 suffices [32].

Our proof of Lemma 3.8 is built on the integrity of the age algebra of infinite multichainable relational structures and Ramsey's theorem. Here is a sketch (details will appear in [43]). We reduce the first part to the integrity of a shuffle algebra. For this, let R be a multichainable relational structure and let V and L, with L infinite, as in 2.4. Consider the vector space over [??] spanned by the words whose letters are non-empty subsets of a finite set V, the shuffle u[??]v of two words u and v being the sum of all words w which are the disjoint union of one occurrence of u and one occurrence of v (eg if V := {a, b} then {a}{b} = {a}{b} + {b}{a} + {a, b}). Using a lexicographical order, one can show that the resulting algebra is an integral domain [44]. This algebra is the age algebra of a relational structure M of a special form: the product of a relational structure on V by an infinite chain L (see subsection 4.5). Since the isomorphic classes of R contain those of M, the age algebra of R is an integral domain.

Next, we consider a pair f, g of maps as in Lemma 3.8, we suppose m [less than or equal to] n and that the subsets S for which the conclusion of the lemma holds are "large" (that is |S| = [mu](m, n) where [mu](m, n) is a number depending on [tau](m, n - 1), [tau](m - 1, n), and r(n + m) := [R.sup.n.sub.k](m + n), where k := [5.sup.s] and s := [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. We observe then that there are at least r(m + n) pairwise disjoint m + n-element subsets [V.sub.0],..., [V.sub.i],..., [V.sub.r(m+n)]-1 of E, each satisfying f([P.sub.i])g([V.sub.i] \ [P.sub.i]) [not equal to] 0 for some [P.sub.i] [member of] [[[V.sub.i]].sup.m]. Supposing that the union E' of these subsets is the product of an m + n element set V by a r(m + n)-element chain L', we encode the action of f and g on E' by a relational structure R' made of a m-uniform hypergraph and a n-uniform hypergraph whose hyperedges are coloured in at most four colors. Dividing the m + n-element subsets of L' into equivalence classes, Ramsey's theorem provides a m + n-element subchain L" such that the isomorphic classes of [R'.sub.|VxL"] contains those of the product of V by L". From the fact that the shuffle algebra built on V is an integral domain we deduce that either the restriction of f to [[V x L"].sup.m] or the restriction of g to [[V x L"].sup.n] vanishes. But this is not the case. Hence S cannot be large.

3.5 Initial segments of an age and ideals of a ring

As stated in Theorem 2.12, if the profile of a relational structure R, with bounded signature or finite kernel, has a polynomial growth, then it is almost multichainable. As we will see in Theorem 4.19, if a relational structure R is almost multichainable, its age A(R), ordered by embeddability, is well-quasi-ordered, that is every final segment of A(R) is finitely generated, which amounts to the fact that the collection F(A(R)) of final segments of A(R) is noetherian, w.r.t. the inclusion order (see subsection 4.3). Final segments play for posets the same role than ideals for rings. Noticing that an age algebra is finitely generated if and only if it is noetherian, we are lead to have a closer look at the relationship between the basic objects of the theory of relations and of ring theory, particularly ages and ideals.

We mention the following result which will be incorporated into a joint paper with N.Thiery.

Proposition 3.9. Let A be the age of a relational structure R such that the profile of R takes only finite values and [??].A be its age algebra. If A' is an initial segment of A then:

(i) The vector subspace J := [??].(A\A') spanned by A\A' is an ideal of [??].A. Moreover, the quotient of [??].A by J is a ring isomorphic to the ring [??].A'.

(ii) If this ideal is irreducible then A' is a subage of A.

(iii) This is a prime ideal if and only if A' is an inexhaustible age.

The proof of Item (i) and Item (ii) are immediate. The proof of Item (iii) is essentially based on Theorem 3.7.

According to Item (i), F(A) embeds into the collection of ideals of [??].A). Consequently:

Corollary 3.10. If an age algebra is finitely generated then the age is well-quasi-ordered by embeddability.

Problem 8. How the finite generation of an age algebra translates in terms of embeddability between members of the age?

4 Tools for Classifying Profiles

Beside graded algebras, Hilbert series and rudimentary algebraic geometry, the tools we use to classify profiles can be divided into the following categories:

--Orders, well-founded orders, well-quasi-orders;

--Ramsey Theorem;

--Compactness theorem;

--Combinatorial properties of the kernel.

In this section, we show the role of these tools in the proof of Theorem 2.6 and Theorem 2.12. For reader convenience, we record in the first subsection below some notions and notations we are using in this paper.

4.1 Basic Notions, Relational Structures, Embeddability and Ages

We use standard set-theoretical notations. If E is a set, |E| denotes its cardinality. If n is an integer, [[E].sup.n] denotes the set of n-element subsets of E; whereas [E.sup.n] denotes the set of n-tuples of elements of E. An n-ary relation on E is any subset n of [E.sup.n]. As said in subsection 2.1, a pair R := (E, [([[rho].sub.i]).sub.i[member of]I]) made of a set E and of a family of mi-ary relations [[rho].sub.i] on E is a relational structure of signature [mu] := [([m.sub.i]).sub.i[member of]I]. If I' is a subset of I, the relational structure [R.sup.I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) is a reduct of R.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) and R' := (E', [([[rho]'.sub.i).sub.i[member of]I]) be two relational structures of the same signature [mu] := [([m.sub.i]).sub.i[member of]I].

A map f : E [right arrow] E' is an isomorphism from R onto R' if

1. f is bijective,

2. ([x.sub.1],..., [x.sub.[m.sub.i]]) [member of] [[rho].sub.i] if and only if (f ([x.sub.1]),..., f([x.sub.[m.sub.i]])) [member of] [[rho]'.sub.i] for every ([x.sub.1],..., [x.sub.[m.sub.i]]) [member of] [E.sup.[m.sub.i]], i [member of] I.

A map f from a subset A of E onto a subset A' of E' is a local isomorphism or a local embedding of R into R' if f is an isomorphism from [R.sub.[up arrow]A] onto [R'.sub.[up arrow]A']. If A = E, this is an embedding from R into R'.

We say that R is isomorphic, resp. embeddable, to R', resp. into R', and we write R [congruent to] R', resp. R [less than or equal to] R', if there is an isomorphism, resp. an embedding, from R onto R', resp. into R'. Clearly, R is embeddable into R' if and only if R is isomorphic to some restriction of R'. To each relational structure R one may associate an isomorphic type [tau](R), in such a way that R [congruent to] R' if and only if [tau](R) = [tau](R'). The collection of isomorphic types of finite relational structures of signature [mu] is a set, that we denote [[OMEGA].sub.[mu]]. The embeddability relation is a quasi-order on the class of relational structures of signature [mu]. It induces a quasi-order on the class of their isomorphic types. On the set [[OMEGA].sub.[mu]] this is an ordering.

The age of a relational structure R is the set A(R) of isomorphic types of the restrictions of R to the finite subsets of its domain.

Ages can be (almost) characterized in terms of ordered sets (posets). Let us recall that if P is a poset, an initial segment of P is a subset I such that x [member of] P, y [member of] I and x [less than or equal to] y imply x [member of] I. An ideal is a non-empty initial segment which is up-directed, that is x, y [member of] I imply x, y [less than or equal to] z for some z [member of] I.

The following characterization is essentially due to R. Fraisse 1954 (see [14]).

Lemma 4.1. a) Let R be a relational structure of arity [mu] and size [kappa], then A(R), the age of R, is an ideal of [[OMEGA].sub.[mu]], whose size is at most e if [kappa] is infinite and [2.sup.[kappa]] otherwise; b) Conversely, let C be an ideal of [[OMEGA].sub.[mu]]; if C is countable, then C is the of age a countable [mu]-ary relational structure.

In particular:

c) If [mu] is finite, then a subset C of [[OMEGA].sub.[mu]] is the age of a [mu]-ary relational structure if and only if C is an ideal of [[OMEGA].sub.[mu]].

The equivalence stated in c) does not hold without some condition on [mu]. An example was obtained with C. Delhomme and mentionned in [40], see [11] for other examples and further developments.

Still, [[OMEGA].sub.[mu]] is an age -and the largest one. As a poset, it decomposes into levels, the levels of a poset P being defined inductively by the formula [P.sub.n] := Min(P \ [union]{[P.sub.n'] : n' < n}). The n-th level is the set of isomorphic types of relational structures on n elements. The same holds for the age of a relational structure R, hence the profile [[phi].sub.R](n) is simply the function which assign to each n the number of elements of the n-th level of A(R) (in the general theory of posets, the numbers of elements of the levels of a poset P are the Whitney numbers- of the second kind- of P). In the study of their growth, we have only to consider profiles taking finite values. Hence, according to the above characterization, our study is about ideals of [[OMEGA].sub.[mu]], each one with finite levels. A characterization in order-theoretical terms, of these ideals eludes us, the study of the profile is just a bare approach.

4.2 The Height Function on a Well-Founded Poset, the Height of an age and its Relation with the Profile

Let P be a poset; P is well-founded if every non-empty subset A of P contains some minimal element a (that is there is no b [member of] A with b < a). The height function on a poset P associates to an element x [member of] P an ordinal number h(x, P) is such a way that:

h(x, P) := Sup{h(y, P) + 1 : y < x}

The ordinal h(x, P) is the height of x in P.

With this definition, h(x, P) = 0 if and only if x is minimal in P; also h(x, P) is defined if and only if [down arrow] x := {y [less than or equal to] P : y [less than or equal to] x} is well-founded.

Let A be an ideal of [[OMEGA].sub.[mu]] and let J(A) be the set of ideals included into A. The height of A, denoted by H(A), is the height of A in J(A). With this definition, H(A) = n with n < [omega], if and only if A = A(R) for some R on n elements. Furthermore, H(A) = [omega] if and only if A is infinite and every ideal properly included into A is finite.

The characterization of ideals of height is given by the following result:

Theorem 4.2 ([37]). Let A be an ideal of [[OMEGA].sub.[mu]]. Then the following properties are equivalent:

(i) H(A) = [omega].

(ii) A is the age of an infinite monomorphic relational structure R (that is [[phi].sub.R](n) = 1 for all n).

(iii) A is the age of an infinite chainable relational structure.

The essential part is the implication (i) [??] (iii). For that, observe that A is countable. Hence, from Lemma 4.1 b), A is the age of some countable relational structure R. From Theorem 2.23 and Compactness theorem of first order logic, R is chainable.

This generalizes:

Theorem 4.3 ([37]). Let A be an ideal of [[OMEGA].sub.[mu]]. Then the following properties are equivalent:

(i) H(A) = [omega] + p, for some p < [omega].

(ii) A is the age of an infinite relational structure with a bounded profile.

(iii) A is the age of an infinite almost chainable relational structure.

This result opens the road for proving Theorem 2.6. Indeed, as it will appear at the end of this section:

Theorem 4.4. If R has a finite kernel then the growth of [[phi].sub.R] is polynomial of degree k if and only if A(R) has an height and H(A(R)) = [omega](k + 1) + p for some integer p.

At this point, we are still far away of a proof. More tools are needed.

4.3 Well-Quasi-Ordering, Higman Theorems, Very-Well-Quasi-Ordered Classes

A poset P is well-quasi-ordered, in brief w.q.o., if every non-empty subset contains finitely many minimal elements(this number being non-zero). A final segment F of a poset P is finitely generated if for some finite subset K of P, F equals the set [up arrow] K := {y [member of] P : x [less than or equal to] y for some x [member of] K}.

A basic result due to Higman [21] is the following.

Theorem 4.5. For a poset P, the following properties are equivalent:

1. P is w.q.o.

2. P contains no infinite strictly descending chain and no infinite antichain.

3. Every final segment of P is finitely generated.

4. The set I (P) ordered by inclusion and made of initial segments of P is well-founded.

Corollary 4.6. If an ideal A of [[OMEGA].sub.[mu]] is w.q.o. then J(A) is well-founded, hence H(A) is defined.

Non-w.q.o posets for which the collection of ideals is well-founded abund. Not a single example of non-w.q.o age whose the collection of subages is well-founded as been discovered yet.

With Zorn lemma, one may observe that if a poset P is not w.q.o. it contains some final segment F which is not finitely generated and maximal w.r.t. inclusion. If follows that its complement P \ F is w.q.o.

This fact applies nicely to [[OMEGA].sub.[mu]]. For that, let us mention that a bound of a relational structure R is any relational structure S on a finite set F such that S does not embed into R but [S.sub.-x] := [S.sub.[up arrow]F\{x}] embeds into R for every x [member of] F. A bound of an initial segment C of [[OMEGA].sub.[mu]] is any minimal element of [[OMEGA].sub.[mu]] \ C. Clearly, the bounds of A(R) are the isomorphic types of the bounds of R.

Lemma 4.7. If an initial segment C of [[OMEGA].sub.[mu]] is level finite and is not w.q.o., then it contains an ideal which has infinitely many bounds in C.

Let us recall that a word is a finite sequence of letters and that a word u is a subword of a word w if u can be obtained from w by erasing some letters of w. We have the following theorem of Higman [21].

Theorem 4.8. The set [A.sup.*] made of words on a finite alphabet A is w.q.o. with respect to the subword ordering.

A class C of relational structures is very-well-quasi-ordered, in short v.w.q.o., if for every integer m the class [C.sub.m] made of R [member of] C added of m unary relations is w.q.o for the embeddability relation We will need the following result.

Theorem 4.9. Let C be a class of finite relational structures, then:

1. C is v.w.q.o iff [down arrow] C, its downward closure, is v.w.q.o.

2. If [down arrow] C is v.w.q.o. then all the ages it contains are almost inexhaustible.

3. If [down arrow] C is v.w.q.o. and all of its members have the same finite signature [mu] then it has only finitely many bounds [31].

An other important result on w.q.o. is this (see [50] for the first part, [10] for the second). Theorem 4.10. If a poset P is w.q.o. then all the linear extensions of P are well-ordered and there is one having the largest possible order type.

This largest order type, denoted [tau](P), is the ordinal length of P.

Lemma 4.11 ([10]). If A is an alphabet made of k letters then [tau]([A.sub.*) = [[omega].sup.[[omega].sup.k-1]].

The computation for ages (see [41], [49]) yields:

Theorem 4.12. If J(A(R)) is w.q.o then [tau](A(R)) = [[omega].sup.a] x q where [alpha] is such that [omega] x [alpha] [less than or equal to] H(A(R)) < [omega] x ([alpha] + 1) and q is the number of ages included into A(R) whose height is between [omega] x [alpha] and [omega] x ([alpha] + 1).

4.4 Kernel, Almost Inexhaustibility, Height and Profile

Most of the properties of the kernel (defined in subsection 2.2.2)are based on the following simple lemma (see [34] for finite signature and 3 of Lemma 2.12 of [40] for the general case).

Lemma 4.13. A([R.sub.[up arrow]E\{a}]) = A(R) [??] A([R.sub.[up arrow]E\{a,b}]) = A([R.sub.[up arrow]E\{b}]) for all a, b [member of] E

From this lemma, one immediately gets the following:

Corollary 4.14. A relational structure R has an empty kernel if and only if its age A(R) has the disjoint embedding property.

Instead of saying that an age has the disjoint embedding property, we say that it is inexhaustible. We say that a relational structure R is age-inexhaustible if K(R) is empty and almost age-inexhaustible if K(R) is finite.

Lemma 4.15. Let A be an infinite inexhaustible age. Then:

1. For every age A' included into A there is an infinite strictly increasing sequence of ages included into A such that

A' = [A.sub.0] [subset] ... [subset] [A.sub.n] [sunset] ...

2. The height of A, is a limit ordinal, provided that it is defined.

See Proposition 4.7 of [40]. Notice that the converse of (2) does not hold in general, a fact which causes some complications.

The relationship between almost inexhaustibility and inexhaustibility is based upon properties of reductions.

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure and F be a subset of E. A reduction of R over F is a relational structure M := (E \ F, [([[tau].sub.j).sub.j[member of]J]) such that the local automorphisms of M are precisely the restrictions of local isomorphisms of R fixing F pointwise.

Lemma 4.16. Let R be a relational structure, K(R) be its kernel, r := |K(R)|, and M be a reduction of R over K(R). If K(R) is finite then:

1. K(M) is empty.

2. H(A(R)) = H(A(M)) + p, for some integer p, if and only if one of these heights exists.

3. [[phi].sub.R](n) [less than or equal to] [2.sup.r] [[phi].sub.S](n) and [[phi].sub.S](n) = a[[phi].sub.R](n + k) for some a [member of] [[??].sup.*.sub.+], k [member of] [??], and all n [member of] [??].

Item 1 is special case of Theorem 20 [19]. Item 2 is a special case of Theorem 4.6 of [40]. Item 3 can be proved in the same way as Theorem 21 of [19].

The growth of a map [phi] : [??] [right arrow] [??] is invariant under translation if [phi] and its translate n [right arrow] [phi](n+1) have the same growth. In this case, [phi] is bounded by an exponential function. Clearly, polynomial functions are invariant under translation. Under the hypotheses of Lemma 4.16 we get from Item (3):

Corollary 4.17. [[phi].sub.R] is bounded by a polynomial of degree k, resp. has polynomial growth of degree k, iff [[phi].sub.M] is bounded by a polynomial of degree k, resp. has polynomial growth of degree k.

This tells us that in order to prove that the growth of the profile of a relational structure with finite kernel is polynomial it suffices to prove that the growth of a reduction over its kernel is polynomial.

4.5 Product of a Finite Relational Structure by a Chain

Let S := (V, [([[rho].sub.i]).sub.i[member of]I]) be a relational structure of signature [mu] and L := (D, [less than or equal to]) be a chain. A relational structure R of signature [mu] is a product of S and L, denoted by S [crosss product] L, if it satisfies the following conditions.

(a) The domain is V x D.

(b) For every y [member of] D, the map x [right arow] (x, y) is an isomorphism from S into R.

(c) For each local isomorphism f of L, the map ([1.sub.V], f) which to (x, y) associates (x, f(y)) is a local isomorphism of R.

If |V| = 1, this reduces to say that every local isomorphism of L is a local isomorphism of R. As we have said, a relational structure is chainable if there is such a chain defined on its domain.

In this context, a relational structure is almost multichainable, resp. almost chainable, if its kernel is finite and a reduction over its kernel is a multiple of a finite, resp. a one-element, relational structure by a chain.

A relational structure M freely interprets a relational structure R on the same set if each local isomorphism of M is a local isomorphism of R. Clearly, if a relational structure M is almost multichainable, every relational structure freely interpretable by M has the same property. In fact, an almost multichainable relational structure is freely interpretable by an almost multichainable relational structure of a special form:

Let R := (E, [([[rho].sub.i]).sub.i[member of]I]) be an almost multichainable relational structure; let F and V be two finite sets, L := (D, [less than or equal to]) be a chain such that E = F [union] V x D and every local isomorphism of f extended by the identity on F and D induces a local isomorphism of R. Let r := |F|, m := |V|, [a.sub.1],..., [a.sub.r], resp. [v.sub.1],..., [v.sub.m], be an enumeration of the members of F, resp. of V. Set M := (E, [A.sub.1],..., [A.sub.r], [V.sub.1],... [V.sub.m], Eq, W) be the relational structure in which [A.sub.1],..., [A.sub.r] and [V.sub.1],..., [V.sub.m] are unary relations, [A.sub.i] := {[a.sub.i]} for i = 1,..., r, [V.sub.i] := {i} x D, Eq is an equivalence relation defined by (u, v) [member of] Eq if either u = v or u = (x, y) and v = (x', y), W is an order defined by (u, v) [member of] W if either u = v or u = (x, y), v = (x', y') and y < y' in L.

Clearly, M interprets R. This relational structure has a finite signature. The fact that an almost multichainable relational structures is freely-interpretable by a relational structure with finite signature allows to use the compactness theorem of first order logic. This yields:

Proposition 4.18. If a relational structure R is almost multichainable then every relational structure R' such that A(R') [[subset].bar] A(R) is also almost multichainable.

Proof. Let M as above which interprets freely R. If some relational structure R' verifies A(R') [[subset].bar] A(R) then, since the signature of M is finite, the compactness theorem yields some relational structure M' such that A(M') [[subset].bar] A(M) and M' interprets freely R'. The multirelation M is almost multichainable. It is easy to see that M' is almost multichainable too. Hence R' is almost multichainable too. '

Theorem 4.19. Let A be the age of an almost multichainable relational structure. Then:

1. A is very well-quasi-ordered;

2. H(A) < [[omega].sup.[omega]].

Proof. Let R such that A(R) = A. Let R' be a reduction over K(R). Then R' is the product S [cross prodcuct] L of a finite relational structure S by a chain L. Let V be the domain of S, m := |V|, D be the domain of L and M be the multirelation interpreting R'.

(1) In order to prove that A is v.w.q.o. it suffices to prove that A(M) is v.w.q.o. For that, we consider the alphabet A whose letters are the non-empty subsets of V (that is A = [??](V) \ {[empty set]}). We order A by inclusion; we extend this order to an order, compatible with the concatenation of words, on [A.sup.*], the set of words over A. With this ordering [A.sup.*] is isomorphic to A(M). Thus from Theorem 4.8, A(M) is w.q.o. and in fact v.w.q.o.

(2) Since M interprets R' we have [tau](A(R')) [less than or equal to] [tau](A(M)). We also have [tau](A(M)) [less than or equal to] o([A.sup.*]) and, since |A| = [2.sup.m] - 1, we have o([A.sup.*]) = [[omega].sup.[[omega].sup.[2.sup.m]- 2]] from Lemma 4.11. Thus, o(R') [less than or equal to] [[omega].sup.[[omega].sup.[2.sup.m]-2]]. Theorem 4.12 yields H(A(R')) [less than or equal to] [[omega].sup.[2.sup.m]-1]. From this inequality, Lemma 4.16 yields H(A) < [[omega].sup.[2.sup.m]-1] + [omega].

Combining (1) of Theorem 4.19 and (3) of Theorem 4.9, we get:

Theorem 4.20. An almost multichainable relational structure having a finite signature has only finitely many bounds.

For the special case of chainable relations this conclusion was obtained by C.Frasnay in 1965 [17] by means of his theory of indicative groups. Atruly reamarkable consequence also due to Frasnay is that for every integer m there is an integer f (m) such that a monomorphic relational structure with signature bounded by m and size at least f (m) is chainable (see Chapter 13 of [14]).

Lemma 4.21 ([34]). Let R' be a relational structure and L be a chain with at least two elements. Then the kernel of R' is empty if and only if there is a product R" := R' [cross product] L such that A(R") = A(R').

Corollary 4.22. The age A of a denumerable relational structure with empty kernel is the union of an infinite sequence

[A.sub.0] [[subset].bar] [A.sub.1] [[subset].bar] ... [[subset].bar] [A.sub.n] [[subset].bar] ...

where each [A.sub.n] is the age of a product of some S [member of] [A.sub.n] by an infinite chain.

Proof. Let R' be a denumerable relational structure such that A(R') = A and L be an infinite chain. According to Lemma 4.21, there is a product R" := R' [cross product] L such that A(R") = A. Let [F.sub.0] [[subset].bar] ... [[subset].bar] [F.sub.n] [[subset].bar] ... be an non-decreasing sequence of finite subsets of the domain E' of R' whose union is E'. Let [R".sub.n] := [R".sub.[up arrow][F.sub.n]xL] and [A.sub.n] := A([R".sub.n]) for n [member of] [??]. The sequence [A.sub.n],..., [A.sub.n],.... is non-decreasing and A = [[union].sub.n[member of]N] [A.sub.n].

Proposition 4.23. If the age A of a denumerable relational structure is inexhaustible then

--Either A is the age of a multichainable relational structure and H(A) < [[omega].sup.2].

--Or for every integer k, A contains the age [A.sub.k] of an almost multichainable relational structure such that H([A.sub.k]) = [omega].(k + 1).

Proof.

Claim. Either A is the age of a multichainable relational structure or for every integer k it contains the age [A.sub.k] of a multichainable relational structure such that H([A.sub.k]) [greater than or equal to] [omega].(k + 1). Proof of the claim. Apply Corollary 4.22. If the sequence

[A.sub.0] [[subset].bar] [A.sub.1] [[subset].bar] ... [[subset].bar] [A.sub.n] [[subset].bar] ...

is eventually constant, then A = [A.sub.[n.sub.0]] for some non-negative integer [n.sub.0]. Let [S.sub.[n.sub.0]] := [R'.sub.[up arrow][F.sub.[n.sub.0]]] and R := [R".sub.[n.sub.0] = [R".sub.[up arrow][F.sub.[n.sub.0]]xL]. Then R is a product of [S.sub.[n.sub.0]] by L. If this sequence is not eventually constant, it contains an infinite subsequence which is strictly increasing, say:

[A.sub.[n.sub.0]] [subset] ... [subset] [A.sub.[n.sub.i]] [subset] ...

Since [R".sub.[n.sub.i]] is a product of product of [S.sub.[n.sub.i]] by L, its kernel is empty, that is [A.sub.[n.sub.i]] is inexhaustible. Hence, from (1) of Lemma 4.15 there is a strictly increasing sequence of ages between [A.sub.[n.sub.k-1]] and [A.sub.[n.sub.k]]. Since [R".sub.[n.sub.i]] is multichainable, [A.sub.[n.sub.k]] has an height. It follows that H([A.sub.[n.sub.k]]) [greater than or equal to] [omega].(k + 1).

Now, suppose that A is the age of a multichainable relational structure. Then H(A) is defined. If H(A) < [[omega].sup.2], the conclusion of the proposition holds. If H(A) [greater than or equal to] [[omega].sup.2], then for every k, A contains an age [A.sub.k] of height [omega].(k + 1). According to Proposition 4.18, [A.sub.k] is the age of an almost multichainable relational structure. Suppose that A is not the age of a multichainable relational structure. Let k be an integer. According to our claim, A contains the age [A.sub.k] of an almost multichainable relational structure such that H([A.sub.k]) = [omega].(k + 1). Let A' [[subset].bar] [A.sub.k] be an age of height [omega].(k + 1). According to Proposition 4.18, A is the age of an almost multichainable relational structure. This proves the proposition.

For relational structures with finite signature we have a similar result with a more intricate proof.

Theorem 4.24. Let A be the age of infinite relational structure R with finite signature.

1. If H(A) < [[omega].sup.2] then R is an almost multiple of a finite relation by a chain; in particular, R has a finite kernel.

2. If A has no height then A contains some age of height [[omega].sup.2] (and, in fact, ages of height [[omega].sup.2] + p for every integer p).

The proof is given below for relational structures made of binary or unary relations; beyond, the proof is quite involved.

Proof. (1)We argue by induction on the height. Let [alpha], [omega] [less than or equal to] [alpha] < [[omega].sup.2]. Suppose that Property (1) holds for every age A such that [omega] [less than or equal to] H(A) < [alpha]. Let A be an age with H(A) = [alpha].

Let R such that A(R) = A. First, K(R), the kernel of R, is finite. Indeed, let x [member of] K(R). We have A([R.sub.-x]) [??] A. Hence, from the induction hypothesis, A([R.sub.-x]) is the age of an almost multiple of a finite relation by a chain. According to Theorem 4.19, A([R.sub.-x]) is very well-quasi-ordered. Since R is made of binary and unary relations, it follows that A(R) is very-well-quasi-ordered too. From (2) of Theorem 4.9, K(R) is finite. Let R' be a reduction of R over K(R). Let n, p < [omega] such that [alpha] = [omega]n + p. According to (2) of Lemma 4.16, we have H(A(R')) = [omega]n and K(R') = [empty set]. Apply Proposition 4.23.

(2)If A has no height then A is not w.q.o., hence it contains some age A' which is w.q.o. and has infinitely many bounds in A (Lemma 4.7). Being w.q.o., A' has an height. If H(A') < [[omega].sup.2], then from (1) A' is the age of an almost multiple of a finite relation by a chain, hence is v.w.q.o. But according to (3) of Theorem 4.9, it cannot have infinitely many bounds, a contradiction. Hence H(A') [greater than or equal to] [[omega].sup.2].

4.6 Profile of Almost Multichainable Relational Structures

Let A be the age of a product R := S [cross product] L with S := (V , [([[rho].sub.i]).sub.i[member of]I]) [member of] A. Let J be a non-empty initial segment of [??](V). Let [F.sub.J]:= {F [member of] [[V x E].sup.<[omega]] : [F.sup.-1](y) [member of] J for every y [member of] E}. Let [A.sub.J] := {[tau]([S.sub.[up arow]F]) : F [member of] [F.sub.J]}.

Lemma 4.25. (i) The age AJ is inexhaustible.

(ii) [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.];

(iii) [A.sub.[??](V)] = A.

Let J be a non-empty initial segment of [??](V) which is minimal w.r.t. inclusion such that [A.sub.J] = A. Let V' be a maximal element of J [member of] Let m' := |V'| and J' := J {V'}. Note that if J' = [empty set] then A is the age of a chainable relation, in which case its profile is 1.

Given an integer p, let [A.sub.p] := {[tau]([S.sub.[up arrow]F]) : F [member of] [F.sub.J] and |{i : [F.sup.-1](i) = V'}| [less than or equal to] p}.

Lemma 4.26. 1. [A.sub.p] is an age for every p < [omega].

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

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

4. [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.].

5. If [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. In other words, if [p.sub.0] is minimum such that [A.sub.[p.sub.0]] [not equal to] [A.sub.0] then [A.sub.p] [??] [A.sub.p+1] for every p [greater than or equal to] [p.sub.0].

6. For each p [greater than or equal to] [p.sub.0], the kernel of any relation with age [A.sub.p] has m'.p elements.

Proof. Sketch. We may suppose that L is the chain [??] of rational numbers. In the product V x [??], we select a subset X made of "slices" F x {r} with F [member of] J and r [member of] [??], in such a way that between two rational all possible slices appear. Obviously A([R.sub.[up arrow]X]) = A. Let [X.sub.p] obtained by deleting from X all slices of the form V' x {r} except p such slices. Then A([R.sub.[up arrow][X.sub.p]]) = [A.sub.p]. To obtain that, for p larger than some non-negative integer [p.sub.0], K([R.sub.[up arrow][X.sub.p]]) is made of these p slices, apply Lemma 4.13.

Lemma 4.27. Let A be the age of a product R := S [cross product] L with S := (V , [([[rho].sub.i]).sub.i[member of]I]) [member of] A. If H(A) = [omega](k + 1) then [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. for every integer n.

Proof. Induction on k. We apply Lemma 4.26. For p < [omega], we denote by [R.sub.p] a relational structure with age [A.sub.p], by [R'.sub.p] a reduction over its kernel and by [A'.sub.p] its age. We have :

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] ...

Set

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

that is

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

With Pascal identity this yields:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

According to (1) of Lemma 4.16 we have H([A.sub.p]) = H([A'.sub.p]) + [n.sub.p] for some [n.sub.p] < [omega] Hence H([A'.sub.p]) [less than or equal to] [omega]k. Via the inductive hypothesis, [[phi].sub.[R'.sub.p]](n) [less than or equal to] [[phi].sub.[omega]k](n) for every n and every p. This yields:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

We get the following result mentioned in the introduction.

Theorem 4.28. If the age A of a denumerable relational structure R is inexhaustible and its height H(A) is at most [omega](k + 1) then [[phi].sub.R](n) [less than or equal to] [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every integer n.

Proof. We have [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]. Since A is inexhaustible, (1) of Lemma 4.16 tells us that p = 0. According to Proposition 4.23 there is some R having age A which is a product of some S [member of] A by a chain. According to Lemma 4.27, [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.] for every integer n. Since [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.], the desired conclusion follows.

Lemma 4.29. Let A be the age of a product R := S [cross product] L with S := (V, [([[rho].sub.i]).sub.i[member of]I]) [member of] A. If H(A) = [omega](k + 1) then [[phi].sub.R] grows at least as a polynomial of degree k.

For the proof of this counterpart of Lemma 4.27 fix an increasing sequence [([A.sub.i]).sub.i[less than or equal to]k] of sub-ages of A such that H([A.sub.i]) = [omega].(i + 1). Then show that increasing sequences [([T.sub.i]).sub.i[less than or equal to]k], [T.sub.i] [member of] [A.sub.i] \ [A.sub.i-1], |[T.sub.k]| = n, yields O([n.sup.k]) distinct types. With this we obtain:

Theorem 4.30. Let R := (E, [([[rho].sub.i]).sub.i[member of]I])) be a relational structure. If the signature of R is bounded or R has a finite kernel then either R is almost multichainable and H(A(R)) = [omega](k + 1) + p -in which case [[phi].sub.R] grows as a polynomial of degree k- or [[phi].sub.R] grows faster than every polynomial.

Proof. Suppose that the kernel K(R) of R is finite. Let R' be a reduction over K(R). If A(R') has an height, then according to (2) of Lemma 4.16, A(R) too and H(A(R)) = H(A(R')) + p for some non-negative integer p. If H(A(R')) = [omega](k + 1) < [[omega].sup.2], then R' is multichainable (Proposition 4.23), hence R is almost multichainable, and [[phi]'.sub.R] grows as a polynomial of degree k (Lemma 4.27 and Lemma 4.29). According to Corollary 4.17, [[phi].sub.R] grows as a polynomial of degree k too. If A(R') has no height or contains an age of height [[omega].sup.2], then for every non-negative integer k it contains the age of an almost multichainable relational structure of height [omega](k + 1) (Proposition 4.23). Hence, according to Lemma 4.29, [[omega].sub.R'] grows faster than every polynomial and, via Corollary 4.17, [[phi].sub.R] too. If K(R) is infinite, then, with our hypothesis, the signature is bounded. Suppose that I is finite. It follows from Theorem 4.24 that A(R) contains ages of height [omega](k + 1) for every non negative integer k, hence [[phi].sub.R] grows faster than every polynomial. If I is infinite, then since the signature is bounded by some integer m, there is some finite subset I' such that the reduct [R.sup.[up arrow]I'] := (E, [([[rho].sub.i]).sub.i[member of]I']) has the same profile as [[phi].sub.R] (Fact 2), thus this case reduces to the previous one.

Theorem 2.6, Theorem 2.12 and Theorem 4.4 are immediate consequences of this result. In the case of a relational structure with empty kernel, Theorem 4.4 has a more precise form. With the help of Lemma 4.27 we get the following result announced in [35]:

Theorem 4.31. If the age of a relational structure R is inexhaustible and [[phi].sub.R] has polynomial growth of degree k then

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

for every integer n.

We conclude this tour with the following:

Problem 9. Is the profile of a relational structure R bounded by some exponential whenever the age of R is very-well-quasi-ordered under embeddability?

* Dedicated to Roland Fraisse, at the occasion of his 86th birthday.

(1) In order to agree with the Fraisse's terminology, we disagree with the terminology of our papers, in which inexhaustibility, resp. almost inexhaustibility, is used for relational structures with empty, resp. finite, kernel, rather than for their ages.

References

[1] J. Berstel, C. Retenauer, Les series rationnelles et leurs langages. Etudes et recherches en Informatique. Masson, Paris, 1984, 132 pp.

[2] Y. Boudabbous, M. Pouzet, The morphology of infinite tournaments. Application to the growth of their profile. Oct. 2005, Revised Nov. 2006. 20 pp.

[3] P.J. Cameron, Transitivity of permutation groups on unordered sets, Math. Z. 48 (1976), pp. 127-139.

[4] P.J. Cameron, Orbits of permutation groups on unordered sets. II. J. London Math. Soc. 23(2) (1981), pp. 249-264.

[5] P.J. Cameron, Oligomorphic permutation groups. Cambridge University Press, Cambridge, 1990.

[6] P.J. Cameron, The algebra of an age. In Model theory of groups and automorphism groups (Blaubeuren, 1995), pages 126-133. Cambridge Univ. Press, Cambridge, 1997.

[7] P.J. Cameron, Sequences realized by oligomorphic permutation groups. J. Integer Seq. 3(1), Article 00.1.5, 1 HTML document (electronic), 2000.

[8] P.J. Cameron, Some counting problems related to permutation groups. Discrete Math. 225(1-3) (2000), pp. 77-92. Formal power series and algebraic combinatorics (Toronto, ON, 1998).

[9] P.J. Cameron, On an algebra related to orbit-counting. J. Group Theory 1(2) (1998), pp. 173-179.

[10] D.H.J. de Jongh and R. Parikh, Well-partial orderings and hierarchies. Nederl. Akad. Wetensch. Proc. Ser. A 80=Indag. Math. 39(3) (1977), pp. 195-207.

[11] C. Delhomme, M. Pouzet, N. Sauer, G. Sagi, Representation of ideals of relational structures, preprint, Calgary, July 2006, 18pp. http://arxiv.org/math.CO/0607725

[12] R. Fraisse, Sur quelques classifications des systemes de relations, These, Paris (1953), Alger-Math. 1 (1954), pp. 35-182.

[13] R. Fraisse, Sur l'extension aux relations de quelques proprietes des ordres, Ann. Sci. Ecole Norm. Sup. 71 (1954), pp. 361-388.

[14] R. Fraisse, Theory of relations. Second edition, North-Holland Publishing Co., Amsterdam, 2000.

[15] R. Fraisse and M. Pouzet, Interpretabilite d'une relation pour une chaine. C. R. Acad. Sci. Paris Ser. A-B 272 (1971), pp. 1624-1627.

[16] R. Fraisse, Cours de logique mathematique. Tome 1: Relation et formule logique. Gauthier-Villars Editeur, Paris, 1971.

[17] C. Frasnay, Quelques problemes combinatoires concernant les ordres totaux et les relations monomorphes. These. Paris. Annales Institut Fourier Grenoble 15 (1965), pp. 415-524.

[18] A.M. Garsia and N.Wallach, Qsym over Sym is free. J. of Comb. Theory, Series A 104 (2003), pp. 217-263.

[19] P. Gibson, M. Pouzet, and R. Woodrow, Relational Structures Having Finitely Many Full-cardinality Restrictions. Discrete Mathematics 291 (2005), pp. 115-134.

[20] D.H. Gottlieb, A class of incidence matrices, Proc. Amer. Math. Soc. 17 (1966), pp. 1233-1237.

[21] G. Higman, Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) (1952), pp. 326-336.

[22] I.M. Hodkinson, H.D. Macpherson, Relational structures determined by their finite induced substructures. J. Symbolic Logic 53(1) (1988), pp. 222-230.

[23] W.M. Kantor, On incidence matrices of finite projective and affine spaces, Math. Z. 124 (1972), pp. 315-318.

[24] J.B. Kruskal, The theory of well-quasi-ordering: a frequently discovered concept. J. Com. Th. 13 (1972), pp. 297-305.

[25] D. Livingstone, A. Wagner, Transitivity of finite permutation groups on unordered sets. Math. Z. 90 (1965), pp. 393-403.

[26] M. Lothaire, Combinatorics on words. Vol. 17 of Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, Mass. Reprinted in the Cambridge Mathematical Library, Cambridge University Press, U.K. 1997.

[27] H.D. Macpherson, Growth rates in infinite graphs and permutation groups. J. London Math. Soc. 35(2) (1987), pp. 276-286.

[28] H.D. Macpherson, Permutation groups of rapid growth. Proc. London Math. Soc. 51(2) (1985), pp. 285-294.

[29] H.D. Macpherson, M. Pouzet, and R.E.Woodrow, Countable structures of a given age. The Journal of Symbolic Logic 57 (1992), pp. 992-1010.

[30] E.C. Milner, Basic wqo- and bqo-theory. In Graphs and order, I.Rival Ed. (Banff, Alta., 1984), pages 487-502. Reidel, Dordrecht, 1985.

[31] M. Pouzet, Un belordre d'abritement et ses rapports avec les bornes d'une multirelation. Comptes rendus Acad. Sci. Paris 274(A) (1972), pp. 1677-1680.

[32] M. Pouzet, Application d'une propriete combinatoire des parties d'un ensemble aux groupes et aux relations. Math. Z. 150(2) (1976), pp. 117-134.

[33] M. Pouzet, Sur la theorie des relations. These d'etat, Universite Claude-Bernard, Lyon 1, pp. 78-85, 1978.

[34] M. Pouzet, Relation minimale pour son age. Z. Math. Logik Grundlag. Math. 25 (1979), pp. 315-344.

[35] M. Pouzet, The asymptotic behavior of a class of counting functions. Combinatorics 79 Part 2. M.DEZA and I.G.ROSENBERG Eds., Annals of Discrete Math. 9 (1980), pp. 223-224.

[36] M. Pouzet, Relation impartible. Dissertationnes 103 (1981), pp. 1-48.

[37] M. Pouzet, Application de la notion de relation presque-enchainable au denombrement des restrictions finies d'une relation. Z. Math. Logik Grundlag. Math. 27(4) (1981), pp. 289-332.

[38] M. Pouzet, Applications of well quasi-ordering and better quasi-ordering. In Graphs and order (Banff, Alta., 1984), pages 503-519. Reidel, Dordrecht, 1985.

[39] M. Pouzet and I.G. Rosenberg, Sperner properties for groups and relations, Europ. J. Combinatorics 7 (1986), pp. 349-370.

[40] M. Pouzet and M. Sobrani, Sandwiches of ages. Ann. Pure Appl. Logic 108(3) (2001), pp. 295-326.

[41] M. Pouzet and M. Sobrani, Ordinal invariants of an age. Preprint, 2002.

[42] M. Pouzet and N. Thiery, Some relational structures with polynomial growth and their associated algebras. May 10th, 2005, 19pages, presented at FPSAC for the 75 birthday of A.Garsia. http://arxiv.org/math.CO/0601256.

[43] M. Pouzet,When the orbit algebra of group is an integral domain? Proof of a Cameron's conjecture. Manuscript, Oct. 2002.

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

[45] F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. 30 (1930), pp. 264-286.

[46] C. Ryll-Nardzewski, On categoricity in power [less than or equal to] [[??].sub.a]. Bull. Acad. Pol. Sci. Ser. Math. Astr. Phys. 7 (1959), pp. 545-548.

[47] J. Schmerl, Coinductive [[??].sub.0]-categorical theories The Journal of Symbolic Logic 55 (1990), pp. 1130-1137.

[48] R.P. Stanley, Enumerative combinatorics. Volume 1, Wadsworth--Brooks/Cole Advanced Books and Software, Belmont, Calif. 1986.

[49] M. Sobrani, Sur les ages de relations et quelques aspects homologiques des constructions D+M. These de Doctorat d'etat, Universite S.M. Ben Abdallah-Fez, Fez, 2002.

[50] E.S. Wolk, Partially well-ordered sets and partial ordinals. Fun. Math. 60 (1967), pp. 175-185.

MAURICE POUZET ([dagger])

Probabilites-Combinatoire-Statistique,

Universite Claude-Bernard Lyon1, Domaine de Gerland,

bat. recherche, 50 Avenue Tony Garnier,

69365 Lyon cedex 07, France

([dagger]) E-mail address: pouzet@univ-lyon1.fr

Printer friendly Cite/link Email Feedback | |

Author: | Pouzet, Maurice |
---|---|

Publication: | Global Journal of Pure and Applied Mathematics |

Geographic Code: | 4EUFR |

Date: | Dec 1, 2006 |

Words: | 20422 |

Previous Article: | Solutions approximation for stochastic differential equations. |

Next Article: | On some classes of meromorphic starlike functions defined by a differential operator. |

Topics: |