In
combinatorial
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
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 pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
s 2413 and 3142;
[; , Theorem 2.2.36, p. p.58.] they are also the permutations whose
permutation graph
In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be ...
s are
cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s 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
![Large_separable_permutation_small](https://upload.wikimedia.org/wikipedia/commons/8/81/Large_separable_permutation_small.png)
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
In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape ...
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 In combinatorics, the skew sum and direct sum of permutations are two operations to combine shorter permutations into longer ones. Given a permutation ''π'' of length ''m'' and the permutation ''σ'' of length ''n'', the skew sum of ''π'' and '' ...
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 prove, separable permutations may also be characterized in terms of
permutation pattern In combinatorial mathematics and theoretical computer science, a permutation pattern is a sub-permutation of a longer permutation. Any permutation may be written in one-line notation as a sequence of digits representing the result of applying the p ...
s: 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 , then the permutation that describes how the numerical ordering of the polynomials changes at is separable, and every separable permutation can be realized in this way.
Combinatorial enumeration
The separable permutations are enumerated by the
Schröder number
In mathematics, the Schröder number S_n, also called a ''large Schröder number'' or ''big Schröder number'', describes the number of lattice paths from the southwest corner (0,0) of an n \times n grid to the northeast corner (n,n), using only ...
s. 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, ....
This result was proven for a class of
permutation matrices
In mathematics, particularly in matrix theory, a permutation matrix is a square binary matrix that has exactly one entry of 1 in each row and each column and 0s elsewhere. Each such matrix, say , represents a permutation of elements and, when ...
equivalent to the separable permutations by , 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 .
Algorithms
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
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
.
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 , 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.
considered separable permutations again in their study of
bootstrap percolation In statistical mechanics, bootstrap percolation is a percolation process in which a random initial configuration of active cells is selected from a lattice or other space, and then cells with few active neighbors are successively removed from the a ...
, 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 , who considered them for their algorithmic properties.
Related structures
![Permutation graph](https://upload.wikimedia.org/wikipedia/commons/7/78/Permutation_graph.svg)
Every permutation can be used to define a
permutation graph
In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be ...
, a graph whose vertices are the elements of the permutation and whose edges are the
inversions of the permutation. In the case of a separable permutation, the structure of this graph can be read off from the separation tree of the permutation: two vertices of the graph are adjacent if and only if their
lowest common ancestor
In graph theory and computer science, the lowest common ancestor (LCA) (also called least common ancestor) of two nodes and in a tree or directed acyclic graph (DAG) is the lowest (i.e. deepest) node that has both and as descendants, where ...
in the separation tree is negative. The graphs that can be formed from trees in this way are called
cograph
In graph theory, a cograph, or complement-reducible graph, or ''P''4-free graph, is a graph that can be generated from the single-vertex graph ''K''1 by complementation and disjoint union. That is, the family of cographs is the smallest class of ...
s (short for complement-reducible graphs) and the trees from which they are formed are called cotrees. Thus, the separable permutations are exactly the permutations whose permutation graphs are cographs. The
forbidden graph characterization
In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidde ...
of the cographs (they are the graphs with no four-vertex
induced path
In the mathematical area of graph theory, an induced path in an undirected graph is a path that is an induced subgraph of . That is, it is a sequence of vertices in such that each two adjacent vertices in the sequence are connected by an edg ...
) corresponds to the two four-element forbidden patterns of the separable permutations.
Separable permutations are also closely related to
series-parallel partial orders, the
partially ordered set
In mathematics, especially order theory, a partially ordered set (also poset) formalizes and generalizes the intuitive concept of an ordering, sequencing, or arrangement of the elements of a set. A poset consists of a set together with a bina ...
s whose comparability graphs are the cographs. As with the cographs and separable permutations, the series-parallel partial orders may also be characterized by four-element forbidden suborders. Every permutation defines a partial order whose
order dimension
In mathematics, the dimension of a partially ordered set (poset) is the smallest number of total orders the intersection of which gives rise to the partial order.
This concept is also sometimes called the order dimension or the Dushnik–Miller di ...
is two, in which the elements to be ordered are the elements of the permutation, and in which ''x'' ≤ ''y'' whenever ''x'' has a smaller numerical value than ''y'' and is left of it in the permutation. The permutations for which this partial order is series-parallel are exactly the separable permutations.
Separable permutations may also be used to describe hierarchical partitions of rectangles into smaller rectangles (so-called "slicing floorplans", used for instance in the design of
integrated circuits
An integrated circuit or monolithic integrated circuit (also referred to as an IC, a chip, or a microchip) is a set of electronic circuits on one small flat piece (or "chip") of semiconductor material, usually silicon. Large numbers of tiny ...
) by using the positive and negative signs of the separating tree to describe horizontal and vertical slices of a rectangle into smaller rectangles.
[; ]
The separable permutations include as a special case the
stack-sortable permutations, which avoid the pattern 231.
Notes
References
*
*.
*.
*.
*
* .
*.
*.
*{{citation
, last = West , first = Julian
, doi = 10.1016/0012-365X(94)00067-1
, issue = 1–3
, journal =
Discrete Mathematics
, mr = 1360119
, pages = 247–262
, title = Generating trees and the Catalan and Schröder numbers
, volume = 146
, year = 1995.
Permutation patterns