Hereditary classes of ordered binary structures

DOI10.21494/ISTE.OP.2020.0542arXiv1901.09363MaRDI QIDQ6136170FDOQ6136170

Authors: Djamila Oudrar 

Publication date: 28 August 2023

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

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.

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

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
• Hereditary semiorders and enumeration of semiorders by dimension
• A hierarchy of hereditarily finite sets

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)

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• Structure of hereditary orders
• Algebras, Graphs and Ordered Sets – ALGOS 2020 & the Mathematical Contributions of Maurice Pouzet
• Well-quasi-ordering and Embeddability of Relational Structures

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)