The weak order on integer posets
Algebraic Combinatorics, Volume 2 (2019) no. 1, p. 1-48
We explore lattice structures on integer binary relations (i.e. binary relations on the set {1,2,,n} for a fixed integer n) and on integer posets (i.e. partial orders on the set {1,2,,n} for a fixed integer n). We first observe that the weak order on the symmetric group naturally extends to a lattice structure on all integer binary relations. We then show that the subposet of this weak order induced by integer posets defines as well a lattice. We finally study the subposets of this weak order induced by specific families of integer posets corresponding to the elements, the intervals, and the faces of the permutahedron, the associahedron, and some recent generalizations of those.
Received : 2017-07-29
Revised : 2018-07-20
Accepted : 2018-07-23
Published online : 2019-02-04
DOI : https://doi.org/10.5802/alco.36
Classification:  03G10,  06A07,  06B99,  52B12
Keywords: Integer binary relations, Weak order, Lattices
@article{ALCO_2019__2_1_1_0,
     author = {Chatel, Gr\'egory and Pilaud, Vincent and Pons, Viviane},
     title = {The weak order on integer posets},
     journal = {Algebraic Combinatorics},
     publisher = {MathOA foundation},
     volume = {2},
     number = {1},
     year = {2019},
     pages = {1-48},
     doi = {10.5802/alco.36},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_1_1_0}
}
The weak order on integer posets. Algebraic Combinatorics, Volume 2 (2019) no. 1, pp. 1-48. doi : 10.5802/alco.36. https://alco.centre-mersenne.org/item/ALCO_2019__2_1_1_0/

[1] Björner, Anders; Wachs, Michelle L. Permutation statistics and linear extensions of posets, J. Comb. Theory, Ser. A, Volume 58 (1991) no. 1, pp. 85-114 | Article | MR 1119703 | Zbl 0742.05084

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

[3] Châtel, Grégory; Pons, Viviane Counting smaller elements in the Tamari and m-Tamari lattices, J. Comb. Theory, Ser. A, Volume 134 (2015), pp. 58-97 | Article | MR 3345297 | Zbl 1315.05143

[4] Dermenjian, Aram; Hohlweg, Christophe; Pilaud, Vincent The facial weak order and its lattice quotients, Trans. Am. Math. Soc., Volume 370 (2018) no. 2, pp. 1469-1507 | Article | MR 3729508 | Zbl 1375.05270

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

[6] Kassel, Christian; Lascoux, Alain; Reutenauer, Christophe The singular locus of a Schubert variety, J. Algebra, Volume 269 (2003) no. 1, pp. 74-108 | Article | MR 2015302 | Zbl 1032.14012

[7] Krob, Daniel; Latapy, Matthieu; Novelli, Jean-Christophe; Phan, Ha-Duong; Schwer, Sylviane Pseudo-Permutations I: First Combinatorial and Lattice Properties (2001) http://www-igm.univ-mlv.fr/~novelli/ARTICLES/pp1.ps (13th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2001))

[8] Lange, Carsten; Pilaud, Vincent Associahedra via spines, Combinatorica, Volume 38 (2018) no. 2, pp. 443-486 | Article | MR 3800847 | Zbl 06906521

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

[10] Müller-Hoissen, Folkert; Pallo, Jean Marcel; Stasheff, Jim Associahedra, Tamari Lattices and Related Structures. Tamari Memorial Festschrift, Birkhäuser, Progress in Mathematics, Volume 299 (2012), xx+433 pages | Zbl 1253.00013

[11] Novelli, Jean-Christophe; Thibon, Jean-Yves Polynomial realizations of some trialgebras (2006) (18th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2006), https://arxiv.org/abs/math/0605061) | Zbl 1101.17003

[12] Palacios, Patricia; Ronco, María O. Weak Bruhat order on the set of faces of the permutohedron and the associahedron, J. Algebra, Volume 299 (2006) no. 2, pp. 648-678 | Article | MR 2228332 | Zbl 1110.16046

[13] Pilaud, Vincent; Pons, Viviane IntegerPosets (2018) (Research code. https://github.com/VivianePons/public-notebooks/tree/master/IntegerPosets)

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

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

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

[17] Sloane, N. J. A. The On-Line Encyclopedia of Integer Sequences (2010) (http://oeis.org )

[18] The Sage-Combinat Community Sage-Combinat: enhancing Sage as a toolbox for computer exploration in algebraic combinatorics (2016) (http://wiki.sagemath.org/combinat )

[19] The Sage Developers SageMath, the Sage Mathematics Software System (2016) (http://www.sagemath.org/ )