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

graphsindecomposabilityordered setpermutationsprofilerelational structurestournamentswell quasi-ordering

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Enumeration in graph theory (05C30) Partial orders, general (06A06) 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

(11)

• Structure and enumeration theorems for hereditary properties in finite relational languages
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Pairs of orthogonal countable ordinals
• Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
• The profile of relations
• Hereditary classes of ordered binary structures
• Embedding dualities for set partitions and for relational structures
• Hereditary classes of ordered sets of width at most two
• Minimal prime ages, words and permutation graphs
• Ordered structures with no finite monomorphic decomposition: application to the profile of hereditary classes
• Systems of ideals parameterized by combinatorial structures

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)