Quasisymmetric Functions (10w5031)

Arriving Sunday, November 14 and departing Friday November 19, 2010


Louis Billera (Cornell University)
Sara Billey (University of Washington)
Richard Stanley (Massachusetts Institute of Technology)


By holding this five-day workshop on the theme of "Quasisymmetric Functions" at the Banff International Research Station, we hope to bring together the various researchers using these functions in different ways. The objective of this workshop is to highlight the important role that quasisymmetric functions play in many different research topics, to foster new developments and enhance the common understanding of the applications.

Quasisymmetric functions are power series of bounded degree in variables $x_1,x_2,dots$ (say) which are shift invariant in the sense that $x_1^{a_1}cdots x_k^{a_k}$ and $x_{i_1}^{a_1}cdots x_{i_k}^{a_k}$ have the same coefficient for any strictly increasing sequence of positive integers $i_1

For over a century, symmetric functions have played a major role in mathematics with applications in algebraic topology, combinatorics, representation theory, and geometry. Quasisymmetric functions are extensions of symmetric functions that are becoming of comparable importance. They were first used by Stanley around 1970 in the theory of $P$-partitions, though he did not consider them per se. In the 1980's Ira Gessel defined quasisymmetric functions, developed many of their basic properties, and applied them to permutation enumeration.

Quasisymmetric functions have developed into a powerful tool in many areas of mathematics today. Their first algebraic interpretations were as Frobenius characteristics of the representations of the 0-Hecke algebra and as the dual to Solomon's descent algebra of the symmetric group. Their applications have since exploded in many directions. We have outlined some of these topics below.

We feel the timing of this workshop comes at a critical point in the development of quasisymmetric functions. There are lots of interesting applications in current research yet there have not been specific conferences devoted this subject to date.

Research Directions

- Partially ordered sets. Quasisymmetric functions appear in the enumeration of chains in finite graded posets cite{Ehr,rs:fs}, in Eulerian posets cite{BMSV, BMSV2,BHV} and in Bruhat intervals cite{BBr}. Here a single homogeneous quasisymmetric function is used to encode the entire flag $f$-vector of a graded poset. Changing invariants in this case to the flag $h$-vector or the ${bf cd}$-index amounts to changing bases in the algebra of quasisymmetric functions. Extending the definitions, one can get a non-homogeneous version of this quasisymmetric function for any Bruhat interval in a Coxeter group, allowing the expression of its Kazhdan-Lusztig polynomial in terms of its coefficients. In all of these cases, the classical nonnegativity theorems (and conjectures) can be viewed in a new light.

- Stanley symmetric functions. Every permutation can be expressed as a product of the adjacent transpositions $s_{i}=t_{i,i+1}$. If $w=s_{a_{1}}s_{a_{2}}cdots s_{a_p}$ and $p$ is minimal over all such expressions for $w$, then $i_{1}i_{2}dotsb i_{p}$ is a textit{reduced word} for $w$. Given a permutation $w$, let $R(w)$ be the set of all reduced words for $w$. Let $X$ be the infinite alphabet ${x_{1},x_{2},ldots}$, and let

newcommand{bm}[1]{{mbox{bf {it #1}}}}
newcommand{bms}[1]{{mbox{bf {it scriptsize{#1}}}}}

label{e:stanley.symmectric.functions} G_{w}(X)= sum_{bms{a}=a_{1}dotsb a_{p} in R(w)} sum_{i_{1}dotsb i_{p} in C(bms{a})} x_{i_{1}}x_{i_{2}}cdots x_{i_{p}}, end{equation}

where $C(bm{a})$ is the set of all integer sequences $1leq i_{1}leq i_{2} leq dotsb leq i_{p}$ such that $i_{j}

Later Edelman and Greene cite{EG} showed each $G_{w}$ expands into a positive sum of Schur functions: $G_{w} = sum a_{lambda } s_{lambda }$ with $a_{lambda } in mathbb{N}$. As a corollary of this result we know $#R(w)= sum a_{lambda } f^{lambda }$ where $f^{lambda}$ is the number of standard tableaux of shape $lambda$, which is easily computed using the Frame-Robinson-Thrall hook length formula.

The definition of the Stanley symmetric functions in eqref{e:stanley.symmectric.functions} inspired formulas for Schubert polynomials of various types cite{BJS,FS,BH,Lam-2008}. Schubert polynomials are used to compute cup products in the cohomology ring of flag manifolds. For more results inspired by eqref{e:stanley.symmectric.functions}, see the subsection on strong Schur functions below.

- Noncommutative symmetric functions. The central result connecting noncommutative symmetric functions with quasisymmetric functions is that the algebra of quasisymmetric functions is dual to the algebra of noncommutative symmetric functions cite[{S}6]{GKL}. This result has led to a vast number of applications and generalizations that connect quasisymmetric functions with other algebraic objects.

- Combinatorics of riffle shuffles. Given a probability distribution $x_i$ on a totally ordered set, there is a natural way to define for each $ngeq 1$ a probability distribution on the symmetric group $mathfrak{S}_n$, called the $QS$-distribution (corresponding to $x_i$) cite{rs:riffle}. Several previously studied probability distributions on $mathfrak{S}_n$ turn out to be special cases of the $QS$-distribution. If $winmathfrak{S}_n$ is a random permutation with respect to the $QS$-distribution, then the probability that $w$ satisfies many standard properties is a quasisymmetric function in the $x_i$'s which often in fact is a symmetric function. Hence the machinery of symmetric and quasisymmetric functions can be used to investigate the behavior of $w$ as a random permutation, such as its descent set and its shape under the RSK algorithm.

- Combinatorial Hopf algebras. These are Hopf algebras equipped with a multiplicative linear functional (character) cite{Ag,ABS}. A principal example is the Hopf algebra of quasisymmetric functions, with character the indicator function of monomial symmetric functions corresponding to trivial compositions into one (or no) parts. A main result is that the quasisymmetric functions are terminal in the category of combinatorial Hopf algebras, giving explanation to the large number of quasisymmetric generating functions one finds in many areas of combinatorics. One example of this is a matroid quasisymmetric function cite{BJR} that gives a valuation on decompositions of the matroid basis polytope.

- Macdonald polynomials. Macdonald polynomials are a generalization of Schur functions that have many remarkable connections to Hilbert schemes of points in the plane, Cherednik algebras cite{Haiman-2006}, affine Hecke algebras cite{H-Gr}, Catalan numbers cite{Haglund}, and representation theory cite{Garsia-Haiman}.

Macdonald originally showed the existence of these polynomials as the basis of symmetric functions over $mathbb{Q}(q,t)$ satisfying certain orthogonality conditions with respect to a given inner product. This definition proved that these "polynomials" are symmetric functions but resulted in a very inefficient means of calculation. Recently, Haiman, Haglund, and Loehr cite{HHL} gave the following beautiful formula for expanding Macdonald polynomials into the textit{fundamental basis} ${L_{sigma} }$ of quasisymmetric functions cite{ECII} with coefficients in $mathbb{N}[q,t]$ determined by generalizations of the inversion statistic and major index statistic for permutations:

tilde{H}_{mu}(X; q,t) = sum_w q^{mathrm{inv}(w)} t^{mathrm{maj}(w)}
end{equation} summed over all bijective fillings $w$ of the Ferrers diagram for

This formula for Macdonald polynomials is now taken as the definition by some researchers because it is more efficient for computations. In particular, Assaf cite{Assaf} has used this definition to give a combinatorial proof that the Macdonald polynomials expand into a sum of Schur functions with coefficients in $mathbb{N}[q,t]$. One important open problem in this field is to determine if Macdonald polynomials also expand positively in this way into a sum of $k$-Schur functions defined by Lapointe, Lascoux, and Morse cite{Lapointe-Lascoux-Morse-2003}. Proving this conjecture would establish a interesting link between Macdonald polynomials, the Hilbert Scheme, and affine Grassmannians as detailed further in the next subsection.

- Strong Schur functions and affine Grassmannians. Let $W$ be a finite irreducible Weyl group associated to a simple connected compact Lie Group $G$, and let $widetilde{W}$ be its associated affine Weyl group. In analogy with the Grassmann manifolds in classical type $A$, the quotient $widetilde{W}/W$ is the indexing set for the Schubert varieties in the affine Grassmannians $mathcal{L} _G$. Much of the geometry and topology for the affine Grassmannians can be studied from the combinatorics of the minimal length coset representatives for $widetilde{W}/W$ and vice versa. A beautiful example of this phenomena can be found in the work of Lam, Lapointe, Morse and Shimozono cite{LLMS}. They have identified a family of symmetric functions they call textit{strong Schur functions} which determine a Schubert basis for the cohomology ring of $mathcal{L} _G$. The strong Schur functions are related to the $k$-Schur functions cite{Lapointe-Lascoux-Morse-2003} by setting $t=1$.

The LLMS formula for strong Schur functions can compactly be written as a positive sum of fundamental basis elements for quasisymmetric functions. The sum in this case is indexed by labeled sequences of reflections. Furthermore, there is a conjectured statistic on labeled sequences of reflections which would allow them to recover the $k$-Schur functions from the data for the strong Schur functions in the fundamental quasisymmetric function basis cite{LLMS}.


{Ag} M. Aguiar, Infinitesimal Hopf algebras and the ${bf cd}$-index of
polytopes, Discrete Comput. Geometry {bf 27} (2002), 3-28.

{ABS} M. Aguiar, N. Bergeron, and F. Sottile,
Combinatorial Hopf algebras and generalized Dehn-Sommerville relations,
Compositio Math. {bf 142} (2006), 1--30.

{Assaf} S. Assaf, The Schur expansion of Macdonald polynomials. Preprint. 2007.

{BMSV} N. Bergeron, S. Mykytiuk, F. Sottile
and S. van Willigenburg,
Non-commutative Pieri operators on posets, {it J. Comb. Theory Ser. A}
{bf 91} (2000), 84-110.

{BMSV2} N. Bergeron, S. Mykytiuk, F. Sottile and S. van Willigenburg,
Shifted quasi-symmetric functions and the Hopf algebra of peak functions,
Discrete Math. {bf 256} (2002), 57-66.

{BBr} L.J. Billera and F. Brenti,
Quasisymmetric functions and Kazhdan-Lusztig polynomials,
arXiv:0710.3965, October, 2007.

{BHV} L.J. Billera, S. K. Hsiao, and S. van Willigenburg,
Peak quasisymmetric functions and Eulerian enumeration, Adv.
Math. {bf 176} (2003), no. 2, 248--276.

{BJR} L.J. Billera, N. Jia and V. Reiner, A quasisymmetric
function for matroids, {it Europ. J. Combinatorics} (to appear),

{BH} { S.~Billey and M.~Haiman}, { {Schubert polynomials for the classical
groups}}, J. Amer. Math. Soc., 8 (1995), pp.~443--482.

{BJS} { S.~Billey, W.~Jockusch, and R.~Stanley}, { {Some Combinatorial
Properties of Schubert Polynomials}}, J. Alg. Comb.}, 2 (1993), pp.~345--374.

{EG} { P.~Edelman and C.~Greene}, { {Balanced Tableaux}}, {it Adv. Math.}, 63
(1987), pp.~42--99.

{Ehr} R. Ehrenborg, On posets and Hopf algebras, Adv. in Math. {bf 119} (1996), 1--25.

{FS}{ S.~Fomin and R.~P. Stanley}, { {Schubert Polynomials and the NilCoxeter
Algebra}}, Adv. Math., 103 (1994), pp.~196--207.

{GKL} I. M. Gelfand, D. Krob, A. Lascoux, B. Leclerc,
V. Retakh and J.-Y. Thibon, Noncommutative symmetric functions,
Adv. in Math. {bf 112} (1995), 218--348.
{Garsia-Haiman}{ A.~M. Garsia and M.~Haiman}, { A graded representation model for {M}acdonald's polynomials}, Proc. Nat. Acad. Sci. U.S.A., 90 (1993),

{Ges} I. M. Gessel, Multipartite $P$-partitions and inner products
of Schur functions, in Combinatorics and Algebra, C. Greene, ed.,
Contemporary Mathematics, vol. 34, Amer. Math. Soc., Providence, 1984.
{Haglund}{ J.~Haglund}, "The {$q$},{$t$}-{C}atalan numbers and the space of
diagonal harmonics", vol.~41 of University Lecture Series, American
Mathematical Society, Providence, RI, 2008.

With an appendix on the combinatorics of Macdonald polynomials.
{HHL} { J.~Haglund, M.~Haiman, and N.~Loehr}, { A combinatorial formula for
nonsymmetric {M}acdonald polynomials}, Amer. J. Math., 130 (2008),
{Haiman-2006} { M.~Haiman}, { Cherednik algebras, {M}acdonald polynomials and
combinatorics}, in International {C}ongress of {M}athematicians. {V}ol.
{III}, Eur. Math. Soc., Zurich, 2006, pp.~843--872.

{H-Gr} { M.~Haiman and I.~Grojnowski}, "Affine Hecke
algebras and positivity of LLT and Macdonald polynomials", preprint
available at http://math.berkeley.edu/$sim$mhaiman/, (2007).

{LLMS} { T.~Lam, L.~Lapointe, J.~Morse, and M.~Shimozono},
{em Affine insertion and pieri rules for the affine Grassmannian},
preprint, 2006.

{ T.~Lam}, { Schubert polynomials for the affine {G}rassmannian}, {it J.
Amer. Math. Soc.}, 21 (2008), pp.~259--281 (electronic).

{ L.~Lapointe, A.~Lascoux, and J.~Morse}, { Tableau atoms and a new
{M}acdonald positivity conjecture}, Duke Math. J., 116 (2003), pp.~103--146.

{Luoto} K. Luoto, A matroid-friendly basis for quasisymmetric
functions, Journal of Combinatorial Theory, Series A, to appear.

{MR} C. Malvenuto and C. Reutenauer, Duality between
quasi-symmetric functions and the Solomon descent algebra, Journal of Algebra {bf 177} (1995), 967--982.
{ R.~Stanley}, { {On the number of reduced decompositions of elements of
Coxeter groups}}, Europ. J. Combinatorics, 5 (1984), pp.~359--372.

{rs:fs} { R.~Stanley}, Flag-symmetric and locally rank-symmetric partially ordered sets, Electronic J. Combinatorics textbf{3}, R6 (1996), 22
pp.; reprinted in emph{The Foata Festschrift} (J. Desarmenien,
A. Kerber, and V. Strehl, eds.), Imprimerie Louis-Jean, Gap, 1996,
pp. 165--186.

{ECII} R. Stanley, Enumerative Combinatorics, Vol. 2,
Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge
University Press, Cambridge, UK, 1999.

{rs:riffle} R. Stanley, A generalized riffle shuffle and
quasisymmetric functions, Ann. Combinatorics textbf{5}
(2001), 479--491.

{Stem} J. Stembridge, Enriched $P$-partitions,
Trans. Amer. Math. Soc. {bf 349} (1997), 763--788.