Permutree sorting

Pilaud, Vincent; Pons, Vivane; Tamayo Jimenez, Daniel

doi:10.5802/alco.249

Permutree sorting

Pilaud, Vincent ¹; Pons, Vivane ²; Tamayo Jimenez, Daniel ²

¹ CNRS & LIX École Polytechnique Palaiseau France
² Université Paris-Saclay CNRS Laboratoire Interdisciplinaire des Sciences du Numérique 91400 Orsay France

Algebraic Combinatorics, Volume 6 (2023) no. 1, pp. 53-74.

Abstract

Generalizing stack sorting and $c$ -sorting for permutations, we define the permutree sorting algorithm. Given two disjoint subsets $U$ and $D$ of ${2, \dots, n - 1}$ , the $(U, D)$ -permutree sorting tries to sort the permutation $π \in 𝔖_{n}$ and fails if and only if there are $1 \leq i < j < k \leq n$ such that $π$ contains the subword $j k i$ if $j \in U$ and $k i j$ if $j \in 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: 2021-07-27
Accepted: 2022-05-23
Published online: 2023-02-24

DOI: 10.5802/alco.249

Classification: 68P10, 68Q45, 68R05, 05E99
Keywords: stack sorting, automata, permutrees, weak order

Author's affiliations:

Pilaud, Vincent ¹; Pons, Vivane ²; Tamayo Jimenez, Daniel ²

¹ CNRS & LIX École Polytechnique Palaiseau France
² 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/

References
Cited by

[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: