Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile (Q1953475)

Summary: The profile of a relational structure \(R\) is the function \(\phi_R\) which counts for every integer \(n\) the number \(\phi_R(n)\), possibly infinite, of substructures of \(R\) induced on the \(n\)-element subsets, isomorphic substructures being identified. If \(\phi_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 \(\phi_R\) is eventually a quasi-polynomial, this supporting the conjecture that, under mild assumptions on \(R, \phi_R\) is eventually a quasi-polynomial when it is bounded by some polynomial.