Search

A key fact about M.-P. Sch\"{u}tzenberger's (1972) promotion operator on rectangular standard Young tableaux is that iterating promotion once per entry recovers the original tableau. For tableaux with strictly increasing rows and columns, H. Thomas and A. Yong (2009) introduced a theory of $K$-jeu de taquin with applications to $K$-theoretic Schubert calculus. The author (2014) studied a $K$-promotion operator $\mathcal{P}$ derived from this theory, but showed that the key fact does not generally extend to $K$-promotion of such increasing tableaux. Here we show that the key fact holds for labels on the boundary of the rectangle. That is, for $T$ a rectanglar increasing tableau with entries bounded by $q$, we have $\mathsf{Frame}(\mathcal{P}^q(T)) = \mathsf{Frame}(T)$, where $\mathsf{Frame}(U)$ denotes the restriction of $U$ to its first and last row and column. Using this fact, we obtain a family of homomesy results on the average value of certain statistics over $K$-promotion orbits, extending a $2$-row theorem of J. Bloom, D. Saracino, and the author (2016) to arbitrary rectangular shapes., Comment: 12 pages

We give a backward jeu de taquin slide analogue on semistandard reverse composition tableaux. These tableaux were first studied by Haglund , Luoto , Mason and van Willigenburg when defining quasisymmetric Schur functions. Our algorithm for performing backward jeu de taquin slides on semistandard reverse composition tableaux results in a natural operator on compositions that we call the jdt operator. This operator in turn gives rise to a new poset structure on compositions whose maximal chains we enumerate. As an application, we also give a noncommutative Pieri rule for noncommutative Schur functions that uses the jdt operators.

We give combinatorial proofs of two identities from the representation theory of the partition algebra $C A_k(n), n \ge 2k$. The first is $n^k = \sum_\lambda f^\lambda m_k^\lambda$, where the sum is over partitions $\lambda$ of $n$, $f^\lambda$ is the number of standard tableaux of shape $\lambda$, and $m_k^\lambda$ is the number of "vacillating tableaux" of shape $\lambda$ and length $2k$. Our proof uses a combination of Robinson-Schensted-Knuth insertion and jeu de taquin. The second identity is $B(2k) = \sum_\lambda (m_k^\lambda)^2$, where $B(2k)$ is the number of set partitions of $\{1, >..., 2k\}$. We show that this insertion restricts to work for the diagram algebras which appear as subalgebras of the partition algebra: the Brauer, Temperley-Lieb, planar partition, rook monoid, planar rook monoid, and symmetric group algebras., Comment: 24 pages

In a 1989 paper, Hanlon and Wales showed that the algebra structure of the Brauer Centralizer Algebra $A_f^{(x)}$ is completely determined by the ranks of certain combinatorially defined square matrices $Z^{\lambda / \mu}$, whose entries are polynomials in the parameter $x$. We consider a set of matrices $M^{\lambda / \mu}$ found by Jockusch that have a similar combinatorial description. These new matrices can be obtained from the original matrices by extracting the terms that are of "highest degree" in a certain sense. Furthermore, the $M^{\lambda / \mu}$ have analogues ${\cal M}^{\lambda / \mu}$ that play the same role that the $Z^{\lambda / \mu}$ play in $A_f^{(x)}$, for another algebra that arises naturally in this context. We find very simple formulas for the determinants of the matrices $M^{\lambda/\mu}$ and ${\cal M}^{\lambda / \mu}$, which prove Jockusch's original conjecture that $\det M^{\lambda / \mu}$ has only integer roots. We define a Jeu de Taquin algorithm for standard matchings, and compare this algorithm to the usual Jeu de Taquin algorithm defined by Schützenberger for standard tableaux. The formulas for the determinants of $M^{\lambda/\mu}$ and ${\cal M}^{\lambda / \mu}$ have elegant statements in terms of this new Jeu de Taquin algorithm.

We discuss the Robinson-Schensted and Schutzenberger algorithms, and the fundamental identities they satisfy, systematically interpreting Young tableaux as chains in the Young lattice. We also derive a Robinson-Schensted algorithm for the hyperoctahedral groups. Finally we show how the mentioned identities imply some fundamental properties of Schutzenberger's glissements. The two algorithms referred to in our title are combinatorial algorithms dealing with Young tableaux. The former was found originally by G. de B. Robinson (Rob), and independently rediscovered much later, and in a difierent form, by C. Schensted (Sche); it establishes a bijective correspondence between permutations and pairs of Young tableaux of equal shape. The latter algorithm (which is sometimes associated with the term jeu de taquin) was introduced by M. P. Schutzenberger (Schu1), who also demonstrated its great importance in relation to the former algorithm; it establishes a shape preserving involutory correspondence between Young tableaux. These algorithms have been studied mainly for their own sake|they exhibit quite remarkable combinatorial properties|rather than primarily serving (as is usually the case with algorithms) as a means of computing some mathematical value. 0.1. Some history. The Robinson-Schensted algorithm is the older of the two algorithms considered here. It was flrst de- scribed in 1938 by Robinson (Rob), in a paper dealing with the representation theory of the symmetric and general linear groups, and in particular with an attempt to prove the correctness of the rule that Littlewood and Richardson (LiRi) had given for the computation of the coe-cients in the decomposition of products of Schur functions. Robinson's description of the algorithm is rather obscure however, and his proof of the Littlewood-Richardson rule incomplete; apart from the fact that the supposed proof was reproduced in (Littl), the algorithm does not appear to have received much mention in the literature of the subsequent decades. The great interest the algorithm enjoys nowadays by combinatorialists was triggered by its independent reformulation by Schensted (Sche) published in 1961, whose main objective was counting permutations with given lengths of their longest increasing and decreasing subsequences; it was not recognised until several years later that this algorithm is essentially the same as Robinson's, despite its rather difierent deflnition. The combinatorial signiflcance of Schensted's algorithm was indi- cated by Schutzenberger (Schu1), who at the same time introduced the other algorithm that we shall be considering (the operation called I in (Schu1,x5)): he stated a number of important identities satisfled by the correspondences deflned by the two algorithms, and relations between them. That paper represents a big step forward in the understanding of the Robinson-Schensted algorithm, but the important results are somewhat obscured by the complicated notation and many minor errors, and by the fact that its emphasis lies on treating the limiting case of inflnite permutations and Young tableaux, a generalisation that has been ignored in the further development of the subject.

A bijective proof of the product formula for the principal specialization of super Schur functions (also called hook Schur functions) is given using the combinatorial description of super Schur functions in terms of certain tableaux due to Berele and Regev. Our bijective proof is based on the Hillman–Grassl algorithm and a modified version of Schützenberger's jeu de taquin. We then explore the relationship between our modified jeu de taquin and a modified jeu de taquin by Goulden and Greene. We define a common extension and prove an invariance property for it, thus discovering that both modified jeu de taquins are, though different, equivalent.