Profile and hereditary classes of ordered relational structures

zbMATH Open1393.05036arXiv1409.1108MaRDI QIDQ4583889FDOQ4583889

Authors: Djamila Oudrar, Maurice Pouzet 

Publication date: 3 September 2018

Abstract: Let $mathfrakC$ be a class of finite combinatorial structures. The extit{profile} of $mathfrakC$ is the function $varph{i}_{mathfrakC}$ which counts, for every integer $n$, the number $varph{i}_{mathfrakC}(n)$ of members of $mathfrakC$ defined on $n$ elements, isomorphic structures been identified. The extit{generating function of} $mathfrakC$ is $mathcal{H}_{mathfrakC}(x):=su{m}_{ngeqq0}varph{i}_{mathfrakC}(n)x^n$. Many results about the behavior of the function $varph{i}_{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.

Full work available at URL: https://arxiv.org/abs/1409.1108

Recommendations

• The profile of relations
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
• Profile classes and partial well-order for permutations
• On growth rates of permutations, set partitions, ordered graphs and other objects

zbMATH Keywords

permutationsgraphsprofileordered settournamentsindecomposabilityrelational structureswell quasi-ordering

Mathematics Subject Classification ID

Partial orders, general (06A06) Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Combinatorics of partially ordered sets (06A07)

Cited In (8)

• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Pairs of orthogonal countable ordinals
• Hereditary classes of ordered sets of width at most two
• Structure and enumeration theorems for hereditary properties in finite relational languages
• Hereditary classes of ordered binary structures
• Embedding dualities for set partitions and for relational structures
• Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
• The profile of relations

This page was built for publication: Profile and hereditary classes of ordered relational structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4583889)