Profile and hereditary classes of ordered relational structures

MaRDI QIDQ4583889zbMATH OpenFDO

Authors Djamila Oudrar, Maurice Pouzet

Publication date 3 September 2018

Full work available at URL https://arxiv.org/abs/1409.1108, http://www.oldcitypublishing.com/journals/mvlsc-home/mvlsc-issue-contents/mvlsc-volume-27-number-5-6-2016/mvlsc-27-5-6-p-475-500/

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)

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.

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

Cited in

(8)

• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Pairs of orthogonal countable ordinals
• Structure and enumeration theorems for hereditary properties in finite relational languages
• Hereditary classes of ordered sets of width at most two
• 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)