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

### Summary

Summary: For classes O of structures on finite linear orders (permutations, ordered graphs etc.) endowed with containment order (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, ). We present a framework of edge P -colored complete graphs $(C(P )$, ) 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$nc for all n $\geq 1$ for a constant c > 0 or f (n) $\geq$Fn for all n $\geq 1$, Fn being the Fibonacci numbers. This generalizes a fragment of a more detailed theorem of Balogh, Bollob$\acute$as and Morris on hereditary properties of ordered graphs.

05A16, 0530