Hereditary properties of combinatorial structures: Posets and oriented graphs

DOI10.1002/JGT.20266MaRDI QIDQ5434263zbMATH OpenOpenAlexFDO

Authors József Balogh, Béla Bollobás, Robert Morris

Publication date 4 January 2008

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

hereditary propertyposettournament

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Combinatorics of partially ordered sets (06A07)

Abstract: A hereditary property of combinatorial structures is a collection of structures (e.g. graphs, posets) which is closed under isomorphism, closed under taking induced substructures (e.g. induced subgraphs), and contains arbitrarily large structures. Given a property P, we write P_n for the collection of distinct (i.e., non-isomorphic) structures in a property P with n vertices, and call the function n -> |P_n| the speed (or unlabelled speed) of P. Also, we write P^n for the collection of distinct labelled structures in P with vertices labelled 1,...,n, and call the function n -> |P^n| the labelled speed of P. The possible labelled speeds of a hereditary property of graphs have been extensively studied, and the aim of this paper is to investigate the possible speeds of other combinatorial structures, namely posets and oriented graphs. More precisely, we show that (for sufficiently large n), the labelled speed of a hereditary property of posets is either 1, or exactly a polynomial, or at least 2^n - 1. We also show that there is an initial jump in the possible unlabelled speeds of hereditary properties of posets, tournaments and directed graphs, from bounded to linear speed, and give a sharp lower bound on the possible linear speeds in each case.

Recommendations

• Hereditary and monotone properties of combinatorial structure
• On the size of hereditary classes of graphs
• The penultimate rate of growth for graph properties
• The speed of hereditary properties of graphs
• Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring

Cites work

• Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
• Hereditary properties of ordered graphs
• Hereditary properties of tournaments
• The average number of linear extensions of a partial order

Cited in

(12)

• Structure and enumeration theorems for hereditary properties in finite relational languages
• Hereditarily odd-even and combinatorial isols.
• Comparison theorems in hereditary structures and applications
• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• On the structure of oriented graphs and digraphs with forbidden tournaments or cycles
• Jumps in speeds of hereditary properties in finite relational languages
• Hereditary properties of ordered graphs
• scientific article; zbMATH DE number 5704233 (Why is no real title available?)
• scientific article; zbMATH DE number 4116592 (Why is no real title available?)
• The penultimate rate of growth for graph properties
• A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
• Well-quasi-ordering and Embeddability of Relational Structures

This page was built for publication: Hereditary properties of combinatorial structures: Posets and oriented graphs

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