In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums. Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142; they are also the permutations whose permutation graphs are cographs and the permutations that realize the series-parallel partial orders. It is possible to test in polynomial time whether a given separable permutation is a pattern in a larger permutation, or to find the longest common subpattern of two separable permutations.
Definition and characterization
Bose, Buss & Lubiw (1998) define a separable permutation to be a permutation that has a separating tree: a rooted binary tree in which the elements of the permutation appear (in permutation order) at the leaves of the tree, and in which the descendants of each tree node form a contiguous subset of these elements. Each interior node of the tree is either a positive node in which all descendants of the left child are smaller than all descendants of the right node, or a negative node in which all descendants of the left node are greater than all descendants of the right node. There may be more than one tree for a given permutation: if two nodes that are adjacent in the same tree have the same sign, then they may be replaced by a different pair of nodes using a tree rotation operation. Each subtree of a separating tree may be interpreted as itself representing a smaller separable permutation, whose element values are determined by the shape and sign pattern of the subtree. A one-node tree represents the trivial permutation, a tree whose root node is positive represents the direct sum of permutations given by its two child subtrees, and a tree whose root node is negative represents the skew sum of the permutations given by its two child subtrees. In this way, a separating tree is equivalent to a construction of the permutation by direct and skew sums, starting from the trivial permutation. As Bose, Buss & Lubiw (1998) prove, separable permutations may also be characterized in terms of permutation patterns: a permutation is separable if and only if it contains neither 2413 nor 3142 as a pattern. The separable permutations also have a characterization from algebraic geometry: if a collection of distinct real polynomials all have equal values at some number x, then the permutation that describes how the numerical ordering of the polynomials changes at x is separable, and every separable permutation can be realized in this way.
Combinatorial enumeration The separable permutations are enumerated by the Schröder numbers. That is, there is one separable permutation of length one, two of length two, and in general the number of separable permutations of a given length (starting with length one) is
1, 2, 6, 22, 90, 394, 1806, 8558, .... (sequence A006318 in the OEIS) This result was proven for a class of permutation matrices equivalent to the separable permutations by Shapiro & Stephens (1991), by using a canonical form of the separating tree in which the right child of each node has a different sign than the node itself and then applying the theory of generating functions to these trees. Another proof applying more directly to separable permutations themselves, was given by West (1995).
Algorithms Bose, Buss & Lubiw (1998) showed that it is possible to determine in polynomial time whether a given separable permutation is a pattern in a larger permutation, in contrast to the same problem for non-separable permutations, which is NP-complete. The problem of finding the longest separable pattern that is common to a set of input permutations may be solved in polynomial time for a fixed number of input permutations, but is NP-hard when the number of input permutations may be variable, and remains NP-hard even when the inputs are all themselves separable.
History Separable permutations first arose in the work of Avis & Newborn (1981), who showed that they are precisely the permutations which can be sorted by an arbitrary number of pop-stacks in series, where a pop-stack is a restricted form of stack in which any pop operation pops all items at once. Shapiro & Stephens (1991) considered separable permutations again in their study of bootstrap percolation, a process in which an initial permutation matrix is modified by repeatedly changing to one any matrix coefficient that has two or more orthogonal neighbors equal to one. As they show, the class of permutations that are transformed by this process into the all-one matrix is exactly the class of separable permutations. The term "separable permutation" was introduced later by Bose, Buss & Lubiw (1998), who considered them for their algorithmic properties.
Related structures
… excerpt ends here. Continue reading the full article.
