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.     

Pattern avoidance in binary trees

This paper considers the enumeration of trees avoiding a contiguous pattern. We provide an algorithm for computing the generating function that counts n-leaf binary trees avoiding a given binary tree pattern t. Equipped with this counting mechanism, we study the analogue of Wilf equivalence in which two tree patterns are equivalent if the respective n-leaf trees that avoid them are equinumerous. We investigate the equivalence classes combinatorially. Toward establishing bijective proofs of tree pattern equivalence, we develop a general method of restructuring trees that conjecturally succeeds to produce an explicit bijection for each pair of equivalent tree patterns.     

Pattern avoidance in “flattened” partitions

To flatten a set partition (with apologies to Mathematica^®) means to form a permutation by erasing the dividers between its blocks. Of course, the result depends on how the blocks are listed. For the usual listing—increasing entries in each block and blocks arranged in increasing order of their first entries—we count the partitions of [n] whose flattening avoids a single 3-letter pattern. Five counting sequences arise: a null sequence, the powers of 2, the Fibonacci numbers, the Catalan numbers, and the binomial transform of the Catalan numbers.     

Pattern avoidance and Boolean elements in the Bruhat order on involutions

We show that the principal order ideal of an element w in the Bruhat order on involutions in a symmetric group is a Boolean lattice if and only if w avoids the patterns 4321, 45312 and 456123. Similar criteria for signed permutations are also stated. Involutions with this property are enumerated with respect to natural statistics. In this context, a bijective correspondence with certain Motzkin paths is demonstrated. This article is largely based on results from the second author’s M.Sc. thesis [15].     

Hydrodynamic limit of the Robinson–Schensted–Knuth algorithm

We investigate the evolution in time of the position of a fixed number in the insertion tableau when the Robinson–Schensted–Knuth algorithm is applied to a sequence of random numbers. When the length of the sequence tends to infinity, a typical trajectory after scaling converges uniformly in probability to some deterministic curve.     

On (0, 1)-matrices with prescribed row and column sum vectors

Given partitions R and S with the same weight, the Robinson-Schensted-Knuth correspondence establishes a bijection between the class A(R,S) of (0, 1)-matrices with row sum R and column sum S and pairs of Young tableaux of conjugate shapes λ and λ^∗, with S?λ?R^∗. An algorithm for constructing a matrix in A(R,S) whose insertion tableau has a prescribed shape λ, with S?λ?R^∗, is provided. We generalize some recent constructions due to R. Brualdi for the extremal cases λ=S and λ=R^∗.     

On a Conjectured Formula for Quiver Varieties

In A.S. Buch and W. Fulton [Invent. Math. 135 (1999), 665–687] a formula for the cohomology class of a quiver variety is proved. This formula writes the cohomology class of a quiver variety as a linear combination of products of Schur polynomials. In the same paper it is conjectured that all of the coefficients in this linear combination are non-negative, and given by a generalized Littlewood-Richardson rule, which states that the coefficients count certain sequences of tableaux called factor sequences. In this paper I prove some special cases of this conjecture. I also prove that the general conjecture follows from a stronger but simpler statement, for which substantial computer evidence has been obtained. Finally I will prove a useful criterion for recognizing factor sequences.     

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.

     

Plane overpartitions and cylindric partitions

Generating functions for plane overpartitions are obtained using various methods such as nonintersecting paths, RSK type algorithms and symmetric functions. We extend some of the generating functions to cylindric partitions. Also, we show that plane overpartitions correspond to certain domino tilings and we give some basic properties of this correspondence.     

Pattern avoidance and the Bruhat order

The structure of order ideals in the Bruhat order for the symmetric group is elucidated via permutation patterns. The permutations with boolean principal order ideals are characterized. These form an order ideal which is a simplicial poset, and its rank generating function is computed. Moreover, the permutations whose principal order ideals have a form related to boolean posets are also completely described. It is determined when the set of permutations avoiding a particular set of patterns is an order ideal, and the rank generating functions of these ideals are computed. Finally, the Bruhat order in types B and D is studied, and the elements with boolean principal order ideals are characterized and enumerated by length.     

Construction of Graded Covariant GL(m/n) Modules Using Tableaux

Irreducible covariant tensor modules for the Lie supergroups GL(m/n) and the Lie superalgebras gl(m/n) and sl(m/n) are obtained through the use of Young tableaux techniques. The starting point is the graded permutation action, first introduced by Dondi and Jarvis, on V ^l . The isomorphism between this group of actions and the symmetric group S _l enables the graded generalization of the Young symmetrizers, and hence of the column relations and Garnir relations, to be made. Consequently, corresponding to each partition of l an irreducible GL(m/n) module may be obtained as a submodule of V ^l . A basis for the module labeled by the partition is provided by GL(m/n)–standard tableaux of shape defined by Berele and Regev. The reduction of an arbitrary tableau to standard form is accomplished through the use of graded column relations and graded Garnir relations. The standardization procedure is algorithmic and allows matrix representations of the Lie superalgebras gl(m/n) and sl(m/n) to be constructed explicitly over the field of rational numbers. All the various steps of the standardization algorithm are exemplified, as well as the explicit construction of matrices representing particular elements of gl(m/n) and sl(m/n).     

Growth for the Central Polynomials

We study the growth of the central polynomials for the infinite dimensional Grassmann algebra G, and for the algebra M_k(F) of the k × k matrices, both over a field F of characteristic zero.