Klazar, Martin

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

Electron. J. Comb. 15(1), Research Paper R75, 22 p. (2008)


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.

Mathematics Subject Classification

05A16, 0530