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.     

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.     

Four correspondences between graphs and generalized young tableaux

Read's method of counting the number of undirected labeled graphs with a prescribed valency at each labeled node implies that the number of different graphs with a given degree sequence (d₁, d₂, d₃…d_n) is equal to the number of generalized Young tableaux of a certain shape filled with objects of specification (d₁, d₂, d₃…d_n). There are in fact four such results which are applicable to graphs with or without loops and with or without multiple edges. This paper contains four one-one correspondences between the four types of graph and generalized Young tableaux having four different shapes. The correspondences can be considered as combinatorial proofs of four identities of Littlewood.     

An explicit bijection between semistandard tableaux and non-elliptic sl 3 webs

The sl ₃ spider is a diagrammatic category used to study the representation theory of the quantum group U _q (sl ₃). 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 ₃ webs. As an application, we generalize results of Petersen–Pylyavskyy–Rhoades and Tymoczko proving that, for all non-elliptic sl ₃ webs, rotation corresponds to jeu de taquin promotion and join corresponds to shuffling.     

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.     

On the Orthogonal Tableaux of Koike and Terada

Many different definitions have been given for semistandard odd and even orthogonal tableaux which enumerate the corresponding irreducible orthogonal characters. Weightpreserving bijections have been provided between some of these sets of tableaux (see [3], [8]). We give bijections between the (semistandard) odd orthogonal Koike-Terada tableaux and the odd orthogonal Sundaram-tableaux and between the even orthogonal Koike-Terada tableaux and the even orthogonal King-Welsh tableaux. As well, we define an even version of orthogonal Sundaram tableaux which enumerate the irreducible characters of O(2n).     

Combinatorics of the K-theory of affine Grassmannians

We introduce a family of tableaux that simultaneously generalizes the tableaux used to characterize Grothendieck polynomials and k-Schur functions. We prove that the polynomials drawn from these tableaux are the affine Grothendieck polynomials and k-K-Schur functions – Schubert representatives for the K-theory of affine Grassmannians and their dual in the nil Hecke ring. We prove a number of combinatorial properties including Pieri rules.     

Pattern avoidance for alternating permutations and Young tableaux

We define a class Ln,k of permutations that generalizes alternating (up-down) permutations and give bijective proofs of certain pattern-avoidance results for this class. As a special case of our results, we give bijections between the set A2n(1234) of alternating permutations of length 2n with no four-term increasing subsequence and standard Young tableaux of shape 〈n³〉, and between the set A2n+1(1234) and standard Young tableaux of shape 〈³n−1,2,1〉. This represents the first enumeration of alternating permutations avoiding a pattern of length four. We also extend previous work on doubly-alternating permutations (alternating permutations whose inverses are alternating) to our more general context.The set Ln,k may be viewed as the set of reading words of the standard Young tableaux of a certain skew shape. In the last section of the paper, we expand our study to consider pattern avoidance in the reading words of standard Young tableaux of any skew shape. We show bijectively that the number of standard Young tableaux of shape λ/μ whose reading words avoid 213 is a natural μ-analogue of the Catalan numbers (and in particular does not depend on λ, up to a simple technical condition), and that there are similar results for the patterns 132, 231 and 312.     

Young-Fibonacci insertion, tableauhedron and Kostka numbers

This work is first concerned with some properties of the Young-Fibonacci insertion algorithm and its relation with Fomin's growth diagrams. It also investigates a relation between the combinatorics of Young-Fibonacci tableaux and the study of Okada's algebras associated to the Young-Fibonacci lattice. The original algorithm was introduced by Roby and we redefine it in such a way that both the insertion and recording tableaux of any permutation are conveniently interpreted as saturated chains in the Young-Fibonacci lattice. Using our conventions, we give a simpler proof of a property of Killpatrick's evacuation algorithm for Fibonacci tableaux. It also appears that this evacuation is no longer needed in making Roby's and Fomin's constructions coincide. We provide the set of Young-Fibonacci tableaux of size n with a structure of graded poset called tableauhedron, induced by the weak order of the symmetric group, and realized by transitive closure of elementary transformations on tableaux. We show that this poset gives a combinatorial interpretation of the coefficients of the transition matrix from the analogue of complete symmetric functions to analogue of the Schur functions in Okada's algebra associated to the Young-Fibonacci lattice. We prove a similar result relating usual Kostka numbers with four partial orders on Young tableaux, studied by Melnikov and Taskin.     

q-Analog of tableau containment

We prove a q-analog of the following result due to McKay, Morse and Wilf: the probability that a random standard Young tableau of size n contains a fixed standard Young tableau of shape λ?k tends to fλ/k! in the large n limit, where fλ is the number of standard Young tableaux of shape λ. We also consider the probability that a random pair (P,Q) of standard Young tableaux of the same shape contains a fixed pair (A,B) of standard Young tableaux.     

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.     

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 σ.     

Properties of four partial orders on standard Young tableaux

Let SYTn be the set of all standard Young tableaux with n cells. After recalling the definitions of four partial orders, the weak, KL, geometric and chain orders on SYTn and some of their crucial properties, we prove three main results:

•

Intervals in any of these four orders essentially describe the product in a Hopf algebra of tableaux defined by Poirier and Reutenauer.

•

The map sending a tableau to its descent set induces a homotopy equivalence of the proper parts of all of these orders on tableaux with that of the Boolean algebra ²[n−1]. In particular, the Möbius function of these orders on tableaux is (−1)ⁿ⁻³.

•

For two of the four orders, one can define a more general order on skew tableaux having fixed inner boundary, and similarly analyze their homotopy type and Möbius function.

     

Cyclic sieving, promotion, and representation theory

We prove a collection of conjectures of White [D. White, personal communication, 2007], as well as some related conjectures of Abuzzahab, Korson, Li, and Meyer [O. Abuzzahab, M. Korson, M. Li, S. Meyer, Cyclic and dihedral sieving for plane partitions, U. Minnesota REU Report, 2005] and of Reiner and White [V. Reiner, personal communication, 2007; D. White, personal communication, 2007], regarding the cyclic sieving phenomenon of Reiner, Stanton and White [V. Reiner, D. Stanton, D. White, The cyclic sieving phenomenon, J. Combin. Theory Ser. A 108 (2004)] as it applies to jeu-de-taquin promotion on rectangular tableaux. To do this, we use Kazhdan-Lusztig theory and a characterization of the dual canonical basis of C[x₁₁,…,xnn] due to Skandera [M. Skandera, On the dual canonical and Kazhdan-Lusztig bases and 3412, 4231-avoiding permutations, 2006, submitted for publication]. Afterwards, we extend our results to analyzing the fixed points of a dihedral action on rectangular tableaux generated by promotion and evacuation, suggesting a possible sieving phenomenon for dihedral groups. Finally, we give applications of this theory to cyclic sieving phenomena involving reduced words for the long elements of hyperoctohedral groups and noncrossing partitions.     

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.     

Crystal bases of modified quantized enveloping algebras and a double RSK correspondence

We give a new combinatorial realization of the crystal base of the modified quantized enveloping algebras of type A+∞ or A_∞. It is obtained by describing the decomposition of the tensor product of a highest weight crystal and a lowest weight crystal into extremal weight crystals, and taking its limit using a tableaux model of extremal weight crystals. This realization induces in a purely combinatorial way a bicrystal structure of the crystal base of the modified quantized enveloping algebras and hence its Peter-Weyl type decomposition generalizing the classical RSK correspondence.     

Relations between the Clausen and Kazhdan-Lusztig representations of the symmetric group

We use Kazhdan-Lusztig polynomials and subspaces of the polynomial ring C[x_1,1,…,x_n,n] to give a new construction of the Kazhdan-Lusztig representations of S_n. This construction produces exactly the same modules as those which Clausen constructed using a different basis in [M. Clausen, Multivariate polynomials, standard tableaux, and representations of symmetric groups, J. Symbolic Comput. (11), 5-6 (1991) 483-522. Invariant-theoretic algorithms in geometry (Minneapolis, MN, 1987)], and does not employ the Kazhdan-Lusztig preorders. We show that the two resulting matrix representations are related by a unitriangular transition matrix. This provides a C[x_1,1,…,x_n,n]-analog of results due to Garsia and McLarnan, and McDonough and Pallikaros, who related the Kazhdan-Lusztig representations to Young’s natural representations.     

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….