Pattern avoidance classes and subpermutations (Q2583660)

The paper under review gives a structural theorem for classes of permutations defined by their avoiding a given set of permutation patterns. The authors call a pattern-avoidance class atomic if it cannot be expressed as a union of proper subclasses. They show that the atomic classes are precisely the classes that arise as the set of restrictions of some injection from one ordered set to another. The main theorem is a characterization of such injection and classes in the case when the order types are those of the natural numbers.