On growth rates of permutations, set partitions, ordered graphs and other objects (Q1010798): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: math/0703047 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 19:33, 18 April 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On growth rates of permutations, set partitions, ordered graphs and other objects |
scientific article |
Statements
On growth rates of permutations, set partitions, ordered graphs and other objects (English)
0 references
7 April 2009
0 references
Summary: For classes \({\mathcal O}\) of structures on finite linear orders (permutations, ordered graphs etc.) endowed with containment order \(\preceq\) (containment of permutations, subgraph relation etc.), we investigate restrictions on the function \(f(n)\) counting objects with size \(n\) in a lower ideal in \(({\mathcal O},\preceq)\). We present a framework of edge \(P\)-colored complete graphs \(({\mathcal C}(P),\preceq)\) 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)\geq n\) for all \(n\geq 1; f(n)\leq n^c\) for all \(n\geq 1\) for a constant \(c>0\) or \(f(n)\geq F_n\) for all \(n\geq 1, F_n\) being the Fibonacci numbers. This generalizes a fragment of a more detailed theorem of \textit{J. Balogh}, \textit{B. Bollobás}, and \textit{R. Morris} [Eur. J. Comb. 27, No.\,8, 1263--1281 (2006; Zbl 1114.05068)] on hereditary properties of ordered graphs.
0 references
jumps in the growth of combinatorial structures
0 references
finite linear orders
0 references
containment order
0 references