Counting Permutation Patterns with Multidimensional Trees

We introduce pattern-trees: a family of graphs that generalise the corner-trees of Even-Zohar and Leng [18]. Pattern-trees are rooted labeled trees, in which every vertex is associated with a set of point variables, along with constraints that fix their relative ordering in the plane, and every edge is labeled by a list of constraints over the ordering of points associated with its incident vertices.

Using an algorithm derived from pattern-trees, we obtain our first result.

Our proof of Theorem 1.1 relies on embeddings of trees into permutations. Consider the number of distinct embeddings of the points of a pattern-tree $T$ into the points in the plane associated with a permutation $\pi \in {𝕊}_n$, in which the embedding satisfies all constraints defined by the tree (as demonstrated in Figure 1). We show that this quantity can be expressed as a fixed integer linear combination of permutation pattern-counts, irrespective of $\pi$. Interpreted as a formal sum of patterns, this is simply a vector in ${\mathbb{Z}}^{{𝕊}_{\le k}}$, where $k$ is the number of point variables in the tree. These vectors are associated with pairwise compositions of linear extensions of partially ordered sets, whose Hasse diagrams can be partitioned in a particular way.

The subspaces spanned by the vectors of trees, over the rationals, are central to our proof. It is not hard to show that when the subspace of a set of trees is full-dimensional, one can derive from those trees an algorithm for the $k$-profile. To this end, we design an evaluation algorithm: given a pattern-tree $T$ and an input permutation $\pi \in {𝕊}_n$⁵⁵5 Throughout this paper we operate on $n$-element permutations as input. Such inputs are assumed to be presented to the algorithm sparsely, e.g., as a length-$n$ vector representing the permutation in one-line notation., the algorithm computes the number of occurrences of $T$ in $\pi$, denoted $\mathrm{\#}T(\pi )$. The complexity of this algorithm depends on properties of the tree. In our proof of Theorem 1.1, we construct a family of trees evaluable in $\widetilde{𝒪}\left(n^2\right)$-time, which are of full dimension for ${𝕊}_{\le 7}$.

Compared to previous results, Theorem 1.1 offers an improvement whenever $k\in \{5,6,7\}$. The best known bound for the $k$-profile problem is $𝒪(n^{k/4+o(k)})$, due to Berendsohn et al. [7]. Their approach relies on formulating a binary CSP, and bounding its tree-width. It is well known that binary CSPs can be solved in time $𝒪(n^{t+1})$ [13, 20], where $n$ is the domain size, and $t$ is the tree-width of the constraint graph. In the algorithm of [7], the tree-width is bounded by $k/4+o(k)$, where the $o(k)$-term is greater than one. Therefore, their algorithm has at least cubic running time when $k\ge 4$.

The relationship between properties of pattern-trees and the dimensions of the subspaces spanned by them is still far from understood (see Section 5). Corner-trees, which are exactly the pattern-trees whose evaluation is quasi-linear, were shown in [18] to have full rank for ${𝕊}_{\le 3}$, and rank only $|{𝕊}_4|-1=23$, restricted to ${𝕊}_4$. Intriguingly, we show that the family of pattern-trees with which our proof of Theorem 1.1 is obtained, whose evaluation complexity is quadratic, have full rank for ${𝕊}_{\le 7}$, and rank only $|{𝕊}_8|-1=40319$ restricted to ${𝕊}_8$. We observe several striking resemblances between the two vectors spanning the orthogonal complements, for ${𝕊}_4$ and ${𝕊}_8$ respectively, in terms of their symmetries. In fact, we extend a characterisation of [15] regarding the symmetries for ${𝕊}_4$ to the case of ${𝕊}_8$ (see Section 3.4).

Our second result is a sub-quadratic algorithm for the $5$-profile.

The proof of Theorem 1.2 is obtained by speeding-up the evaluation algorithm of pattern-trees. The original algorithm for pattern-trees has an integral exponent in its complexity, which is determined by properties of the tree. We show that trees with certain topological properties, i.e., containing a particular set of “gadgets”, can be evaluated faster. The family of trees constituting all corner-trees, and their augmentation by our gadgets, span a full-dimensional subspace over ${𝕊}_5$. This allows us to break the quadratic barrier for the $5$-profile.

One of the key ingredients, both in the original evaluation algorithm and in its extended version, is a data structure known as a multidimensional segment-tree, or rectangle-tree [22, 9].⁶⁶6A $2$-dimensional version of this data structure features in both [18] and [15]. A $d$-dimensional rectangle-tree holds (possibly weighted) points in ${[n]}^d$, and answers sum-queries over rectangles $ℛ\subseteq {[n]}^d$ (i.e., Cartesian products of segments) in poly-logarithmic time.

The gadgets appearing in the proof of Theorem 1.2 are sub-structures related to the patterns $\mathrm{𝟹𝟸𝟷𝟺}$ and $\mathrm{𝟺𝟹𝟸𝟷𝟻}$. For the former, we extend an algorithm of [18] into a weighted variant, and provide an evaluation algorithm of complexity $\widetilde{𝒪}(n^{5/3})$. We then further extend this into an algorithm for the latter gadget, of complexity $\widetilde{𝒪}(n^{7/4})$. The latter proof is involved, and requires the introduction of a new data structure, which we call a pair-rectangle-tree. A pair-rectangle-tree is an extension of rectangle-trees that can facilitate more complex queries, in particular, regarding the dominance counting of a set of points in a rectangle. These queries are also more general than those supported by the $2$-dimensional dominance counting data-structures due to [22, 10]. We remark that the original pattern-tree evaluation algorithm can only compute equivalent gadgets in quadratic time. That is, the evaluation algorithm is not always optimal.

In Section 3 we introduce pattern-trees. Our construction for $3\le k\le 7$ can be found in Section 3.3, and the case $k=8$ is dealt with in Section 3.4. A straightforward application of pattern-trees for general $k$ is given in Section 3.5. Section 4 revolves around our construction of an $\widetilde{𝒪}\left(n^{7/4}\right)$-time algorithm for the $5$-profile. The augmentation of the pattern-trees evaluation algorithm can be found in Section 4.2, and the particular gadgets used in the $5$-profile are obtained in Section 4.3 and Section 4.4. The data structure we introduce for dominance counting in rectangles, pair-rectangle-tree, is given in Section 4.5. Finally, in Section 5 we discuss open questions and possible extensions of this work.

The proofs of Theorem 1.1 and Theorem 1.2 are accompanied by computer-assisted computations. All such computations are available in [5].

A permutation $\pi \in {𝕊}_n$ over $n$ elements is a bijection from $[n]$ to itself, where $[n]:=\{1,2,\mathrm{\dots },n\}$. Throughout this paper, we express permutations using one-line notation, and if the permutation range is sufficiently small, we omit the parentheses. For instance, $\mathrm{𝟷𝟸𝟹}$ is the identity permutation over $3$ elements. Associated with any permutation $\pi \in {𝕊}_n$ is a set of $n$ points in the plane, $p(\pi ):=\{(i,\pi (i)):i\in [n]\}$, which we refer to as the points of $\pi$. In the other direction, any set of $n$ points in the plane defines a permutation $\pi \in {𝕊}_n$, provided that no two points lie on an axis-parallel line. Given such a set $S\subset {ℝ}^2$, we use the notation $S\cong \pi$ to indicate that the points are order-isomorphic to $\pi$.

An occurrence of a pattern $\tau \in {𝕊}_k$ in a permutation $\pi \in {𝕊}_n$ is a $k$-tuple such that the set of points $(i_j,\pi (i_j))$ is order-isomorphic to $\tau$. That is, if and only if for all $j,l\in [k]$. The number of occurrences of $\tau$ in $\pi$ is denoted by $\mathrm{\#}\tau \left(\pi \right)$.

The dihedral group $D_k$ is the symmetry group of the regular $k$-gon. The group $D_4$ naturally acts on the symmetric group ${𝕊}_n$, by acting on ${[1,n]}^2$. Formally, for any element $g\in D_4$ and permutation $\pi \in {𝕊}_n$, we have that $(g.\pi )\in {𝕊}_n$ is the permutation for which $g.(p(\pi ))\cong g.\pi$. Our algorithms usually receive permutations as input, and compute some combination of pattern-counts. To this end, it is sometimes helpful to first act on the input with an element $g\in D_4$ (as a preprocessing step), and only then invoke the algorithm as usual. In this way, if an algorithm computes the count $\mathrm{\#}\tau \left(\pi \right)$, then after the action we obtain $\mathrm{\#}\tau (g.\pi )=\mathrm{\#}(g^{-1}.\tau )\left(\pi \right)$.

Our main focus in this paper is the computation of $\mathrm{\#}\tau \left(\pi \right)$ for all $\tau \in {𝕊}_k$, where $\pi \in {𝕊}_n$ is given as input and $k$ is fixed. This collection of counts is defined as follows.

A partially ordered set (poset) $𝒫(X,\le )$ over a ground set $X$ is a partial arrangement of the elements in $X$ according to the order relation $\le$. If $\le$ is not reflexive, we say that $𝒫$ is strict. A partial order ${\le }^{\star }$ is said to be an extension of $\le$ if $x\le y$ implies $x{\le }^{\star }y$ for all $x,y\in X$. If an extension ${\le }^{\star }$ is a total order, it is called a linear extension of $\le$. As usual, the set of all linear extensions of a poset $𝒫$ is denoted by $ℒ(𝒫)$.

Throughout this paper we disregard all $\mathrm{polylog}(n)$-factors, so our results hold for any choice of standard computational model (say, word-RAM). The notation $\widetilde{𝒪}\left(n^k\right)$ (adding the tilde) is used to hide poly-logarithmic factors. The algorithms presented in this paper operate on $n$-element permutations as input, and we remark that such inputs are assumed to be presented to the algorithm sparsely, e.g., as a length-$n$ vector representing the permutation in one-line notation.

Our algorithms for efficiently computing profiles rely heavily on a simple and powerful data structure, which we refer to as a rectangle-tree⁷⁷7 A rectangle $ℛ\subseteq {[n]}^d$ is a Cartesian product of segments, i.e., invervals of the form $\{a,a+1,\mathrm{\dots },b\}\subseteq [n]$. or a multidimensional segment-tree. Concretely, we require the following folklore fact.

One illustration of the application of rectangle-trees to pattern-counting is given by the simple (and again, folklore) case of monotone pattern-counting.

One of the main components in the work of [18] is the introduction of corner-trees. Corner-trees are a family of rooted edge-labeled trees. Every corner-tree of $k$ vertices is associated with a particular vector in ${\mathbb{Z}}^{{𝕊}_{\le k}}$; i.e., a formal integer linear combination of permutations, each of size at most $k$. Furthermore, there exists an efficient evaluation algorithm for corner-trees: given any input permutation $\pi \in {𝕊}_n$ and corner-tree $T$, the integer sum of permutation pattern-counts in $\pi$, called the vector of $T$, can be computed in time $\widetilde{𝒪}\left(n\right)$. We refer to this operation as evaluating the vector of $T$ over $\pi$.

An occurrence of a corner-tree $T$ in a permutation $\pi$ is a map $\phi :V(T)\to p(\pi )$, in which the image agrees with the edge-labels of the tree. That is, for every edge $(u\to v)\in E(T)$, $\phi (v)$ is to the left of $\phi (u)$ if the edge is labeled NW or SW, and to its right otherwise. Similar rules apply for their vertical ordering. As in [18], the number of occurrences of a corner-tree $T$ in a permutation $\pi$ is denoted by $\mathrm{\#}T(\pi )$.

The vector of a corner-tree is a formal sum of permutation patterns with integer coefficients, representing the number of occurrences of the tree in any input permutation. For instance, the vector of is $\mathrm{\#}\mathrm{𝟸𝟷𝟹}+\mathrm{\#}\mathrm{𝟹𝟷𝟸}$. Clearly, the vector of a corner-tree over $k$ vertices may involve patterns of size at most $k$, as the tree conditions on the relative ordering of at most $|V(T)|$ points (smaller patterns may appear as well, since occurrences are not necessarily injective).

Theorem 1.1 of [18] presents an algorithm for evaluating the vector of a corner-tree over an input permutation $\pi \in {𝕊}_n$. For expositionary purposes, under Section 3.1 we sketch a simplified version of their algorithm, phrased in terms of rectangle-trees.

We introduce pattern-trees: a family of graphs that generalise the corner-trees of [18]. In pattern-trees, every vertex is labeled by a permutation, and every edge is labeled by a list of constraints. The permutations written on the vertices fix the exact ordering of the points corresponding to them, and the edge-constraints are similarly imposed over the points corresponding to the two incident vertices. As with corner-trees, pattern-trees serve two purposes: firstly, every pattern-tree is associated with a set of constraints over permutation points, the number of satisfying assignments to which can be expressed as a formal integer linear combination of patterns (that is, a vector). Secondly, we present an algorithm for evaluating this vector over an input permutation. This allows us to efficiently compute certain pattern combinations not spanned by corner-trees.

The size $s(v)$ of a vertex $v$ is the size $r$ of the permutation ${\tau }_v\in {𝕊}_r$ with which it is labeled. The maximum size of a pattern-tree, denoted $s(T)$, is the maximum over all vertex sizes. The total size, denoted $\mathrm{\Sigma }(T)$, is the sum over all vertex sizes. Under this notation, a corner-tree is a pattern-tree of maximum size one. Lastly, $p(T):={⨆}_{v\in V(T)}{p}_v$ is the set of all $\mathrm{\Sigma }(T)$ points in the tree.

The corner-trees of [18] are very efficiently computable. However, asymptotically, there are quite few of them: the number of rooted unlabeled trees over $k$ vertices is only exponential in $k$ (see, e.g., [23] for a more accurate estimate), and clearly so is the number of corner-tree edge labels. Therefore, as $k\to \mathrm{\infty }$, even if asymptotically almost all corner-trees vectors were linearly independent over ${𝕊}_{\le k}$, they would nevertheless contribute only a negligible proportion with respect to the full dimension, $|{𝕊}_{\le k}|={\sum }_{r=1}^{k}r!$.

In contrast, it is not hard to see that pattern-trees are fully expressive: for every pattern $\tau \in {𝕊}_k$, there exists a pattern-tree $T$ with $s(T)=k$, whose vector is precisely that pattern (in fact, $s(T)=\lceil k/2\rceil$ suffices, see Section 3.5). To design efficient algorithms for the $k$-profile, we are interested in finding families of pattern-trees of least maximum size, whose corresponding vectors are linearly independent.

In [18], corner-trees (i.e., pattern-tree of maximum size $1$) over $k$ vertices were shown to have full rank over ${\mathbb{Q}}^{{𝕊}_{\le k}}$ for $k=3$, and in the cases $k=4$ and $k=5$, the subspaces spanned by them, restricted to ${𝕊}_4$ and ${𝕊}_5$, were found to be of dimensions only $23$ and $100$, respectively. Here, we show that for $k\le 7$, pattern-trees of maximum size $\le 2$ suffice.

Do pattern-trees over at most $8$ points, and with $s(T)\le 2$, have full dimension for ${𝕊}_{\le 8}$? Using a computer program, we exhaustively enumerate all pattern-trees with the following properties,¹²¹²12 See Appendix A for a description of the enumeration process. For $k=8$, this yields a matrix with $|{𝕊}_8|=8!$ columns, and $|{𝕊}_8\times {𝕊}_8\times \{T_{\lambda }\}|\approx 2^{37}$ rows. We remark that we explicitly do not consider pattern-trees over more than $8$ points, and trees whose edges are labeled by equalities. Whether this is without loss of generality, i.e., could their inclusion increase the rank, is unknown to us.

1. 1.

   Every tree has $|p(T)|=8$ points, and maximum size $s(T)\le 2$.

2. 2.

   No edge is labeled with an equality.

In [18] it was shown that pattern-trees with $4$ vertices and maximum size $1$ (corner-trees) span a subspace of dimension only $|{𝕊}_4|-1=23$, when restricted to ${𝕊}_4$. Our pattern-trees extend this result: the subspace spanned by the above family of pattern-trees, with $8$ points and maximum size $\le 2$, is of dimension exactly $|{𝕊}_8|-1=40319$, when restricted to ${𝕊}_8$. The two vectors spanning the orthogonal complements of the subspaces for ${𝕊}_4$ and ${𝕊}_8$, $v_4\in {\mathbb{Q}}^{{𝕊}_4}$ and $v_8\in {\mathbb{Q}}^{{𝕊}_8}$ respectively, bear striking resemblance. See the full version [4] for the details.

We end this section by considering the problem of computing the $k$-profile via pattern-trees, for arbitrary (fixed) $k$. In the following proposition, we show that families of pattern-trees of maximal size $s(T)=\lceil k/2\rceil$ suffice for computing the $k$-profile, through Algorithm 1. See Section 5 for a discussion on the relationship between $s(T)$ and $k$.

For the proof of Theorem 1.2, we introduce the following notation.

Recall that Algorithm 1 has time complexity $\widetilde{𝒪}\left(n^{s(T)}\right)$, where $s(T)$ is an integer. As we seek sub-quadratic algorithms, and since trees of $s(T)=1$ (i.e., corner-trees) do not have full rank for ${𝕊}_{\le 5}$, we take an alternative approach. We extend the family of pattern-trees of maximum size $1$ by allowing them to contain “gadgets” with specific patterns of sizes $4$ and $5$, defined below. To evaluate such trees efficiently, we show a variation of Algorithm 1 that handles these gadgets as special cases.

Suppose that, for the permutation ${\tau }_u\in {𝕊}_r$ and index $l\in [r]$, and given a set of weight functions ${\{w_j\}}_j$,¹³¹³13 We assume that for every weight function $w_j:[n]\to \mathbb{Z}$, the value $w_j(a)$ can be computed in $\widetilde{𝒪}\left(1\right)$-time. we are able to construct a $2$-dimensional rectangle-tree representing the weighted marked pattern-count, ${\mathrm{\#}}_w{\tau }_u\left(\pi \right)$ marked at $l$. Then, we claim that one can modify Algorithm 1 by replacing the rectangle-tree ${𝒯}_u$ associated with $u$, with the weighted marked pattern-count of $\tau$, marked at $l$, for a particular choice of weight functions. Concretely, we make the following modifications in Algorithm 1:

Theorem 1.2 of [18] describes an algorithm for counting $\mathrm{\#}\mathrm{𝟹𝟸𝟷𝟺}$. We require a slight alteration of their algorithm, and in particular, a weighted variant.

The evaluation of the weighted marked pattern-count $\mathrm{\#}\mathrm{𝟺𝟹𝟸𝟷}\underset{¯}{\mathrm{𝟻}}$ relies on a data structure that can efficiently count ascending and descending pairs in a given rectangle.