arXiv:1402.3090v1 [math.CO] 13 Feb 2014

Some relational structures with polynomial growth
and their associated algebras I:
Quasi-polynomiality of the profile
Maurice Pouzet∗
Université Claude-Bernard, Lyon1, ICJ,
43, Bd. du 11 Novembre 1918, Villeurbanne, F-69622
Department of Mathematics and Statistics, The University of Calgary,
Calgary, Alberta, Canada
pouzet@univ-lyon1.fr

Nicolas M. Thiéry
Université Paris-Sud, Laboratoire de Mathématiques d’Orsay, Orsay, F-91405;
CNRS, Orsay, F-91405
nthiery@users.sf.net
Dedicated to Adriano Garsia, with warmth and admiration
Mathematics Subject Classification: 05A15, 05E15, 03E20
March 20, 2014

Abstract
The profile of a relational structure R is the function ϕR which counts for every
integer n the number ϕR (n), possibly infinite, of substructures of R induced on the
n-element subsets, isomorphic substructures being identified. If ϕR takes only finite
values, this is the Hilbert function of a graded algebra associated with R, the age
algebra KA(R), introduced by P. J. Cameron.
In this paper we give a closer look at this association, particularly when the
relational structure R admits a finite monomorphic decomposition. This setting
still encompass well-studied graded commutative algebras like invariant rings of
finite permutation groups, or the rings of quasi-symmetric polynomials. We prove
that ϕR is eventually a quasi-polynomial, this supporting the conjecture that, under
mild assumptions on R, ϕR is eventually a quasi-polynomial when it is bounded by
some polynomial.
Keywords: Relational structure, profile, graded algebra, Hilbert function, Hilbert
series, polynomial growth.
∗

This work was done under the auspices of the Intas programme Universal algebra and Lattice theory,
and supported by CMCU Franco-Tunisien ”Outils mathématiques pour l’informatique”.
the electronic journal of combinatorics 20 (2013), #1

1

Introduction
This paper is about a counting function: the profile of a relational structure R and its
interplay with a graded connected commutative algebra associated with R, the age algebra
of R.
Many natural counting functions are profiles. Several interesting examples come from
permutation groups. For example, if G is a permutation group on a set E, the function θG
which counts for every integer n the number of orbits of the action of G on the n-element
subsets of E, is a profile, the orbital profile of G. Groups whose orbital profile takes
only finite values are called oligomorphic; their study, introduced by Cameron, is a whole
research subject by itself [Cam90, Cam09]. If G acts on {1, . . . , k}, the Hilbert function
of the subalgebra K[X]G of the polynomials in K[X] := K[X1 , . . . , Xk ] which are invariant
under the action of G is a profile, and in fact an orbital profile. This fact led Cameron
to associate a graded algebra KA(R) to each relational structure R [Cam97]; its main
feature is that its Hilbert function coincides with the profile of R as long as it takes only
finite values. As it is well know, the Hilbert function of a graded commutative algebra A
is eventually a quasi-polynomial (hence bounded by some polynomial), provided that A
is finitely generated. The converse does not hold. Still, this leads us to conjecture that
the profile ϕR of a relational structure R is eventually a quasi-polynomial when ϕR is
bounded by some polynomial (and the kernel of R is finite).
This conjecture holds if R is an undirected graph [BBSS09] or a tournament [BP10].
In this paper, we prove that it holds for any relational structure R admitting a finite
monomorphic decomposition. Its age algebra is (essentially) a graded subalgebra of a
finitely generated polynomial algebra. It needs not be finitely generated (see Example A.4). Still, and this is our main result, the profile is eventually a quasi-polynomial
whose degree is controlled by the dimension of the monomorphic decomposition of R
(Theorem 1.7). This result was applied in [BP10] to show that the above conjecture holds
for tournaments.
Relational structures admitting a finite monomorphic decomposition are not so peculiar. Many familiar algebras, like invariant rings of permutation groups, rings of quasisymmetric polynomials, can be realized this way. We give many examples in Appendix A.
Further studies, notably a characterization of these relational structures for which the age
algebra is finitely generated are included in [PT12].
The study of the profile started in the seventies; see [Pou06] for a survey and [Pou08]
for more recent results. Our line of work is parallel to the numerous researches made in
recent years about the behavior of counting functions for hereditary classes made of finite
structures, like undirected graphs, posets, tournaments, ordered graphs, or permutations,
which also enter into this frame; see [Kla08a] and [Bol98] for a survey, and [BBM07,
BBSS09, MT04, AA05, AAB07, Vat11, KK03, Kla08b, BHV08, OP11]. These classes are
hereditary in the sense that they contain all induced structures of each of their members;
in several instances, members of these classes are counted up to isomorphism and with
respect to their size.
Results point out jumps in the behavior of these counting functions. Such jumps

the electronic journal of combinatorics 20 (2013), #1

2

were for example announced for extensive hereditary classes in [Pou80], with a proof
for the jump from constant to linear published in [Pou81b]. The growth is typically
polynomial or faster than any polynomial, though not necessarily exponential (as indicates
the partition function; see Example A.6). For example, the growth of an hereditary class
of graphs is either polynomial or faster than the partition function [BBSS09]. In several
instances, these counting functions are eventually quasi-polynomials, e.g. [BBSS09] for
graphs and [KK03] for permutations.
Klazar asked in his survey [Kla08a] how the two approaches relate. At first glance,
the structures we consider are more general; however the classes we consider in this paper
are more restrictive: the profile of a relational structure R is the counting function of its
age, and ages are hereditary classes structures which are up-directed by embeddability
([Fra54]). A priori, results on the behavior of counting functions of ages do not extend
straightforwardly to hereditary classes. There is a notable exception: the study of hereditary classes with polynomially bounded profiles can indeed be reduced to that of ages,
thanks to the following result:
Theorem 0.1. Consider an hereditary class C of finite structures of fixed finite signature.
If C has polynomially bounded profile then it is a finite union of ages. Otherwise it contains
an age with non polynomially bounded profile.
The proof is given in section 4.
This paper is organized as follows. In Section 1 we recall the definitions and basic
properties of relational structures, their profiles, and age algebras, and state our guiding
problems. We introduce the key combinatorial notion of monomorphic decomposition of
a relational structure, mention the existence of a unique minimal one (Proposition 1.6),
and state our main theorem (Theorem 1.7) together with some other results. In Section 2,
we study the properties of monomorphic decompositions and prove Proposition 1.6, while
Section 3 contains the proof of Theorem 1.7. Analyzing lots of examples has been an
essential tool in this exploration. Appendix A gathers them, with a description of their
age algebras; see in particular Examples A.4, A.18, and A.19, and Proposition A.23.
We urge the reader to start by browsing them, and to come back to them each time a
new notion is introduced. The overview of the results in Table 1 (which includes results
from [PT12]) may be of help as well.

Acknowledgments
A strong impulse to this research came from a paper by Garsia and Wallach [GW03]
who proved that the ring of quasi-symmetric polynomials is Cohen-Macaulay. Most, but
not all, of the results where previously announced at the FPSAC conference in honor of
Adriano Garsia [PT05], at the 14th Symposium of the Tunisian Mathematical Society,
held in Hammamet in 2006 [Pou06], and at ROGICS’08 [PT08].
We would like to thank the anonymous referee for a thorough report including many
helpful suggestions for improvements.

the electronic journal of combinatorics 20 (2013), #1

3

the electronic journal of combinatorics 20 (2013), #1

4

id o SN

Polynomials

b

yes

Table 1: Overview of the results

P (Z) ←∈∈N[Z]
(1−Z)···(1−Z |X| )

here, ”no” means ”not always”: there are both examples and counter-examples

unless when stated otherwise below

yes

(1+Z)···(1+Z+···+Z |X| )
(1−Z)···(1−Z |X| )

Sn o SN

Symmetric
polynomials

a

yes

1
(1−Z)···(1−Z |X| )

G o SN

yes

Invariants of a
permutation group G

P (Z) ←∈N[Z]
(1−Z)···(1−Z |X| )

Inc oSN

Quasi symmetric
polynomials [Ges84]

yes

h1 7→ 2i o SN

yes

yes

yes

yes

nevera

Finitely
generated

Non Cohen-Macaulay
example
1+Z 2 +Z 3 −Z 4
(1−Z)2 (1−Z 2 )

P (Z) ←∈Z[Z]
(1−Z)···(1−Z |X| )

Invariants of a
permutation groupoid G
G o SN

P (Z) ←∈N[Z]
(1−Z)···(1−Z |X| )

r-Quasi symmetric
polynomials [Hiv05]

Shape preserving

Hereditary optimal

Hilbert
Series
P (Z) ←∈Z[Z]
(1−Z)···(1−Z |X∞ | )
P (Z) ←∈Z[Z]
(1−Z)···(1−Z |X∞ | )
P (Z) ←∈Z[Z]
(1−Z)···(1−Z |X∞ | )

|X| < ∞

local
Relational
isomorphisms
structure

|X∞ |

<∞

≤

≤

1

|X|

|X|(|X|−1)
2

|X|(|X|+1)
2

2

|X|(|X|+1)
2

|X|

|X|

|X|

|X|

|X|

|X|

|X|

|X∞ |

<∞

|X|(|X|+2r−1)
2

≤

≤

≤ |X∞ |

yes

yes

yes

yes

yes

yes

yes

yes

almost

nob

nob

nob

yes

yes

yes

yes [GW03]

no

nob

yes

yes

nevera
[TT04]

no

no

nevera

no

nob

nob

yes

nob

Finite
SAGBI

nob

CohenSymKrull
Macaulay
dimension module

= ∞a

Degree
bound

1

1.1

Age algebras and quasi-polynomiality of relational
structure admitting a finite monomorphic decomposition
Relational structures and their profile

A relational structure is a realization of a language whose non-logical symbols are predicates. This is a pair R := (E, (ρi )i∈I ) made of a set E and a family of mi -ary relations ρi
on E. The set E is the domain or base of R; the family µ := (mi )i∈I is the signature of R;
the signature is finite if I is. The substructure induced by R on a subset A of E, simply
called the restriction of R to A, is the relational structure RA := (A, (Ami ∩ ρi )i∈I ). The
notion of isomorphism between relational structures is defined in the natural way. A local
isomorphism of R is any isomorphism between two restrictions of R. Two relational structures R and R0 are isomorphic is there is an isomorphism f from R onto R0 . We also say
that they have the same isomorphism type. The isomorphism type of a relational structure
is a formal object τ (R) such that a relational structure R0 is isomorphic to R if and only
if τ (R0 ) = τ (R). In some situations, isomorphism types have a concrete representation.
Let R be as above. For two subsets A and A0 of E, we set A ≈ A0 if RA and RA0 are
isomorphic. The orbit of a subset A of E is the set A of all subsets A0 of E such that
A0 ≈ A (the name “orbit” is given by analogy with the case of permutation groups; see
Subsection A.2). The orbit A can play the role of the isomorphism type τ (A) := τ (RA )
of RA .
The profile of R is the function ϕR which counts, for every integer n, the number ϕR (n)
of isomorphism types of restrictions of R on n-element subsets. Clearly, this function only
depends upon the set A(R) of isomorphism types of finite restrictions of R; this set, called
the age of R, was introduced by R. Fraı̈ssé (see [Fra00]). If the signature of R is finite,
ϕR (n) is necessarily finite. In order to capture examples coming from algebra and group
theory, we cannot preclude an infinite signature. However, since the profile is finite in
these examples, and unless explicitly stated otherwise, we always make the assumption
that ϕR (n) is finite, even if the signature of R is not.
The profile of an infinite relational structure is non-decreasing. Furthermore, provided
some mild conditions, there are jumps in the behavior of the profile:
Theorem 1.1. Let R := (E, (ρi )i∈I ) be a relational structure on an infinite set. Then,
ϕR is non-decreasing. And provided that either the signature µ is bounded or the kernel
K(R) of R is finite, the growth of ϕR is either polynomial or as fast as every polynomial.
A map ϕ : N → N has polynomial growth, of degree k, if ank ≤ ϕ(n) ≤ bnk for
some a, b > 0 and n large enough. The kernel of R is the set K(R) of x ∈ E such that
A(RE\{x} ) 6= A(R). Relations with empty kernel are the age-inexhaustible relations of
R. Fraı̈ssé’(see [Fra00]). We call almost age-inexhaustible those with finite kernel.
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
the electronic journal of combinatorics 20 (2013), #1

5

its kernel is finite. Some hypotheses on R are needed, indeed for every increasing and
unbounded map ϕ : N → N, there is a relational structure R such that ϕR is unbounded
and eventually bounded above by ϕ (see [Pou81b]). The first part of the result was obtained
in 1971 by the first author (see Exercise 8 p. 113 [Fra71]). A proof based on linear algebra
is given in [Pou76]. The second part was obtained in [Pou78] and a part was published in
[Pou81b].
The theorem above is not the best possible. It is natural to ask
Question 1.2. Does ϕR have polynomial growth in the strong sense: ϕR (n) ∼ ank for some
positive real a whenever R has bounded signature or finite kernel and ϕR is bounded
above by some polynomial.
This question, raised by Cameron [Cam90] in the special case of orbital profile, is
unsettled.
We consider a stronger condition. Recall that a map ϕ : N → N is a quasi-polynomial
of degree k if ϕ(n) = ak (n)nk + · · · + a0 (n) whose coefficients ak (n), . . . , a0 (n) are periodic
functions. Note that, when a profile is eventually a quasi-polynomial, it has polynomial
growth in the strong sense. Indeed, since the profile is non-decreasing, the coefficient ak (n)
of highest degree of the quasipolynomial is constant. We make the following:
Conjecture 1.3. The profile of a relational structure with bounded signature or finite
kernel is eventually a quasi-polynomial whenever the profile is bounded by some polynomial.
This conjecture is motivated by the association made by Cameron of a graded commutative algebra, the age algebra KA(R), to a relational structure R. Indeed, if A is
a graded commutative algebra, the Hilbert function hA of A, where hA (n) is the dimension of the homogeneous component of degree n of A, is eventually a quasi-polynomial
whenever A
Pis finitely generated. In fact, if A is such an algebra, the generating series
HA (Z) := n hA (n)Z n , called the Hilbert series of A, is a rational fraction of the form
(1 −

Z n1 )(1

P (Z)
,
− Z n2 ) · · · (1 − Z nk )

(1)

where 1 = n1 ≤ · · · ≤ nk and P (Z) ∈ Z[Z] (see e.g. [CLO97, Chapter 9, §2]). Furthermore, whenever A is Cohen-Macaulay, P (Z) ∈ N[Z] for some choice of n1 , . . . , nk . And,
as it is also well known ([Sta97]), a counting function is eventually a quasi-polynomial of
degree at most k − 1 whenever its generating series has the form (1) above.
As shown by Cameron, the Hilbert function of the age algebra of a relational structure
R is the profile of R (provided that it takes only finite values). Thus, provided that the age
algebra is finitely generated, Conjecture 1.3 and hence Question 1.2 have a positive answer.
In fact, as we will see, there are many relational structures for which the generating series
of their profile has the form (1) above, but few for which the age algebra is finitely
generated.
We present now the age algebra.

the electronic journal of combinatorics 20 (2013), #1

6

1.2

Age algebras

Let K be a field of characteristic 0, and E be a set. For n ≥ 0, denote by [E]n the set of
n
the subsets of E of size n, and let K[E] be the vector space of mapsLf : [E]n → K. The
<ω
n
set algebra is the graded connected commutative algebra K[E] := n K[E] , where the
product of f : [E]m → K and g : [E]n → K is defined as f g : [E]m+n → K such that:
X
(f g)(A) :=
f (A1 )g(A2 ) .
(2)
(A1 ,A2 ) : A=A1 ]A2

Identifying a set S with its characteristic function χS , elements of the set algebra can be
thought as (possibly infinite but of bounded degree) linear combination of sets; the unit is
the empty set, and the product of two sets is their disjoint union, or 0 if their intersection
is non trivial.
Let R be a relational structure with base set E. A map f : [E]m → K is R-invariant
if f (A) = f (A0 ) whenever A ≈ A0 . It is easy to show that the product of two R-invariant
maps is again invariant. The K-vector space spanned by the R-invariant maps is therefore
a graded connected commutative subalgebra of the set algebra, the age algebra of R, that
we denote by KA(R). It can be shown that two relational structures with the same age
yield the same algebra (up to an isomorphism of graded algebras); thus the name, coined
by Cameron who invented the notion [Cam97]. If the profile of R takes only finite values,
then KA(R) identifies with the set of (finite) linear combinations of elements of A(R) and,
as pointed out by Cameron, ϕR (n) is the dimension of the homogeneous component of
degree n of KA(R); indeed, define an orbit sum as the characteristic function of an orbit;
more specifically,
P the orbit sum of an isomorphism type τ ∈ A(R) is the characteristic
function oτ := A∈[E]<ω : τ (A)=τ A of its representatives in R; then observe that the set
of orbit sums form a basis of the age algebra KA(R)). By a slight abuse, we sometimes
identify τ with its orbit sum to see it as an element of KA(R).
Given three isomorphic types τ, τ1 , τ2 , we define a coefficient cττ1 ,τ2 by taking any subset
A of E of type τ and setting
cττ1 ,τ2 := |{(A1 , A2 ) : A1 ] A2 = A, τ (A1 ) = τ1 , τ (A2 ) = τ2 }| .

(3)

Clearly, this coefficient does not depend on the choice of A. The collection (cττ1 ,τ2 )τ,τ1 ,τ2
are the structure constants of the age algebra:
X
oτ1 oτ2 =
cττ1 ,τ2 oτ .
(4)
τ

P
Let us illustrates the role that the age algebra of Cameron can play. Let e := a∈E {a},
which we can think of as the sum of isomorphic
of the one-element restrictions of
L∞ types
n
R. Let U be the graded free algebra K[e] = n=0 Ke . Cameron (see [Cam97]) proved:
Theorem 1.4. If R is infinite then e is not a zero-divisor; namely for any u ∈ KA(R),
eu = 0 if and only if u = 0.
the electronic journal of combinatorics 20 (2013), #1

7

This result implies that ϕR is non decreasing. Indeed, the image of a basis of the vector
space KA(R)n under multiplication by e is a linearly independent subset of KA(R)n+1 .
The relationship between profile and age algebra is particularly simple for relational
structures with bounded profile. These structures were characterized in [FP71] for finite
signature and in [Pou81b, Théorème 1.2] for arbitrary signature, by means of Ramsey
theorem. We recall it below.
Let R := (E, (ρi )i∈I ) be a relational structure, F be a subset of E and B := E \ F .
Following R. Fraı̈ssé, who invented these notions, we say that R is F -monomorphic if for
every integers n and every A, A0 ∈ [B]n there is an isomorphism from RA∪F onto RA0 ∪F
which is the identity on F . We say that R is F -chainable if there is a linear order ≤ on
B such that the local isomorphisms of (B, ≤) extended by the identity on F are local
isomorphisms of R. We say that R is almost monomorphic, resp. almost chainable, if R
is F -monomorphic, resp. F -chainable, for some finite subset F of E. We say that R is
monomorphic, resp. chainable, if one can take F empty.
Assume for example, that R is made of a single relation ρ and is chainable by some
linear order ≤. If ρ is unary, then it is the full or empty relation. If ρ is binary, there
are eight possibilities: four if ρ is reflexive (ρ coincides with either ≤, its opposite ≥, the
equality relation =, or the complete relation E × E) and four if not (the same as for the
reflexive case, with loops removed).
For infinite relational structures, the notions of monomorphy and chainability coincide [Fra54]. For finite structures, they are distinct. However, it was proved by C. Frasnay
that, for any integer n, there is an integer f (n) such that every monomorphic relational
structure of arity at most n and size at least f (n) is chainable (see [Fra65] and [Fra00,
Chapter 13]).
The following theorem links the profile with the age algebra in the context of almostchainable and almost-monomorphic relational structures.
Theorem 1.5. Let R be a relational structure with E infinite. Then, the following properties are equivalent:
(a) The profile of R is bounded.
(b) R is almost-monomorphic.
(c) R is almost-chainable.
(d) The Hilbert series is of the following form, with P (Z) ∈ N[Z] and P (1) 6= 0:
HR =

P (Z)
.
1−Z

(e) The age
P algebra is a finite dimensional free-module over the free-algebra K[e], where
e := a∈E a; in particular it is finitely generated and Cohen-Macaulay.

the electronic journal of combinatorics 20 (2013), #1

8

Proof. Trivially, (c) implies (b) and (b) implies (a). The equivalence between (a) and
(c) is in [FP71] for finite signature and in [Pou81b, 1.2 Théorème, p. 317] for arbitrary
signature.
Straightforwardly, (e) implies (d) and (d) implies (a). Finally (e) follows from (a):
indeed, by Theorem 1.4, e is not a zero divisor in KA(R); using the grading, it follows
that K[e] is a free algebra and that KA(R) is a free-module over K[e]. Since the profile is
bounded, this free-module is finite dimensional.

1.3

Relational structures admitting a finite monomorphic decomposition

We now introduce a combinatorial notion which generalizes that of almost-monomorphic
relational structure.
Let E be a set and (Ex )x∈X be a set partition of E. Write X∞ := {x ∈ X : |Ex | = ∞}.
For a subset A of E, set dx (A) := |A ∩ Ex |, d(A) := (dx (A))x∈X and d(A) be the sequence
d(A) sorted in decreasing order. The sequence d(A) is the shape of A with respect to the
partition (Ex )x∈X . When A is finite it is oftenQconvenient, and even meaningful, to encode
d(A) as a monomial in K[X], namely X A := x∈X xdx (A) ; furthermore, up to trailing zero
parts, d(A) is an integer partition of |A|.
Let R be a relational structure on E. We call (Ex )x∈X a monomorphic decomposition
of R if the induced structures on two finite subsets A and A0 of E are isomorphic when0
ever X A = X A . The following proposition states the basic result about monomorphic
decompositions; we will prove it in a slightly more general setting (see Proposition 2.12).
Proposition 1.6. There is a monomorphic decomposition of R of which every other
monomorphic decomposition of R is a refinement.
This monomorphic decomposition is called minimal ; its number k := k(R) := |X∞ | of
infinite blocks is the monomorphic dimension of R.
Our main result, which we prove in Section 3, is a complete solution for Conjecture 1.3 for relational structures admitting a finite monomorphic decomposition (the
almost-monomorphic ones being those of dimension 1):
Theorem 1.7. Let R be an infinite relational structure with a finite monomorphic decomposition, and let k be its monomorphic dimension. Then, the generating series HR is
a rational fraction of the following form, with P ∈ Z[Z] and P (1) 6= 0:
P (Z)
.
(1 − Z)(1 − Z 2 ) · · · (1 − Z k )
In particular, ϕR is eventually a quasi polynomial of degree k − 1, hence ϕR (n) ∼ ank−1 .
This refines Theorem 2.16 of [PT05], by refining the denominator and the growth rate.
Among relational structures which admit a finite monomorphic decomposition, those
made of a single unary or binary relation are easy to characterize (cf. Corollary 2.26). For
the electronic journal of combinatorics 20 (2013), #1

9

example, the undirected graphs admitting a finite monomorphic decomposition are the
lexicographical sums of cliques or independent sets indexed by a finite graph. Similarly,
the tournaments admitting a finite monomorphic decomposition are the lexicographical
sums of acyclic (aka transitive) tournaments indexed by a finite tournament. In Section 2.3
we prove the following generalization.
Theorem 1.8. A relational structure R := (E, (ρi )i∈I ) admits a finite monomorphic
decomposition if and only if there exists a linear order ≤ on E and a finite partition
(Ex )x∈X of E into intervals of (E, ≤) such that every local isomorphism of (E, ≤) which
preserves each interval is a local isomorphism of R. Moreover, there exists such a partition
whose number of infinite blocks is the monomorphic dimension of R.
The interest for this notion goes beyond these examples and this characterization. It
turns out that familiar algebras like invariant rings of finite permutation groups can be
realized as age algebras of relational structures admitting a finite monomorphic decomposition (see Example A.16); another example is the algebra of quasi-symmetric polynomials
and variants (see Examples A.18 of Appendix A).
The relationship with polynomials is not accidental:
Proposition 1.9 ([PT12]). If R admits a monomorphic decomposition into finitely many
blocks E1 , . . . , Ek , all infinite, then the age algebra KA(R) is isomorphic to a subalgebra
K[x1 , . . . , xk ]R of the algebra K[x1 , . . . , xk ] of polynomials in the indeterminates x1 , . . . , xk .
Invariant rings of finite permutation groups, as well as the algebras of quasi-symmetric
polynomials are finitely generated and in fact Cohen-Macaulay. It is however worth noticing on the onset that there are examples of relational structures such that
• X is finite, but the age algebra is not finitely generated (see Example A.4);
• X is finite, the Hilbert series is of the form of Equation 1 with P (Z) ∈ N[Z] but the
age algebra is not Cohen-Macaulay (see Example A.19);
• X is infinite but the profile still has polynomial growth (see Examples A.9 and A.10).
In those examples, the profile is still a quasi-polynomial. This raises the following problems.
Problems 1.10. Let R be a relational structure whose profile is bounded by some polynomial. Find combinatorial conditions on R for
(a) the profile to be eventually a quasi-polynomial;
(b) the age algebra to be finitely generated;
(c) the age algebra to be Cohen-Macaulay.
We give here a partial answer to (a), while (b) and (c) are investigated in length in a
subsequent paper [PT12].
the electronic journal of combinatorics 20 (2013), #1

10

2

Monomorphic decompositions

We start by stating some simple properties of set partitions. For the sake of completeness,
proofs are included. Then, we apply those results to the lattice of monomorphic decompositions (Proposition 2.12), and derive a lower bound on the profile (Theorem 2.17)

2.1

On certain lattices of set partitions

Fix a set E, finite or not, and a collection C of subsets of E which are called good. We
assume that this collection satisfies the following:
Axioms 2.1 (Goodness axioms). (a) Singletons are good;
(b) A subset of a good subset is good;
(c) A (possibly infinite) union of good subsets with a non trivial intersection is good.
Lemma 2.2. A collection C of subsets of E satisfies Axioms 2.1 if and only if every
subset of a maximal member of C belongs to C and the maximal members of C form a set
partition of E.
Proof. Suppose that C satisfy Axioms 2.1 above. The fact that subsets of maximal members of C belong to C follows directly from (b). Now take some a ∈ E. By (a) and (c),
the union C(a) of all good subsets containing a is good. Furthermore, any maximal good
subset of E (for inclusion) is of this form. Using (c), two maximal good subsets C(a) and
C(b) either coincide or are disjoint. Hence, the collection P(C) := {C(a)}a∈E forms a set
partition of E into good subsets. The converse is immediate.
Let C be a collection of subsets of E satisfying Axioms 2.1. The components of C are
the maximal members of C. We denote by P(C) the partition of E into components of C
and by s(C) the number of components, that is the size of P(C).
We consider the refinement order on the set S(E) of the set partitions on E, choosing
by convention that P  Q if P is coarser than Q (that is each block of P is a union of
blocks of Q). With this ordering S(E) forms a lattice, with {E} as minimal element and
{{a} : a ∈ E} as maximal element.
A set partition P := (Px )x∈X of E is good if each block Px is good. For example, P(C)
is good and so is the trivial partition into singletons. From Lemma 2.2 above we have:
Proposition 2.3. A set partition P is good if and only if it refines P(C). Hence the set
of all good set partitions is a principal filter of the lattice S(E); in particular, it is stable
under joins and meets.
Due to this fact, we name P(C) the minimal good set partition.
Take now a set E, and associate to each subset D of E a collection CD of subsets of D,
called D-good, and satisfying the axioms above. Assume further that the following axiom
is satisfied:
the electronic journal of combinatorics 20 (2013), #1

11

Axiom 2.4 (Goodness axioms, continued). (d) If D1 ⊆ D2 ⊆ E and F ⊆ D2 is D2 -good,
then F ∩ D1 is D1 -good.
Take D1 ⊆ D2 . A set partition P of D2 induces (by intersection of each of its block
with D1 and removal of the empty ones) a set partition of D1 . The latter is properly
induced by P if D1 intersects non trivially each block of P (that is no block vanishes in
the process).
Axiom (d) implies right away the following properties.
Proposition 2.5. Let D1 ⊆ D2 ⊆ D3 ⊆ E.
(a) Any D2 -good set partition of D2 induces a D1 -good set partition of D1 .
(b) The size of the minimal good set partition of D2 is at least that of the minimal good
set partition of D1 . If it is finite there is equality if and only if the minimal good set
partition P(D1 ) of D1 is properly induced by P(D2 ).
(c) If P(D1 ) is properly induced by P(D3 ), then P(D1 ) is properly induced by P(D2 )
which itself is properly induced by P(D3 )
To derive the main desired property, we need to add a last axiom on good subsets.
Axiom 2.6 (Goodness axioms, continued). (e) If D is a chain of subsets of E whose
union is D, then a subset F of D is D-good as soon as F ∩ D0 is D0 -good for all
D0 ∈ D.
Lemma 2.7. Every subset D of E such that s(CD ) is finite includes some finite subset F
such that s(CF ) = s(CD ).
Proof. We argue by induction on the cardinality κ of D. If κ is finite there is nothing
to prove. Suppose otherwise that κ is infinite, and write D as the union of a chain D of
subsets D0 of D, such that |D0 | < κ. By induction, we may assume that the property
holds for each D0 in D. There remains to prove that s(CD0 ) = s(CD ) for some D0 ∈ D.
According to Proposition 2.5 (a) we have s(CD0 ) ≤ s(CD00 ) ≤ s(CD ) for all D0 ⊆ D00 ⊆ D.
Since s(CD ) is finite, there is some k and some D0 ∈ D such that s(CD00 ) = k for all D00 ∈ D
such that D0 ⊂ D00 . Set X := {1, . . . , k}. For each such D00 , denote (Dx00 )x∈X the minimal
good set partition P(CD00 ) of D00 . Without loss of generality, and up to some renumbering
of the blocks, we may assume that, for each x ∈ X, the set Dx := {Dx00 : D0 ⊆ D00 ∈ D}
forms a chain for inclusion. Using Axiom (e), the union Dx of those is a D-good block.
Then, (Dx )x∈X is a good set partition of D into k blocks and thus it is the minimal one,
proving that s(CD0 ) = k = s(CD ), as desired.
Proposition 2.8. Assume that E has a good partition into finitely many blocks, and let
F be the collection of all subsets D of E whose minimal good set partition is properly
induced by that of E. Then, a subset D is in F if and only if it includes a finite subset
in F.
Proof. The “if” part follows from Proposition 2.5. The converse follows from Lemma 2.7.

the electronic journal of combinatorics 20 (2013), #1

12

2.2

Minimal monomorphic decompositions

We start with some elementary properties of the monomorphic decompositions of a relational structure R with base set E, and in particular we show that their blocks satisfy the
goodness axioms.
Lemma 2.9. Let R be a relational structure with base set E. For a subset F of E, the
following conditions are equivalent:
(i) there exists some monomorphic decomposition of R admitting F as a block;
(ii) the set partition {F } ∪ {{x}}x6∈F is a monomorphic decomposition of R;
(iii) for every pair A, A0 of subsets of E with the same finite cardinality the induced
structures on A and A0 are isomorphic whenever A \ F = A0 \ F .
A subset F is a monomorphic part of R if any (and therefore all) of the previous
conditions hold.
Note that in (iii) above, we do not not impose that the induced substructures on A
and A0 are isomorphic via an isomorphism which is the identity on A \ F . However, this
condition is fulfilled as soon as F is an infinite monomorphic part which is maximal w.r.t.
inclusion (see Theorem 2.25; beware of a different use of the letter F in this result).
Lemma 2.10. A set partition (Ex )x∈X of E is a monomorphic decomposition of R if and
only if it is made of monomorphic parts of R.
Proof. The “only if” part is by definition. Consider now a set partition whose blocks
0
are monomorphic parts of R, and take A and A0 such that X A = X A . Let E1 , . . . , Ek
be the blocks that A and A0 intersect non trivially, and for l ∈ 0, . . . , k, set A0 := A0 ,
Al := (A ∩ E1 ) ∪ · · · ∪ (A ∩ El ) ∪ (A0 ∩ El+1 ) ∪ · · · ∪ (A0 ∩ Ek ). Then, for l < k, Al and
Al+1 have the same cardinality and Al \El+1 = Al+1 \El+1 are equal. Since A0 = A0 and
Ak = A, one has A ≈ A0 , as desired.
Lemma 2.11. Let R be a relational structure on a set E. Then the set of monomorphic
parts of R satisfies Axioms 2.1. If furthermore for every subset D of E the good sets of
D consist of the monomorphic parts of RD then Axioms 2.4, and 2.6 are satisfied.
Proof. We denote by A and A0 two subsets of E of the same finite cardinality.
Axiom 2.1(a): if F is a singleton, and A \ F = A0 \ F , then A and A0 are equal, hence
trivially isomorphic.
Axiom 2.1(b): let F be a monomorphic part of R and F 0 ⊆ F . If A \ F 0 = A0 \ F 0 ,
then A \ F = A0 \ F , and therefore A and A0 are isomorphic.
Axiom 2.1(c): let (Fi )i∈I be a (possibly infinite)
S family of monomorphic parts0 which
all share at least a common point x, and set F = i∈I Fi , and assume A \ F = A \ F .
Without loss of generality, we may assume that A and A0 differ by a single point:
A = B ∪ {a} and A0 = B ∪ {a0 } with a and a0 in F (otherwise, pickup a sequence

the electronic journal of combinatorics 20 (2013), #1

13

A := A1 , . . . , Al = A0 , where at each step Aj \ F = A \ F , and Aj and Aj+1 differ by a
single point; then use transitivity).
If {a, a0 } is a subset of some Fi , then it forms a monomorphic part. Using that
A \ {a, a0 } = B = A0 \ {a, a0 }, wet get A ≈ A0 .
Otherwise, take Fi and Fi0 such that a ∈ Fi and a0 ∈ Fi0 .
If x 6∈ B, then using successively that {a, x} ⊆ Fi is a monomorphic part and {a0 , x} ⊆
Fi0 is a monomorphic part, one gets,
A = B ∪ {a} ≈ B ∪ {x} ≈ B \ ∪{a0 } = A0 .

(5)

A = B ∪ {a} ≈ B \ {x} ∪ {a, a0 } ≈ B \ ∪{a0 } = A0 .

(6)

Similarly, if x ∈ B,

Axiom 2.4(d): Let F be D2 -good, and assume that A and A0 are subsets of D1 such
that A\(F ∩ D1 ) = A0 \(F ∩ D1 ). Then, A\F = A\(F ∩ D1 ) = A0 \(F ∩ D1 ) = A0 \F ;
hence A ≈ A0 .
Axiom 2.6(e): assume A and A0 are subsets of D such that A\F = A\F . Take D0
large enough in D so that D0 contains both A and A0 . Then A\(F ∩D0 ) = A\F = A0 \F =
A0 \(F ∩ D0 ), and therefore A ≈ A0 .
We can now specialize Proposition 2.3 to monomorphic decompositions, to prove and
refine Proposition 1.6.
Proposition 2.12. The maximal monomorphic parts of R form a monomorphic decomposition of R. Furthermore, the other monomorphic decompositions are exactly the finer
set partitions of this partition.
The monomorphic components of R, or components for short, are the maximal monomorphic parts of R. We denote by c(R) the number of components of R. The partition of
E into components, that we denote by P(R), is the minimal monomorphic decomposition
of R.
The main consequence of Proposition 2.12 is the following:
Corollary 2.13. Let R and R0 be two relational structures with domains E and E 0 respectively. If R and R0 are isomorphic, then the components of R are mapped bijectively
onto the components of R0 by any isomorphism σ. In particular, every automorphism of
R induces a permutation of the components of R and, if the domain E of R is finite, E
and E 0 have the same number of components and the same shape w.r.t. their minimal
decompositions.
Propositions 2.5 and 2.8 also apply, and will be used in the sequel. In particular, we
get the following:
Proposition 2.14. Let R be a relational structure and R0 be a restriction of it. Then
any monomorphic decomposition of R induces a monomorphic decomposition of R0 . Note
however that this monomorphic decomposition may have fewer components, and that minimality is not necessarily preserved.
the electronic journal of combinatorics 20 (2013), #1

14

Let (Ex )x∈X be a partition of a set E. Given d ∈ N, call d-fat a subset A of E
such that, for all x ∈ X, dx (A) ≥ d whenever A 6⊇ Ex . We prove that, if the minimal
monomorphic decomposition has finitely many components, then the isomorphism relation
is shape preserving on fat enough sets, and we derive a lower bound on the profile.
Lemma 2.15. Let R be an infinite relational structure on a set E admitting a finite
monomorphic decomposition. Then, there exists some integer d such that on every d-fat
subset A of E (w.r.t. P(R)) the partition P(R)A induced by P(R) on A coincides with
P(RA ). In particular the shape of A w.r.t. P(R) coincides with the shape of A w.r.t.
P(RA ).
Proof. Let E be the base set of R and (Ex )x∈X be the minimal partition of E into
monomorphic parts. According to Proposition 2.8 there is a family F of finite subsets F
of E such that for every subset D of E the minimal partition of D into monomorphic parts
of RD is properly induced by the partition of E if and only if D contains some member
of F. Pick F ∈ F. We claim that every subset F 0 of E such that d(F 0 ) = d(F ) has the
same property as F . Indeed, according to (c) of Proposition 2.5, it suffices to prove that
c(RF 0 ) = c(R). This fact is straightforward, indeed, since d(F 0 ) = d(F ), RF is isomorphic to RF 0 , hence from Corollary 2.13 the components of RF correspond bijectively to
the components of RF 0 . Hence, c(RF ) = c(RF 0 ). By our choice of F , c(RF ) = c(R).
Since the components of R induce a monomorphic decomposition of RF 0 , c(RF 0 ) ≤ c(R).
This yields c(RF 0 ) = c(R), as required. Let d := max{|F ∩ Ex | : x ∈ X}. Let A be a
d-fat subset of E w.r.t. the partition (Ex )x∈X . Then A contains a subset F 0 such that
d(F 0 ) = d(F ) and we are done.
With the notations of Lemma 2.15 we have
Corollary 2.16. Two isomorphic d-fat subsets of E always have the same shape w.r.t.
P(R).
Theorem 2.17. Let R be an infinite relational structure with a finite monomorphic decomposition, and let k be its monomorphic dimension. Then, the profile ϕR of R is
bounded from below by a polynomial of degree k − 1; namely, there exists n0 such that for
n ≥ n0 , ϕR (n) ≥ ℘k (n − n0 ), where ℘k (m) is the number of integer partitions of m in at
most k parts.
Proof. Take d as in Lemma 2.15, and let n0 := k1 d + m, where k1 is the number of
monomorphic components of R having at least d elements, and m is the sum of the
cardinalities of the other finite monomorphic components of R.
Let E1 , . . . , Ep be the monomorphic components of R, enumerated in such a way that
|E1 | ≥ · · · ≥ |Ep |. To each decreasing sequence x := x1 ≥ · · · ≥ xk0 of positive integers
such that k 0 ≤ k and x1 + · · · + xk0 = n − n0 associate an n-element subset A(x) of E such
that |A(x) ∩ Ei | is respectively d + xi if i ≤ k 0 , d if k 0 < i ≤ k1 and |Ei | if k1 < i ≤ p. The
set A(x) is d-fat and its shape is (|A(x) ∩ E1 |, . . . , |A(x) ∩ Ep |). Clearly, if x and x0 are two
distinct sequences as above, the shapes of A(x) and A(x0 ) are distincts. Since these sets
the electronic journal of combinatorics 20 (2013), #1

15

are d-fats, the restrictions RA(x) and RA(x0 ) are not isomorphic. The claimed inequality
follows.
mk−1
As it is well known, ℘k (m) is asymptotically equivalent to (k−1)!k!
(see e.g. [vLW92]).
Thus ϕR (n) is asymptotically bounded below by

2.3

nk−1
.
(k−1)!k!

Monomorphic decompositions, chainability and a proof of
Theorem 1.8

In Theorem 2.25 below, we present the relationship between the notions of chainability,
monomorphy and our notion of monomorphic parts. The key ingredients of the proof are
Ramsey’s theorem, Compactness theorem of first order logic and some properties of the
kernel of relational structures. We give below the facts we need.
0
Let R := (E, (ρi )i∈I ) a relational structure. For each subset I 0 of I we set RI :=
(E, (ρi )i∈I 0 ).
Compactness theorem of first order logic yields the following lemma:
Lemma 2.18. A relational structure R := (E, (ρi )i∈I ) is F -chainable if and only if for
0
I0
each finite subset F 0 of F and every finite subset I 0 of I, R(E\F
)∪F 0 is F -chainable.
Ramsey’s theorem yields the following result:
Lemma 2.19 (Fraı̈ssé [Fra54]). 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 0 of E
containing F on which the restriction R0 := RE 0 is F -chainable.
We also need some properties of the kernel. Most of these properties are based on the
following simple lemma (see [Pou79] for finite signature and [PS01, 3 of Lemma 2.12] for
the general case).
Lemma 2.20. For all a, b ∈ E, A(RE\{a} ) = A(R) =⇒ A(RE\{a,b} ) = A(RE\{b} ).
From this property, we have easily:
Lemma 2.21. Let R be a relational structure with domain E, and E 0 be a subset of E. If
K(R) ⊆ E 0 and E \ E 0 is finite then R and RE 0 have the same age and the same kernel.
Lemma 2.22. Let R be a relational structure with domain E, and F be a finite subset of
E \ K(R). Assume furthermore that K(R) is finite. Then, for every finite subset A of E
there is some subset A0 of E \ F such that A ≈ A0 and A ∩ K(R) = A0 ∩ K(R).
The proof of this lemma can obtained via the existence of a finite subset of E localizing
A ∩ K(R) (see Proposition 2.17 of [PS01]).
Trivially, we have:
Lemma 2.23. If E 0 is an infinite monomorphic part of R then K(R) ∩ E 0 = ∅.
Using Lemma 2.18 and Lemma 2.22 we get:
the electronic journal of combinatorics 20 (2013), #1

16

Lemma 2.24. If R is almost-chainable then R is K(R)-chainable.
Theorem 2.25. Let R := (E, (ρi )i∈I ) be a relational structure, E 0 be a subset of E and
F := E 0 \ E. Let us consider the following properties:
(i) R is F -chainable;
(ii) R is F -monomorphic;
(iii) E 0 is a monomorphic part of R.
Then (i) ⇒ (ii) ⇒ (iii). If E 0 is infinite then (ii) ⇒ (i). If E 0 is infinite and E 0 is a
monomorphic component of R then (iii) ⇒ (i).
Proof. The implications (i) ⇒ (ii) ⇒ (iii) are obvious. Implication (ii) ⇒ (i) when E 0 is
infinite is due to Fraı̈ssé. A proof in the case of a finite signature is in [FP71]. We just
recall the principle of the proof. We prove first that for each finite subset I 0 of I, each
I0
0
finite subset F 0 of F and each finite subset E 00 of E 0 , the restriction R0 := RE
00 ∪F 0 is F chainable. For that we apply Lemma 2.19. It yields an infinite subset E10 of E 0 on which
I0
R10 = RE
0
0 is F -chainable. Since R is F -monomorphic, there is a local isomorphism
1 ∪F
0
I0
fixing F 0 pointwise which send E 00 ∪ F 0 into E10 ∪ F 0 ; thus R0 := RE
00 ∪F 0 is F -chainable.
0
We conclude with Lemma 2.18. The proof of (iii) ⇒ (i) when E is a component relies
on the following claim:
Claim 1. Let F 0 be a finite subset of F . There is some finite subset F 00 of F containing
F 0 such that K(RE 0 ∪F 00 ) = F 00 .
Proof of Claim 1. Let x ∈ F . Since the components of R are the maximal monomorphic parts of R, the set E 0 ∪ {x} is not a monomorphic part of R. Hence, there are nx
and Ax 6≈ A0x in [E]nx such that
Ax \ (E 0 ∪ {x}) = A0x \ (E 0 ∪ {x}) .

(7)

S
For each x ∈ F 0 select Ax and A0x as above. Define V := x∈F 0 Ax ∪ A0x , as well as
R0 := RE 0 ∪V , and F 00 := K(R0 ).
Subclaim 1. K(RE 0 ∪F 00 ) = F 00 .
Proof of Subclaim 1. Since (E 0 ∪ V ) \ (E 0 ∪ F 00 ) is finite and F 00 = K(R0 ), Lemma 2.21
asserts that RE 0 ∪V and RE 0 ∪F 00 have the same age and the same kernel.
Subclaim 2. F 0 ⊆ F 00 ⊆ F .
Proof of Subclaim 2. Since E 0 is a monomorphic component of R, this is a monomorphic
part of R0 and Lemma 2.23 asserts that K(R0 ) is disjoint from E 0 . This yields F 00 ⊆
V \ E 0 ⊆ F . Suppose that F 0 6⊆ F 00 . Let x ∈ F 0 \ F 00 . Then, since F 00 ⊆ V \ E 0 , we have
F 00 ⊆ E \(E 0 ∪{x}). Thus from (7) we have Ax ∩F 00 = A0x ∩F 00 . Since V \(E 0 ∪F 00 ) is finite,
it follows from Lemma 2.22 that there are A, A0 ∈ [F 00 ∪ E 0 ]nx such that A ∩ F 00 = Ax ∩ F 00 ,
0
0
0
A0x ∩ F 00 = A0 ∩ F 00 , and the restrictions RA
and RA
0 are respectively isomorphic to RA
x
0
0
0
0
0
and RA
0 . Since E is a monomorphic component of R , RA and RA0 are isomorphic.
x
However this implies that Ax ≈ A0x , a contradiction. Therefore, F 0 ⊆ F 00 ⊆ V . This
completes the proof of the claim.
the electronic journal of combinatorics 20 (2013), #1

17

With these two subclaims, the proof of Claim 1 is complete.
Now, since E 0 is a monomorphic part of RE 0 ∪F 00 , the profile of RE 0 ∪F 00 is bounded.
According to the implication (a) ⇒ (c) in Theorem 1.5, RE 0 ∪F 00 is almost chainable.
According to Lemma 2.24, RE 0 ∪F 00 is K(RE 0 ∪F 00 )-chainable, that is F 00 -chainable. It
follows that RE 0 ∪F 0 is F 0 -chainable. Since this holds for every finite subset F 0 of F , it
follows from Lemma 2.18 that R is F -chainable. Hence (ii) holds. This completes the
proof of Theorem 2.25.
Theorem 1.8 follows immediately from Theorem 2.25. Indeed, if R admits a finite
monomorphic decomposition, we may choose one such that all the finite blocks are singletons. Hence, if (Ex )x∈X is such a decomposition, then a lexicographical sum, in any
order, of the chains (Ex , ≤x ) given by (i) of Theorem 2.25 yields a linear order on E for
which the Ex are intervals and every local isomorphism preserving the Ex ’s preserves R.
In the special case of relational structures made of unary or binary relations, Theorem 1.8 yields the following characterization:
Corollary 2.26. If a relational structure R is at most binary, it has a finite monomorphic
decomposition if and only if it is a lexicographical sum of chainable relational structures
indexed by a finite relational structure.
Let us say that a relational structure R := (E, (ρi )i∈I ) is almost multichainable if there
is a finite subset F of E and an enumeration (ax,y )(x,y)∈V ×L of the elements of E \ F by
a set V × L, where V is finite and L is a linearly ordered set such that for every local
isomorphism f of L, the map (1V , f ) extended by the identity on F is a local isomorphism
of R (the map (1V , f ) is defined by (1V , f )(x, y) := (x, f (y))). If the map (1V , f ) extended
by the identity on F is a local isomorphism of R for every permutation f of L, R is cellular.
The notion of almost multichainability was introduced in [Pou78] and appeared in
[Pou81a, Pou79]. It was shown that a relational structure with polynomially bounded
profile and finite kernel has the same age as an almost multichainable relational structure
[Pou06]. Cellularity was introduced by J. Schmerl [Sch90] in 1990. In [Pou06] it is shown
that a graph has a polynomially bounded profile if and only if it is cellular (see [Pou06]).
The following easy corollary of Theorem 1.8 show that relational structures with a
finite monomorphic decomposition are essentially almost multichainable (the converse is
far from be true).
Corollary 2.27. If an infinite relational structure has a finite monomorphic decomposition, then it has some restriction having the same age which is almost multichainable.

3
3.1

Proof of Theorem 1.7
Preliminary steps

From now on, we assume that R has a finite monomorphic decomposition (Ex )x∈X . The
growth rate of the profile ϕR is at most nk−1 where k = |X∞ |; indeed ϕR (n) is bounded
the electronic journal of combinatorics 20 (2013), #1

18

P
above by the number of integer vectors (dx )x∈X such that dx ≤ |Ex | and x∈X dx = n;
a more algebraic explanation is that the association A 7→ X A makes the age algebra into
(essentially) a subalgebra of K[X∞ ] (see [PT12]). If the decomposition is minimal then,
according to Lemma 2.15, the growth rate of the profile is at least nk−1 . We now turn to
the proof that the Hilbert series is a rational fraction.
We define a total order on monomials in K[X] by comparing their shapes w.r.t. the
degree reverse lexicographic order and breaking ties by the usual lexicographic order
on monomials for some arbitrary fixed order on X (recall that the reverse lexicographic
order ≤revlex is defined as follow: for two integer sequences d := (d1 , . . . , dn ) and d0 :=
(d01 , . . . , d0n ) of same length, d <revlex d0 if d 6= d0 and di > d0i where i is the largest
j ≤ n such that dj 6= d0j ; for example (4, 1, 1) <revlex (3, 3, 0); for the degree reverse
lexicographic order, one first compares the sum of the two sequences and then break ties
with reverse lexicographic order; for example (3, 2, 0) <degrevlex (4, 1, 1)). Beware that this
total order on monomials is well founded but not a monomial order. We define the leading
monomial lm(τ ) of an isomorphism type τ as the unique maximal monomial in the set
{X A : τ (A) = τ }.
To prove the theorem, we essentially endow the set of leading monomials with a monomial ideal structure in some appropriate polynomial ring. The point is that the Hilbert
series of such monomial ideals are simple rational fractions (see e.g. [CLO97, Chapter 9,
§2]; note that their presentation is in term of the Hilbert function, but this is equivalent).
Proposition 3.1. Let K[x1 , . . . , xn ] be a polynomial ring whose variables have positive
degree di := deg(xi ), and let I be a monomial ideal. Then, the Hilbert series of I is of
the form:
P (Z)
.
d
1
(1 − Z ) · · · (1 − Z dn )
where P ∈ Z[Z].
We include the proof, as it is short and sheds some light for our purpose.
Proof. First, the Hilbert series of a principal ideal K[x1 , . . . , xn ].m generated by a monomial m of degree d is
Zd
.
(1 − Z d1 ) · · · (1 − Z dn )
Furthermore, the intersection of two principal ideals is again principal. Take now any
monomial ideal I. By Dickson Lemma, it is finitely generated by monomials m1 , . . . , mr .
Therefore, the Hilbert series of I can be computed by inclusion-exclusion from that of the
principal ideals (K[x1 , . . . , xn ].mi1 ∩ · · · ∩ K[x1 , . . . , xn ].mis )1≤i1 <···<is ≤r .
The key property of leading monomials of age algebras is reminiscent
of StanleyQ
Reisner rings. To each set S ⊆ X, associate the monomial xS := i∈S xi . By square
free factorization, any monomial m ∈ K[X] can be written in a unique way as a product
m = xeS11 . . . xeSrr where ∅ ⊂ S1 ⊂ · · · ⊂ Sr ⊂ X is a chain of non empty subsets of X, and
the ei are positive. Each Si is a layer of m, and S1 ⊂ · · · ⊂ Sr is the chain support of m.
the electronic journal of combinatorics 20 (2013), #1

19

Lemma 3.2. Let m be a leading monomial, and S ⊆ X be a layer of m. Then, mxS is
again a leading monomial unless di = |Ei | for some i in S.
Proof. Suppose that di < |Ei | for every i in S. Let A, A0 , B, B 0 be subsets of E such that
0
X A = m, X B = mxS , X B is the leading monomial lm(B), and A0 is any subset of B 0
belonging to A. Let RA , RB , RA0 and RB 0 be the corresponding induced structures,
and let ψ be an isomorphism from RB to RB 0 .
Setting e := |X|, write respectively d(A) = (α1 , . . . , αe ) and d(B) = (β1 , . . . , βe ) the
shapes of A and B, and similarly for A0 and B 0 . Our first goal is to prove that the shapes
of B and B 0 are the same.
Claim 1. αp = βp = βp0 = αp0 for all p > s where s := |S|.
Proof of Claim 1. Using that A and A0 have the same degree, and similarly for B and
B 0 , we have:
(α1 , . . . , αe ) ≥revlex (α10 , . . . , αe0 ) and (β10 , . . . , βe0 ) ≥revlex (β1 , . . . , βe ) .

(8)

Using that X B = X A xS , we get:
(β1 , . . . , βe ) = (α1 + 1, . . . , αs + 1, αs+1 , . . . , αe ) .

(9)

From the inclusion A0 ⊂ B 0 , we deduce that:
(α10 , . . . , αe0 ) ≥revlex (β10 , . . . , βe0 ).

(10)

Altogether, using that ≤revlex is preserved on suffixes, we conclude that:
0
0
(βs+1 , . . . , βe ) = (αs+1 , . . . , αe ) ≥revlex (αs+1
, . . . , αe0 ) ≥revlex (βs+1
, . . . , βe0 )
≥revlex (βs+1 , . . . , βe ) ,

(11)

and therefore all those suffixes coincide.
Claim 2. For each i ∈ S, Ei ∩ B is a component of RB , that is a maximal monomorphic part of RB .
Proof of Claim 2. Suppose not. Choose i ∈ S such that Ei ∩ B is not a component of
RB and is of maximal cardinality with that property. Since (Ek )k∈X is a monomorphic decomposition of R, then by Proposition 2.14, (Ek ∩B)k∈X is a monomorphic decomposition
of RB . Hence, by Proposition 2.12, it refines the minimal monomorphic decomposition
of RB . Since Ei ∩ B is not a maximal monomorphic part, there is some index j ∈ X such
that (Ei ∪ Ej ) ∩ B is still a monomorphic part of RB . Due to our choice of i, we have
|Ei ∩B| ≥ |Ej ∩B|. Note that this implies |Ei ∩A| ≥ |Ej ∩A|. Let a be the unique element
of Ei ∩ (B\A), pick a0 in Ej ∩ A, and set A00 := A ∪ {a}\{a0 }. Since the elements a and
a0 belong to the same component of RB , A00 ≈ A”. We also have d(A) <degrevlex d(A00 ), a
contradiction with the fact that X A is a leading monomial.
The proof of Claim 2 would have been simpler if the decomposition induced on A by
the Ex were the components of RA . However this is not true in general, even with the
assumption that X A is a leading monomial. For a simple example, take for R the union
the electronic journal of combinatorics 20 (2013), #1

20

of two non trivial cliques, and A containing exactly one element in each clique; then RA
has a single monomorphic component and not two.
0
0
Let S 0 := {i1 , . . . , S
is } be s distinct elements
S of X such0 that |Eik ∩ B | = βk for
0
k = 1, . . . , s. Set U := i6∈S (Ei ∩ B) and U := i6∈S 0 (Ei ∩ B ).
Claim 3. U is the set of all b ∈ B such that the B \ {b} contains no member of A.
The same statement holds for U 0 w.r.t. B 0 . In particular, ψ transforms U into U 0 .
0
, . . . , αe0 ) =
Proof of Claim 3. Let b ∈ U 0 . According to Claim 1, the equality (αs+1
0
0
0
0
0
(βs+1 , . . . , βe ) holds for any A ⊂ B such that A ≈ A . Hence, no member of A is included
in B 0 \ {b}. On the other hand, from the definition of U , B \ {b} contains a member of A
0
for every element b ∈ B \ U . Since |U | = βs+1 + · · · + βe = βs+1
+ · · · + βe0 = |U 0 | and ψ
is an isomorphism from RB to RB 0 , the statement follows by cardinality count.
Claim 4. ψ transforms (Ei ∩ B, i ∈ S) into (Ei ∩ B 0 , i ∈ S 0 ).
Proof of Claim 4. Let P (B) be the minimal monomorphic decomposition of B. By
Claim 2, it is of the form {Ei ∩ B : i ∈ S} ∪ P, where P is some partition of U . Then
{ψ(Ei ∩ B) : i ∈ S} ∪ P 0 , where P 0 := {ψ(C) : C ∈ P}, is the minimal monomorphic
decomposition P (B 0 ) of B 0 . Since (Ei ∩ B 0 )i∈X is a monomorphic decomposition of B 0 ,
this is a refinement of P (B 0 ). Using that, from Claim 3, ψ(B \ U ) = B 0 \ U 0 , we obtain
that (Ei ∩ B 0 )i∈S 0 is a refinement of (ψ(Ei ∩ B))i∈S . Since these two decompositions have
the same cardinality, they must coincide. The statement of Claim 4 follows.
Claim 2 and Claim 4 imply immediately that B and B 0 have the same shape. Fix now
0
A := ψ(A). Using Claim 4, A0 is obtained from B 0 by removing exactly one element in
each Ei ∩ B 0 , i ∈ S 0 . Putting everything together, we have:
0

• X A and X A have the same shape; similarly for B and B 0 ;
0

0

• X B = X A xS , where xS is a layer of X A ; similarly X B = X A xS 0 ;
0

0

• X B ≤lex X B and X A ≥lex X A .
Recall that, if two monomials have the same shape and at least one layer of size s, then
lexicographic comparison is preserved upon changing the multiplicity of that layer (this is
0
just applying a strictly monotone function to the exponents). Therefore, X A = X A and
0
X B = X B . In particular, X B = mxS is a leading monomial, as desired.

3.2

Final step

Fix a chain C := ∅ ⊂ S1 ⊂ · · · ⊂ Sr ⊆ X, and let lmC be the set of leading monomials
of the age algebra with this chain support. The plan is essentially to realize lmC as the
linear basis of some monomial ideal of a polynomial ring, so that the generating series
of lmC is realized as an Hilbert series. Consider the polynomial ring K[S1 , . . . , Sl ], with
its embedding in K[X] by Sj 7→ xSj . Let I be the subspace spanned by the monomials
m := S1r1 · · · Slrl such that di (m) > |Ei | for some i. It is obviously a monomial ideal. When
all monomorphic blocks are infinite, I is the trivial ideal {0}. Consider the subspace
K.lmC of K[S1 , . . . , Sl ] spanned by the monomials in lmC . Lemma 3.2 exactly states that

the electronic journal of combinatorics 20 (2013), #1

21

J := K.lmC ⊕I is in fact also a monomial ideal of K[S1 , . . . , Sl ]. Applying Proposition 3.1,
the Hilbert series of I and J are rational fractions of the form
P (Z)
(1 −

Z |S1 | ) · · · (1

− Z |Sl | )

.

Hence, the same hold for HK.lmC = HJ − HI . Furthermore, whenever Sj contains i with
|Ei | < ∞, the denominator (1 − Z |Sl | ) can be canceled out in HK.lmC . The remaining
denominator divides (1 − Z) · · · (1 − Z k ).
By summing up those Hilbert series HK.lmC over all chains C of subsets of X, we get
the generating series of all the leading monomials, that is the Hilbert series of KA(R).
Hence, it is a rational fraction of the form
P (Z)
.
(1 − Z) · · · (1 − Z k )
Recall that, if f (z) is a rational fraction that is analytic at zero and has poles at points
α1 , . . . , αm , then there exists m polynomials (πj (x))m
j=1 such that, for n large enough,
n

fn = [z ]f (z) =

m
X

πj (n)αj−n ;

j=1

furthermore, the degree of πj is equal to the order of the pole of f at αj minus one (see
e.g. [SF96, Theorem IV.9]).
Our fraction has a pole of order at most k a 1. The other poles are at roots of unity
and are of order at most k − 1. Hence ϕR (n) is eventually a quasi-polynomial. Since its
growth rate is bounded below by nk−1 (Lemma 2.15) we deduce that the pole at 1 is of
order k, that is P (1) 6= 0. It follows that ϕR (n) = ank−1 + O(nk−2 ), for some a ∈ R+ , as
desired.

4

Proof of Theorem 0.1

Let Ωµ be the class of finite relational structures with signature µ. The embeddability
relation is a quasi order; once isomorphic structures are identified, Ωµ is a poset. Initial
segments of this poset correspond to hereditary classes. If C is a hereditary class, members
of Ωµ \ C are obstructions to C. The minimal obstructions (minimal w.r.t. embeddability)
are the bounds of C. Clearly C is determined by its bounds. Indeed, if B is a subset of
Ωµ , set ↑ B := {S ∈ Ωµ : B ≤ S for some B ∈ B} and F orb(B) := Ωµ \ ↑ B. Then
C = F orb(B) where B is the set of bounds of C. Hence, the fact that C can be defined by
a finite number of obstructions amounts to the fact that it has only finitely many bounds
(considered up to isomorphy). An ideal of a poset is a non-empty and up directed initial
segment. Clearly, the age of a relational structure is an ideal; the converse holds provided
that µ is finite [Fra54]. By extension, the bounds of a relational structure are the bounds
of its age. The decomposition of a poset, or of an initial segment thereof, into ideals is
the electronic journal of combinatorics 20 (2013), #1

22

the backbone of the theory of ordered sets and the proof of Theorem 0.1 starts with well
known properties of such decompositions.
In the sequel we suppose that µ is finite, despite that some of the results hold without
this requirement. We consider two cases:
Case 1: C contains no infinite antichain (w.r.t. embedability). Then, C is a finite union
of ages. This is a special case of a general result about posets of Erdös-Tarski [ET43].
The statement follows.
Case 2: C contains an infinite antichain. Then it contains an age which cannot be
defined by finitely many obstructions and contains no infinite antichain [Pou81b, 3.9
p. 329] (this fact is a special instance of a property of posets which is similar to NashWilliam’s lemma on minimal bad sequences [NW63]). With this in mind, Theorem 0.1 is
a consequence of the following lemma.
Lemma 4.1. An age with polynomially bounded profile can be defined by finitely many
obstructions.
Lemma 4.1 is one of the many properties of relational structures with polynomially
bounded profile. These properties were stated in the thesis of the first author [Pou78];
some have been published in [Pou81b]. They are presented in the survey [Pou06] with
a complete treatment of the case of binary structures. For the reader’s convenience, the
remainder of this section contains a sketch of the proof of Lemma 4.1, in two steps:
Lemma 4.2 ([Pou06, Theorem 2.12]1 ). If the profile of a relational structure R is bounded
by a polynomial then there is some R0 with the same age which is almost multichainable.
Lemma 4.3 ([Pou06, Theorem 4.20]). The age of an almost multichainable structure can
be defined by finitely many obstructions.
Lemma 4.3 relies on the following notion and result which are are exposed in Fraı̈ssé’s
book (see Chapter 13 p. 354, [Fra00]). A class C of finite structures is very beautiful if
for every integer k, the collection C(k) of structures (S, U1 , . . . , Uk ), where S ∈ C and
U1 , . . . , Uk are unary relations with the same domain as S, has no infinite antichain w.r.t.
embeddability. A straightforward consequence of Higman’s theorem on words (see [Hig52])
is that the age of an almost multichainable structure is very beautiful. We conclude using
that a very beautiful age can be defined by finitely many obstructions [Pou72].
The proof of Lemma 4.2 uses the notions of kernel and of height. The height of an
age A is an ordinal, denoted by h(A) and defined by induction as follows: h(A) = 0 if A
has no proper sub-age; that is A is the age of the empty relational structure. Otherwise
h(A) := sup{h(A0 ) + 1 : A0 is a proper sub-age of A}. Clearly, the height is defined if
and only if there is no strictly descending infinite sequence of sub-ages of A. With this
definition, it is easy to check that an age A has height n with n ∈ N if and only if A is
the age of a relational structure on n elements. Denote by ω the first infinite ordinal, set
1

Beware that it is stated there that R itself is almost multichainable which might actually be an
overstatement.

the electronic journal of combinatorics 20 (2013), #1

23

ω.2 := ω + ω, ω 2 := ω + ω + · · · . For example, we have h(A) < ω.2 if and only if A is the
age of an almost chainable relational structure [PS01].
Lemma 4.2 follows from the next two facts:
Fact 1 ([Pou06, Theorem 4.30]) The profile ϕR grows as a polynomial of degree k if and
only if ω.(k + 1) ≤ h(A(R)) < ω.(k + 2).
Fact 2 ([Pou06, Theorem 4.24])If h(A) < ω 2 then A is the age of an almost multichainable
structure.
We need two more facts before sketching the proofs of Facts 1 and 2:
Fact 3. If A is inexhaustible then either A is the age of a multichainable structure and
h(A) < ω 2 or A contains the age Ak of a multichainable structure with h(Ak ) ≥ ω.(k + 1)
for every integer k.
Fact 4. Let R be a relational structure; if every sub-age of A(R) is very beautiful then
either h(A) ≥ ω 2 or K(R) is finite.
Fact 3 is easy (see Proposition 4.23 of [Pou06]). Fact 4 is deeper. It is in [Pou78]. It
is not known if the first part of the conclusion of Fact 4 can be dropped. It can if R is
made of binary structures (see Theorem 4.24 of [Pou06]).
The proof of Fact 2 is by induction on α := h(A), with α = ω.(k + 1) + p. From
the induction hypothesis, every proper sub-age is the age of an almost multichainable
structure; thus is very beautiful. By Fact 4, the kernel of any relational structure R with
age A is finite. Write F := K(R) and E 0 := E \ K(R). Let M be a relational structure
with base E 0 whose local isomorphisms are those of RE 0 which can be extended by the
identity on F to local isomorphisms of R. Then, M is age-inexhaustible and h(A(M )) = β
with β := ω.(k + 1). By Fact 3, A(M ) is the age of a multichainable structure. Thus,
A(R) is the age of an almost multichainable structure, as desired.
For the proof of Fact 1, we suppose first that R is almost multichainable. As in the
proof of Fact 2, we replace R by M and we prove that ϕM is bounded by a polynomial of
degree k if and only if h(A(M)) = ω.(k + 1). For that, we prove first that if h(A(M )) =
ω.(k + 1) then ϕM (n) ≤ n+k
for every integer n (Lemma 4.27 of [Pou06]). Next, in a
k
similar way as in the proof of Theorem 2.17, we prove that ϕM is bounded from below by
a polynomial of degree k. Since ϕR is bounded by a polynomial of the same degree as ϕM ,
we get the equivalence stated in Fact 1 when R is almost multichainable. Now, according
to Fact 2, if h(A(R)) < ω.(k + 2) there is some R0 with the same age as R which is almost
multichainable, and thus ϕR = ϕR0 is bounded by a polynomial of degree k. Conversely,
suppose that ϕR grows as a polynomial of degree k. We claim that A(R) has an height.
Indeed, otherwise A(R) contains an infinite antichain. Hence, as we saw in Case 2, it
contains an age A0 with no infinite antichain which cannot be defined by finitely many
obstructions. This age has an height, say α0 . If α0 < ω 2 then, by Fact 2, A0 is the age of an
almost multichainable structure, and thus can be defined by finitely many obstructions,
which is impossible. Thus α ≥ ω 2 . But then by Fact 3, A0 contains ages of height
ω.(k 0 + 1) for every k 0 and thus ϕR grows faster than every polynomial. A contradiction.
This proves our claim. Now, let α = h(A(R)). By the same token, α < ω 2 , hence A(R)
is the age of an almost multichainable structure. And thus ω.(k + 1) ≤ α < ω.(k + 2), as
desired.
the electronic journal of combinatorics 20 (2013), #1

24

A
A.1

Examples of relational structures and age algebras
Examples coming from graphs and digraphs

A graph G := (V, E) being considered as a binary irreflexive and symmetric relation,
its profile ϕG is the function which counts, for each integer n, the number ϕG (n) of
induced subgraphs on n elements subsets of V (G), isomorphic subgraphs counting for one.
Graphs with profile bounded by a polynomial have been described in [Pou06, BBSS09].
According to [BBSS09] the profile is either a quasi-polynomial or is eventually bounded
below by the partition function ℘, where ℘(n) is the number of integer partitions of n.
Tournaments with polynomially bounded profile have been characterized in [BP10] as
lexicographical sums of acyclic tournaments indexed by a finite tournament. They admit
finite monomorphic decomposition, hence their profile is a quasi-polynomial.
Example A.1. Trivially, if G is an infinite clique K∞ or coclique K ∞ , then there is a single
isomorphic type for each d, hence ϕG (n) = 1. There is one monomorphic component
1
. If instead one consider
Ex = E, the age algebra is K[x], and its Hilbert series is 1−Z
digraphs, we recover the same age and age algebra from any infinite chain N, Z, Q, R, etc.
or antichain.
A bit less trivial is the fact that ϕG is bounded if and only if G is almost constant in
the sense of Fraı̈ssé [Fra00] (there exists a finite subset FG of vertices such that two pairs
of vertices having the same intersection on FG are both edges or both non-edges).
Example A.2. Let G be the direct sum Kω ⊕ · · · ⊕ Kω of k infinite cliques (or chains)
E1 , . . . , Ek (see figure in Table 1). The Ei form the monomorphic components. The
nk
of integer partitions with at most k
profile counts the number ϕG (n) = pk (n) ' (k+1)!k!
parts. The age algebra is the ring of symmetric polynomials Sym(X) on k variables whose
1
Hilbert series is (1−Z)···(1−Z
k) .
Examples A.3. Let G be the direct sum Kω ⊕ K ω of an infinite clique and an infinite
Z
1−Z+Z 2
1+Z 3
independent set. Then, ϕG (n) = n for n ≥ 1, and HG = 1+ (1−Z)
2 = (1−Z)2 = (1−Z)(1−Z 2 ) .
Hence, the Hilbert series has one representation as a rational fraction with a numerator
with some negative coefficient, and another with all coefficients non-negative.
This Hilbert series coincides further with that of Examples A.4, and A.18 for k =
2. Still, in the first and third case, there are two infinite monomorphic components
whereas in the second there are three: one finite and two infinite. Furthermore, the age
algebra is finitely generated and even Cohen-Macaulay in the first (take the free subalgebra
generated by a point and a 2-chain, and take as module generators the empty set and a
3-chain) and third case, but not in the second.
Example A.4. Let G be the direct sum K(1,ω) ⊕ K ω of an infinite wheel and an infinite
independent set. There are two infinite monomorphic components, E1 the set of leaves of
the wheel and E2 the independent set, and one finite, E3 , containing the center c of the
wheel. Each isomorphism type consists of a wheel and an independent set, so the Hilbert
2
Z2
1
1+Z 3
series is HG (Z) = (1 + 1−Z
) 1−Z
= 1−Z+Z
= (1−Z)(1−Z
2) .
(1−Z)2

the electronic journal of combinatorics 20 (2013), #1

25

What makes this relational structure special is that the monomorphic decomposition
(E1 , E2 , E3 ) is minimal, whereas (E1 , E2 ) is not a minimal monomorphic decomposition
of the restriction of R to E1 ∪ E2 . We now prove that this causes the age algebra not
to be finitely generated. Consider the subalgebra B := K[e1 (E)]. In each degree d, it is
spanned by the sum bd of all subsets of size d of E. Key fact: any element s of KA(R) can
be uniquely written as s =: a(s) + b(s) where b(s) is in B, and all subsets in the support
of a(s) contain the unique element c of E3 . Note in particular that a(s)2 = 0 for any s
homogeneous of positive degree. Let S be a finite generating set of the age algebra made
of homogeneous elements of positive degree. By the remark above, {a(s), s ∈ S} generates
KA(R) as a B-module. It follows that the graded dimension of KA(R) is bounded by |S|,
a contradiction.
Example A.5. When extending Example A.2 to infinitely many cliques the ageQalgebra be1
comes the ring Sym of symmetric functions whose Hilbert series is HR (Z) = d≥1 (1−Z
d) .
Example A.6. If G is an infinite path, then the finite restrictions are direct sums of paths.
Therefore, the profile counts the number of integer partitions of n. The age algebra is
the free commutative algebra generated by the paths of length 1, 2, . . . , which is again
isomorphic to Sym. However, this time, the monomorphic components are reduced to
singletons.
Example A.7. If G is the Rado graph, then ϕG (n) counts the total number of unlabelled
graphs. The age algebra is the free Q
commutative algebra generated by the connected
graphs. Its Hilbert series is HR (Z) = d≥1 (1−Z1d )cd , where cd is the number of connected
graphs with d vertices.
Example A.8. Let G be the lexicographic sum tournament obtained by substituting each
point i of the cycle C3 := {(1, 2), (2, 3), (3, 1)} on {1, 2, 3} by the chain N. The three
chains (E1 , E2 , E3 ) give the minimal monomorphic decomposition of G, but this decomposition is not recursively minimal and the age algebra is not finitely generated because, as
above, (E1 , E2 ) is not the minimal monomorphic decomposition of R restricted to E1 ∪ E2
(see [PT12]).
Example A.9. Take the direct sum K ∞ o G of infinitely many copies of a finite connected
graph G. The age algebra is the free commutative algebra generated by the (finitely
many) connected induced subgraphs of G. Taking for G the graph K1,1 , one gets the
infinite matching. The age algebra is finitely generated, whereas there are infinitely many
monomorphic blocks. The extension of this example to G a finite relational structure is
straightforward.
Examples A.10. Let G be the simple graph consisting of the direct sum of an infinite
wheel and an infinite matching. Each isomorphism type is the direct sum of a wheel, an
Z
1
1
independent set, and a matching. Therefore, the Hilbert series is HG (Z) = 1−Z
,
1−Z 1−Z 2
2
and the profile has polynomial growth: ϕG (n) ∼ an . There is one infinite monomorphic
block (the leaves of the wheel), and infinitely many finite ones (the center of the wheel, and
the edges of the matching). The age algebra is not finitely generated because G contains
as restriction the graph of Example A.4 whose age algebra is not finitely generated.
the electronic journal of combinatorics 20 (2013), #1

26

A.2

Examples coming from groups

We first look at orbital profiles. The fact that they are special cases of profiles is easy to
prove. In fact, for every permutation group G on a set E, there is a relational structure
R on E such that AutR = G (the topological closure of G in the symmetric group G(E),
equipped with the topology induced by the product topology on E E , E being equipped
with the discrete topology). In particular, θG (n) = ϕR (n) for all n. Oligomorphic groups
are quite common. Indeed, if E is denumerable, then G is oligomorphic if and only if
the complete theory of R is ℵ0 -categorical [RN59]. Cameron conjectured that the orbital
profile θG is polynomial (in the sense that θG (n) ∼ ank ) provided that it is bounded by
some polynomial. This particular consequence of Conjecture 1.3 has not been solved yet.
Example A.11. Let G be the trivial group on an m element set E. Set R := (E, u1 , . . . , um ),
where
 each ui is a unary relation defining the i-th element of E. Then, θG (n) = ϕR (n) =
m
.
n
Example A.12. Let G be the symmetric group SN , acting on the set of all pairs {i, j} of
{1, . . . , N } by σ({i, j}) = {σ(i), σ(j)}. Then, the orbits of G are the unlabelled graphs
on N vertices, counted by number of edges. In the age algebra, the product of two graphs
is the sum (with multiplicities) of all graphs that can be obtained by superposing them
without overlapping edges.
Example A.13. Let A be a finite alphabet with k elements, and let A∗ be the set of words
over A. Then each word can be viewed as a finite chain coloured by k colors. Hence
A∗ is the age of the relational structure R made of the chain Q of rational numbers
divided into k colors in such a way that, between two distinct rational numbers, all
colors appear. Furthermore, R is homogeneous in the sense that every local isomorphism
of R with finite domain extends to an automorphism of R, hence the set of orbits of
G := Aut(R) can be identified to A(R). As pointed out by Cameron [Cam97], the
age algebra KA(R) is isomorphic to the shuffle algebra over A, an important object in
algebraic combinatorics (see [Lot97]). A more sophisticated example of shuffle algebra is
presented in Subsection A.4.
Example A.14. Let G := Aut Q, where Q = (Q, ≤) is the chain of rational numbers. Then,
θG (n) = ϕQ (n) = 1 for all n. There is a single monomorphic block, and KA(R) ≈ K[x].
Example A.15. Let R := (Q, ≤, u1 , . . . , uk ), where Q is the chain of rational numbers, and
u1 , . . . , uk are k unary relations which divide Q into k non-trivial intervals E1 , . . . , Ek .
1
Then, ϕR (n) = n+k−1
and HR = (1−Z)
k . The Ei ’s are the monomorphic blocks and
k−1
KA(R) ≈ K[X].
Example A.16. Let G0 be the wreath product G0 := GoSN of a permutation group G acting
on {1, . . . , k} and of SN , the symmetric group on N. Looking at G0 as a permutation group
acting on E 0 := {1, . . . , k} × N, then G0 = AutR0 for some relational structure R0 on E 0 ;
moreover, for all n, θG0 (n) = ϕR0 (n). Among the possible R0 take R o N := (E 0 , ≡, (ρi )i∈I ),
where ≡ is {((i, n), (j, m)) ∈ E 02 : i = j}, ρi := {((x1 , m1 ), . . . , (xni , mni )) : (x1 , . . . , xni ) ∈
ρi , (m1 , . . . , mni ) ∈ Nni }, and R := ({1, . . . , k}, (ρi )i∈I ) is a relational structure having

the electronic journal of combinatorics 20 (2013), #1

27

signature µ := (ni )i∈I such that AutR = G. The relational structure R o N decomposes
into k monomorphic blocks, namely the equivalence classes of ≡.
As it turns out [Cam90], HRoN is the Hilbert series of the invariant ring K[X]G of G,
that is the subring of the polynomials in X which are invariant under the action of G.
In fact, the identification of the age algebra as a subring of K[X] gives an isomorphism
with K[X]G . As it is well known, this ring is Cohen-Macaulay, and the Hilbert series is
a rational fraction of the form given in Theorem 1.7, where the coefficients of P (Z) are
non-negative.
When G is the trivial group, one recovers the polynomial ring K[X], as in Example A.15.
Problem A.17. Find an example of a permutation group G0 with no finite orbit, such
that the orbital profile of G0 has polynomial growth, but the generating series is not the
Hilbert series of the invariant ring K[X]G of some permutation group G acting on a finite
set X.

A.3

Examples coming from permutation groupoids

Let X be a set. A local bijection of X is a bijective function f whose domain domf and
image imf are subsets of X. The inverse f −1 of a local bijection f , its restriction fX 0
to a subset X 0 of domf (with codomain f (X 0 )), and the composition f ◦ g of two local
bijections f and g such that img = domf are defined in the natural way. A set G of
local bijections of X is called a permutation groupoid if it contains the identity and is
stable by restriction, inverse, and composition. It is furthermore locally closed if a local
bijection f is in G whenever all its finite restrictions are. Obviously, the closure ↓G of
a permutation group G by restriction is a permutation groupoid. More interestingly, the
local isomorphisms of a relational structure form a locally closed permutation groupoid,
and reciprocally, any locally closed permutation groupoid G can be obtained from a suitable
relational structure RG on X.
The wreath product construction of an age algebra matching the invariant ring K[X]G
of a permutation group G (see Example A.16) can be extended straightforwardly to permutation groupoids. Many, but not all, properties of invariant rings of permutation groups
carry over (see Table 1 and [PT05, PT12]); in particular, the invariant ring is still a module
over symmetric functions, but not necessarily Cohen-Macaulay.
Examples A.18. Take n ∈ N ∪ {∞} and let G be the permutation groupoid of the strictly
increasing local bijections of {1, . . . , n}, or equivalently of the local isomorphisms of the
chain 1 < · · · < n. Then, K[X]G is the ring QSym(X) of quasi-symmetric polynomials
on the ordered alphabet X, as introduced by I. Gessel [Ges84]. As shown by F. Bergeron
Pn (Z)
and C. Reutenauer, HQSym(X) = (1−Z)(1−Z
2 )···(1−Z n ) , where the coefficients of Pn (Z) are
non negative. In fact, the ring is Cohen-Macalay [GW03].
Taking the same groupoid G, and letting it act naturally on respectively pairs, couples, k-subsets, or k-tuples of elements of {1, . . . , n}, yield respectively the (un)oriented
(hyper)graph quasi-symmetric polynomials of [NTT04].
the electronic journal of combinatorics 20 (2013), #1

28

The r-quasi symmetric polynomials [Hiv05] can be realized as well as the age algebra of
a relational structure (but not as the invariant ring of a permutation groupoid). Namely
start from the relational structure of Example A.2, and add another 2r-ary relation ρ
such that ρ(x1 , . . . , xr , y1 , . . . , yr ) holds if x1 , . . . , xr are distinct and in some block Ei
and y1 , . . . , yr are distinct and in some block Ej with i < j. For r = 1, one recovers the
relational structure giving quasi symmetric functions and for r = 0 the relational structure
giving symmetric polynomials.
Example A.19. Let G be the permutation groupoid on {1, 2, 3} generated by the local
bijection 1 7→ 2. Then, G is the restriction of the finite permutation group h(1, 2), (3, 4)i
whose invariant ring is Cohen-Macaulay. However, the age algebra K[X]G itself is not
Cohen-Macaulay. In fact, the numerator of the Hilbert series cannot be chosen with non2 −Z 3
, and the coefficient of highest degree
negative coefficients. Indeed, HK[X]G = 1−Z+2Z
(1−Z)3
in the product of the numerator by

A.4

(1−Z n1 )(1−Z n2 )(1−Z n3 )
(1−Z)3

is always −1.

Example: the shuffle algebra of planar tree polynomials

As a final example, and in order to illustrate the limits of monomorphic decompositions, we
consider the shuffle algebra of planar tree polynomials (K{x}∞ , ) which arises naturally
in the study of non associative analogues of the exponential and logarithm [DG04, Ger05].
We realize (K{x}∞ , ) as an age algebra, and show that the minimal monomorphic
decomposition of the underlying relational structure is trivial, and in particular infinite.
In this section, all trees are rooted, ordered, and unlabelled (in the papers cited above,
those trees are called planar ). A tree is reduced if all its internal nodes areSof arity at
least two. Let Ti be the set of all reduced trees with i leaves and set T := ∞
d=0 Td . By
convention, T0 contains the empty reduced tree with zero leaves. Denoting leaves by “◦”
and subtrees using parentheses, one has:
T1 = { ◦ },

T2 = { (◦, ◦) },

T3 = { (◦, (◦, ◦)), (◦, ◦, ◦), ((◦, ◦), ◦) } .

Those trees are counted by the sequence of Schröder numbers or super Catalan numbers
(#A001003 of [FI12]):
1, 1, 1, 3, 11, 45, 197, 903, 4279, 20793, 103049, ...
To each tree τ can be associated a canonical reduced tree red(τ ) by contracting all paths
in τ to suppress intermediate nodes of arity 1. Given a subset A of the leaves of τ , one
defines the contraction of τ on A as τA := red(τ 0 ), where τ 0 is the subtree induced by τ
on the set of all nodes of τ between the root and the leaves in A.
Lemma A.20. Let τ and τ 0 be two reduced trees with d leaves. Then, τ = τ 0 if and only
0
if the contractions τA and τA
are identical for any 3-subset A of the leaves.
Proof. The “only if” statement is obvious, and we turn to the “if” statement. For simplicity
we denote the leaves {1, . . . , d}. Consider an internal node of τ ; since τ is reduced, this
the electronic journal of combinatorics 20 (2013), #1

29

node is uniquely caracterized by the interval [i, j] formed by the leaves under it. We call
[i, j] a node interval. Note that a reduced tree is uniquely caracterized by the collection
of its node invervals. Note further that an interval [i, j] is a node interval if and only if:
• for k < i, the restriction τ{k,i,j} is the tree (◦, (◦, ◦)), and
• for k > j, the restriction τ{i,j,k} is the tree ((◦, ◦), ◦).
This concludes the proof.
We now construct a relational structure whose isomorphism types are given by the
reduced trees. Consider the infinite rooted ordered tree T such that each internal node
has infinitely many children, each alternatively a leaf or a copy of T (see Figure 1). Let
E be the set of leaves of T . To each finite subset A of E, we associate the reduced tree
TA obtained by contracting T on A as in the finite case (see the example in Figure 1).

Figure 1: Above: the infinite tree T ; in white, its internal nodes; in red and blue: its
leaves. Below: the reduced tree TA , where A is the set of blue leaves in T .
Let R be the relational structure obtained by endowing E with:
• the total order < induced by left-right infix order on T ;
the electronic journal of combinatorics 20 (2013), #1

30

• for each of the three reduced trees τ in T3 , the ternary relation
ρτ := {(x, y, z) : x < y < z and T{x,y,z} = τ } .
Note that the relational structure (E, <) is isomorphic to the chain of rationals.
Proposition A.21. The profile of R counts the reduced trees. Namely, A ≈ A0 if and
only if TA = TA0 , and any reduced tree τ ∈ T arises this way.
Proof. We need only to consider the case where A and A0 are of the same size d. Write
A = {x1 , . . . , xd } and A0 = {x01 , . . . , x0d } along the total order <. Take {i, j, k} a 3-subset
of leaves of TA (and of TA0 ). Thanks to the compatibility of contraction with <, one has
(TA ){i,j,k} = T{xi ,xj ,xk } and similarly for A0 . Therefore A and A0 are isomorphic if and
only if TA and TA0 have the same 3-leaf contractions. We conclude by reconstruction
using Lemma A.20.
For the last statement, choose any of the straightforward embeddings of τ in T .
Proposition A.22. The minimal monomorphic decomposition of R is trivial: each of its
monomorphic component is a singleton.
Proof. Since a subset of a monomorphic part is a monomorphic part (see Lemma 2.11),
it is sufficient to prove that there is no two-element monomorphic part. Take a < b in E.
In between a and b in T there is a full-blown copy of T . Thus, we can take two leaves
c, d of T with a < c < d < b such that c, d have a common ancestor which is neither an
ancestor of a nor of b. Then,
T{a,c,d} = (◦, (◦, ◦)) 6= ((◦, ◦), ◦) = T{b,c,d} .
Therefore {a, b} is not a monomorphic part.
Proposition A.23. The age algebra of R is isomorphic to the shuffle algebra of planar
tree polynomials (K{x}∞ , ).
Proof. Let τ, τ1 , τ2 be three reduced trees. The structure coefficient cττ1 ,τ2 is obtained by
taking any A such that τ = TA and counting the number of A1 ] A2 = A such that
τ1 = TA1 and τ2 = TA2 . This matches with the definition of the structure constants of
the shuffle product on planar tree polynomials (see [Ger05, Section 3]).

References
[AA05]

M. H. Albert and M. D. Atkinson. Simple permutations and pattern restricted
permutations. Discrete Math., 300(1-3):1–15, 2005.

[AAB07] M. H. Albert, M. D. Atkinson, and Robert Brignall. Permutation classes of
polynomial growth. Ann. Comb., 11(3-4):249–264, 2007.
the electronic journal of combinatorics 20 (2013), #1

31

[BBM07] József Balogh, Béla Bollobás, and Robert Morris. Hereditary properties of combinatorial structures: posets and oriented graphs. J. Graph Theory, 56(4):311–
332, 2007.
[BBSS09] József Balogh, Béla Bollobás, Michael Saks, and Vera T. Sós. The unlabelled
speed of a hereditary graph property. J. Combin. Theory Ser. B, 99(1):9–19,
2009.
[BHV08] Robert Brignall, Sophie Huczynska, and Vincent Vatter. Decomposing simple
permutations, with enumerative consequences. Combinatorica, 28(4):385–400,
2008.
[Bol98]

Béla Bollobás. Hereditary properties of graphs: asymptotic enumeration, global
structure, and colouring. In Proceedings of the International Congress of Mathematicians, Vol. III (Berlin, 1998), number Extra Vol. III, pages 333–342 (electronic), 1998.

[BP10]

Youssef Boudabbous and Maurice Pouzet. The morphology of infinite tournaments; application to the growth of their profile. European J. Combin.,
31(2):461–481, 2010.

[Cam90] Peter J. Cameron. Oligomorphic permutation groups, volume 152 of London
Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 1990.
[Cam97] Peter J. Cameron. The algebra of an age. In Model theory of groups and
automorphism groups (Blaubeuren, 1995), volume 244 of London Math. Soc.
Lecture Note Ser., pages 126–133. Cambridge Univ. Press, Cambridge, 1997.
[Cam09] Peter Cameron. Oligomorphic permutation groups. In Mohan Delampady N. S.
Narasimha Sastry, T. S. S. R. K. Rao and B. Rajeev, editors, Perspectives in
Mathematical Sciences II: Pure Mathematics, pages 37–61. World Scientific,
Singapore, 2009.
[CLO97] David Cox, John Little, and Donal O’Shea. Ideals, varieties, and algorithms.
Springer-Verlag, New York, second edition, 1997. An introduction to computational algebraic geometry and commutative algebra.
[DG04]

Vesselin Drensky and Lothar Gerritzen. Nonassociative exponential and logarithm. J. Algebra, 272(1):311–320, 2004.

[ET43]

P. Erdös and A. Tarski. On families of mutually exclusive sets. Ann. of Math.
(2), 44:315–329, 1943.

[FI12]

OEIS Foundation Inc. The on-line encyclopedia of integer sequences, 2012.

[FP71]

Roland Fraı̈ssé and Maurice Pouzet. Interprétabilité d’une relation pour une
chaı̂ne. C. R. Acad. Sci. Paris Sér. A-B, 272:A1624–A1627, 1971.

[Fra54]

Roland Fraı̈ssé. Sur quelques classifications des systèmes de relations. Publ.
Sci. Univ. Alger. Sér. A., 1:35–182 (1955), 1954.

the electronic journal of combinatorics 20 (2013), #1

32

[Fra65]

Claude Frasnay. Quelques problèmes combinatoires concernant les ordres totaux et les relations monomorphes. Ann. Inst. Fourier (Grenoble), 15(fasc.
2):415–524, 1965.
[Fra71]
Roland Fraı̈ssé. Cours de logique mathématique. Tome 1: Relation et formule
logique. Gauthier-Villars Éditeur, Paris, 1971. Deuxième édition revue et modifiée, Collection de “Logique Mathématique”, Série A, No. 23.
[Fra00]
Roland Fraı̈ssé. Theory of relations, volume 145 of Studies in Logic and the
Foundations of Mathematics. North-Holland Publishing Co., Amsterdam, revised edition, 2000. With an appendix by Norbert Sauer.
[Ger05] L. Gerritzen. Planar shuffle product, co-addition and the non-associative exponential. 2005. arXiv:math/0502378v1 [math.RA].
[Ges84] Ira M. Gessel. Multipartite P -partitions and inner products of skew Schur
functions. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of
Contemp. Math., pages 289–317. Amer. Math. Soc., Providence, RI, 1984.
[GW03] A. M. Garsia and N. Wallach. Qsym over Sym is free. J. Combin. Theory Ser.
A, 104(2):217–263, 2003.
[Hig52] Graham Higman. Ordering by divisibility in abstract algebras. Proc. London
Math. Soc. (3), 2:326–336, 1952.
[Hiv05] Florent Hivert. Local actions of the symmetric group and generalisations of
quasi-symmetric functions, 2005.
[KK03] Tomáš Kaiser and Martin Klazar. On growth rates of closed permutation
classes. Electron. J. Combin., 9(2):Research paper 10, 20 pp. (electronic),
2002/03. Permutation patterns (Otago, 2003).
[Kla08a] M. Klazar. Overview of some general results in combinatorial enumeration.
Arxiv preprint arXiv:0803.4292, 2008.
[Kla08b] Martin Klazar. On growth rates of permutations, set partitions, ordered graphs
and other objects. Electron. J. Combin., 15(1):Research Paper 75, 22, 2008.
[Lot97] M. Lothaire. Combinatorics on words. Cambridge Mathematical Library. Cambridge University Press, Cambridge, 1997. With a foreword by Roger Lyndon
and a preface by Dominique Perrin, Corrected reprint of the 1983 original, with
a new preface by Perrin.
[MT04] Adam Marcus and Gábor Tardos. Excluded permutation matrices and the
Stanley-Wilf conjecture. J. Combin. Theory Ser. A, 107(1):153–160, 2004.
[NTT04] Jean-Christophe Novelli, Jean-Yves Thibon, and Nicolas M. Thiéry. Algèbres
de Hopf de graphes. C. R. Math. Acad. Sci. Paris, 339(9):607–610, 2004.
doi:10.1016/j.crma.2004.09.012, arXiv:0812.3407v1 [math.CO].
[NW63] C. St. J. A. Nash-Williams. On well-quasi-ordering finite trees. Proc. Cambridge
Philos. Soc., 59:833–835, 1963.
[OP11]
Djamila Oudrar and Maurice Pouzet. Profile and hereditary classes of relational
structures. In H.Ait Haddadene, I.Bouchemakh, M.Boudar, and S.Bouroubi
the electronic journal of combinatorics 20 (2013), #1

33

(LAID3), editors, Proceedings ISOR’11, International Symposium on Operational Research, Algiers, Algeria, May 30-June 2, 2011.
[Pou72]

Maurice Pouzet. Un bel ordre d’abritement et ses rapports avec les bornes
d’une multirelation. C. R. Acad. Sci. Paris Sér. A-B, 274:A1677–A1680, 1972.

[Pou76]

Maurice Pouzet. Application d’une propriété combinatoire des parties d’un
ensemble aux groupes et aux relations. Math. Z., 150(2):117–134, 1976.

[Pou78]

Maurice Pouzet. Sur la théorie des relations. PhD thesis, Thèse d’état, Université Claude-Bernard, Lyon 1, 1978.

[Pou79]

Maurice Pouzet. Relation minimale pour son âge. Z. Math. Logik Grundlag.
Math., 25(4):315–344, 1979.

[Pou80]

Maurice Pouzet. The asymptotic behavior of a class of counting functions. In
M. Deza and I. G. Rosenberg, editors, Combinatorics 79. Part II, Proceedings
of the Colloquium held at the University of Montréal, Montreal, Que., June
11–16, 1979, volume 9, pages 223–224. Elsevier, 1980.

[Pou81a] M. Pouzet. Relations impartibles. Dissertationes Math. (Rozprawy Mat.),
193:43, 1981.
[Pou81b] Maurice Pouzet. Application de la notion de relation presque-enchaı̂nable au
dénombrement des restrictions finies d’une relation. Z. Math. Logik Grundlag.
Math., 27(4):289–332, 1981.
[Pou06]

Maurice Pouzet. The profile of relations. Glob. J. Pure Appl. Math., 2(3):237–
272, 2006.

[Pou08]

Maurice Pouzet. When is the orbit algebra of a group an integral domain?
Proof of a conjecture of P. J. Cameron. Theor. Inform. Appl., 42(1):83–103,
2008.

[PS01]

Maurice Pouzet and Mohamed Sobrani. Sandwiches of ages. In Proceedings of
the XIth Latin American Symposium on Mathematical Logic (Mérida, 1998),
volume 108, pages 295–326, 2001.

[PT05]

Maurice Pouzet and Nicolas M. Thiéry. Some relational structures with polynomial growth and their associated algebras. In Proceedings of FPSAC’05
Taormina, 2005. arXiv:0601256 [math.CO].

[PT08]

Maurice Pouzet and Nicolas M. Thiéry. Some relational structures with polynomial growth and their associated algebras. In Youssef Boudabbous and Nejib
Zaguia, editors, ROGICS’08: International Conference on Relations, Orders
and Graphs: Interaction with Computer Science, 12-17 may, 2008 Mahdia,
Tunisia. Nouha, 2008. arXiv:0801.4404v1 [math.CO].

[PT12]

Maurice Pouzet and Nicolas M. Thiéry. Some relational structures with polynomial growth and their associated algebras II: Finite generation. 2012. In
preparation, 20 pages.

[RN59]

C. Ryll-Nardzewski. On the categoricity in power ≤ ℵ0 . Bull. Acad. Polon.
Sci. Sér. Sci. Math. Astr. Phys., 7:545–548. (unbound insert), 1959.

the electronic journal of combinatorics 20 (2013), #1

34

[Sch90]

James H. Schmerl. Coinductive ℵ0 -categorical theories. J. Symbolic Logic,
55(3):1130–1137, 1990.

[SF96]

R. Sedgewick and P. Flajolet. Analysis of algorithms. Addison Wesley, 42:192,
1996.

[Sta97]

Richard P. Stanley. Enumerative combinatorics. Vol. 1, volume 49 of Cambridge
Studies in Advanced Mathematics. Cambridge University Press, Cambridge,
1997. With a foreword by Gian-Carlo Rota, Corrected reprint of the 1986
original.

[TT04]

Nicolas M. Thiéry and Stéphan Thomassé. Convex cones and SAGBI bases of
permutation invariants. In Invariant theory in all characteristics, volume 35 of
CRM Proc. Lecture Notes, pages 259–263. Amer. Math. Soc., Providence, RI,
2004. arXiv:0607380 [].

[Vat11]

V. Vatter. Small permutation classes. Proceedings of the London Mathematical
Society, 103(5):879–921, 2011. arXiv:0712.4006.

[vLW92] J. H. van Lint and R. M. Wilson. A course in combinatorics. Cambridge
University Press, Cambridge, 1992.

the electronic journal of combinatorics 20 (2013), #1

35

