Hereditary properties of combinatorial structures: Posets and oriented graphs

DOI10.1002/JGT.20266zbMATH Open1135.05024arXivmath/0702350OpenAlexW2950647997MaRDI QIDQ5434263FDOQ5434263

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)

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.

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

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

zbMATH Keywords

hereditary propertyposettournament

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

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

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)