Search

Cylindric skew Schur functions, a generalization of skew Schur functions, are closely related to the well-known problem of finding a combinatorial formula for the 3-point Gromov-Witten invariants of Grassmannians. In this paper, we prove cylindric Schur positivity of cylindric skew Schur functions, as conjectured by McNamara. We also show that all the coefficients appearing in the expansion are the same as the 3-point Gromov-Witten invariants. We start by discussing the properties of affine Stanley symmetric functions for general affine permutations and 321-avoiding affine permutations, and we explain how these functions are related to cylindric skew Schur functions. In addition, we provide an effective algorithm to compute the expansion of cylindric skew Schur functions in terms of cylindric Schur functions, as well as the expansion of affine Stanley symmetric functions in terms of affine Schur functions.

The classical Littlewood-Richardson rule is a rule for computing coefficients in many areas, and comes in many guises. In this paper we prove two Littlewood-Richardson rules for symmetric skew quasisymmetric Schur functions that are analogous to the famed version of the classical Littlewood-Richardson rule involving Yamanouchi words. Furthermore, both our rules contain this classical Littlewood-Richardson rule as a special case. We then apply our rules to combinatorially classify symmetric skew quasisymmetric Schur functions. This answers affirmatively a conjecture of Bessenrodt, Luoto and van Willigenburg.

Generalizing the notion of a vexillary permutation, we introduce a filtration of S_infinity by the number of Schur function terms in the Stanley symmetric function, with the kth filtration level called the k-vexillary permutations. We show that for each k, the k-vexillary permutations are characterized by avoiding a finite set of patterns. A key step is the construction of a Specht series, in the sense of James and Peel, for the Specht module associated to the diagram of a permutation. As a corollary, we prove a conjecture of Liu on diagram varieties for certain classes of permutation diagrams. We apply similar techniques to characterize multiplicity-free Stanley symmetric functions, as well as permutations whose diagram is equivalent to a forest in the sense of Liu., 29 pages; corrected typos in section 3, fixed arguments and improved results in section 6

We prove that the well-known condition of being a balanced labeling can be characterized in terms of the sliding algorithm on tower diagrams. The characterization involves a generalization of authors@? Rothification algorithm. Using the characterization, we obtain descriptions of Schubert polynomials and Stanley symmetric functions.

We define a type B derangement polynomial by q-counting derangements by the number of excedances in the hyperoctahedral group Bn. Properties of the derangement polynomial, including the recurrence relation, generating function, real-rootedness, reciprocity and a unimodal decomposition arising from a symmetric function identity, are studied. The results presented generalize and unify earlier ones due to Brenti, Stanley, Stembridge and Zhang.

In Stanley [R.P. Stanley, Irreducible symmetric group characters of rectangular shape, Sém. Lothar. Combin. 50 (2003) B50d, 11 p.] the author introduces polynomials which help evaluate symmetric group characters and conjectures that the coefficients of the polynomials are positive. In [R.P. Stanley, A conjectured combinatorial interpretation of the normalised irreducible character values of the symmetric group, math.CO/0606467, 2006] the same author gives a conjectured combinatorial interpretation for the coefficients of the polynomials. Here, we prove the conjecture for the terms of highest degree.

The paper contains proofs of the following results. For all sufficiently large odd integers n, there exists a set of 2n−1 permutations that pairwise generate the symmetric group Sn. There is no set of 2n−1+1 permutations having this property. For all sufficiently large integers n with n≡2mod4, there exists a set of 2n−2 even permutations that pairwise generate the alternating group An. There is no set of 2n−2+1 permutations having this property.

In (Adv. Math. 174(2) (2003) 236), a bijection between collections of reduced factorizations of elements of the symmetric group was described. Initially, this bijection was used to show the Schur positivity of the Stanley symmetric functions. Further investigations have revealed that our bijection has strong connections to other more familiar combinatorial algorithms. In this paper we will show how the Robinson–Schensted–Knuth correspondence can be decomposed into a sequence of applications of this bijection.

We study here the ring QSn of Quasi-symmetric functions in the variables x1,x2,…,xn. Bergeron and Reutenauer (personal communication) formulated a number of conjectures about this ring; in particular, they conjectured that it is free over the ring Λn of symmetric functions in x1,x2,…,xn. We present here an algorithm that recursively constructs a Λn-module basis for QSn thereby proving one of the Bergeron–Reutenauer conjectures. This result also implies that the quotient of QSn by the ideal generated by the elementary symmetric functions has dimension n!. Surprisingly, to show the validity of our algorithm we were led to a truly remarkable connection between QSn and the harmonics of Sn.

We introduce and study a class of symmetric functions that depend on a parameter q, which includes symmetric functions that have already appeared in the literature in connection with Jack symmetric functions, parking functions, and lattices of noncrossing partitions. Our results generalize previous results by Haiman, Stanley, and the author.

A basis of symmetric functions, which we denote byqλ(X; q, t), was introduced in the work of Ram and King and Wybourne in order to describe the irreducible characters of the Hecke algebras of type A. In this work we give combinatorial descriptions of the expansions of the functionsqλ(X; q, t) in terms of the classical bases of symmetric functions and apply these results in determining the determinant of the character table of the Iwahori–Hecke algebras and in giving a generating function for certain permutation statistics.

Waring's formula for expressing power sum symmetric functions in terms of elementary symmetric functions is generalized to monomial symmetric functions with equal exponents by applying the orthogonality property of Ramanujan sums together with the Möbius function over the set partition lattice.

We define noncommutative analogues of the characters of the symmetric group which are induced by transitive cyclic subgroups (cyclic characters). We investigate their properties by means of the formalism of noncommutative symmetric functions. The main result is a multiplication formula whose commutative projection gives a combinatorial formula for the resolution of the Kronecker product of two cyclic representations of the symmetric group. This formula can be interpreted as a multiplicative property of the major index of permutations.

A new class of symmetric functions called factorial Schur symmetric functions has recently been discovered in connection with a branch of mathematical physics. We align this theory more closely with the standard symmetric function theory, giving the factorial Schur function a tableau definition, introducing a shift operator and a new generating function with which we extend to factorial symmetric functions proofs of various determinantal identities for classical symmetric functions, and defining a new factorial symmetric function—the factorial elementary symmetric function.

We establish a combinatorial interpretation for various operations on symmetric functions, such as plethysm, scalar product, and derivation. Thus we obtain proofs of formulas involving symmetric functions in term of combinatorial constructions on permutations.

In a recent paper, Brenti shows that enumerating a conjugacy class of Sn with respect to excedances produces polynomials which are unimodal and symmetric. He then shows that these polynomials arise naturally from the theory of symmetric functions. We give combinatorial proofs of Brenti's results; our combinatorial methods lead to numerous extensions, as well as to the definition of new combinatorial objects—border rim hook tabloids.

Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. We extend Gessel's work by providing algorithms that compute differential equations these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel's class. Examples of applications to k-regular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself., 51 pages, full paper version of FPSAC 02 extended abstract; v2: corrections from original submission, improved clarity; now formatted for journal + bibliography

We extend Stanley's work on alternating permutations with extremal number of fixed points in two directions: first, alternating permutations are replaced by permutations with a prescribed descent set; second, instead of simply counting permutations we study their generating polynomials by number of excedances. Several techniques are used: Desarmenien's desarrangement combinatorics, Gessel's hook-factorization and the analytical properties of two new permutation statistics "DEZ" and "lec". Explicit formulas for the maximal case are derived by using symmetric function tools., minor change about corollary 3

We study asymptotics of characters of the symmetric groups on a fixed conjugacy class. It was proved by Kerov that such a character can be expressed as a polynomial in free cumulants of the Young diagram (certain functionals describing the shape of the Young diagram). We show that for each genus there exists a universal symmetric polynomial which gives the coefficients of the part of Kerov character polynomials with the prescribed homogeneous degree. The existence of such symmetric polynomials was conjectured by Lassalle.

Let $T$ be an unrooted tree. The \emph{chromatic symmetric function} $X_T$, introduced by Stanley, is a sum of monomial symmetric functions corresponding to proper colorings of $T$. The \emph{subtree polynomial} $S_T$, first considered under a different name by Chaudhary and Gordon, is the bivariate generating function for subtrees of $T$ by their numbers of edges and leaves. We prove that $S_T = $, where $$ is the Hall inner product on symmetric functions and $\Phi$ is a certain symmetric function that does not depend on $T$. Thus the chromatic symmetric function is a stronger isomorphism invariant than the subtree polynomial. As a corollary, the path and degree sequences of a tree can be obtained from its chromatic symmetric function. As another application, we exhibit two infinite families of trees (\emph{spiders} and some \emph{caterpillars}), and one family of unicyclic graphs (\emph{squids}) whose members are determined completely by their chromatic symmetric functions., Comment: 16 pages, 3 figures. Added references [2], [13], and [15]

A MacMahon symmetric function is a formal power series in a finite number of alphabets that is invariant under the diagonal action of the symmetric group. In this article, we show that the MacMahon symmetric functions are the generating functions for the orbits of sets of functions indexed by partitions under the diagonal action of a Young subgroup of a symmetric group. We define a MacMahon chromatic symmetric function that generalizes Stanley's chromatic symmetric function. Then, we study some of the properties of this new function through its connection with the noncommutative chromatic symmetric function of Gebhard and Sagan.

The Bernstein operators allow to build recursively the Schur functions. We present a recursion formula for k-Schur functions at t=1 based on combinatorial operators that generalize the Bernstein operators. The recursion leads immediately to a combinatorial interpretation for the expansion coefficients of k-Schur functions at t=1 in terms of homogeneous symmetric functions., 18 pages, 3 figures

Snakes are analogues of alternating permutations defined for any Coxeter group. We study these objects from the point of view of combinatorial Hopf algebras, such as noncommutative symmetric functions and their generalizations. The main purpose is to show that several properties of the generating functions of snakes, such as differential equations or closed form as trigonometric functions, can be lifted at the level of noncommutative symmetric functions or free quasi-symmetric functions. The results take the form of algebraic identities for type B noncommutative symmetric functions, noncommutative supersymmetric functions and colored free quasi-symmetric functions.