## 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

### Citations:

Zbl 1401.06003; Zbl 0810.06006; Zbl 1082.06006; Zbl 1219.06016
Full Text:

### References:

  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  Guilbaud, G.; Rosenstiehl, P., Analyse algébrique d’un scrutin, Math. Sci. Hum., 4, 9-33 (1963)  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  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  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  Björner, A.; Brenti, F., Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231 (2005), Springer: Springer New York · Zbl 1110.05001  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  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  Caspard, N., The lattice of permutations is bounded, Int. J. Algebra Comput., 10, 4, 481-489 (2000) · Zbl 1008.06004  Santocanale, L.; Wehrung, F., Sublattices of associahedra and permutohedra, Adv. Appl. Math., 51, 3, 419-445 (2013) · Zbl 1288.06011  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  Bennett, M. K.; Birkhoff, G., Two families of Newman lattices, Algebra Univers., 32, 1, 115-144 (1994) · Zbl 0810.06006  Flath, S., The order dimension of multinomial lattices, Order, 10, 3, 201-219 (1993) · Zbl 0795.06004  Alfonsín, J. L.R.; Romero, D., Embeddability of the combinohedron, Discrete Math., 254, 1, 473-483 (2002) · Zbl 1027.05029  Santocanale, L., On the join depenency relation in multinomial lattices, Order, 24, 3, 155-179 (2007) · Zbl 1129.06005  Ferrari, L.; Pinzani, R., Lattices of lattice paths, J. Stat. Plan. Inference, 135, 1, 77-92 (2005) · Zbl 1082.06006  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  Banderier, C.; Flajolet, P., Basic analytic combinatorics of directed lattice paths, Theor. Comput. Sci., 281, 1, 37-80 (2002) · Zbl 0996.68126  Barr, M., ⋆-Autonomous Categories, Lecture Notes in Mathematics, vol. 752 (1979), Springer-Verlag  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  Lawvere, F. W., Metric spaces, generalized logic and closed categories, Rend. Semin. Mat. Fis. Milano, XLIII, 135-166 (1973) · Zbl 0335.18006  Goubault, E., Some geometric perspectives in concurrency theory, Homol. Homotopy Appl., 5, 2, 95-136 (2003) · Zbl 1034.68059  Grandis, M., The shape of a category up to directed homotopy, Theory Appl. Categ., 15, 4, 95-146 (2005) · Zbl 1091.55006  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  Dunn, J.; Hardegree, G., Algebraic Methods in Philosophical Logic, Oxford Logic Guides (2001), Oxford University Press · Zbl 1014.03002  Cockett, J.; Seely, R., Weakly distributive categories, J. Pure Appl. Algebra, 114, 2, 133-173 (1997) · Zbl 0867.18008  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  Rosenthal, K., Quantales and Their Applications, Pitman Research Notes in Mathematics Series (1990), Longman Scientific & Technical · Zbl 0703.06007  Paoli, F., ⋆-autonomous lattices, Stud. Log., 79, 2, 283-304 (2005) · Zbl 1067.03066  Emanovský, P.; Rachůnek, J., A non commutative generalization of ⋆-autonomous lattices, Czechoslov. Math. J., 58, 3, 725-740 (2008) · Zbl 1174.06008  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  Joyal, A.; Tierney, M., An extension of the Galois theory of Grothendieck, Mem. Am. Math. Soc., 51, 309 (1984) · Zbl 0541.18002  Raney, G. N., Tight Galois connections and complete distributivity, Trans. Am. Math. Soc., 97, 418-426 (1960) · Zbl 0098.02703  Santocanale, L.; Meloni, G., Relational semantics for distributive linear logic (1995), Available from Hal:  Holland, C., The lattice-ordered group of automorphisms of an ordered set, Mich. Math. J., 10, 399-408 (1963) · Zbl 0116.02102  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  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  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  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  Santocanale, L.; Wehrung, F., Generalizations of the Permutohedron, Lattice Theory: Special Topics and Applications, vol. 2, 287-397 (2016), Birkhäuser · Zbl 1426.06002  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  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  Stubbe, I., An introduction to quantaloid-enriched categories, Fuzzy Sets Syst., 256, 95-116 (2014) · Zbl 1335.18002  Papadopoulos, A.; Troyanov, M., Weak metrics on Euclidean domains, JP J. Geom. Topol., 7, 1, 23-44 (2007) · Zbl 1189.30083  Kabil, M.; Pouzet, M.; Rosenberg, I. G., Free monoids and generalized metric spaces, Eur. J. Comb., 80, 339-360 (2019) · Zbl 07078541  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  Chang, C.; Keisler, H., Model Theory, Dover Books on Mathematics (2012), Dover Publications  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.