Small permutation classes

Details Small permutation classes Small permutation classes

2007-12-24

arxiv.org/abs/0712.4006v2

Mathematics

Combinatorics

Scientific paper

We establish a phase transition for permutation classes (downsets of permutations under the permutation containment order): there is an algebraic number $\kappa$, approximately 2.20557, for which there are only countably many permutation classes of growth rate (Stanley-Wilf limit) less than $\kappa$ but uncountably many permutation classes of growth rate $\kappa$, answering a question of Klazar. We go on to completely characterize the possible sub-$\kappa$ growth rates of permutation classes, answering a question of Kaiser and Klazar. Central to our proofs are the concepts of generalized grid classes (introduced herein), partial well-order, and atomicity (also known as the joint embedding property).

Affiliated with

Also associated with

No associations

Rating

Small permutation classes 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 Small permutation classes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Small permutation classes will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-165555