×

The continuous weak order. (English) Zbl 1446.18004

The paper studies a generalization of the weak Bruhat order on the set of permutations of a set with \(n\) elements, also known as permutohedron (see, e.g., [N. Caspard et al., in: Lattice theory: special topics and applications. Volume 2. Basel: Birkhäuser/Springer. 215–286 (2016; Zbl 1401.06003)] for more details).
One of the natural generalizations of permutohedra are multinomial lattices (introduced in [M. K. Bennett and G. Birkhoff, Algebra Univers. 32, No. 1, 115–144 (1994; Zbl 0810.06006)] as part of an order-theoretic investigation of rewrite systems associated with common algebraic laws). Elements of a multinomial lattice are multipermutations, i.e., words on a totally ordered finite alphabet \(\Sigma = \{a,b,c,\ldots\}\) with a fixed number of occurrences of each letter. The weak order on multipermutations is the reflexive and transitive closure of the binary relation \(\prec\) defined by \(wabu\prec wbau\) for \(a, b\in\Sigma\) such that \(a < b\). If each letter of the alphabet has exactly one occurrence, then these words are permutations, and the ordering is the weak Bruhat ordering.
Multipermutations can be given a geometrical interpretation as discrete increasing paths in some Euclidean cube of dimension \(d=\mathrm{card}(\Sigma)\), and the weak order can be considered as a way of making these paths into a lattice structure. When \(\mathrm{card}(\Sigma)=2\), the connection with geometry is well-established, i.e., these lattices are also known as lattices of lattice paths [L. Ferrari and R. Pinzani, J. Stat. Plann. Inference 135, No. 1, 77–92 (2005; Zbl 1082.06006)]. The present paper answers the question on whether the weak order can be extended from discrete paths to continuous increasing paths.
The authors consider the quantale \(Q_{\vee}(\mathbb{I})\) of join-preserving maps from the unit interval \(\mathbb{I}=[0,1]\) to itself (with the standard structure of map composition as quantale tensor and the identity map as quantale unit; see, e.g., [D. Kruml and J. Paseka, Handb. Algebra 5, 323–362 (2008; Zbl 1219.06016)] for more details on quantales). With the notation \([d]_2=\{(i, j)\,|\,1\leqslant i\leqslant j\leqslant d\}\) for \(d\geqslant 2\), they show that certain elements (called clopen (closed and open) tuples and denoted \(\mathsf{L}_d(Q_{\vee}(\mathbb{I}))\)) of the product quantale \(Q_{\vee}(\mathbb{I})^{[d]_2}\) are in bijective correspondence with images of monotone increasing continuous maps \(p:\mathbb{I}\rightarrow\mathbb{I}^d\) such that \(p(0)=\vec{0}\) and \(p(1)=\vec{1}\) (called paths). The obtained lattice-theoretic structure on paths is then said to be the continuous weak order in dimension \(d\). The authors additionally show that the construction \(\mathsf{L}_d(-)\) gives a limit-preserving functor from a certain category of lattice-ordered semigroups to the category of lattices.
The paper also has a section devoted to the algebraic structure of the lattices of the form \(\mathsf{L}_d(Q_{\vee}(\mathbb{I}))\), namely, it characterizes their join-irreducible elements and also shows that these lattices have neither completely join-irreducible elements (an element \(a\) of a complete lattice \(L\) is called completely join-irreducible provided that for every subset \(S\subseteq L\), \(a=\bigvee S\) implies \(a\in S\)) nor compact elements (an element \(c\in L\) is said to be compact provided that for every directed subset \(D\subseteq L\), \(c\leqslant\bigvee D\) implies \(c\leqslant d\) for some \(d\in D\)).
The paper is well written and contains most of its required preliminaries. Despite its rather technical nature (and a number of lengthy proofs), the paper will be of interest to all the researchers doing lattice theory.

MSC:

18B35 Preorders, orders, domains and lattices (viewed as categories)
05A05 Permutations, words, matrices
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B23 Complete lattices, completions
06F07 Quantales
18F75 Quantales
52B99 Polytopes and polyhedra
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Gouveia, M. J.; Santocanale, L., MIX ⋆-autonomous quantales and the continuous weak order, (Desharnais, J.; Guttmann, W.; Joosten, S., Relational and Algebraic Methods in Computer Science, RAMiCS 2018. Relational and Algebraic Methods in Computer Science, RAMiCS 2018, Lecture Notes in Computer Science, vol. 11194 (2018), Springer: Springer Cham), 184-201 · Zbl 06975210
[2] Guilbaud, G.; Rosenstiehl, P., Analyse algébrique d’un scrutin, Math. Sci. Hum., 4, 9-33 (1963)
[3] Yanagimoto, T.; Okamoto, M., Partial orderings of permutations and monotonicity of a rank correlation statistic, Ann. Inst. Stat. Math., 21, 489-506 (1969) · Zbl 0208.44704
[4] Caspard, N.; Santocanale, L.; Wehrung, F., Algebraic and Combinatorial Aspects of Permutohedra, Lattice Theory: Special Topics and Applications, vol. 2, 215-286 (2016), Birkhäuser · Zbl 1401.06003
[5] Björner, A., Orderings of Coxeter groups, (Combinatorics and Algebra. Combinatorics and Algebra, Boulder, Colo., 1983. Combinatorics and Algebra. Combinatorics and Algebra, Boulder, Colo., 1983, Contemp. Math., vol. 34 (1984), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 175-195
[6] Björner, A.; Brenti, F., Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231 (2005), Springer: Springer New York · Zbl 1110.05001
[7] Reading, N., Lattice Theory of the Poset of Regions, Lattice Theory: Special Topics and Applications, vol. 2, 399-487 (2016), Birkhäuser · Zbl 1404.06004
[8] Reading, N., Finite Coxeter Groups and the Weak Order, Lattice Theory: Special Topics and Applications, vol. 2, 489-561 (2016), Birkhäuser · Zbl 1388.20056
[9] Caspard, N., The lattice of permutations is bounded, Int. J. Algebra Comput., 10, 4, 481-489 (2000) · Zbl 1008.06004
[10] Santocanale, L.; Wehrung, F., Sublattices of associahedra and permutohedra, Adv. Appl. Math., 51, 3, 419-445 (2013) · Zbl 1288.06011
[11] Santocanale, L.; Wehrung, F., The equational theory of the weak Bruhat order on finite symmetric groups, J. Eur. Math. Soc., 20, 8, 1959-2003 (2018) · Zbl 1450.06001
[12] Bennett, M. K.; Birkhoff, G., Two families of Newman lattices, Algebra Univers., 32, 1, 115-144 (1994) · Zbl 0810.06006
[13] Flath, S., The order dimension of multinomial lattices, Order, 10, 3, 201-219 (1993) · Zbl 0795.06004
[14] Alfonsín, J. L.R.; Romero, D., Embeddability of the combinohedron, Discrete Math., 254, 1, 473-483 (2002) · Zbl 1027.05029
[15] Santocanale, L., On the join depenency relation in multinomial lattices, Order, 24, 3, 155-179 (2007) · Zbl 1129.06005
[16] Ferrari, L.; Pinzani, R., Lattices of lattice paths, J. Stat. Plan. Inference, 135, 1, 77-92 (2005) · Zbl 1082.06006
[17] Krattenthaler, C., The enumeration of lattice paths with respect to their number of turns, (Advances in Combinatorial Methods and Applications to Probability and Statistics. Advances in Combinatorial Methods and Applications to Probability and Statistics, Stat. Ind. Technol. (1997), Birkhäuser Boston: Birkhäuser Boston Boston, MA), 29-58 · Zbl 0882.05004
[18] Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theor. Comput. Sci., 281, 1, 37-80 (2002) · Zbl 0996.68126
[19] Barr, M., ⋆-Autonomous Categories, Lecture Notes in Mathematics, vol. 752 (1979), Springer-Verlag
[20] Cockett, J.; Seely, R., Proof theory for full intuitionistic linear logic, bilinear logic, and mix categories, Theory Appl. Categ., 3, 5, 85-131 (1997) · Zbl 0879.03022
[21] Lawvere, F. W., Metric spaces, generalized logic and closed categories, Rend. Semin. Mat. Fis. Milano, XLIII, 135-166 (1973) · Zbl 0335.18006
[22] Goubault, E., Some geometric perspectives in concurrency theory, Homol. Homotopy Appl., 5, 2, 95-136 (2003) · Zbl 1034.68059
[23] Grandis, M., The shape of a category up to directed homotopy, Theory Appl. Categ., 15, 4, 95-146 (2005) · Zbl 1091.55006
[24] Berstel, J.; Lauve, A.; Reutenauer, C.; Saliola, F. V., Combinatorics on Words, CRM Monograph Series, vol. 27 (2009), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1161.68043
[25] Dunn, J.; Hardegree, G., Algebraic Methods in Philosophical Logic, Oxford Logic Guides (2001), Oxford University Press · Zbl 1014.03002
[26] Cockett, J.; Seely, R., Weakly distributive categories, J. Pure Appl. Algebra, 114, 2, 133-173 (1997) · Zbl 0867.18008
[27] Galatos, N.; Přenosil, A., Embedding lattice-ordered bi-monoids in involutive commutative residuated lattices, (Logic, Algebra and Truth Degrees, Proceedings of the Conference Logic, Algebra and Truth Degrees. Logic, Algebra and Truth Degrees, Proceedings of the Conference Logic, Algebra and Truth Degrees, Bern, Switzerland, August 28-31 2018 (2018)), 4
[28] Rosenthal, K., Quantales and Their Applications, Pitman Research Notes in Mathematics Series (1990), Longman Scientific & Technical · Zbl 0703.06007
[29] Paoli, F., ⋆-autonomous lattices, Stud. Log., 79, 2, 283-304 (2005) · Zbl 1067.03066
[30] Emanovský, P.; Rachůnek, J., A non commutative generalization of ⋆-autonomous lattices, Czechoslov. Math. J., 58, 3, 725-740 (2008) · Zbl 1174.06008
[31] Galatos, N.; Raftery, J., A category equivalence for odd Sugihara monoids and its applications, J. Pure Appl. Algebra, 216, 10, 2177-2192 (2012) · Zbl 1279.03043
[32] Joyal, A.; Tierney, M., An extension of the Galois theory of Grothendieck, Mem. Am. Math. Soc., 51, 309 (1984) · Zbl 0541.18002
[33] Raney, G. N., Tight Galois connections and complete distributivity, Trans. Am. Math. Soc., 97, 418-426 (1960) · Zbl 0098.02703
[34] Santocanale, L.; Meloni, G., Relational semantics for distributive linear logic (1995), Available from Hal:
[35] Holland, C., The lattice-ordered group of automorphisms of an ordered set, Mich. Math. J., 10, 399-408 (1963) · Zbl 0116.02102
[36] Ball, R. N.; Droste, M., Normal subgroups of doubly transitive automorphism groups of chains, Trans. Am. Math. Soc., 290, 2, 647-664 (1985) · Zbl 0578.06001
[37] Eklund, P.; Gutiérrez García, J.; Höhle, U.; Kortelainen, J., Semigroups in Complete Lattices, Developments in Mathematics, vol. 54 (2018), Springer: Springer Cham
[38] Santocanale, L., The involutive quantaloid of completely distributive lattices, (Fahrenberg, U.; Jipsen, P.; Winter, M., Relational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Palaiseau, France, April 8-11, 2020, Proceedings (postponed). Relational and Algebraic Methods in Computer Science - 18th International Conference, RAMiCS 2020, Palaiseau, France, April 8-11, 2020, Proceedings (postponed), Lecture Notes in Computer Science, vol. 12062 (2020), Springer), 286-301
[39] Krob, D.; Latapy, M.; Novelli, J.-C.; Phan, H. D.; Schwer, S., Pseudo-permutations I: first combinatorial and lattice properties, (Barcelo, H.; Welker, V., FPSAC 2001 (2001), Arizona State University), 285-292
[40] Santocanale, L.; Wehrung, F., Generalizations of the Permutohedron, Lattice Theory: Special Topics and Applications, vol. 2, 287-397 (2016), Birkhäuser · Zbl 1426.06002
[41] Dermenjian, A.; Hohlweg, C.; Pilaud, V., The facial weak order and its lattice quotients, Trans. Am. Math. Soc., 370, 1469-1507 (2018) · Zbl 1375.05270
[42] Kelly, G. M., Basic Concepts of Enriched Category Theory, Repr. Theory Appl. Categ.. Repr. Theory Appl. Categ., Lecture Notes in Mathematics, vol. 64, 1-136 (1982), Cambridge University Press, Originally published as · Zbl 1086.18001
[43] Stubbe, I., An introduction to quantaloid-enriched categories, Fuzzy Sets Syst., 256, 95-116 (2014) · Zbl 1335.18002
[44] Papadopoulos, A.; Troyanov, M., Weak metrics on Euclidean domains, JP J. Geom. Topol., 7, 1, 23-44 (2007) · Zbl 1189.30083
[45] Kabil, M.; Pouzet, M.; Rosenberg, I. G., Free monoids and generalized metric spaces, Eur. J. Comb., 80, 339-360 (2019) · Zbl 07078541
[46] Gierz, G.; Hofmann, K. H.; Keimel, K.; Lawson, J. D.; Mislove, M.; Scott, D. S., A Compendium of Continuous Lattices (1980), Springer-Verlag: Springer-Verlag Berlin · Zbl 0452.06001
[47] Chang, C.; Keisler, H., Model Theory, Dover Books on Mathematics (2012), Dover Publications
[48] Gehrke, M.; Harding, J., Bounded lattice expansions, J. Algebra, 238, 1, 345-371 (2001) · Zbl 0988.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.