Hereditary classes of ordered binary structures

DOI10.21494/ISTE.OP.2020.0542MaRDI QIDQ6136170FDOQ6136170

Authors Djamila Oudrar

Publication date 28 August 2023

Published in Advances in Pure and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

profileordered setordered graphswell quasi-orderingmonomorphic decompositionordered binary relational structures

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Planar graphs; geometric and topological aspects of graph theory (05C10) Model theory of finite structures (03C13) Ordered structures (06F99)

Abstract: Balogh, Bollob'{a}s and Morris (2006) have described a threshold phenomenon in the behavior of the profile of hereditary classes of ordered graphs. In this paper, we give an other look at their result based on the notion of monomorphic decomposition of a relational structure introduced in cite{P-T-2013}. We prove that the class $mathfrakS$ of ordered binary structures which do not have a finite monomorphic decomposition has a finite basis (a subset $mathfrakA$ such that every member of $mathfrakS$ embeds some member of $mathfrakA$). In the case of ordered reflexive directed graphs, the basis has 1242 members and the profile of their ages grows at least as the Fibonacci function. From this result, we deduce that the following dichotomy property holds for every hereditary class $mathfrakC$ of finite ordered binary structures of a given finite type. Either there is an integer $ell$ such that every member of $mathfrakC$ has a monomorphic decomposition into at most $ell$ blocks and in this case the profile of $mathfrakC$ is bounded by a polynomial of degree $ell-1$ (and in fact is a polynomial), or $mathfrakC$ contains the age of a structure which does not have a finite monomorphic decomposition, in which case the profile of $mathfrakC$ is bounded below by the Fibonacci function.

Recommendations

• Profile and hereditary classes of ordered relational structures
• Structure of hereditary orders
• On the structure of hereditary classes of graphs
• Hereditary properties of ordered graphs
• Hereditary and monotone properties of combinatorial structure
• scientific article; zbMATH DE number 3323940
• THE LATTICE STRUCTURE OF HEREDITARY PRETORSION CLASSES
• scientific article; zbMATH DE number 3841924
• Hereditary semiorders and enumeration of semiorders by dimension
• A hierarchy of hereditarily finite sets

Cites work

• scientific article; zbMATH DE number 3400958 (Why is no real title available?)
• scientific article; zbMATH DE number 3198033 (Why is no real title available?)
• scientific article; zbMATH DE number 4183470 (Why is no real title available?)
• Application d'une propriété combinatoire des parties d'un ensemble aux groupes et aux rélations
• Application de la Notion de Relation Presque‐Enchainable au Denombrement des Restrictions Finies D'une Relation
• Chains in Ehrenfeucht Mostowski models
• Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Hereditary properties of ordered graphs
• Hereditary properties of partitions, ordered graphs and ordered hypergraphs
• Hereditary properties of tournaments
• Homogeneous permutations
• Isomorphy up to complementation
• On families of mutually exclusive sets
• On growth rates of closed permutation classes
• On growth rates of permutations, set partitions, ordered graphs and other objects
• Ordering by Divisibility in Abstract Algebras
• Overview of some general results in combinatorial enumeration
• Permutation classes
• Profile and hereditary classes of ordered relational structures
• Quelques problèmes combinatoires concernant les ordres totaux et les rélations monomorphes
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• The morphology of infinite tournaments; application to the growth of their profile
• The profile of relations
• The unlabelled speed of a hereditary graph property
• Theory of relations. Transl. from the French by P. Clote
• Une extension d'un théorème de P. Jullien sur les âges de mots

Cited in

(4)

• Algebras, Graphs and Ordered Sets – ALGOS 2020 & the Mathematical Contributions of Maurice Pouzet
• Well-quasi-ordering and Embeddability of Relational Structures
• scientific article; zbMATH DE number 3323940 (Why is no real title available?)
• Structure of hereditary orders

This page was built for publication: Hereditary classes of ordered binary structures

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