Profile and hereditary classes of ordered relational structures

2014/09/03 by Oudrar, Djamila, Pouzet, Maurice
#03C13 #05A05 #05C30 #06F99 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1409.1108

Abstract

Let \mathfrakC be a class of finite combinatorial structures. The profile of \mathfrakC is the function φ_\mathfrakC which counts, for every integer n, the number φ_\mathfrakC(n) of members of \mathfrakC defined on n elements, isomorphic structures been identified. The generating function of \mathfrakC is \mathcal H_\mathfrakC(x):=∑_{n\geqq 0}φ_\mathfrakC(n)xⁿ. Many results about the behavior of the function φ_\mathfrakC have been obtained. Albert and Atkinson have shown that the generating series of several classes of permutations are algebraic. In this paper, we show how their results extend to classes of ordered binary relational structures; putting emphasis on the notion of hereditary well quasi order, we discuss some of their questions and answer one.

Related

• Sur l' 'enum 'eration de structures discr `etes, une approche par la\n th 'eorie des relations
• Ordered structures with no finite monomorphic decomposition. Application to the profile of hereditary classes
• Décomposition monomorphe des structures relationnelles et profil de classes héréditaires
• The Profile of relations
• Hereditary classes of ordered binary structures