pith. sign in

arxiv: 2605.18274 · v2 · pith:53B6ZHG3new · submitted 2026-05-18 · 🧮 math.CO

Max-tree for d-permutations and pattern avoidance

Thomas Muller This is my paper

Pith reviewed 2026-05-21 08:08 UTC · model grok-4.3

classification 🧮 math.CO
keywords d-permutationspattern avoidancemax-treed-ary treesbijectionenumeration
0
0 comments X

The pith

A generalized max-tree maps d-permutations avoiding (21,12) and 231 bijectively onto d-ary trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Higher-dimensional permutations appear as point sets in a d-dimensional grid. The paper defines a natural extension of the classical max-tree construction that sends any d-permutation to a 2^{d-1}-ary tree. When the input avoids the patterns (21,12) and 231, the same construction becomes a bijection onto the set of d-ary trees. A reader cares because the bijection supplies an explicit combinatorial explanation for the enumeration of these objects and settles one of the open conjectures stated by Bonichon and Morel.

Core claim

The mapping from d-permutations to 2^{d-1}-ary trees that generalizes the classical max-tree construction yields a bijection with d-ary trees precisely when restricted to d-permutations avoiding the patterns (21,12) and 231.

What carries the argument

The generalized max-tree construction that builds a tree from the maximum elements across the d coordinates of a d-permutation.

If this is right

  • The number of d-permutations avoiding (21,12) and 231 equals the number of d-ary trees.
  • The bijection transfers any known enumeration or structural result on d-ary trees directly to these pattern-avoiding d-permutations.
  • Further combinatorial properties of the permutations can now be studied by examining the corresponding trees.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same tree construction could be tested on other pattern classes to see whether additional bijections appear.
  • If the mapping preserves inversion tables or other statistics, it would give refined enumerations by tree parameters.
  • Explicit small-d computations of both sides would provide an independent check of the bijection for concrete values.

Load-bearing premise

The generalized max-tree remains injective on every d-permutation and becomes surjective onto d-ary trees exactly when the permutation avoids (21,12) and 231.

What would settle it

A single d-permutation that avoids both (21,12) and 231 yet maps either to a non-d-ary tree or to the same tree as a different avoiding d-permutation would disprove the claimed bijection.

Figures

Figures reproduced from arXiv: 2605.18274 by Thomas Muller.

Figure 1
Figure 1. 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 construc￾tion, 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 … view at source ↗
Figure 2
Figure 2. Figure 2: A permutation and a 3 [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: On the left the quadrants of a point in a permutation. On the right the [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: A quaternary tree in T 4 5 dir(pmax,d−1 , p′ ) = f). This splits π in 2d−1 subpermutations, each associated to a direction in F d . Definition 2. Let π be a d-permutation, the max-tree of π with respect to the axis d −1, denoted Tmax(π), is the 2 d−1 -ary tree obtained recursively such that: • The maximal point pmax,d−1 of π is the root of the tree. • It has 2 d−1 subtrees: each such subtree is associated … view at source ↗
Figure 5
Figure 5. Figure 5: A 3−permutation and its max-tree with respect to the z axis 1 2 3 4 5 6 y 1 4 6 5 3 2 x [[1, 6, 5, 2, 4, 3]] 6 5 (-+) 4 (--) 3 (-+) (--) 2 (-+) (--) (-+) (--) (-+) 1 (--) (-+) (--) [PITH_FULL_IMAGE:figures/full_fig_p007_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: A permutation and its max-tree with respect to the [PITH_FULL_IMAGE:figures/full_fig_p007_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Two permutations with the same max-tree with respect to the axis [PITH_FULL_IMAGE:figures/full_fig_p007_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: The structure of a 3−permutation respecting Cex. It is clear that the trees in T 2 d−1 n (F) are the max-trees of the permutations that are admissible with respect to CF. There is thus a bijection between S d−1 n,CF and T 2 d−1 n,d−1 (F). Additionally, if F is a subset of Fk containing k directions, there is a bijection between the trees in T 2 d−1 n (F) and the set of k−ary trees with n internal nodes: Le… view at source ↗
Figure 9
Figure 9. Figure 9: On the left a quaternary tree. On the right the ternary tree obtained from [PITH_FULL_IMAGE:figures/full_fig_p010_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Possible configurations of two internal nodes. [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: Possible configurations of three internal nodes (1st part). [PITH_FULL_IMAGE:figures/full_fig_p019_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: Possible configurations of three internal nodes (2nd part). [PITH_FULL_IMAGE:figures/full_fig_p020_12.png] view at source ↗
read the original abstract

Higher dimensional permutations are tuples of d-1 permutations that can be identified with a point set in a d-dimensional grid. In N. Bonichon and P.-J. Morel, {\it J. Integer Sequences} 25 (2022), several conjectures regarding the enumeration of pattern avoiding d-permutations were stated. In this paper, we consider a mapping from d-permutations to $2^{d-1}-$ary trees that naturally generalizes the classical max-tree construction for permutations. We then show that, when restricted to d-permutations avoiding (21,12) and 231, this mapping yields a bijection with d-ary trees. This result resolves one of the conjectures of Bonichon and Morel.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper introduces a generalization of the classical max-tree construction that maps d-permutations (identified with point sets in a d-dimensional grid) to 2^{d-1}-ary trees. It then proves that, when restricted to d-permutations avoiding the patterns (21,12) and 231, this mapping is a bijection onto the set of d-ary trees, resolving one of the conjectures stated by Bonichon and Morel in 2022.

Significance. If the bijection holds, the result supplies a direct combinatorial link between a specific class of pattern-avoiding d-permutations and d-ary trees, furnishing both an enumerative interpretation and a potential tool for further structural results in higher-dimensional pattern avoidance. Resolving the stated conjecture is a concrete advance in the area.

major comments (2)
  1. [Section 2] The generalized max-tree construction (Section 2): injectivity on the full set of d-permutations is asserted via recursion on the d-dimensional subregions determined by the global maximum. The inductive argument must be checked to confirm that distinct d-permutations cannot produce identical trees; any ambiguity in how the maximum is selected or how the sub-permutations are extracted would undermine the claim that the map is well-defined and injective before the avoidance restrictions are imposed.
  2. [Section 3] Proof of the restricted bijection (Section 3, main theorem): the argument that avoidance of (21,12) and 231 forces every internal node to have at most d children (while still hitting every d-ary tree) relies on an explicit translation between forbidden patterns and forbidden branching configurations. The induction must be verified to ensure the base cases and recursive steps preserve the exact degree restriction; an incomplete correspondence here would mean the map is neither surjective onto all d-ary trees nor injective on the avoiding class.
minor comments (2)
  1. [Introduction] The introduction would benefit from a small explicit example (e.g., for d=3) showing how a concrete avoiding d-permutation maps to a 3-ary tree.
  2. [Section 2] Notation for the d-dimensional grid and the precise definition of the patterns (21,12) and 231 in higher dimensions should be recalled or referenced at the start of the construction section for reader convenience.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive review of our manuscript. We address each major comment in turn below, providing clarifications on the arguments while noting where we will strengthen the exposition in revision.

read point-by-point responses

  1. Referee: [Section 2] The generalized max-tree construction (Section 2): injectivity on the full set of d-permutations is asserted via recursion on the d-dimensional subregions determined by the global maximum. The inductive argument must be checked to confirm that distinct d-permutations cannot produce identical trees; any ambiguity in how the maximum is selected or how the sub-permutations are extracted would undermine the claim that the map is well-defined and injective before the avoidance restrictions are imposed.

    Authors: We appreciate the referee drawing attention to the details of the injectivity proof. The construction selects the unique global maximum point (which exists for any finite nonempty d-permutation) as the root; the remaining points are partitioned into the 2^{d-1} orthants obtained by fixing the coordinate-wise comparisons relative to the maximum in a canonical way that yields exactly 2^{d-1} sub-permutations. Each sub-permutation is then renormalized by order-preserving maps on its coordinates. Injectivity follows by induction on the number of points: the root label and the subtree shapes determine the position of the maximum and the relative ordering of points in each orthant. We agree that an expanded paragraph spelling out the precise orthant grouping and the renormalization step will remove any potential ambiguity, and we will add this in the revised manuscript. revision: yes

  2. Referee: [Section 3] Proof of the restricted bijection (Section 3, main theorem): the argument that avoidance of (21,12) and 231 forces every internal node to have at most d children (while still hitting every d-ary tree) relies on an explicit translation between forbidden patterns and forbidden branching configurations. The induction must be verified to ensure the base cases and recursive steps preserve the exact degree restriction; an incomplete correspondence here would mean the map is neither surjective onto all d-ary trees nor injective on the avoiding class.

    Authors: The referee correctly identifies the core of the bijection argument. Avoidance of (21,12) and 231 is shown to forbid any local configuration in which an internal node would be assigned more than d children or an ordering of children that violates the d-ary tree definition. The induction is performed on the size of the permutation: the base cases (empty and single-point) map to the empty and single-node trees, respectively, and the inductive step uses the fact that the sub-permutations in the children subtrees also avoid the same patterns. We will insert an auxiliary lemma that makes the forbidden-pattern-to-forbidden-branching dictionary fully explicit and will verify the inductive step in greater detail to confirm both injectivity on the avoiding class and surjectivity onto all d-ary trees. revision: yes

Circularity Check

0 steps flagged

No circularity: independent recursive mapping and explicit avoidance conditions establish the bijection

full rationale

The paper introduces a generalized max-tree mapping from d-permutations to 2^{d-1}-ary trees by locating a global maximum and recursing on subregions. It then proves injectivity on the full set and surjectivity onto d-ary trees exactly for inputs avoiding (21,12) and 231. This is established via the recursive definition of the map and the translation of pattern-avoidance into degree restrictions on the tree, without any fitted parameters, self-referential definitions, or load-bearing self-citations. The conjecture resolved originates from unrelated authors (Bonichon and Morel). The derivation chain is self-contained against the combinatorial definitions and does not reduce any claimed result to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions of d-permutations, pattern containment, and the classical max-tree; the new contribution is the generalized mapping and the proof that it restricts to a bijection under the stated avoidance conditions. No free parameters, invented entities, or non-standard axioms are introduced.

axioms (1)
  • domain assumption Standard definitions of d-permutations as (d-1)-tuples of permutations and of pattern avoidance in the multidimensional setting
    Invoked to set up the objects on which the new mapping acts; taken from the cited Bonichon-Morel paper.

pith-pipeline@v0.9.0 · 5640 in / 1321 out tokens · 41380 ms · 2026-05-21T08:08:07.189968+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

64 extracted references · 64 canonical work pages

  1. [1]

    , title =

    OEIS Foundation Inc. , title =. 2022. Available at

    work page 2022

  2. [2]

    Separable d -permutations and guillotine partitions , author =. Ann. Comb. , volume =. 2010 , publisher =

    work page 2010

  3. [3]

    Pattern matching for permutations , author =. Inform. Process. Lett. , volume =. 1998 , publisher =

    work page 1998

  4. [4]

    European J

    Restricted permutations , author =. European J. Combin. , volume =. 1985 , publisher =

    work page 1985

  5. [5]

    Permuting machines and priority queues , author =. Theoret. Comput. Sci. , volume =. 2005 , publisher =

    work page 2005

  6. [6]

    Labelled trees and pairs of input-output permutations in priority queues , author =. Theoret. Comput. Sci. , volume =. 1998 , publisher =

    work page 1998

  7. [7]

    Bassino, Fr. The. Annals of Probability , volume =. 2018 , publisher =

    work page 2018

  8. [8]

    and Gutekunst, Samuel C

    Earnest, Michael J. and Gutekunst, Samuel C. , journal =. Permutation patterns in

    work page

  9. [9]

    Asymptotics of pattern avoidance in the

    Gunby, Benjamin and P. Asymptotics of pattern avoidance in the. European J. Combin. , volume =. 2019 , publisher =

    work page 2019

  10. [10]

    A combinatorial theory of higher-dimensional permutation arrays , author =. Adv. in Appl. Math. , volume =. 2000 , publisher =

    work page 2000

  11. [11]

    Brooke , journal =

    Shapiro, Louis and Stephens, A. Brooke , journal =. Bootstrap percolation, the. 1991 , publisher =

    work page 1991

  12. [12]

    Order , volume =

    Random k -dimensional orders: Width and number of linear extensions , author =. Order , volume =. 1992 , publisher =

    work page 1992

  13. [13]

    Baxter permutations and plane bipolar orientations , author =. S

    work page

  14. [14]

    Bijections for

    Felsner, Stefan and Fusy,. Bijections for. J. Combin. Theory Ser. A , volume =. 2011 , publisher =

    work page 2011

  15. [15]

    12301", pages =. 2020 , publisher=

    Plattenbauten: touching rectangles in space , author =. International Workshop on Graph-Theoretic Concepts in Computer Science , volume = "12301", pages =. 2020 , publisher="Springer", series ="Lect. Notes in Comp. Sci.", editor="Adler, Isolde and M

    work page 2020

  16. [16]

    Priority queue sorting and labeled trees , author =. Ann. Comb. , volume =. 2003 , publisher =

    work page 2003

  17. [17]

    Electron

    Priority queues and multisets , author =. Electron. J. Combin. , volume =

    work page

  18. [18]

    Enumeration and

    Mansour, Toufik , journal =. Enumeration and

    work page

  19. [19]

    , journal =

    Stembridge, John R. , journal =. On the fully commutative elements of. 1996 , publisher =

    work page 1996

  20. [20]

    BIT , volume =

    The permutational power of a priority queue , author =. BIT , volume =. 1993 , publisher =

    work page 1993

  21. [21]

    Transactions of the American Mathematical Society , volume =

    How often are two permutations comparable? , author =. Transactions of the American Mathematical Society , volume =

    work page

  22. [22]

    Electron

    Orders Induced by Segments in Floorplans and (2-14-3, 3-41-2) -Avoiding Permutations , author =. Electron. J. Combin. , volume =

    work page

  23. [23]

    Journal of Combinatorics , volume =

    Some Wilf-equivalences for vincular patterns , author =. Journal of Combinatorics , volume =. 2015 , publisher =

    work page 2015

  24. [24]

    Rodney Baxter , title =. Ann. Comb. , year =

    work page

  25. [25]

    Glen Baxter , title =. Proc. Amer. Math. Soc. , year =

    work page

  26. [26]

    Tableau sequences, open diagrams, and

    Burrill, Sophie and Courtiel, Julien and Fusy,. Tableau sequences, open diagrams, and. European J. Combin. , volume =. 2016 , publisher =

    work page 2016

  27. [27]

    Discrete Math

    Stack sortable permutations , author =. Discrete Math. , volume =. 1981 , publisher =

    work page 1981

  28. [28]

    Monographs in Theoretical Computer Science

    Patterns in Permutations and Words , author=. Monographs in Theoretical Computer Science. An EATCS Series , year=

    work page

  29. [29]

    The Art of Computer Programming, volume 3: Searching and sorting , author =

    work page

  30. [30]

    On permutations induced by commuting functions, and an embedding question , author =. Math. Scand. , volume =. 1963 , publisher =

    work page 1963

  31. [31]

    Baxter permutations and meanders , year = 2012, howpublished =

    Fusy,. Baxter permutations and meanders , year = 2012, howpublished =

    work page 2012

  32. [32]

    Doubly alternating

    Guibert, Olivier and Linusson, Svante , journal =. Doubly alternating. 2000 , publisher =

    work page 2000

  33. [33]

    Discrete Math

    Baxter permutations , author =. Discrete Math. , volume =. 1998 , publisher =

    work page 1998

  34. [34]

    Bijective counting of involutive

    Fusy,. Bijective counting of involutive. Fund. Inform. , volume =. 2012 , publisher =

    work page 2012

  35. [35]

    Baxter Tree-like Tableaux , author =. (2021),. 2108.06212 , archiveprefix =

    work page arXiv 2021

  36. [36]

    Bouvel, Mathilde and Guerrini, Veronica and Rechnitzer, Andrew and Rinaldi, Simone , journal =. Semi-. 2018 , publisher =

    work page 2018

  37. [37]

    Cutting Corners , author =. (2020),. 2002.08730 , archiveprefix =

    work page arXiv 2020

  38. [38]

    Enumeration of

    West, Julian and Guibert, Olivier , booktitle =. Enumeration of

    work page

  39. [39]

    Cardinal, Jean , title =

    work page

  40. [40]

    2018 , month = Nov, pages =

    A Note on Flips in Diagonal Rectangulations , author =. 2018 , month = Nov, pages =. doi:10.23638/DMTCS-20-2-14 , journal =

    work page doi:10.23638/dmtcs-20-2-14 2018

  41. [41]

    Discrete Applied Mathematics , volume=

    A bijection between permutations and floorplans, and its applications , author=. Discrete Applied Mathematics , volume=. 2006 , publisher=

    work page 2006

  42. [42]

    , year =

    Bóna, M. , year =. Combinatorics of permutations , journal =

    work page

  43. [43]

    Singleton mesh patterns in multidimensional permutations , journal =

    Sergey Avgustinovich and Sergey Kitaev and Jeffrey Liese and Vladimir Potapov and Anna Taranenko , keywords =. Singleton mesh patterns in multidimensional permutations , journal =. 2024 , issn =. doi:https://doi.org/10.1016/j.jcta.2023.105801 , url =

    work page doi:10.1016/j.jcta.2023.105801 2024

  44. [44]

    Journal of Integer Sequences , volume=

    Baxter d-Permutations and Other Pattern-Avoiding Classes , author=. Journal of Integer Sequences , volume=

    work page

  45. [45]

    2024 , eprint=

    Patterns in Multi-dimensional Permutations , author=. 2024 , eprint=

    work page 2024

  46. [46]

    2025 , eprint=

    Higher dimensional floorplans and Baxter d-permutations , author=. 2025 , eprint=

    work page 2025

  47. [47]

    2025 , eprint=

    3D permutations and triangle solitaire , author=. 2025 , eprint=

    work page 2025

  48. [48]

    The Annals , volume=

    BIPOLAR ORIENTATIONS ON PLANAR MAPS AND SLE12 , author=. The Annals , volume=

    work page

  49. [49]

    European Journal of Combinatorics , volume=

    On the enumeration of plane bipolar posets and transversal structures , author=. European Journal of Combinatorics , volume=. 2024 , publisher=

    work page 2024

  50. [50]

    Bijections for Baxter families and related objects , volume=

    Felsner, Stefan and Fusy, Éric and Noy, Marc and Orden, David , year=. Bijections for Baxter families and related objects , volume=. Journal of Combinatorial Theory, Series A , publisher=. doi:10.1016/j.jcta.2010.03.017 , number=

    work page doi:10.1016/j.jcta.2010.03.017 2010

  51. [51]

    arXiv preprint arXiv:2208.08506 , year=

    On d -permutations and Pattern Avoidance Classes , author=. arXiv preprint arXiv:2208.08506 , year=

    work page arXiv

  52. [52]

    2025 , school=

    Study of combinatorial objects in higher dimensions , author=. 2025 , school=

    work page 2025

  53. [53]

    Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design , pages=

    Corner block list: an effective and efficient topological representation of non-slicing floorplan , author=. Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design , pages=

    work page 2000

  54. [54]

    Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings , journal =

    Benjamin Gunby and Dömötör Pálvölgyi , abstract =. Asymptotics of pattern avoidance in the Klazar set partition and permutation-tuple settings , journal =. 2019 , issn =. doi:https://doi.org/10.1016/j.ejc.2019.07.003 , url =

    work page doi:10.1016/j.ejc.2019.07.003 2019

  55. [55]

    and Chu, C.C.N

    Young, E.F.Y. and Chu, C.C.N. and Shen, Z.C. , TITLE=. IEEE TCAD , FJOURNAL=. 2003 , NUMBER=

    work page 2003

  56. [56]

    Combinatorics of rectangulations: Old and new bijections , YEAR=

    Andrei Asinowski and Jean Cardinal and Stefan Felsner and Eric Fusy , EPRINT=. Combinatorics of rectangulations: Old and new bijections , YEAR=

    work page

  57. [57]

    1996 , issn =

    Stack words, standard tableaux and Baxter permutations , journal =. 1996 , issn =. doi:https://doi.org/10.1016/S0012-365X(96)83009-3 , url =

    work page doi:10.1016/s0012-365x(96)83009-3 1996

  58. [58]

    A Note on Flips in Diagonal Rectangulations , volume =

    Cardinal, Jean and Sacristan, Vera and Silveira, Rodrigo , year =. A Note on Flips in Diagonal Rectangulations , volume =. Discrete Mathematics and Theoretical Computer Science , doi =

    work page

  59. [59]

    1985 , isbn =

    Puech, Claude and Yahia, Hussein , title =. 1985 , isbn =. doi:10.1145/323233.323268 , booktitle =

    work page doi:10.1145/323233.323268 1985

  60. [60]

    Finkel, R. A. and Bentley, J. L. , title =. Acta Inf. , month = mar, pages =. 1974 , issue_date =. doi:10.1007/BF00288933 , abstract =

    work page doi:10.1007/bf00288933 1974

  61. [61]

    , title =

    Yau, Mann-May and Srihari, Sargur N. , title =. Commun. ACM , month = jul, pages =. 1983 , issue_date =. doi:10.1145/358150.358158 , abstract =

    work page doi:10.1145/358150.358158 1983

  62. [62]

    Combinatorial generation via permutation languages. III. Rectangulations , author=. 2021 , eprint=

    work page 2021

  63. [63]

    2024 , eprint=

    From geometry to generating functions: rectangulations and permutations , author=. 2024 , eprint=

    work page 2024

  64. [64]

    and Fujiyoshi, K

    Murata, H. and Fujiyoshi, K. and Watanabe, T. and Kajitani, Y. , booktitle=. A mapping from sequence-pair to rectangular dissection , year=

    work page