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

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

2007-03-01

arxiv.org/abs/math/0703047v1

Mathematics

Combinatorics

20 pages, submitted to Electr. J. Combin

Scientific paper

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)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.

Affiliated with

Also associated with

No associations

Rating

On growth rates of permutations, set partitions, ordered graphs and other objects does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On growth rates of permutations, set partitions, ordered graphs and other objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On growth rates of permutations, set partitions, ordered graphs and other objects will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-284769