Hereditary properties of partitions, ordered graphs and ordered hypergraphs

Details Hereditary properties of partitions, ordered graphs and ordered hypergraphs Hereditary properties of partitions, ordered graphs and ordered hypergraphs

2007-02-13

arxiv.org/abs/math/0702351v1

European Journal of Combinatorics (special edition, eds. M. Krivelevich and B. Sudakov), 8 (2006), 1263-1281

Mathematics

Combinatorics

25 pgs, no figures

Scientific paper

In this paper we use the Klazar-Marcus-Tardos method to prove that if a hereditary property of partitions P has super-exponential speed, then for every k-permutation pi, P contains the partition of [2k] with parts {i, pi(i) + k}, where 1 <= i <= k. We also prove a similar jump, from exponential to factorial, in the possible speeds of monotone properties of ordered graphs, and of hereditary properties of ordered graphs not containing large complete, or complete bipartite ordered graphs. Our results generalize the Stanley-Wilf Conjecture on the number of n-permutations avoiding a fixed permutation, which was recently proved by the combined results of Klazar and of Marcus and Tardos. Our main results follow from a generalization to ordered hypergraphs of the theorem of Marcus and Tardos.

Affiliated with

Also associated with

No associations

Rating

Hereditary properties of partitions, ordered graphs and ordered hypergraphs 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 Hereditary properties of partitions, ordered graphs and ordered hypergraphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Hereditary properties of partitions, ordered graphs and ordered hypergraphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-409716