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
- 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?)
- 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
- 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 Stanley-Wilf conjecture for the number of permutations avoiding a given pattern
- 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
- 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
(16)- Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings
- Hereditary classes of ordered sets of width at most two
- Jumps in speeds of hereditary properties in finite relational languages
- The structure of almost all graphs in a hereditary property
- Hereditary classes of ordered binary structures
- Shadows of ordered graphs
- A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
- Extensions of the linear bound in the Füredi-Hajnal conjecture
- Foot-sorting for socks
- A characterization and hereditary properties for partition graphs
- Formal structure of periodic system of elements
- Embedding dualities for set partitions and for relational structures
- Forbidden configurations and product constructions
- Well-quasi-ordering and Embeddability of Relational Structures
- Some relational structures with polynomial growth and their associated algebras. II: Finite generation.
- Hereditary properties of ordered graphs
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)
