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

MaRDI QIDQ1010798zbMATH OpenFDO

Authors Martin Klazar

Publication date 7 April 2009

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

Full work available at URL https://arxiv.org/abs/math/0703047, https://eudml.org/doc/129975, http://www.emis.de/journals/EJC/Volume_15/Abstracts/v15i1r75.html

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

zbMATH Keywords

containment orderfinite linear ordersjumps in the growth of combinatorial structures

Mathematics Subject Classification ID

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

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.

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

Cited in

(8)

• Some relational structures with polynomial growth and their associated algebras. I: Quasi-polynomiality of the profile
• Growth constants of minor-closed classes of graphs
• Hereditary classes of ordered binary structures
• 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)