A simple bijectio n betwee n sta ndard 3× n tableaux a nd irreducible webs for $\mathfrak{sl}_{3}$

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₂\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 \mathfraksl₃\mathfrak{sl}_{3} whose boundary vertices are all sources.     

Symmetry and Log-Concavity Results for Statistics on Fibonacci Tableaux

In this paper, we study the properties of the inversion statistic and the Fibonacci major index, Fibmaj, as defined on standard Fibonacci tableaux. We prove that these two statistics are symmetric and log-concave over all standard Fibonacci tableaux of a given shape μ and provide two combinatorial proofs of the symmetry result, one a direct bijection on the set of tableaux and the other utilizing 0, 1-fillings of a staircase shape. We conjecture that the inversion and Fibmaj statistics are log-concave over all standard Fibonacci tableaux of a given size n. In addition, we show a well-known bijection between standard Fibonacci tableaux of size n and involutions in S _n which takes the Fibmaj statistic to a new statistic called the submajor index on involutions.     

Increasing Tableaux,Narayana Numbers and an Instance of the Cyclic Sieving Phenomenon

We give a counting formula for the set of rectangular increasing tableaux in terms of generalized Narayana numbers. We define small m–Schröder paths and give a bijection between the set of increasing rectangular tableaux and small m–Schröder paths, generalizing a result of Pechenik [4]. Using K–jeu de taquin promotion, we give a cyclic sieving phenomenon for the set of increasing hook tableaux.     

Admissible Pictures and U 𝔮(𝔤𝔩(m,n))–Littlewood–Richardson Tableaux

We construct a natural bijection between the set of admissible pictures and the set of U_q(𝔤𝔩(m, n))–Littlewood–Richardson tableaux.     

Shifted tableaux,schur Q-functions,and a conjecture of R. Stanley

We present an analog of the Robinson-Schensted correspondence that applies to shifted Young tableaux and is considerably simpler than the one proposed in [B. E. Sagan, J. Combin. Theory Ser. A 27 (1979), 10–18]. In addition, this algorithm enjoys many of the important properties of the original Robinson-Schensted map including an interpretation of row lengths in terms of k-increasing sequences, a jeu de taquin, and a generalization to tableaux with repeated entries analogous to Knuth's construction (Pacific J. Math. 34 (1970), 709–727). The fact that the Knuth relations hold for our algorithm yields a simple proof of a conjecture of Stanley.     

Pairs of noncrossing free Dyck paths and noncrossing partitions

Using the bijection between partitions and vacillating tableaux, we establish a correspondence between pairs of noncrossing free Dyck paths of length 2n and noncrossing partitions of [2n+1] with n+1 blocks. In terms of the number of up steps at odd positions, we find a characterization of Dyck paths constructed from pairs of noncrossing free Dyck paths by using the Labelle merging algorithm.     

Permutation tableaux and permutation patterns

In this paper we introduce and study a class of tableaux which we call permutation tableaux; these tableaux are naturally in bijection with permutations, and they are a distinguished subset of the -diagrams of Alex Postnikov [A. Postnikov, Webs in totally positive Grassmann cells, in preparation; L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. The structure of these tableaux is in some ways more transparent than the structure of permutations; therefore we believe that permutation tableaux will be useful in furthering the understanding of permutations. We give two bijections from permutation tableaux to permutations. The first bijection carries tableaux statistics to permutation statistics based on relative sizes of pairs of letters in a permutation and their places. We call these statistics weak excedance statistics because of their close relation to weak excedances. The second bijection carries tableaux statistics (via the weak excedance statistics) to statistics based on generalized permutation patterns. We then give enumerative applications of these bijections. One nice consequence of these results is that the polynomial enumerating permutation tableaux according to their content generalizes both Carlitz' q-analog of the Eulerian numbers [L. Carlitz, q-Bernoulli and Eulerian numbers, Trans. Amer. Math. Soc. 76 (1954) 332-350] and the more recent q-analog of the Eulerian numbers found in [L. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005) 319-342]. We conclude our paper with a list of open problems, as well as remarks on progress on these problems which has been made by A. Burstein, S. Corteel, N. Eriksen, A. Reifegerste, and X. Viennot.     

Rational tableaux and the tensor algebra of gln

A generalization of the usual column-strict tableaux (equivalent to a construction of R. C. King) is presented as a natural combinatorial tool for the study of finite dimensional representations of GL_n(C). These objects are called rational tableaux since they play the same role for rational representations of GL_n as ordinary tableaux do for polynomial representations. A generalization of Schensted's insertion algorithm is given for rational tableaux, and is used to count the. multiplicities of the irreducible GL_n-modules in the tensor algebra of GL_n. The problem of counting multiplicities when the kth tensor power gl_n^⊗k is decomposed into modules which are simultaneously irreducible with respect to GL_n and the symmetric group S_k is also considered. The existence of an insertion algorithm which describes this decomposition is proved. A generalization of border strip tableaux, in which both addition and deletion of border strips is allowed, is used to describe the characters associated with this decomposition. For large n, these generalized border strip tableaux have a simple structure which allows derivation of identities due to Hanlon and Stanley involving the (large n) decomposition of gl_n^⊗k.     

Evacuation and a geometric construction for Fibonacci tableaux

Tableaux have long been used to study combinatorial properties of permutations and multiset permutations. Discovered independently by Robinson and Schensted and generalized by Knuth, the Robinson–Schensted correspondence has provided a fundamental tool for relating permutations to tableaux. In 1963, Schützenberger defined a process called evacuation on standard tableaux which gives a relationship between the pairs of tableaux (P,Q) resulting from the Schensted correspondence for a permutation and both the reverse and the complement of that permutation. Viennot gave a geometric construction for the Schensted correspondence and Fomin described a generalization of the correspondence which provides a bijection between permutations and pairs of chains in Young's lattice.In 1975, Stanley defined a Fibonacci lattice and in 1988 he introduced the idea of a differential poset. Roby gave an insertion algorithm, analogous to the Schensted correspondence, for mapping a permutation to a pair of Fibonacci tableaux. The main results of this paper are to give an evacuation algorithm for the Fibonacci tableaux that is analogous to the evacuation algorithm on Young tableaux and to describe a geometric construction for the Fibonacci tableaux that is similar to Viennot's geometric construction for Young tableaux.     

Properties of the nonsymmetric Robinson–Schensted–Knuth algorithm

We introduce a generalization of the Robinson–Schensted–Knuth insertion algorithm for semi-standard augmented fillings whose basement is an arbitrary permutation σ∈S _n . If σ is the identity, then our insertion algorithm reduces to the insertion algorithm introduced by the second author (Sémin. Lothar. Comb. 57:B57e, 2006) for semi-standard augmented fillings and if σ is the reverse of the identity, then our insertion algorithm reduces to the original Robinson–Schensted–Knuth row insertion algorithm. We use our generalized insertion algorithm to obtain new decompositions of the Schur functions into nonsymmetric elements called generalized Demazure atoms (which become Demazure atoms when σ is the identity). Other applications include Pieri rules for multiplying a generalized Demazure atom by a complete homogeneous symmetric function or an elementary symmetric function, a generalization of Knuth’s correspondence between matrices of non-negative integers and pairs of tableaux, and a version of evacuation for composition tableaux whose basement is an arbitrary permutation σ.     

The structure of alternative tableaux

In this paper we study alternative tableaux introduced by Viennot [X. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk in Cambridge, 2008]. These tableaux are in simple bijection with permutation tableaux, defined previously by Postnikov [A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764v1 [math.CO], 2006].We exhibit a simple recursive structure for alternative tableaux, from which we can easily deduce a number of enumerative results. We also give bijections between these tableaux and certain classes of labeled trees. Finally, we exhibit a bijection with permutations, and relate it to some other bijections that already appeared in the literature.     

Affine crystal structure on rigged configurations of type D_{n}^{(1)}

Extending the work in Schilling (Int. Math. Res. Not. 2006:97376, 2006), we introduce the affine crystal action on rigged configurations which is isomorphic to the Kirillov–Reshetikhin crystal B ^r,s of type $D_{n}^{(1)}$ for any r,s. We also introduce a representation of B ^r,s (r≠n?1,n) in terms of tableaux of rectangular shape r×s, which we coin Kirillov–Reshetikhin tableaux (using a nontrivial analogue of the type A column splitting procedure) to construct a bijection between elements of a tensor product of Kirillov–Reshetikhin crystals and rigged configurations.     

Enumeration des tableaux standards

Nous présentons dans cet article un algorithme qui permet de construire parmi les tableaux standards de forme donnée (ou tableaux de Young), celui qui est de rang R. On ordonne l'ensemble des tableaux standards $\text{D}$_a correspondant au diagramme de Ferrers du partage a. que l'on met en bijection avec {1,2,…,card$\text{D}$_a}. L'algorithme construit, par une méthode de dénombrement des chemins intermédiaries entre deux partages dans le treillis de Young, le R-iéme tableau.Cette méthode de rangement des tableaux standards s'applique á l'énumération des permutations dont les plus longues suites extraites croissantes et décroissantes sont de longueurs fixées et á l'énumération des permutations qui présentent une séquence de “croissances-décroissances” (up-down) donnée.     

A Bijection from Staircase Tableaux to Inversion Tables,Giving Some Eulerian and Mahonian Statistics

We give a simple bijection between staircase tableaux and inversion tables. Some nice properties of the bijection allow us to easily compute the generating polynomials of subsets of the staircase tableaux. We also give a combinatorial interpretation of some statistics of these tableaux in terms of permutations.     

A bijection proving orthogonality of the characters of Sn

Suppose ? and β are partitions of n. If ? ? β, a bijection is given between positive pairs of rim hook tableaux of the same shape λ and content β and ?, respectively, and negative pairs of rim hook tableaux of some other shape μ and content β and ?, respectively. If ? = β, the bijection is between positive pairs and either negative pairs or permutations of hooks. The bijection, in the latter case, is a generalization of the Schensted correspondence between pairs of standard tableaux and permutations. If the irreducible characters of S_n are interpreted combinatorially using the Murnaghan-Nakayama formula, these bijections prove

$\text{∑}\text{λ}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\rho }}\text{X}{}^{\mathrm{\lambda }}{}_{\mathrm{\beta }}\text{=δ}{}_{\mathrm{\rho \beta }}\text{1}{}^{\mathrm{j1}}\text{J1!2}{}^{\mathrm{j2}}\text{J2!…}$

where ? = 1^j12^j2….     

Weighted inversion numbers,restricted growth functions,and standard young tableaux

We give a family of weighted inversion numbers with the same generating function which interpolate between the inversion number and MacMahon's major index. Foata's bijection is obtained in a natural way from a simple involution. An alternative proof uses q-difference equations which yield some new results. We obtain a new generating function for restricted growth functions and two q-analogs of a formula for the number of standard Young tableaux of a given shape. While the first really goes back to MacMahon, the second uses one of our weighted inversion numbers and appears to be new.     

Standard Young tableaux and colored Motzkin paths

In this paper, we propose a notion of colored Motzkin paths and establish a bijection between the n-cell standard Young tableaux (SYT) of bounded height and the colored Motzkin paths of length n. This result not only gives a lattice path interpretation of the standard Young tableaux but also reveals an unexpected intrinsic relation between the set of SYTs with at most $2d+1$ rows and the set of SYTs with at most 2d rows.     

A symplectic jeu de taquin bijection between the tableaux of King and of De Concini

The definitions, methods, and results are entirely combinatorial. The symplectic jeu de taquin algorithm developed here is an extension of Schützenberger's original jeu de taquin and acts on a skew form of De Concini's symplectic standard tableaux. This algorithm is used to construct a weight preserving bijection between the two most widely known sets of symplectic tableaux. Anticipated applications to Knuth relations and to decomposing symplectic tensor products are indicated.

     

The Abelian sandpile model on Ferrers graphs — A classification of recurrent configurations

We classify all recurrent configurations of the Abelian sandpile model (ASM) on Ferrers graphs. The classification is in terms of decorations of EW-tableaux, which undecorated are in bijection with the minimal recurrent configurations. We introduce decorated permutations, extending to decorated EW-tableaux a bijection between such tableaux and permutations, giving a direct bijection between the decorated permutations and all recurrent configurations of the ASM. We also describe a bijection between the decorated permutations and the intransitive trees of Postnikov, the breadth-first search of which corresponds to a canonical toppling of the corresponding configurations.