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.
Article PDF
Similar content being viewed by others
References
Abramenko, P., Brown, K.: Buildings. Theory and Applications. Graduate Texts in Mathematics, vol. 248. Springer, New York (2008)
Barnabei, M., Bonetti, F., Silimbani, M.: Restricted involutions and Motzkin paths. Adv. Appl. Math. 47(1), 102–115 (2011)
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)
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)
Carter, R.: Representation theory of the 0-Hecke algebra. J. Algebra 104(1), 89–103 (1986)
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)
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)
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)
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)
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)
Kim, K.H., Roush, F.: Linear representations of semigroups of Boolean matrices. Proc. Am. Math. Soc. 63(2), 203–207 (1977)
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)
Norton, P.: 0-Hecke algebras. J. Aust. Math. Soc. A 27(3), 337–357 (1979)
Novelli, J.-C., Thibon, J.-Y.: Noncommutative symmetric functions and Lagrange inversion. Adv. Appl. Math. 40(1), 8–35 (2008)
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)
Stembridge, J.: A short derivation of the Möbius function for the Bruhat order. J. Algebr. Comb. 25(2), 141–148 (2007)
Straubing, H., Thérien, D.: Partially ordered finite monoids and a theorem of I. Simon. J. Algebra 119(2), 393–399 (1988)
Tenner, B.: Reduced decompositions and permutation patterns. J. Algebr. Comb. 24(3), 263–284 (2006)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mazorchuk, V., Steinberg, B. Double Catalan monoids. J Algebr Comb 36, 333–354 (2012). https://doi.org/10.1007/s10801-011-0336-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10801-011-0336-y