ALGEBRAIC COMBINATORICS

no. 1
Permutree sorting
Pilaud, Vincent1; Pons, Vivane2; Tamayo Jimenez, Daniel2
1 CNRS & LIX École Polytechnique Palaiseau France
2 Université Paris-Saclay CNRS Laboratoire Interdisciplinaire des Sciences du Numérique 91400 Orsay France
Algebraic Combinatorics, Volume 6 (2023) no. 1, pp. 53-74.

Generalizing stack sorting and c-sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets U and D of {2,⋯,n-1}, the (U,D)-permutree sorting tries to sort the permutation π∈𝔖 n and fails if and only if there are 1≤i<j<k≤n such that π contains the subword jki if j∈U and kij if j∈D. This algorithm is seen as a way to explore an automaton which either rejects all reduced words of π, or accepts those reduced words for π whose prefixes are all (U,D)-permutree sortable.

Received:
Accepted:
Published online:
DOI: 10.5802/alco.249
Classification: 68P10, 68Q45, 68R05, 05E99
Keywords: stack sorting, automata, permutrees, weak order
Pilaud, Vincent 1; Pons, Vivane 2; Tamayo Jimenez, Daniel 2

1 CNRS & LIX École Polytechnique Palaiseau France
2 Université Paris-Saclay CNRS Laboratoire Interdisciplinaire des Sciences du Numérique 91400 Orsay France
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights 
@article{ALCO_2023__6_1_53_0,
     author = {Pilaud, Vincent and Pons, Vivane and Tamayo Jimenez, Daniel},
     title = {Permutree sorting},
     journal = {Algebraic Combinatorics},
     pages = {53--74},
     publisher = {The Combinatorics Consortium},
     volume = {6},
     number = {1},
     year = {2023},
     doi = {10.5802/alco.249},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.249/}
}
TY  - JOUR
AU  - Pilaud, Vincent
AU  - Pons, Vivane
AU  - Tamayo Jimenez, Daniel
TI  - Permutree sorting
JO  - Algebraic Combinatorics
PY  - 2023
SP  - 53
EP  - 74
VL  - 6
IS  - 1
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.249/
DO  - 10.5802/alco.249
LA  - en
ID  - ALCO_2023__6_1_53_0
ER  - 
%0 Journal Article
%A Pilaud, Vincent
%A Pons, Vivane
%A Tamayo Jimenez, Daniel
%T Permutree sorting
%J Algebraic Combinatorics
%D 2023
%P 53-74
%V 6
%N 1
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.249/
%R 10.5802/alco.249
%G en
%F ALCO_2023__6_1_53_0
Pilaud, Vincent; Pons, Vivane; Tamayo Jimenez, Daniel. Permutree sorting. Algebraic Combinatorics, Volume 6 (2023) no. 1, pp. 53-74. doi : 10.5802/alco.249. https://alco.centre-mersenne.org/articles/10.5802/alco.249/

[1] Albertin, Doriann; Pilaud, Vincent; Ritter, Julian Removahedral congruences versus permutree congruences, Electron. J. Combin., Volume 28 (2021) no. 4, Paper no. P4.8, 38 pages | DOI | MR | Zbl

[2] Chatel, Grégory; Pilaud, Vincent Cambrian Hopf Algebras, Adv. Math., Volume 311 (2017), pp. 598-633 | DOI | MR | Zbl

[3] Chatel, Grégory; Pilaud, Vincent; Pons, Viviane The weak order on integer posets, Algebr. Comb., Volume 2 (2019) no. 1, pp. 1-48 | Numdam | MR | Zbl

[4] Fomin, Sergey; Zelevinsky, Andrei Cluster algebras. I. Foundations, J. Amer. Math. Soc., Volume 15 (2002) no. 2, pp. 497-529 | DOI | MR | Zbl

[5] Fomin, Sergey; Zelevinsky, Andrei Cluster algebras. II. Finite type classification, Invent. Math., Volume 154 (2003) no. 1, pp. 63-121 | DOI | MR | Zbl

[6] Hohlweg, Christophe; Lange, Carsten Realizations of the associahedron and cyclohedron, Discrete Comput. Geom., Volume 37 (2007) no. 4, pp. 517-543 | DOI | MR | Zbl

[7] Hopcroft, John E.; Ullman, Jeffrey D. Introduction to automata theory, languages, and computation, Addison-Wesley Publishing Co., Reading, Mass., 1979, x+418 pages (Addison-Wesley Series in Computer Science)

[8] Knuth, Donald E. The art of computer programming. Vol. 1: Fundamental algorithms, Second printing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont, 1969, xxi+634 pages

[9] Loday, Jean-Louis Realization of the Stasheff polytope, Arch. Math. (Basel), Volume 83 (2004) no. 3, pp. 267-278 | MR | Zbl

[10] Loday, Jean-Louis; Ronco, María O. Hopf algebra of the planar binary trees, Adv. Math., Volume 139 (1998) no. 2, pp. 293-309 | DOI | MR | Zbl

[11] Malvenuto, Claudia; Reutenauer, Christophe Duality between quasi-symmetric functions and the Solomon descent algebra, J. Algebra, Volume 177 (1995) no. 3, pp. 967-982 | DOI | MR | Zbl

[12] Pilaud, Vincent; Pons, Viviane Permutrees, Algebr. Comb., Volume 1 (2018) no. 2, pp. 173-224 | Numdam | MR | Zbl

[13] Reading, Nathan Lattice congruences of the weak order, Order, Volume 21 (2004) no. 4, pp. 315-344 | DOI | MR | Zbl

[14] Reading, Nathan Cambrian lattices, Adv. Math., Volume 205 (2006) no. 2, pp. 313-353 | DOI | MR | Zbl

[15] Reading, Nathan Clusters, Coxeter-sortable elements and noncrossing partitions, Trans. Amer. Math. Soc., Volume 359 (2007) no. 12, pp. 5931-5958 | DOI | MR | Zbl

[16] Reading, Nathan Sortable elements and Cambrian lattices, Algebra Universalis, Volume 56 (2007) no. 3-4, pp. 411-437 | DOI | MR | Zbl

[17] Tamari, Dov Monoides préordonnés et chaînes de Malcev, Ph. D. Thesis, Université Paris Sorbonne (1951)

Cited by Sources: