FORBIDDEN SUBSEQUENCES

The classification of sets of permutations with forbidden subsequences of length 4 is not yet complete. (In my recent paper Classification of forbidden subsequences of length 4 submitted to European Journal of Combinatorics, Paris, this classification has been completed.) In this paper we show that \S(n)(4132)1=\S(n)(3142)\ by proving the stronger theorem for the corresponding permutation trees: T(4132) congruent-to T(3142). We give a new proof of the so-called Schroder result, some results on forbidding entire classes of symmetries of permutation matrices, and some conjectures concerning the basic question: for what permutations T and sigma it is true that \S(n)(tau)\ = \S(n)(sigma)\ for all n is-an-element-of N. We also discuss possible attacks on cases similar to the Schroder result by 'visualizing' the structure of the corresponding permutations and generalize the method of permutation trees.