Some relational structures with polynomial growth and their associated algebras

Abstract

The profile of a relational structure R is the function phi_R which counts for every integer n the number, possibly infinite, phi_R(n) of substructures of R induced on the n-element subsets, isomorphic substructures being identified. Several graded algebras can be associated with R in such a way that the profile of R is simply the Hilbert function. An example of such graded algebra is the age algebra introduced by P.~J.~Cameron. In this paper, we give a closer look at this association, particularly when the relational structure R decomposes into finitely many monomorphic components. In this case, several well-studied graded commutative algebras (e.g. the invariant ring of a finite permutation group, the ring of quasi-symmetric polynomials) are isomorphic to some age algebras. Also, phi_R is a quasi-polynomial, this supporting the conjecture that, with mild assumptions on R, phi_R is a quasi-polynomial when it is bounded by some polynomial.

20 pages. Presented at FPSAC'05 Taormina, June 2005

References in corpus (1)

• The Profile of relations

Cited by in corpus (8)

• Overview of some general results in combinatorial enumeration
• The Profile of relations
• The morphology of infinite tournaments. Application to the growth of their profile
• Siblings of countable cographs
• Generalizations of Khovanskii's theorems on growth of sumsets in abelian semigroups
• When the orbit algebra of group is an integral domain? Proof of a conjecture of P.J. Cameron
• Grid classes and the Fibonacci dichotomy for restricted permutations
• Algèbre combinatoire et effective: des graphes aux algèbres de Kac, via l'exploration informatique