Profile and Hereditary Classes of Ordered Relational Structures
Djamila Oudrar and Maurice Pouzet
Let ℭ be a class of finite combinatorial structures. The profile of ℭ is the function ϕℭ which counts, for every integer n, the number ϕℭ(n) of members of ℭ defined on n elements, isomorphic structures been identified. The generating series of ℭ is ℋℭ(x) := ∑ n≧0 ϕℭ(n)xn. Many results about the behavior of the function ϕℭ 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.
2000 Mathematics Subject Classification: 05C30, 06F99, 05A05, 03C13.
Keywords: Ordered set, well quasi-ordering, relational structures, profile, indecomposability, graphs, tournaments, permutations.