Descents, inversions, and major indices in permutation groups

A multivariate generating function involving the descent, major index, and inversion statistic first given by Ira Gessel is generalized to other permutation groups. We provide generating functions for variants of these three statistics for the Weyl groups of type B and D, wreath product groups, and multiples of permutations. All of our ideas are combinatorial in nature and exploit fundamental relationships between the elementary and homogeneous symmetric functions.     

Random sorting networks

A sorting network is a shortest path from 12?n to n?21 in the Cayley graph of Sn generated by nearest-neighbour swaps. We prove that for a uniform random sorting network, as n→∞ the space-time process of swaps converges to the product of semicircle law and Lebesgue measure. We conjecture that the trajectories of individual particles converge to random sine curves, while the permutation matrix at half-time converges to the projected surface measure of the 2-sphere. We prove that, in the limit, the trajectories are Hölder-1/2 continuous, while the support of the permutation matrix lies within a certain octagon. A key tool is a connection with random Young tableaux.     

Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups

Eulerian quasisymmetric functions were introduced by Shareshian and Wachs in order to obtain a q-analog of Euler?s exponential generating function formula for the Eulerian numbers (Shareshian and Wachs, 2010 [17]). They are defined via the symmetric group, and applying the stable and nonstable principal specializations yields formulas for joint distributions of permutation statistics. We consider the wreath product of the cyclic group with the symmetric group, also known as the group of colored permutations. We use this group to introduce colored Eulerian quasisymmetric functions, which are a generalization of Eulerian quasisymmetric functions. We derive a formula for the generating function of these colored Eulerian quasisymmetric functions, which reduces to a formula of Shareshian and Wachs for the Eulerian quasisymmetric functions. We show that applying the stable and nonstable principal specializations yields formulas for joint distributions of colored permutation statistics, which generalize the Shareshian–Wachs q-analog of Euler?s formula, formulas of Foata and Han, and a formula of Chow and Gessel.     

A Generating Tree Approach to <Emphasis Type="Italic">k</Emphasis>-Nonnesting Partitions and Permutations

We describe a generating tree approach to the enumeration and exhaustive generation of k-nonnesting set partitions and permutations. Unlike previous work in the literature which uses the connections of these objects to Young tableaux and restricted lattice walks, our approach deals directly with partition and permutation diagrams. We provide explicit functional equations for the generating functions, with k as a parameter. Key to the solution is a superset of diagrams that permit semi-arcs. Many of the resulting counting sequences also count other well-known objects, such as Baxter permutations, and Young tableaux of bounded height.     

Adjacency of Young tableaux and the Springer fibers

We connect different results about irreducible components of the Springer fibers of type A. Firstly, we show a relation between the Spaltenstein partition of the fibers and a total order on the set of standard Young tableaux. Next, using a result of Steinberg, we connect a work of the first author to the Robinson–Schensted map. We also perform the Spaltenstein study of the relative position of the Springer fibers and -fibrations of the flag manifold. This leads us to consider the adjacency relation on the set of standard Young tableaux and to define oriented and labeled graphs with the standard Young tableaux as vertices. Using this adjacency relation, we describe some smooth irreducible components of the Springer fibers. Finally, we show that these graphs can be identified with some full subgraphs of the Bruhat graph.     

A new <Emphasis Type="Italic">q</Emphasis>-Selberg integral,Schur functions,and Young books

Recently, Kim and Oh expressed the Selberg integral in terms of the number of Young books which are a generalization of standard Young tableaux of shifted staircase shape. In this paper the generating function for Young books according to major index statistic is considered. It is shown that this generating function can be written as a Jackson integral which gives a new q-Selberg integral. It is also shown that the new q-Selberg integral has an expression in terms of Schur functions.     

On the sign-imbalance of partition shapes

Let the sign of a standard Young tableau be the sign of the permutation you get by reading it row by row from left to right, like a book. A conjecture by Richard Stanley says that the sum of the signs of all SYTs with n squares is 2^⌊n/2⌋. We present a stronger theorem with a purely combinatorial proof using the Robinson-Schensted correspondence and a new concept called chess tableaux.We also prove a sharpening of another conjecture by Stanley concerning weighted sums of squares of sign-imbalances. The proof is built on a remarkably simple relation between the sign of a permutation and the signs of its RS-corresponding tableaux.     

Eulerian quasisymmetric functions

We introduce a family of quasisymmetric functions called Eulerian quasisymmetric functions, which specialize to enumerators for the joint distribution of the permutation statistics, major index and excedance number on permutations of fixed cycle type. This family is analogous to a family of quasisymmetric functions that Gessel and Reutenauer used to study the joint distribution of major index and descent number on permutations of fixed cycle type. Our central result is a formula for the generating function for the Eulerian quasisymmetric functions, which specializes to a new and surprising q-analog of a classical formula of Euler for the exponential generating function of the Eulerian polynomials. This q-analog computes the joint distribution of excedance number and major index, the only of the four important Euler-Mahonian distributions that had not yet been computed. Our study of the Eulerian quasisymmetric functions also yields results that include the descent statistic and refine results of Gessel and Reutenauer. We also obtain q-analogs, (q,p)-analogs and quasisymmetric function analogs of classical results on the symmetry and unimodality of the Eulerian polynomials. Our Eulerian quasisymmetric functions refine symmetric functions that have occurred in various representation theoretic and enumerative contexts including MacMahon's study of multiset derangements, work of Procesi and Stanley on toric varieties of Coxeter complexes, Stanley's work on chromatic symmetric functions, and the work of the authors on the homology of a certain poset introduced by Björner and Welker.     

A k-tableau characterization of k-Schur functions

We study k-Schur functions characterized by k-tableaux, proving combinatorial properties such as a k-Pieri rule and a k-conjugation. This new approach relies on developing the theory of k-tableaux, and includes the introduction of a weight-permuting involution on these tableaux that generalizes the Bender-Knuth involution. This work lays the groundwork needed to prove that the set of k-Schur Littlewood-Richardson coefficients contains the 3-point Gromov-Witten invariants; structure constants for the quantum cohomology ring.     

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.     

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.     

Schur function identities, their t-analogs, and k-Schur irreducibility

We obtain general identities for the product of two Schur functions in the case where one of the functions is indexed by a rectangular partition, and give their t-analogs using vertex operators. We study subspaces forming a filtration for the symmetric function space that lends itself to generalizing the theory of Schur functions and also provides a convenient environment for studying the Macdonald polynomials. We use our identities to prove that the vertex operators leave such subspaces invariant. We finish by showing that these operators act trivially on the k-Schur functions, thus leading to a concept of irreducibility for these functions.     

Multiplicity Free Expansions of Schur <Emphasis Type="Italic">P</Emphasis>-Functions

After deriving inequalities on coefficients arising in the expansion of a Schur P-function in terms of Schur functions we give criteria for when such expansions are multiplicity free. From here we study the multiplicity of an irreducible spin character of the twisted symmetric group in the product of a basic spin character with an irreducible character of the symmetric group, and determine when it is multiplicity free. Received February 28, 2005     

Symmetric factorizations of the complete uniform hypergraph

Crystal graphs, in the sense of Kashiwara, carry a natural monoid structure given by identifying words labelling vertices that appear in the same position of isomorphic components of the crystal. In the particular case of the crystal graph for the q-analogue of the special linear Lie algebra \(\mathfrak {sl}_{n}\), this monoid is the celebrated plactic monoid, whose elements can be identified with Young tableaux. The crystal graph and the so-called Kashiwara operators interact beautifully with the combinatorics of Young tableaux and with the Robinson–Schensted–Knuth correspondence and so provide powerful combinatorial tools to work with them. This paper constructs an analogous ‘quasi-crystal’ structure for the hypoplactic monoid, whose elements can be identified with quasi-ribbon tableaux and whose connection with the theory of quasi-symmetric functions echoes the connection of the plactic monoid with the theory of symmetric functions. This quasi-crystal structure and the associated quasi-Kashiwara operators are shown to interact just as neatly with the combinatorics of quasi-ribbon tableaux and with the hypoplactic version of the Robinson–Schensted–Knuth correspondence. A study is then made of the interaction of the crystal graph for the plactic monoid and the quasi-crystal graph for the hypoplactic monoid. Finally, the quasi-crystal structure is applied to prove some new results about the hypoplactic monoid.     

A symmetric generalization of Sturm–Liouville problems in q-difference spaces

Classical Sturm–Liouville problems of q-difference variables are extended for symmetric discrete functions such that the corresponding solutions preserve the orthogonality property. Some illustrative examples are given in this sense.     

Riffle shuffles,cycles, and descents

We derive closed form expressions and limiting formulae for a variety of functions of a permutation resulting from repeated riffle shuffles. The results allow new formulae and approximations for the number of permutations inS _n with given cycle type and number of descents. The theorems are derived from a bijection discovered by Gessel. A self-contained proof of Gessel's result is given.     

On the singularity of multivariate skew-symmetric models

In recent years, the skew-normal models introduced by Azzalini (1985) [1]-and their multivariate generalizations from Azzalini and Dalla Valle (1996) [4]-have enjoyed an amazing success, although an important literature has reported that they exhibit, in the vicinity of symmetry, singular Fisher information matrices and stationary points in the profile log-likelihood function for skewness, with the usual unpleasant consequences for inference. It has been shown (DiCiccio and Monti (2004) [23], DiCiccio and Monti (2009) [24] and Gómez et al. (2007) [25]) that these singularities, in some specific parametric extensions of skew-normal models (such as the classes of skew-t or skew-exponential power distributions), appear at skew-normal distributions only. Yet, an important question remains open: in broader semiparametric models of skewed distributions (such as the general skew-symmetric and skew-elliptical ones), which symmetric kernels lead to such singularities? The present paper provides an answer to this question. In very general (possibly multivariate) skew-symmetric models, we characterize, for each possible value of the rank of Fisher information matrices, the class of symmetric kernels achieving the corresponding rank. Our results show that, for strictly multivariate skew-symmetric models, not only Gaussian kernels yield singular Fisher information matrices. In contrast, we prove that systematic stationary points in the profile log-likelihood functions are obtained for (multi)normal kernels only. Finally, we also discuss the implications of such singularities on inference.     

Primitive elements of the Hopf algebras of tableaux

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, Schützenberger’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 Möbius 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.     

The symmetric group given by a Gröbner basis

We present a Gröbner basis associated with the symmetric group of degree n, which is determined by a strong generating set of the symmetric group and is defined by means of a term ordering with the elimination property.