Double Catalan monoids

DOI10.1007/S10801-011-0336-YMaRDI QIDQ1759337zbMATH OpenOpenAlexFDO

Authors Volodymyr Mazorchuk, Benjamin Steinberg

Publication date 20 November 2012

Published in Journal of Algebraic Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1105.5313

0-Hecke monoid Catalan monoid effective representation pattern-avoiding permutation

Permutations, words, matrices (05A05) Hecke algebras and their representations (20C08) Reflection and Coxeter groups (group-theoretic aspects) (20F55) Semigroups of transformations, relations, partitions, etc. (20M20) Algebraic monoids (20M32)

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 {em 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.

Review text

The paper under review considers various finite monoids related to the symmetric group, and in particular introduces a new monoid: the \textit{double Catalan monoid}. Although no application of this monoid is given, the authors show that this is a very natural object to consider, and make a convincing case that it is an interesting monoid to study. The authors start from the 0-Hecke monoid of the symmetric group, which is defined by taking the Coxeter presentation for \(S_n\) and replacing the quadratic relations \(s^2=1\) with \(s^2=s\). This monoid, and in particular its monoid algebra, has been studied at length, both as a special case of the Iwahori--Hecke algebra and in view of applications to non-commutative symmetric functions. The \textit{Catalan monoid} is the monoid of all weakly order-preserving and weakly increasing transformations on \(\{1,\dots,n\}\). It can be defined by taking the 0-Hecke algebra and imposing the additional relations \(s_is_{i+1}s_i=s_is_{i+1}\) for each \(i\). From this, it is easy to show that the monoid has a basis indexed by 321-avoiding permutations, and therefore the dimension of the Catalan monoid is the Catalan number \(\frac1{n+1}\binom{2n}n\). The Catalan monoid is connected to many of the other objects counted by Catalan numbers, such as Dyck paths. The monoid introduced in the present paper is called the double Catalan monoid \(\mathcal{DC}_n\); the idea is to define a quotient of the 0-Hecke algebra in the spirit of the Catalan monoid but without the loss of symmetry (the automorphism \(s_i\mapsto s_{n-i}\) of the 0-Hecke monoid does not descend to the Catalan monoid). The definition of \(\mathcal{DC}_n\) is initially as a natural submonoid of the monoid of binary relations on \(\{1,\dots,n\}\). The authors go to show that \(\mathcal{DC}_n\) has a basis indexed by 4321-avoiding permutations, and give a presentation which realises \(\mathcal{DC}_n\) as a quotient of the 0-Hecke algebra, with the additional defining relation \(s_is_{i+1}s_{i+2}s_{i+1}s_i=s_is_{i+1}s_{i+2}s_is_{i+1}s_i\). There are various other interesting things in the paper too, including discussion of the first derivative of the Kreweras involution on Dyck paths. The paper concludes by extending the definitions to arbitrary finite Coxeter groups, and finding the minimal representation of a 0-Hecke monoid which is \textit{effective} (i.e.\ injective on the monoid algebra, not just the monoid). This result is very interesting, and unfortunately runs the risk of obscurity in this paper; it might have been better to put this in a separate paper. The paper is mostly very well written, though there are a couple of typos. What is slightly frustrating about this paper is the choice of notation, in particular the use of \textbf{N} for the set \(\{1,\dots,n\}\), which runs the risk of confusion with the old-fashioned notation (which still lingers in some places) for \(\mathbb N\). If a notation including the symbol \(n\) had been chosen (\([n]\) being the traditional choice in combinatorics) then the authors would not have needed to introduce a separate notation for \(\{1,\dots,n-1\}\). Furthermore, the authors announce that they use the one-line notation for permutations, but use cycle notation two lines later. And the copy-editor has been caught napping, and failed to purge the paper of the absurd symbol \(\subsetneq\). But these are minor quibbles; this paper is very interesting to read, and will no doubt provide a basis for a great deal of future work.

Recommendations

Cites work

Cited in

(18)

Describes a project that uses

Uses Software

OEIS

This page was built for publication: Double Catalan monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1759337)