Quasi-polynomiality conjecture for profiles of bounded-signature structures

From papers

Let RR be a relational structure. Its profile φR(n)\varphi_R(n) counts the isomorphism types of substructures induced on the nn-element subsets of RR. Say that RR has bounded signature when the arities of the relations in its signature are uniformly bounded, and let the kernel of RR denote the set of elements that do not belong to any infinite monomorphic block. Assume either that RR has bounded signature or that its kernel is finite.

Quasi-polynomiality conjecture. If φR\varphi_R is bounded by some polynomial, then φR\varphi_R is eventually a quasi-polynomial.

The kernel condition is motivated by structural results relating polynomially bounded profiles to finite kernels, while examples show that finite generation of the associated age algebra need not follow from polynomial growth. Eventual quasi-polynomiality would imply strong polynomial growth, but the conjecture is presented as unresolved.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Maurice Pouzet and Nicolas M. Thiéry, “Some relational structures with polynomial growth and their associated algebras I: Quasi-polynomiality of the profile”, arXiv:1402.3090 (2014).

Solutions 0

No solutions have been posted yet.