Hereditary properties of partitions, ordered graphs and ordered hypergraphs
From MaRDI portal
Abstract: In this paper we use the Klazar-Marcus-Tardos method to prove that if a hereditary property of partitions P has super-exponential speed, then for every k-permutation pi, P contains the partition of [2k] with parts {i, pi(i) + k}, where 1 <= i <= k. We also prove a similar jump, from exponential to factorial, in the possible speeds of monotone properties of ordered graphs, and of hereditary properties of ordered graphs not containing large complete, or complete bipartite ordered graphs. Our results generalize the Stanley-Wilf Conjecture on the number of n-permutations avoiding a fixed permutation, which was recently proved by the combined results of Klazar and of Marcus and Tardos. Our main results follow from a generalization to ordered hypergraphs of the theorem of Marcus and Tardos.
Recommendations
Cites work
- A jump to the Bell number for hereditary graph properties
- Counting \(H\)-free graphs
- Counting pattern-free set partitions. I: A generalization of Stirling numbers of the second kind
- Davenport-Schinzel theory of matrices
- Excluded permutation matrices and the Stanley-Wilf conjecture
- Excluding Induced Subgraphs III: A General Asymptotic
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Extremal Graph Problems for Graphs with a Color-Critical Vertex
- Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring
- scientific article; zbMATH DE number 3557819 (Why is no real title available?)
- scientific article; zbMATH DE number 1504588 (Why is no real title available?)
- scientific article; zbMATH DE number 970795 (Why is no real title available?)
- K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
- On 0-1 matrices and small excluded submatrices
- On extremal problems of graphs and generalized graphs
- On the asymptotic structure of sparse triangle free graphs
- On the entropy values of hereditary classes of graphs
- On the number of graphs without 4-cycles
- On the size of hereditary classes of graphs
- On the Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- Projections of Bodies and Hereditary Properties of Hypergraphs
- The asymptotic number of graphs not containing a fixed subgraph and a problem for hypergraphs having no exponent
- The number of graphs without forbidden subgraphs
- The speed of hereditary properties of graphs
Cited in
(19)- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- A characterization and hereditary properties for partition graphs
- Shadows of ordered graphs
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Jumps in speeds of hereditary properties in finite relational languages
- Hereditary properties of ordered graphs
- Forbidden configurations and product constructions
- Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
- Formal structure of periodic system of elements
- Hereditary classes of ordered binary structures
- A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
- The structure of almost all graphs in a hereditary property
- Embedding dualities for set partitions and for relational structures
- Well-quasi-ordering and Embeddability of Relational Structures
- Hereditary classes of ordered sets of width at most two
- Foot-sorting for socks
- Ordered structures with no finite monomorphic decomposition: application to the profile of hereditary classes
- Consistent random vertex-orderings of graphs
- Twin-width. IV: Ordered graphs and matrices
This page was built for publication: Hereditary properties of partitions, ordered graphs and ordered hypergraphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q850077)
