On growth rates of permutations, set partitions, ordered graphs and other objects

zbMATH Open1163.05308arXivmath/0703047MaRDI QIDQ1010798FDOQ1010798

Authors: Martin Klazar 

Publication date: 7 April 2009

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: For classes O of structures on finite linear orders (permutations, ordered graphs etc.) endowed with containment order cont (containment of permutations, subgraph relation etc.), we investigate restrictions on the function f(n) counting objects with size n in a lower ideal in (O, cont). We present a framework of edge P-colored complete graphs (C(P), cont) which includes many of these situations, and we prove for it two such restrictions (jumps in growth): f(n) is eventually constant or f(n) >= n for all n>0; f(n)<n^c for all n>0 for a constant c>0 or f(n) >= F_n for all n>0, F_n being the Fibonacci numbers. This generalizes a fragment of a more detailed theorem of Balogh, Bollobas and Morris on hereditary properties of ordered graphs.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Hereditary properties of ordered graphs
• On the size of hereditary classes of graphs
• The penultimate rate of growth for graph properties
• Growth rates of permutation classes: from countable to uncountable
• Small permutation classes

zbMATH Keywords

containment orderfinite linear ordersjumps in the growth of combinatorial structures

Mathematics Subject Classification ID

Asymptotic enumeration (05A16) Enumeration in graph theory (05C30)

Cited In (8)

• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Hereditary classes of ordered binary structures
• Growth constants of minor-closed classes of graphs
• Counting ordered graphs that avoid certain subgraphs
• Shadows of ordered graphs
• PERMUTATION CLASSES OF EVERY GROWTH RATE ABOVE 2.48188
• A jump to the Narayana number for hereditary properties of ordered 3-uniform hypergraphs
• Profile and hereditary classes of ordered relational structures

This page was built for publication: On growth rates of permutations, set partitions, ordered graphs and other objects

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