Double Catalan monoids
DOI: 10.1007/s10801-011-0336-y
Abstract
In this paper, we define and study what we call the double Catalan monoid. This monoid is the image of a natural map from the 0-Hecke monoid to the monoid of binary relations. We show that the double Catalan monoid provides an algebraization of the (combinatorial) set of 4321-avoiding permutations and relate its combinatorics to various off-shoots of both the combinatorics of Catalan numbers and the combinatorics of permutations. In particular, we give an algebraic interpretation of the first derivative of the Kreweras involution on Dyck paths, of 4321-avoiding involutions and of recent results of Barnabei et al. on admissible pairs of Dyck paths. We compute a presentation and determine the minimal dimension of an effective representation for the double Catalan monoid. We also determine the minimal dimension of an effective representation for the 0-Hecke monoid.
Pages: 333–354
Keywords: Catalan monoid; presentation; pattern avoiding permutation; effective representation
Full Text: PDF
References
248. Springer, New York (2008) Barnabei, M., Bonetti, F., Silimbani, M.: Restricted involutions and Motzkin paths. Adv. Appl. Math. $47(1)$, 102-115 (2011) CrossRef Barnabei, M., Bonetti, F., Silimbani, M.: 1234-avoiding permutations and Dyck paths. Preprint. arXiv:1102.1541 Billey, S., Jockusch, W., Stanley, R.: Some combinatorial properties of Schubert polynomials. J. Algebr. Comb. $2(4)$, 345-374 (1993) CrossRef Björner, A., Brenti, F.: Combinatorics of Coxeter Groups. Graduate Texts in Mathematics, vol.
231. Springer, New York (2005) Bóna, M.: Combinatorics of Permutations. Discrete Mathematics and Its Applications. Chapman \& Hall/CRC, Boca Raton (2004) CrossRef Carter, R.: Representation theory of the 0-Hecke algebra. J. Algebra $104(1)$, 89-103 (1986) CrossRef Denton, T.: Zero-Hecke monoids and pattern avoidance. Available at: http://oz.plymouth.edu/~dcernst/SpecialSession/Denton.pdf Fayers, M.: 0-Hecke algebras of finite Coxeter groups. J. Pure Appl. Algebra 199(1-3), 27-41 (2005) CrossRef Ganyushkin, O., Mazorchuk, V.: Factor powers of finite symmetric groups. Mat. Zametki $58(2)$, 176-188 (1995). Translation in Math. Notes 58(1-2), 794-802 (1996) Ganyushkin, O., Mazorchuk, V.: Classical Finite Transformation Semigroups. An Introduction. Algebra and Applications, vol.
9. Springer, London (2009) CrossRef Ganyushkin, O., Mazorchuk, V.: On Kiselman quotients of 0-Hecke monoids. Int. Electron. J. Algebra 10, 174-191 (2011) Gessel, I.: Symmetric functions and P-recursiveness. J. Comb. Theory, Ser. A $53(2)$, 257-285 (1990) CrossRef Hivert, F., Novelli, J.-C., Thibon, J.-Y.: Yang-Baxter bases of 0-Hecke algebras and representation theory of 0-Ariki-Koike-Shoji algebras. Adv. Math. $205(2)$, 504-548 (2006) CrossRef Hivert, F., Schilling, A., Thiéry, N.: Hecke group algebras as degenerate affine Hecke algebras. In: 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008). Discrete Math. Theor. Comput. Sci. Proc., pp. 611-623. AJ Assoc. Discrete Math. Theor. Comput. Sci., Nancy (2008) Kazhdan, D., Lusztig, G.: Representations of Coxeter groups and Hecke algebras. Invent. Math. $53(2)$, 165-184 (1979) CrossRef Kim, K.H., Roush, F.: Linear representations of semigroups of Boolean matrices. Proc. Am. Math. Soc. $63(2)$, 203-207 (1977) CrossRef Kreweras, G.: Sur les éventails de segments. Cah. BURO 15, 3-41 (1970) Margolis, S., Steinberg, B.: Quivers of monoids with basic algebras. Preprint. arXiv:1101.0416 Mathas, A.: Iwahori-Hecke algebras and Schur algebras of the symmetric group. University Lecture Series, vol.
15. American Mathematical Society, Providence (1999) McNamara, P.: EL-labelings, supersolvability and 0-Hecke algebra actions on posets. J. Comb. Theory, Ser. A $101(1)$, 69-89 (2003) CrossRef Norton, P.: 0-Hecke algebras. J. Aust. Math. Soc. A $27(3)$, 337-357 (1979) CrossRef Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and Lagrange inversion. Adv. Appl. Math. $40(1)$, 8-35 (2008) CrossRef Richardson, R., Springer, T.: The Bruhat order on symmetric varieties. Geom. Dedic. 35(1-3), 389-436 (1990) Sloane, N.: The Online Encyclopedia of Integer Sequences. http://oeis.org/ Solomon, A.: Catalan monoids, monoids of local endomorphisms, and their presentations. Semigroup Forum $53(3)$, 351-368 (1996) CrossRef Stembridge, J.: A short derivation of the Möbius function for the Bruhat order. J. Algebr. Comb. $25(2)$, 141-148 (2007) CrossRef Straubing, H., Thérien, D.: Partially ordered finite monoids and a theorem of I. Simon. J. Algebra $119(2)$, 393-399 (1988) CrossRef Tenner, B.: Reduced decompositions and permutation patterns. J. Algebr. Comb. $24(3)$, 263-284 (2006) CrossRef