Max-tree for d d -permutations and pattern avoidance

Thomas Muller · 2026

Read Max-tree for d d -permutations and pattern avoidance by Thomas Muller (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18274.txt.

Introduction

Thomas Muller's 2026 paper extends the max-tree build to higher-dimensional permutations and pattern avoidance. A d-permutation is a tuple of d minus one permutations, read as points in a d-dimensional grid. The author maps d-permutations to trees with two to the d minus one branches, extending the classic max-tree. Restricted to d-permutations avoiding the patterns (21,12) and 231, the map becomes a bijection with d-ary trees. That link resolves one of the counting guesses stated by Bonichon and Morel.

Catalog record

CREATORThomas Muller
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46811
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2605.18274

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Max-tree for d d -permutations and pattern avoidance Thomas Muller Abstract Higher dimensional permutations are tuples of d − 1 d-1 permutations that can be identified with a point set in a d − d- dimensional grid. In N. Bonichon and P.-J. Morel, J. Integer Sequences 25 (2022), several conjectures regarding the enumeration of pattern avoiding d − d- permutations were stated. In this paper, we consider a mapping from d − d- permutations to 2 d − 1 − 2^{d-1}- ary trees that naturally generalizes the classical max-tree construction for permutations. We then show that, when restricted to d − d- permutations avoiding ( 21 , 12 ) ({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}) and 231 231 , this mapping yields a bijection with d-ary trees. This result resolves one of the conjectures of Bonichon and Morel. 1 Introduction Permutations are bijections from the set [n]=\{1,\ldots,n\} to itself that represent rearrangements of distinguishable elements. They are central objects in combinatorics that can be studied from many different perspectives. In particular, the notion of pattern avoidance in permutations has led to numerous connections with other combinatorial structures (see for instance [ 8 ] and [ 2 ] ). One celebrated example of such a connection is the enumeration of permutations avoiding a single pattern of size three which is given by the Catalan numbers [ 9 ] . In this work, we focus on a classical mapping from permutations to binary trees that we recall here: the max-tree of a permutation. This tree is obtained through a recursive decomposition of the permutation around its maximal element. A permutation \pi is viewed as a set of points (i,\pi(i)) in the plane and the root of the tree is defined as the point with maximal value. Removing this point partitions the permutation into two subpermutations: the points lying to its left and those lying to its right. Then, applying the same construction recursively to these two subpermutations yields the left and right subtrees of the root, respectively. Figure 1: A permutation and its max-tree It is well-known that the max-tree construction induces a bijection between 231 -avoiding permutations and binary trees. Moreover, considering the dual construction, in which the minimal point is used instead of the maximal one, yields a second binary tree called the min-tree . The pairs formed by the min-tree and the max-tree are twin binary trees , and it is also known that the set of such pairs is in bijection with Baxter permutations [ 6 ] . In this article, we generalize the notion of max-tree to the higher-dimensional setting of d- permutations. A d- permutation is a tuple of d-1 permutations that can be geometrically represented as a set of points in a d- dimensional grid. While, in the two-dimensional case, the recursive decomposition of the max-tree is based on the left and right regions determined by a point, in the higher-dimensional setting it relies on the hyperoctants lying below a point with respect to the last axis of the grid. Consequently, the associated recursive structure is no longer a binary tree but a 2^{d-1}- ary tree. Moreover, if one considers the sequence of points of a d- permutation {\boldsymbol{\pi}} ordered by decreasing last coordinate and then projects these points onto the first d-1 coordinates, the d-1 dimensional hyperoctree (also called 2^{d-1}- tree) [ 13 ] associated with this set of points corresponds to the max-tree of the d- permutation {\boldsymbol{\pi}} . The max-tree of a 3- permutation thus corresponds to the quadtree [ 7 ] of a set of two-dimensional points, while the max-tree of a 4- permutations corresponds to the octree [ 11 ] of a set of three-dimensional points. Additionally, as in the two dimensional case, the mapping from d- permutations to 2^{d-1}- ary tree defined by the max-tree is surjective. This leads to the definition of certain admissible classes of d- permutations, for which this mapping becomes bijective. The definition of these classes rely on total orderings of the hyperoctants lying below a point of a d- permutation. The second contribution of this paper focuses on the specialization of this mapping to pattern avoiding d- permutations. Following the notion of pattern avoidance considered in [ 3 ] , we show that the set S^{d-1}_{n}\left(({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}),231\right) of d- permutations avoiding ({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}) and 231 , forms a subset of one of the admissible classes of d- permutations, for which the associated max-trees correspond to d- ary trees. This yields a bijection between S^{d-1}_{n}\left(({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}),231\right) and the set of d- ary trees with n internal nodes. This result is of twofold interest. First, it naturally generalizes the classical bijection between 231- avoiding permutations and binary trees to arbitrary dimension d . Second, it provides an enumeration of the d- permutations in S^{d-1}_{n}\left(({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}),231\right) : |S^{d-1}_{n}\left(({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}),231\right)|=\frac{1}{dn+1}\binom{dn+1}{n}\;. (1) This answers a conjecture originally formulated in [ 3 ] and extended in [ 10 ] . It is also worth mentioning that this bijection adds to other bijective results involving pattern-avoiding d -permutations and combinatorial structures such as triangle solitaire [ 12 ] and higher-dimensional floorplans [ 4 ] . This paper is organized as follows. In Section 3 , we first recall basic notions on d -permutations and d -ary trees. We then introduce the max-tree associated with a d -permutation, together with admissible classes of d -permutations under this max-tree. We show that, restricted to these classes, the max-tree construction yields a bijection with 2^{d-1} -ary trees. In Section 4 , we first recall the notion of pattern avoidance used in this work and establish the bijection between S^{d-1}_{n}\left(({\color[rgb]{0.832,0.168,0.043}21},{\color[rgb]{0.0781,0.3164,0.8008}12}),231\right) and the set of d -ary trees. We then conclude with several open problems related to this work in Section 5 . 2 Prerequisites and notations In this subection, we recall some notions on d- permutations and d- ary trees that will be used in Section 3 to introduce the mappings between d- permutations and 2^{d-1}- ary trees. Note that in this section we do not consider the notion of pattern avoidance in d- permutations. This notion will be presented and used in Section 4 . d- permutations A d- permutation of size n is a tuple of a d-1 permutations of size n . We denote by S^{d-1}_{n} the set of d- permutations of size n . Given a d- permutation {\boldsymbol{\pi}}=(\pi_{1},\ldots,\pi_{d-1}) , we also denote by \pi_{i} the i^{th} permutation in the tuple and by \pi_{i}(j) the j^{th} element of this permutation. The matrix representation of {\boldsymbol{\pi}} is the d\times n matrix \bar{{\boldsymbol{\pi}}}=\begin{pmatrix}1&2&\ldots&n-1&n\\ \pi_{1}(1)&\pi_{1}(2)&\ldots&\pi_{1}(n-1)&\pi_{1}(n)\\ &&\vbox{\kern 6.0pt\hbox{$.$}\hbox{$.$}\hbox{$.$}}&&\\ \pi_{d-1}(1)&\pi_{d-1}(2)&\ldots&\pi_{d-1}(n-1)&\pi_{d-1}(n)\end{pmatrix}\;. The d- dimensional diagram of {\boldsymbol{\pi}} , denoted \Pi({\boldsymbol{\pi}}) , is the point set \Pi({\boldsymbol{\pi}}):=\{(i,\pi_{1}(i),\ldots,\pi_{d-1}(i)),i\in[n]\}\;. This point set is obtained by considering that each column in \bar{{\boldsymbol{\pi}}} correspond to the position vector of a point in a d- dimensional grid. In the following, we consider that the coordinates of this point set are given by x_{0},\ldots,x_{d-1} . In the two and three dimensional case, we will also often denote by x,y and x,y,z those coordinates. Moreover, we will often abuse notation and denote by {\boldsymbol{\pi}}(p) the position vector of the point p in \Pi({\boldsymbol{\pi}}) and denote by \pi_{i}(p) the coordinate i of this position vector. Figure 2: A permutation and a 3- permutation. Directions of dimension

Read the complete text