On Schützenberger monoids in transformations semigroups

K. D. Magill and S. Subbiah [4] have studied the semigroup of continuous selfmaps of a topological space. They have shown that the Schützenberger group of theH containing a selfmap a is in a close relation to the group of homeomorphic selfmaps of the range of a. There arose a naturalproblem to find a generalization of the Schützenberger group, which is in the similar relation to the semigroup of continuous selfmaps of the range of a. C. E. Clark and J. H. Carruth [1] introduced a notion of a Schützenberger monoid. In this paper Schützenberger monoids in an arbitrary semigroup of transformations are studied and it is shown that this notion is the generalization we were looking for.     

The word problem for some classes of Adian inverse semigroups

We show that all of the Schützenberger complexes of an Adian inverse semigroup are finite if the Schützenberger complex of every positive word is finite. This enables us to solve the word problem for certain classes of Adian inverse semigroups (and hence for the corresponding Adian semigroups and Adian groups).     

Alternating permutations and binary increasing trees

In [3], Foata and Schützenberger prove that the binary increasing trees are equinumerous with half of the alternating permutations considered by André [1].In this paper we present a direct recursive proof of this fact, and then exhibit a natural bijection between the two families. In the process a second class of permutations, which forms a main concern of Foata and Schützenberger's paper, is encountered in a natural setting.     

Fundamental groups,inverse schützenberger automata,and monoid presentations

This paper gives decidable conditions for when a finitely generated subgroup of a free group is the fundamental group of a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Also, generalizations are given to specific types of inverse monoids as well as to monoids which are "nearly inverse." This result has applications to computing membership for inverse monoids in a Mal'cev product of the pseudovariety of semilattices with a pseudovariety of groups.

This paper also shows that there is a bijection between strongly connected inverse automata and subgroups of a free group, generated by positive words. Hence, we also obtain that it is decidable whether a finite strongly connected inverse automaton is a Schützenberger automaton corresponding to a monoid presentation of an inverse monoid. Again, we have generalizations to other types of inverse monoids and to "nearly inverse" monoids. We show that it is undecidable whether a finite strongly connected inverse automaton is a Schützenberger automaton of a monoid presentation of anE-unitary inverse monoid.     

Enumeration of lattice paths and generating functions for skew plane partitions

n-dimensional lattice paths not touching the hyperplanesX _i–X _i+1=–1,i=1,2,...,n, are counted by four different statistics, one of which is MacMahon's major index. By a reflection-like proof, heavily relying on Zeilberger's (Discrete Math. 44(1983), 325–326) solution of then-candidate ballot problem, determinantal expressions are obtained. As corollaries the generating functions for skew plane partitions, column-strict skew plane partitions, reverse skew plane plane partitions and column-strict reverse skew plane partitions, respectively, are evaluated, thus establishing partly new results, partly new proofs for known theorems in the theory of plane partitions.     

Presentations of Schützenberger groups of minimal subshifts

In previous work, the first author established a natural bijection between minimal subshifts and maximal regular J -classes of free profinite semigroups. In this paper, the Schützenberger groups of such J -classes are investigated, in particular in respect to a conjecture proposed by the first author concerning their profinite presentation. The conjecture is established for all non-periodic minimal subshifts associated with substitutions. It entails that it is decidable whether a finite group is a quotient of such a profinite group. As a further application, the Schützenberger group of the J -class corresponding to the Prouhet-Thue-Morse subshift is shown to admit a somewhat simpler presentation, from which it follows that it has rank three, and that it is non-free relatively to any pseudovariety of groups.     

Green index in semigroups: generators, presentations, and automatic structures

The Green index of a subsemigroup T of a semigroup S is given by counting strong orbits in the complement S?T under the natural actions of T on S via right and left multiplication. This partitions the complement S?T into T-relative -classes, in the sense of Wallace, and with each such class there is a naturally associated group called the relative Schützenberger group. If the Rees index |S?T| is finite, T also has finite Green index in S. If S is a group and T a subgroup then T has finite Green index in S if and only if it has finite group index in S. Thus Green index provides a common generalisation of Rees index and group index. We prove a rewriting theorem which shows how generating sets for S may be used to obtain generating sets for T and the Schützenberger groups, and vice versa. We also give a method for constructing a presentation for S from presentations of T and the Schützenberger groups. These results are then used to show that several important properties are preserved when passing to finite Green index subsemigroups or extensions, including: finite generation, solubility of the word problem, growth type, automaticity (for subsemigroups), finite presentability (for extensions) and finite Malcev presentability (in the case of group-embeddable semigroups).     

The intersection of free submonoids of a free monoid is free

Several necessary and sufficient conditions exist for a submonoid of a free monoid to be free. For a few, see [1] through [6]. This short note uses one of these conditions, due to Schützenberger (see [2], p. 119, or [4], Theorem 1.4) to establish that the intersection of free submonoids of a free monoid M is again free. Schützenberger's condition is also proven in this note.     

Sliding Presentation of the Jeux de Taquin for Classical Lie Groups

The simple \(GL(n,\mathbb {C})\)-modules are described by using semistandard Young tableaux. Any semistandard skew tableau can be transformed into a well defined semistandard tableau by a combinatorial operation, the Schützenberger jeu de taquin. Associated to the classical Lie groups \(SP(2n,\mathbb {C})\), \(SO(2n+1,\mathbb {C})\), there are other notions of semistandard Young tableaux and jeux de taquin. In this paper, we study these various jeux de taquin, proving that each of them has a simple and explicit formulation as a step-by-step sliding. Any of these jeux de taquin is the restriction of the orthogonal one, associated to \(SO(2n+1,\mathbb {C})\).     

Amalgams of finite inverse semigroups and deterministic context-free languages

Let S be the amalgamated free product of two finite inverse semigroups. We prove that the Schützenberger graph of an element of S with respect to a standard presentation of S is a context-free graph in the sense of Müller and Schupp (Theor. Comput. Sci. 37:51?C75, 1985), showing that the language L recognized by the Schützenberger automaton is context-free. Moreover we construct the grammar generating L proving that L is a deterministic context-free language and we use this fact for solving some algorithmic problems.     

An analogue of the Robinson–Schensted–Knuth correspondence and non-symmetric Cauchy kernels for truncated staircases

We prove a restriction of an analogue of the Robinson–Schensted–Knuth correspondence for semi-skyline augmented fillings, due to Mason, to multisets of cells of a staircase possibly truncated by a smaller staircase at the upper left end corner, or at the bottom right end corner. The restriction to be imposed on the pairs of semi-skyline augmented fillings is that the pair of shapes, rearrangements of each other, satisfies an inequality in the Bruhat order, w.r.t. the symmetric group, where one shape is bounded by the reverse of the other. For semi-standard Young tableaux the inequality means that the pair of their right keys is such that one key is bounded by the Schützenberger evacuation of the other. This bijection is then used to obtain an expansion formula of the non-symmetric Cauchy kernel, over staircases or truncated staircases, in the basis of Demazure characters of type $A$, and the basis of Demazure atoms. The expansion implies Lascoux expansion formula, when specialized to staircases or truncated staircases, and make explicit, in the latter, the Young tableaux in the Demazure crystal by interpreting Demazure operators via elementary bubble sorting operators acting on weak compositions.     

The shifted plactic monoid

We introduce a shifted analog of the plactic monoid of Lascoux and Schützenberger, the shifted plactic monoid. It can be defined in two different ways: via the shifted Knuth relations, or using Haiman’s mixed insertion. Applications include: a new combinatorial derivation (and a new version of) the shifted Littlewood–Richardson Rule; similar results for the coefficients in the Schur expansion of a Schur P-function; a shifted counterpart of the Lascoux–Schützenberger theory of noncommutative Schur functions in plactic variables; a characterization of shifted tableau words; and more.     

The multi-indexed partitional

In this paper we present the multi-indexed partitional. The structure is a generalization of the partitional of Foata and Schützenberger, and gives a combinatorial interpretation for certain multivariate polynomial sequences of binomial type.     

Constructions and presentations for monoids

Presentations are found for the wreath product of two monoids, the Schützenberger product of two monoids, the Bruck-Reilly extension of a monoid, strong semilattices of monoids and Rees matrix semigroups of monoids.     

Divisible and exponent actions of semigroups

In this paper we consider divisible actions of semigroups which have a completely simple minimal ideal and establish that these actions are determined by the divisible actions of the Schützenberger group of the minimal ideal. In the third section, we discuss the concept of an exponent action and present a result which relates the notion of divisible action to the notion of exponent action. The fourth section of this paper exhibits a characterization of exponent functions. To find such a characterization was the original objective of this project.     

Path representation of maximal parabolic Kazhdan–Lusztig polynomials

We provide simple rules for the computation of Kazhdan–Lusztig polynomials in the maximal parabolic case. They are obtained by filling regions delimited by paths with “Dyck strips” obeying certain rules. We compare our results with those of Lascoux and Schützenberger.     

Primitive elements of the Hopf algebras of tableaux

The character theory of symmetric groups, and the theory of symmetric functions, both make use of the combinatorics of Young tableaux, such as the Robinson–Schensted algorithm, Schützenberger’s “jeu de taquin”, and evacuation. In 1995 Poirier and the second author introduced some algebraic structures, different from the plactic monoid, which induce some products and coproducts of tableaux, with homomorphisms. Their starting point are the two dual Hopf algebras of permutations, introduced by the authors in 1995. In 2006 Aguiar and Sottile studied in more detail the Hopf algebra of permutations: among other things, they introduce a new basis, by Möbius inversion in the poset of weak order, that allows them to describe the primitive elements of the Hopf algebra of permutations. In the present Note, by a similar method, we determine the primitive elements of the Poirier–Reutenauer algebra of tableaux, using a partial order on tableaux defined by Taskin.     

An embedding of semigroups into regular semigroups that preserves structure and finiteness

For any semigroup S a regular semigroup is described here that embeds S and is such that its non-trivial maximal subgroups are isomorphic to the Schützenberger groups of S, its Green’s relations restrict to the corresponding Green’s relations on S and it is finite when S is finite.     

McAlister's P-Theorem via Schützenberger Graphs

Abstract

We give a short proof, using Schützenberger graphs, of McAlister's P-theorem. The proof, when restricted to free inverse semigroups, turns into Munn's geometric multiplication of Munn trees.