Search

There exists a well-known hook-length formula for calculating the dimensions of two-dimensional Young diagrams. Unfortunately, an analogous formula for the three-dimensional case is unknown. We introduce an approach to calculating estimated dimensions of three-dimensional Young diagrams, also known as plane partitions. The most difficult part of this task is the calculation of the cotransition probabilities for a central Markov process. We suggest an algorithm for an approximate calculation of these probabilities. It generates numerous random paths to a given diagram. In the case where the generated paths are uniformly distributed, the proportion of paths passing through a certain edge gives us an approximate value of the cotransition probability. As our numerical experiments show, a random generator based on the randomized version of the Schutzenberger transformation allows one to obtain accurate values of cotransition probabilities. Also, a method for constructing three-dimensional Young diagrams with large dimensions is suggested. Bibliography: 13 titles.

In this article, we prove combinatorial and algebraic properties on the plactic and hypoplactic congruences via a new rewriting approach on tableaux, that we apply to the jeu de taquin and the right-bottom recti cation algorithms. The jeu de taquin is an algorithm that transforms a skew tableau into a Young tableau by local transformation rules on the columns of the tableaux. This algorithm has remarkable combinatorial and algorithmic properties, in particular it is con uent, that is the resulting Young tableau does not depend on the way the local transformations rules are applied. We introduce the notion of string of columns rewriting system in order to study rewriting properties of algorithms de ned on glued sequences of columns. We prove the convergence of the jeu de taquin and we show how to deduce algebraic properties on the plactic congruence. We de ne the right-bottom recti cation algorithm that transforms a Young tableau into a quasi-ribbon tableau by a string of columns rewriting system. We prove its convergence and we deduce algebraic properties on the hypoplactic congruence.

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, Schuetzenberger'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 Moebius 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., 10 pages, 2 figures

This paper completely characterizes the standard Young tableaux that can be reconstructed from their sets or multisets of $1$-minors. In particular, any standard Young tableau with at least $5$ entries can be reconstructed from its set of $1$-minors., 9 pages

Kirillov–Reshetikhin (KR) crystals are colored directed graphs encoding the structure of certain finite-dimensional representations of affine Lie algebras. A tensor product of column shape Kirillov–Reshetikhin crystals has recently been realized in a uniform way, for all untwisted affine types, in terms of the so-called quantum alcove model. We enhance this model by using it to give a uniform realization of the corresponding combinatorial R -matrix, i.e., the unique affine crystal isomorphism permuting factors in a tensor product of column shape KR crystals. In other words, we are generalizing to all Lie types Schutzenberger's sliding game (jeu de taquin) for Young tableaux, which realizes the combinatorial R -matrix in type A . Our construction is in terms of certain combinatorial moves, called quantum Yang–Baxter moves, which are explicitly described by reduction to the rank 2 root systems. We also show that the quantum alcove model does not depend on the choice of a sequence of alcoves joining the fundamental one to a translation of it.

We provide an explicit combinatorial description of the embedding of the crystal of Kashiwara–Nakashima tableaux in types B and C into that of i-Lusztig data associated to a family of reduced expressions i of the longest element w 0 . The description of the embedding is simple and elementary using only the Schutzenberger's jeu de taquin and RSK algorithm. A spinor model for classical crystals plays an important role as an intermediate object connecting Kashiwara–Nakashima tableaux and Lusztig data.

We introduce edge labeled Young tableaux. Our main results provide a corresponding analogue of [Sch\"{u}tzenberger '77]'s theory of jeu de taquin. These are applied to the equivariant Schubert calculus of Grassmannians. Reinterpreting, we present new (semi)standard tableaux to study factorial Schur polynomials, after [Biedenharn-Louck '89], [Macdonald '92] and [Goulden-Greene '94] and others. Consequently, we obtain new combinatorial rules for the Schubert structure coefficients, complementing work of [Molev-Sagan '99], [Knutson-Tao '03], [Molev '08] and [Kreiman '09]. We also describe a conjectural generalization of one of our rules to the equivariant K-theory of Grassmannians, extending work of [Thomas-Yong '07]. This conjecture concretely realizes the "positivity" known to exist by [Anderson-Griffeth-Miller '08]. It provides an alternative to the conjectural rule of Knutson-Vakil reported in [Coskun-Vakil '06].

We describe the embedding from the crystal of Kashiwara-Nakashima tableaux in type $D$ of an arbitrary shape into that of $\mathbf{i}$-Lusztig data associated to a family of reduced expressions $\mathbf{i}$ which are compatible with the maximal Levi subalgebra of type $A$. The embedding is described explicitly in terms of well-known combinatorics of type $A$ including the Sch\"{u}tzenberger's jeu de taquin and an analog of RSK algorithm., Comment: 35 pages, typos corrected, comments added on Remark 5.3 and Remark 5.4, to appear in Algebras and Representation Theory

International audience; The diamond cone is a combinatorial description for a basis of a natural indecomposable n-module, where n is the nilpotent factor of a complex semisimple Lie algebra g. After N. J. Wildberger who introduced this notion, this description was achieved for g = sl(n) , the rank 2 semisimple Lie algebras and g = sp (2n).In this work, we generalize these constructions to the Lie algebra g = so(2n + 1). The orthogonal semistandard Young tableaux were defined by M. Kashiwara and T. Nakashima, they index a basis for the shape algebra of so(2n + 1). Defining the notion of orthogonal quasistandard Young tableaux, we prove that these tableaux describe a basis for a quotient of the shape algebra, the reduced shape algebra of so(2n + 1).

We introduce tableau stabilization, a new phenomenon and statistic on Young tableaux based on jeu de taquin. We investigate bounds for tableau stabilization, the shape of stabilized tableaux, and tableau stabilization as a permutation statistic. We apply tableau stabilization to construct the sufficiently large rectangular tableaux fixed by powers of promotion, which were counted by Brendon Rhoades via the cyclic sieving phenomenon [(Rhoades in J Combin Theory Ser A 117(1):38–76, 2010), Theorem 1.3].

We explain how genomic tableaux [Pechenik-Yong '15] are a semistandard complement to increasing tableaux [Thomas-Yong '09]. From this perspective, one inherits genomic versions of jeu de taquin, Knuth equivalence, infusion and Bender-Knuth involutions, as well as Schur functions from (shifted) semistandard Young tableaux theory. These are applied to obtain new Littlewood-Richardson rules for K-theory Schubert calculus of Grassmannians (after [Buch '02]) and maximal orthogonal Grassmannians (after [Clifford-Thomas-Yong '14], [Buch-Ravikumar '12]). For the unsolved case of Lagrangian Grassmannians, sharp upper and lower bounds using genomic tableaux are conjectured., Comment: 30 pages, color figures

We prove that the number of 01-fillings of a given stack polyomino (a polyomino with justified rows whose lengths form a unimodal sequence) with at most one 1 per column which do not contain a fixed-size northeast chain and a fixed-size southeast chain, depends only on the set of row lengths of the polyomino. The proof is via a bijection between fillings of stack polyominoes which differ only in the position of one row and uses the Hecke insertion algorithm by Buch, Kresch, Shimozono, Tamvakis, and Yong and the jeu de taquin for increasing tableaux of Thomas and Yong. Moreover, our bijection gives another proof of the result by Chen, Guo, and Pang that the crossing number and the nesting number have a symmetric joint distribution over linked partitions.

Using Henriques' and Kamnitzer's cactus groups, Schutzenberger's promotion and evacuation operators on standard Young tableaux can be generalised in a very natural way to operators acting on highest weight words in tensor products of crystals. For the crystals corresponding to the vector representations of the symplectic groups, we show that Sundaram's map to perfect matchings intertwines promotion and rotation of the associated chord diagrams, and evacuation and reversal. We also exhibit a map with similar features for the crystals corresponding to the adjoint representations of the general linear groups. We prove these results by applying van Leeuwen's generalisation of Fomin's local rules for jeu de taquin, connected to the action of the cactus groups by Lenart, and variants of Fomin's growth diagrams for the Robinson-Schensted correspondence.

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 Schutzenberger 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})$ .

In this paper, we study tropical-theoretic aspects of the ``rectification algorithm'' on skew Young tableaux. It is shown that the algorithm is interpreted as a time evolution of some tropical integrable system. By using this fact, we construct a new combinatorial map that is essentially equivalent to the rectification algorithm. Some of properties of the rectification can be seen more clearly via this map. For example, the uniqueness of a rectification boils down to an easy combinatorial problem. Our method is mainly based on the two previous researches: the theory of geometric tableaux by Noumi-Yamada, and the study on the relationship between jeu de taquin slides and the ultradiscrete KP equation by Mikami and Katayama-Kakei., Comment: 22pages, 1 figure. Most part of this paper (except for Sections 5.4, 5.5, and 6) is an English translation of the author's unpublished manuscript "S. Iwao, Jeu de taquin, uniqueness of a rectification, and ultradiscrete KP'' written in Japanese

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

Although d-complete posets arose along the interface between algebraic combinatorics and Lie theory, they are defined using only requirements on their local structure. These posets are a mutual generalization of rooted trees, shapes, and shifted shapes. They possess Stanley's hook product property for their P-partition generating functions and Schutzenberger's well defined jeu de taquin rectification property. The original definition of d-complete poset was lengthy, but more succinct definitions were later developed. Here several definitions are shown to be equivalent. The basic properties of d-complete posets are summarized. Background and a partial bibliography for these posets is given., 26 pages, 5 figures. On the question of how to define the notion of "d-complete" for infinite posets: A sentence on p. 6 is reworded, the last sentence on p. 16 is deleted, and an Added Note is inserted. References [KiYo] and [NrOk] are new. This is the final uncopyrighted version; the 'Order' journal version will also include several small exposition clarifications from the referee

Based on Thomas and Yong's K-theoretic jeu de taquin algorithm, we prove a uniform Littlewood-Richardson rule for the K-theoretic Schubert structure constants of all minuscule homogeneous spaces. Our formula is new in all types. For the main examples of Grassmannians of type A and maximal orthogonal Grassmannians it has the advantage that the tableaux to be counted can be recognized without reference to the jeu de taquin algorithm., 37 pages

Jeu-de-taquin promotion yields a bijection on the set of semistandard @l-tableaux with entries bounded by k. In this note, we determine the order of jeu-de-taquin promotion on the set of semistandard hook tableaux CST((n-m,1^m),k), with entries bounded by k, and on the set of semistandard hook tableaux with fixed content @a, CST((n-m,1^m),k,@a). We give a bijection between CST((n-m,1^m),k,@a) and a suitable set of standard hook tableaux that behaves nicely with respect to jeu-de-taquin promotion and use the bijection to give a cyclic sieving phenomenon for CST((n-m,1^m),k,@a).

The sl 3 spider is a diagrammatic category used to study the representation theory of the quantum group U q (sl 3). The morphisms in this category are generated by a basis of non-elliptic webs. Khovanov–Kuperberg observe that non-elliptic webs are indexed by semistandard Young tableaux. They establish this bijection via a recursive growth algorithm. Recently, Tymoczko gave a simple version of this bijection in the case that the tableaux are standard and used it to study rotation and join of webs. This article builds on Tymoczko’s bijection to give a simple and explicit algorithm for constructing all non-elliptic sl 3 webs. As an application, we generalize results of Petersen–Pylyavskyy–Rhoades and Tymoczko proving that, for all non-elliptic sl 3 webs, rotation corresponds to jeu de taquin promotion and join corresponds to shuffling.

We prove a conjecture of Knutson asserting that the Schubert structure constants of the cohomology ring of a two-step flag variety are equal to the number of puzzles with specified border labels that can be created using a list of eight puzzle pieces. As a consequence, we obtain a puzzle formula for the Gromov-Witten invariants defining the small quantum cohomology ring of a Grassmann variety of type A. The proof of the conjecture proceeds by showing that the puzzle formula defines an associative product on the cohomology ring of the two-step flag variety. It is based on an explicit bijection of gashed puzzles that is analogous to the jeu de taquin algorithm but more complicated., Final Version. 32 pages; 381 figures (best viewed in color)

The Wronski map is a finite, PGL_2(C)-equivariant morphism from the Grassmannian Gr(d,n) to a projective space (the projectivization of a vector space of polynomials). We consider the following problem. If C_r < PGL_2(C) is a cyclic subgroup of order r, how may C_r-fixed points are in the in a fibre of the Wronski map over a C_r-fixed point in the base? In this paper, we compute a general answer in terms of r-ribbon tableaux. When r=2, this computation gives the number of real points in the fibre of the Wronski map over a real polynomial with purely imaginary roots. More generally, we can compute the number of real points in certain intersections of Schubert varieties. When r divides d(n-d) our main result says that the generic number of C_r-fixed points in the fibre is the number of standard r-ribbon tableaux rectangular shape (n-d)^d. Computing by a different method, we show that the answer in this case is also given by the number of of standard Young tableaux of shape (n-d)^d that are invariant under N/r iterations of jeu de taquin promotion. Together, these two results give a new proof of Rhoades' cyclic sieving theorem for promotion on rectangular tableaux. We prove analogous results for dihedral group actions., 63 pages, 11 colour figures. Uses LaTeX "rotating" package which may not render correctly in xdvi

We present a proof of a Littlewood–Richardson rule for the K-theory of odd orthogonal Grassmannians OG(n,2n+1), as conjectured by Thomas–Yong (2009). Specifically, we prove that rectification using the jeu de taquin for increasing shifted tableaux introduced there, is well-defined and gives rise to an associative product. Recently, Buch–Ravikumar (2012) proved a Pieri rule for OG(n,2n+1) that confirms a special case of the conjecture. Together, these results imply the aforementioned conjecture.

Combinatorial spiders are a model for the invariant space of the tensor product of representations. The basic objects, webs, are certain directed planar graphs with boundary; algebraic operations on representations correspond to graph-theoretic operations on webs. Kuperberg developed spiders for rank 2 Lie algebras and $\mathfrak {sl}_{2}$ . Building on a result of Kuperberg, Khovanov---Kuperberg found a recursive algorithm giving a bijection between standard Young tableaux of shape 3×n and irreducible webs for $\mathfrak{sl}_{3}$ whose boundary vertices are all sources. In this paper, we give a simple and explicit map from standard Young tableaux of shape 3×n to irreducible webs for $\mathfrak {sl}_{3}$ whose boundary vertices are all sources and show that it is the same as Khovanov---Kuperberg's map. Our construction generalizes to some webs with both sources and sinks on the boundary. Moreover, it allows us to extend the correspondence between webs and tableaux in two ways. First, we provide a short, geometric proof of Petersen---Pylyavskyy---Rhoades's recent result that rotation of webs corresponds to jeu-de-taquin promotion on 3×n tableaux. Second, we define another natural operation on tableaux called a shuffle and show that it corresponds to the join of two webs. Our main tool is an intermediary object between tableaux and webs that we call an m-diagram. The construction of m-diagrams, like many of our results, applies to shapes of tableaux other than 3×n.