Separable permutation

Last updated January 25, 2023

Block structuring of the (transposed) permutation matrix of the separable permutation (4,5,2,1,3,8,6,7) and corresponding labeled binary tree; colors indicate depth in the tree

In combinatorial mathematics, a separable permutation is a permutation that can be obtained from the trivial permutation 1 by direct sums and skew sums.^[1] Separable permutations may be characterized by the forbidden permutation patterns 2413 and 3142;^[2] 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.^[2]

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.^[3]

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).^[4]

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.^[5]

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

Every permutation can be used to define a permutation graph, 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 the separation tree is negative. The graphs that can be formed from trees in this way are called cographs (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.^[6] The forbidden graph characterization of the cographs (they are the graphs with no four-vertex induced path) 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 sets 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 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) by using the positive and negative signs of the separating tree to describe horizontal and vertical slices of a rectangle into smaller rectangles.^[7]

The separable permutations include as a special case the stack-sortable permutations, which avoid the pattern 231.

Notes

↑ Kitaev (2011), p. 57.
1 2 Bose, Buss & Lubiw (1998); Kitaev (2011), Theorem 2.2.36, p. p.58.
↑ Ghys (2017), p. 15.
↑ See Kitaev (2011), Theorem 2.2.45, p. 60.
↑ Bouvel, Rossin & Vialette (2007).
↑ Bose, Buss & Lubiw (1998).
↑ Szepieniec & Otten (1980); Ackerman, Barequet & Pinter (2006)

Related Research Articles

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

In graph theory, an undirected graph $H$ is called a minor of the graph $G$ if $H$ can be formed from $G$ by deleting edges and vertices and by contracting edges.

In mathematics, the double factorial or semifactorial of a number $n$ , denoted by $n ‼$ , is the product of all the integers from 1 up to $n$ that have the same parity as $n$ . That is,

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In complexity theory and graph theory, induced subgraph isomorphism is an NP-complete decision problem that involves finding a given graph as an induced subgraph of a larger graph.

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be bounded even for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$
Disjoint union of two labeled graphs $G$ and $H$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ , where $i \neq j$
Renaming label $i$ to label $j$

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger 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 defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

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 permutation to the digit sequence 123...; for instance the digit sequence 213 represents the permutation on three elements that swaps elements 1 and 2. If π and σ are two permutations represented in this way, then π is said to contain σ as a pattern if some subsequence of the digits of π has the same relative order as all of the digits of σ.

In graph theory, the modular decomposition is a decomposition of a graph into subsets of vertices called modules. A module is a generalization of a connected component of a graph. Unlike connected components, however, one module can be a proper subset of another. Modules therefore lead to a recursive (hierarchical) decomposition of the graph, instead of just a partition.

In order-theoretic mathematics, a series-parallel partial order is a partially ordered set built up from smaller series-parallel partial orders by two simple composition operations.

In combinatorial mathematics, a Stirling permutation of order k is a permutation of the multiset 1, 1, 2, 2, ..., k, k with the additional property that, for each value i appearing in the permutation, the values between the two copies of i are larger than i. For instance, the 15 Stirling permutations of order three are

In mathematics and computer science, a stack-sortable permutation is a permutation whose elements may be sorted by an algorithm whose internal storage is limited to a single stack data structure. The stack-sortable permutations are exactly the permutations that do not contain the permutation pattern 231; they are counted by the Catalan numbers, and may be placed in bijection with many other combinatorial objects with the same counting function including Dyck paths and binary trees.

Anna Lubiw is a computer scientist known for her work in computational geometry and graph theory. She is currently a professor at the University of Waterloo.

In graph theory, a branch of mathematics, a chordal completion of a given undirected graph $G$ is a chordal graph, on the same vertex set, that has $G$ as a subgraph. A minimal chordal completion is a chordal completion such that any graph formed by removing an edge would no longer be a chordal completion. A minimum chordal completion is a chordal completion with as few edges as possible.

In the mathematics of permutations, a layered permutation is a permutation that reverses contiguous blocks of elements. Equivalently, it is the direct sum of decreasing permutations.

The twin-width of an undirected graph is a natural number associated with the graph, used to study the parameterized complexity of graph algorithms. Intuitively, it measures how similar the graph is to a cograph, a type of graph that can be reduced to a single vertex by repeatedly merging together twins, vertices that have the same neighbors. The twin-width is defined from a sequence of repeated mergers where the vertices are not required to be twins, but have nearly equal sets of neighbors.

References

Ackerman, Eyal; Barequet, Gill; Pinter, Ron Y. (2006), "A bijection between permutations and floorplans, and its applications", Discrete Applied Mathematics, 154 (12): 1674–1684, doi: 10.1016/j.dam.2006.03.018 , MR 2233287
Avis, David; Newborn, Monroe (1981), "On pop-stacks in series", Utilitas Mathematica, 19: 129–140, MR 0624050 .
Bouvel, Mathilde; Rossin, Dominique; Vialette, Stéphane (2007), "Longest common separable pattern among permutations", Combinatorial Pattern Matching (CPM 2007), Lecture Notes in Computer Science, vol. 4580, Springer, pp. 316–327, doi:10.1007/978-3-540-73437-6_32, ISBN 978-3-540-73436-9 .
Bose, Prosenjit; Buss, Jonathan; Lubiw, Anna (1998), "Pattern matching for permutations", Information Processing Letters , 65 (5): 277–283, doi:10.1016/S0020-0190(97)00209-3, MR 1620935 .
Ghys, Étienne (2017), A singular mathematical promenade, Lyon: ENS Éditions, arXiv: 1612.06373 , ISBN 978-2-84788-939-0, MR 3702027
Kitaev, Sergey (2011), "2.2.5 Separable permutations", Patterns in permutations and words, Monographs in Theoretical Computer Science. An EATCS Series, Berlin: Springer-Verlag, pp. 57–66, doi:10.1007/978-3-642-17333-2, ISBN 978-3-642-17332-5, Zbl 1257.68007 .
Shapiro, Louis; Stephens, Arthur B. (1991), "Bootstrap percolation, the Schröder numbers, and the N-kings problem", SIAM Journal on Discrete Mathematics , 4 (2): 275–280, doi:10.1137/0404025, MR 1093199 .
Szepieniec, A. A.; Otten, R. H. J. M. (1980), "The genealogical approach to the layout problem", 17th Conf. on Design Automation (DAC 1980), pp. 535–542, doi:10.1145/800139.804582, S2CID 2031785 .
West, Julian (1995), "Generating trees and the Catalan and Schröder numbers", Discrete Mathematics , 146 (1–3): 247–262, doi:10.1016/0012-365X(94)00067-1, MR 1360119 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Kitaev (2011), p. 57.

[forbidden-2] 1 2 Bose, Buss & Lubiw (1998); Kitaev (2011), Theorem 2.2.36, p. p.58.

[3] Ghys (2017), p. 15.

[4] See Kitaev (2011), Theorem 2.2.45, p. 60.

[FOOTNOTEBouvelRossinVialette2007-5] Bouvel, Rossin & Vialette (2007).

[FOOTNOTEBoseBussLubiw1998-6] Bose, Buss & Lubiw (1998).

[7] Szepieniec & Otten (1980); Ackerman, Barequet & Pinter (2006)

[1]

[2]

[3]

[4]

[5]

[6]

[7]