2025-11-10T03:08:02.521234

On injective partial Catalan monoids

Al-Kharousi, Umar, Zubairu

Let $[n]$ be a finite chain $\{1, 2, \ldots, n\}$, and let $\mathcal{IC}_{n}$ be the semigroup consisting of all isotone and order-decreasing injective partial transformations on $[n]$. In addition, let $\mathcal{Q}^{\prime}_{n} = \{Î±\in \mathcal{IC}_{n} : \, 1\not \in \text{Dom } Î±\}$ be the subsemigroup of $\mathcal{IC}_{n}$, consisting of all transformations in $\mathcal{IC}_{n}$, each of whose domains does not contain $1$. For $1 \leq p \leq n$, let $K(n,p) = \{Î±\in \mathcal{IC}_{n} : \, |\text{Im }\, Î±| \leq p\}$ and $M(n,p) = \{Î±\in \mathcal{Q}^{\prime}_{n} : \, |\text{Im } \, Î±| \leq p\}$ be the two-sided ideals of $\mathcal{IC}_{n}$ and $\mathcal{Q}^{\prime}_{n}$, respectively. Moreover, let ${RIC}_{p}(n)$ and ${RQ}^{\prime}_{p}(n)$ denote the Rees quotients of $K(n,p)$ and $M(n,p)$, respectively. It is shown in this article that for any $ S \in \{ \mathcal{RIC}_{p}(n), K(n,p) \} $, $ S $ is abundant; $ \mathcal{IC}_{n} $ is ample; and for any $ S \in \{ \mathcal{Q}^{\prime}_{n}, \mathcal{RQ}^{\prime}_{p}(n), M(n,p) \} $, $ S $ is right abundant for all values of $ n $, but not left abundant for $ n \geq 2 $. Furthermore, the ranks of the Rees quotients ${RIC}_{p}(n)$ and ${RQ}^{\prime}_{p}(n)$ are shown to be equal to the ranks of the two-sided ideals $K(n,p)$ and $M(n,p)$, respectively. These ranks are found to be $\binom{n}{p}+(n-1)\binom{n-2}{p-1}$ and $\binom{n}{p}+(n-2)\binom{n-3}{p-1}$, respectively. In addition, the ranks of the semigroups $\mathcal{IC}_{n}$ and $\mathcal{Q}^{\prime}_{n}$ were found to be $2n$ and $n^{2}-3n+4$, respectively. Finally, we characterize all the maximal subsemigroups of $\mathcal{IC}_{n}$ and $\mathcal{Q}^{\prime}_{n}$.

academic

On injective partial Catalan monoids

Basic Information

Paper ID: 2501.00285
Title: On injective partial Catalan monoids
Authors: F. S. Al-Kharousi, A. Umar, M. M. Zubairu
Classification: math.GR (Group Theory)
Publication Date: January 3, 2025
Paper Link: https://arxiv.org/abs/2501.00285

Abstract

This paper investigates the algebraic and rank properties of the monoid $\mathcal{IC}_n$ of monotone and order-decreasing injective partial transformations on the finite chain $[n] = \{1, 2, \ldots, n\}$ and its submonoid $\mathcal{Q}'_n$ . The main contributions include: proving that $\mathcal{IC}_n$ is ample, while $\mathcal{Q}'_n$ is right abundant but not left abundant for $n \geq 2$ ; determining the ranks of the associated Rees quotient monoids; and characterizing all maximal submonoids of $\mathcal{IC}_n$ and $\mathcal{Q}'_n$ .

Research Background and Motivation

Research Questions

This paper primarily investigates the algebraic properties of the injective partial Catalan monoid $\mathcal{IC}_n$ and its related structures, specifically including:

Characterization of Green's relations and their starred analogues
Determination of abundance and ampleness properties
Computation of ranks for various associated monoids
Complete characterization of maximal submonoids

Significance of the Problem

Theoretical Significance: As an important object in transformation monoid theory, $\mathcal{IC}_n$ has cardinality equal to the $(n+1)$ -th Catalan number $c_{n+1}$ , connecting combinatorics and monoid theory
Structural Research: This class of monoids occupies an important position in the classification and structure theory of transformation monoids
Computational Complexity: Rank computation is crucial for understanding the generating properties of monoids

Limitations of Existing Research

Although certain properties of $\mathcal{IC}_n$ have been studied, the algebraic and rank properties of its submonoid $\mathcal{Q}'_n$ and related Rees quotient monoids have not been systematically investigated.

Core Contributions

Algebraic Structure Analysis: Complete characterization of Green's relations and starred Green's relations for $\mathcal{IC}_n$ , $\mathcal{Q}'_n$ , and their associated ideals and Rees quotients
Abundance Determination: Proof that $\mathcal{IC}_n$ is ample and $\mathcal{Q}'_n$ is right abundant but not left abundant
Rank Formulas: Precise rank formulas for all associated monoids
Maximal Submonoid Characterization: Complete determination of the maximal submonoid structure of $\mathcal{IC}_n$ and $\mathcal{Q}'_n$

Detailed Methodology

Basic Definitions and Notation

For $\alpha \in \mathcal{IC}_n$ , the two-row notation is used: $\alpha = \begin{pmatrix} x_1 & \cdots & x_p \\ a_1 & \cdots & a_p \end{pmatrix}$ where $a_i \leq x_i$ (order-decreasing property) and $1 \leq x_1 < \cdots < x_p \leq n$ , $1 \leq a_1 < \cdots < a_p \leq n$ (monotonicity and injectivity).

Key Concepts

Quasi-idempotent Elements

Definition 3.1: An element $\alpha \in \mathcal{IC}_n$ is called quasi-idempotent if $\alpha^2$ is idempotent, equivalently, $\alpha^4 = \alpha^2$ .

Essential Elements

Definition 3.5: A quasi-idempotent element $\varepsilon$ with shift 1 is called essential if it has the form: $\varepsilon = \begin{pmatrix} y_1 & \cdots & y_{i-1} & y_i & y_{i+1} & \cdots & y_p \\ y_1 & \cdots & y_{i-1} & y_i-1 & y_{i+1} & \cdots & y_p \end{pmatrix}$

Required Elements

Definition 3.18: An injective mapping $\alpha$ of height $p$ in $\mathcal{Q}'_n$ is called required if it has the form: $\alpha_i = \begin{pmatrix} 2 & \cdots & i & a_i & \cdots & a_p \\ 1 & \cdots & i-1 & a_i & \cdots & a_p \end{pmatrix}$

Technical Innovations

Unified Green's Relation Characterization: Characterization of $L^*$ and $R^*$ relations through equality of image and domain sets
Quasi-idempotent Generation Theory: Proof that $\mathcal{IC}_n$ is generated by quasi-idempotent elements, hence by essential elements
Stratified Analysis Method: Analysis of monoid structure through stratification by height of $J^*$ -classes

Main Results

Characterization of Green's Relations

Theorem 2.9: For $\alpha, \beta \in \mathcal{IC}_n$ :

$\alpha L^* \beta$ if and only if $\text{Im}\alpha = \text{Im}\beta$
$\alpha R^* \beta$ if and only if $\text{Dom}\alpha = \text{Dom}\beta$
$\alpha H^* \beta$ if and only if $\alpha = \beta$

Abundance Results

Theorem 2.8:

$\mathcal{IC}_n$ is abundant
$\mathcal{Q}'_n$ is right abundant

Theorem 2.11: $\mathcal{IC}_n$ is ample

Rank Formulas

Theorem 3.13: The rank of the Rees quotient $R\mathcal{IC}_n(p)$ is: $\text{rank}(R\mathcal{IC}_n(p)) = (n-1)\binom{n-2}{p-1} + \binom{n}{p}$

Theorem 3.27: The rank of the Rees quotient $R\mathcal{Q}'_n(p)$ is: $\text{rank}(R\mathcal{Q}'_n(p)) = \binom{n}{p} + (n-2)\binom{n-3}{p-1}$

Corollary 3.17: $\text{rank}(\mathcal{IC}_n) = 2^n$

Theorem 3.35: $\text{rank}(\mathcal{Q}'_n) = n^2 - 3n + 4$

Maximal Submonoids

Theorem 4.1: The maximal submonoids of $\mathcal{IC}_n$ are precisely of three types:

$M_{\text{id}_{[n]}} = \mathcal{IC}_n \setminus \{\text{id}_{[n]}\}$
$M_{\varepsilon_{i,i+1}} = \mathcal{IC}_n \setminus \{\varepsilon_{i,i+1}\}$ ( $1 \leq i \leq n-1$ )
$M_{\varepsilon_i} = \mathcal{IC}_n \setminus \{\varepsilon_i\}$ ( $1 \leq i \leq n$ )

Corollary 4.2: $\mathcal{IC}_n$ has exactly $2n$ maximal submonoids.

Corollary 4.4: $\mathcal{Q}'_n$ has exactly $n^2 - 3n + 4$ maximal submonoids.

Technical Methods

Proof Strategies

Inverse Ideal Method: Proof that $\mathcal{IC}_n$ is an inverse ideal of $I_n$ , thereby inheriting abundance
Decomposition Technique: Decomposition of arbitrary elements into products of essential elements and idempotents
Combinatorial Counting: Utilization of combinatorial identities to compute cardinalities of various element sets
Minimal Generating Set: Determination of minimal generating sets by proving indecomposability of certain elements

Key Lemmas

Lemma 3.3: $\mathcal{IC}_n$ is quasi-idempotent generated.

Lemma 3.14: For $0 \leq p \leq n-2$ and $n \geq 4$ , we have $J^*_p \subset \langle J^*_{p+1} \rangle$ .

This paper builds on a rich literature in transformation monoid theory, particularly:

The classical monograph by Ganyushkin and Mazorchuk provides the theoretical framework
Prior work by Umar and colleagues establishes the foundational theory of order-decreasing transformation monoids
Fountain's theory of abundant monoids provides analytical tools

Conclusions and Discussion

Main Conclusions

Complete determination of the algebraic properties of the injective partial Catalan monoid and its substructures
Precise rank formulas for all associated monoids
Characterization of the complete structure of maximal submonoids

Theoretical Significance

Enriches the content of transformation monoid theory
Establishes new connections between Catalan numbers and monoid ranks
Provides methodological foundations for further study of related transformation monoids

Limitations

Primarily focuses on the finite case; generalization to infinite cases remains unexplored
Some proofs rely on concrete combinatorial calculations with limited generalizability

In-Depth Evaluation

Strengths

Strong Systematicity: Comprehensive investigation of multiple important properties of related monoids
Technical Sophistication: Skillful application of various tools from monoid theory
Complete Results: Precise formulas and complete characterizations provided
Methodological Innovation: Introduction of the concepts of essential and required elements

Weaknesses

Some proofs are highly technical, lacking geometric or combinatorial intuition
Insufficient exploration of connections with other mathematical branches
Limited consideration of computational complexity aspects

Impact

The results of this paper will have significant impact on transformation monoid theory, particularly in:

Classification theory of order-preserving transformation monoids
Study of combinatorial properties of monoids
Counting problems in algebraic combinatorics
Structure analysis of finite monoids

Applicable Scenarios

Research in transformation monoid theory
Combinatorial monoid theory
Counting problems in algebraic combinatorics
Structure analysis of finite monoids

This paper makes important new contributions to transformation monoid theory, demonstrating profound technical expertise and systematic research methodology, representing significant progress in the field.