On growth rates of permutations, set partitions, ordered graphs and other objects (Q1010798): Difference between revisions

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.