Quasisymmetric function

In algebra and in particular in algebraic combinatorics, a quasisymmetric function is any element in the ring of quasisymmetric functions which is in turn a subring of the formal power series ring with a countable number of variables. This ring generalizes the ring of symmetric functions. This ring can be realized as a specific limit of the rings of quasisymmetric polynomials in n variables, as n goes to infinity. This ring serves as universal structure in which relations between quasisymmetric polynomials can be expressed in a way independent of the number n of variables (but its elements are neither polynomials nor functions).

Definitions

The ring of quasisymmetric functions, denoted QSym, can be defined over any commutative ring R such as the integers. Quasisymmetric functions are power series of bounded degree in variables $x_{1},x_{2},x_{3},\dots$ with coefficients in R, which are shift invariant in the sense that the coefficient of the monomial $x_{1}^{\alpha _{1}}x_{2}^{\alpha _{2}}\cdots x_{k}^{\alpha _{k}}$ is equal to the coefficient of the monomial $x_{i_{1}}^{\alpha _{1}}x_{i_{2}}^{\alpha _{2}}\cdots x_{i_{k}}^{\alpha _{k}}$ for any strictly increasing sequence of positive integers $i_{1}<i_{2}<\cdots <i_{k}$ indexing the variables and any positive integer sequence $(\alpha _{1},\alpha _{2},\ldots ,\alpha _{k})$ of exponents.^[1] Much of the study of quasisymmetric functions is based on that of symmetric functions.

A quasisymmetric function in finitely many variables is a quasisymmetric polynomial. Both symmetric and quasisymmetric polynomials may be characterized in terms of actions of the symmetric group $S_{n}$ on a polynomial ring in $n$ variables $x_{1},\dots ,x_{n}$ . One such action of $S_{n}$ permutes variables, changing a polynomial $p(x_{1},\dots ,x_{n})$ by iteratively swapping pairs $(x_{i},x_{i+1})$ of variables having consecutive indices. Those polynomials unchanged by all such swaps form the subring of symmetric polynomials. A second action of $S_{n}$ conditionally permutes variables, changing a polynomial $p(x_{1},\ldots ,x_{n})$ by swapping pairs $(x_{i},x_{i+1})$ of variables except in monomials containing both variables.^[2]^[3] Those polynomials unchanged by all such conditional swaps form the subring of quasisymmetric polynomials. One quasisymmetric polynomial in four variables $x_{1},x_{2},x_{3},x_{4}$ is the polynomial

x_{1}^{2}x_{2}x_{3}+x_{1}^{2}x_{2}x_{4}+x_{1}^{2}x_{3}x_{4}+x_{2}^{2}x_{3}x_{4}.\,

The simplest symmetric polynomial containing these monomials is

{\begin{aligned}x_{1}^{2}x_{2}x_{3}+x_{1}^{2}x_{2}x_{4}+x_{1}^{2}x_{3}x_{4}+x_{2}^{2}x_{3}x_{4}+x_{1}x_{2}^{2}x_{3}+x_{1}x_{2}^{2}x_{4}+x_{1}x_{3}^{2}x_{4}+x_{2}x_{3}^{2}x_{4}\\{}+x_{1}x_{2}x_{3}^{2}+x_{1}x_{2}x_{4}^{2}+x_{1}x_{3}x_{4}^{2}+x_{2}x_{3}x_{4}^{2}.\,\end{aligned}}

Important bases

QSym is a graded R-algebra, decomposing as

\operatorname {QSym} =\bigoplus _{n\geq 0}\operatorname {QSym} _{n},\,

where $\operatorname {QSym} _{n}$ is the $R$ -span of all quasisymmetric functions that are homogeneous of degree $n$ . Two natural bases for $\operatorname {QSym} _{n}$ are the monomial basis $\{M_{\alpha }\}$ and the fundamental basis $\{F_{\alpha }\}$ indexed by compositions $\alpha =(\alpha _{1},\alpha _{2},\ldots ,\alpha _{k})$ of $n$ , denoted $\alpha \vDash n$ . The monomial basis consists of $M_{0}=1$ and all formal power series

M_{\alpha }=\sum _{i_{1}<i_{2}<\cdots <i_{k}}x_{i_{1}}^{\alpha _{1}}x_{i_{2}}^{\alpha _{2}}\cdots x_{i_{k}}^{\alpha _{k}}.\,

The fundamental basis consists $F_{0}=1$ and all formal power series

F_{\alpha }=\sum _{\alpha \succeq \beta }M_{\beta },\,

where $\alpha \succeq \beta$ means we can obtain $\alpha$ by adding together adjacent parts of $\beta$ , for example, (3,2,4,2) $\succeq$ (3,1,1,1,2,1,2). Thus, when the ring $R$ is the ring of rational numbers, one has

\operatorname {QSym} _{n}=\operatorname {span} _{\mathbb {Q} }\{M_{\alpha }\mid \alpha \vDash n\}=\operatorname {span} _{\mathbb {Q} }\{F_{\alpha }\mid \alpha \vDash n\}.\,

Then one can define the algebra of symmetric functions $\Lambda =\Lambda _{0}\oplus \Lambda _{1}\oplus \cdots$ as the subalgebra of QSym spanned by the monomial symmetric functions $m_{0}=1$ and all formal power series $m_{\lambda }=\sum M_{\alpha },$ where the sum is over all compositions $\alpha$ which rearrange to the integer partition $\lambda$ . Moreover, we have $\Lambda _{n}=\Lambda \cap \operatorname {QSym} _{n}$ . For example, $F_{(1,2)}=M_{(1,2)}+M_{(1,1,1)}$ and $m_{(2,1)}=M_{(2,1)}+M_{(1,2)}.$

Other important bases for quasisymmetric functions include the basis of quasisymmetric Schur functions,^[4] the "type I" and "type II" quasisymmetric power sums,^[5] and bases related to enumeration in matroids.^[6]^[7]

Applications

Quasisymmetric functions have been applied in enumerative combinatorics, symmetric function theory, representation theory, and number theory. Applications of quasisymmetric functions include enumeration of P-partitions,^[8]^[9] permutations,^[10]^[11]^[12]^[13] tableaux,^[14] chains of posets,^[14]^[15] reduced decompositions in finite Coxeter groups (via Stanley symmetric functions),^[14] and parking functions.^[16] In symmetric function theory and representation theory, applications include the study of Schubert polynomials,^[17]^[18] Macdonald polynomials,^[19] Hecke algebras,^[20] and Kazhdan–Lusztig polynomials.^[21] Often quasisymmetric functions provide a powerful bridge between combinatorial structures and symmetric functions.

Related algebras

As a graded Hopf algebra, the dual of the ring of quasisymmetric functions is the ring of noncommutative symmetric functions. Every symmetric function is also a quasisymmetric function, and hence the ring of symmetric functions is a subalgebra of the ring of quasisymmetric functions.

The ring of quasisymmetric functions is the terminal object in category of graded Hopf algebras with a single character.^[22] Hence any such Hopf algebra has a morphism to the ring of quasisymmetric functions.

One example of this is the peak algebra.^[23]

Other related algebras

The Malvenuto–Reutenauer algebra^[24] is a Hopf algebra based on permutations that relates the rings of symmetric functions, quasisymmetric functions, and noncommutative symmetric functions, (denoted Sym, QSym, and NSym respectively), as depicted the following commutative diagram. The duality between QSym and NSym mentioned above is reflected in the main diagonal of this diagram.

Many related Hopf algebras were constructed from Hopf monoids in the category of species by Aguiar and Majahan.^[25]

One can also construct the ring of quasisymmetric functions in noncommuting variables.^[3]^[26]

References

^ Stanley, Richard P. Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999. ISBN 0-521-56069-1 (hardback) ISBN 0-521-78987-7 (paperback).
^ Hivert, Florent (2000), "Hecke Algebras, Difference Operators, and Quasi-Symmetric Functions", Advances in Mathematics, 155 (2): 181–238, doi:10.1006/aima.1999.1901
^ ^a ^b Hivert, Florent, Ph.D. Thesis, Marne-la-Vallée
^ Haglund, J.; Luoto, K.; Mason, S.; van Willigenburg, S. (2011), "Quasisymmetric Schur functions", Journal of Combinatorial Theory, Series A, 118 (2): 463–490, arXiv:0810.2489, doi:10.1016/j.jcta.2009.11.002
^ Ballantine, Christina; Daughtery, Zajj; Hicks, Angela; Mason, Sarah; Niese, Elizabeth (2020), "On Quasisymmetric Power Sums", Journal of Combinatorial Theory, Series A, 175: 105273, arXiv:1710.11613, doi:10.1016/j.jcta.2020.105273, S2CID 51775423
^ Luoto, K. (2008), "A matroid-friendly basis for the quasisymmetric functions", Journal of Combinatorial Theory, Series A, 115 (5): 777–798, arXiv:0704.0836, Bibcode:2007arXiv0704.0836L, doi:10.1016/j.jcta.2007.10.003
^ Billera, L.; Jia, N.; Reiner, V. (2009), "A quasisymmetric function for matroids", European Journal of Combinatorics, 30 (8): 1727–1757, arXiv:math/0606646, Bibcode:2006math......6646B, doi:10.1016/j.ejc.2008.12.007
^ Stanley, Richard P. Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, 1972.
^ Gessel, Ira. Multipartite P-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), 289–317, Contemp. Math., 34, Amer. Math. Soc., Providence, RI, 1984.
^ Gessel, Ira; Reutenauer, Christophe (1993), "Counting permutations with given cycle structure and descent set", Journal of Combinatorial Theory, Series A, 64 (2): 189–215, doi:10.1016/0097-3165(93)90095-P
^ Shareshian, John; Wachs, Michelle L. (2007), " $q$ -Eulerian polynomials: excedance number and major index", Electron. Res. Announc. Amer. Math. Soc., 13 (4): 33–45, arXiv:math/0608274, doi:10.1090/S1079-6762-07-00172-2, S2CID 15394306
^ Shareshian, John; Wachs, Michelle L. (2010), "Eulerian quasisymmetric functions", Advances in Mathematics, 225 (6): 2921–2966, arXiv:0812.0764, doi:10.1016/j.aim.2010.05.009
^ Hyatt, Matthew (2012), "Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups", Advances in Applied Mathematics, 48 (3): 465–505, arXiv:1007.0459, Bibcode:2010arXiv1007.0459H, doi:10.1016/j.aam.2011.11.005, S2CID 119118644
^ ^a ^b ^c Stanley, Richard P. (1984), "On the number of reduced decompositions of elements of Coxeter groups", European Journal of Combinatorics, 5 (4): 359–372, doi:10.1016/s0195-6698(84)80039-6
^ Ehrenborg, Richard (1996), "On posets and Hopf algebras", Advances in Mathematics, 119 (1): 1–25, doi:10.1006/aima.1996.0026
^ Haglund, James; The q,t-Catalan numbers and the space of diagonal harmonics. University Lecture Series, 41. American Mathematical Society, Providence, RI, 2008. viii+167 pp. ISBN 978-0-8218-4411-3; 0-8218-4411-3
^ Billey, Sara C.; Jockusch, William; Stanley, Richard P. (1993), "Some combinatorial properties of Schubert polynomials" (PDF), Journal of Algebraic Combinatorics, 2 (4): 345–374, doi:10.1023/A:1022419800503
^ Fomin, Sergey; Stanley, Richard P. (1994), "Schubert polynomials and the nil-Coxeter algebra", Advances in Mathematics, 103 (2): 196–207, doi:10.1006/aima.1994.1009
^ Assaf, Sami (2010), Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity, arXiv:1005.3759, Bibcode:2010arXiv1005.3759A
^ Duchamp, Gérard; Krob, Daniel; Leclerc, Bernard; Thibon, Jean-Yves (1996), "Fonctions quasi-symétriques, fonctions symétriques non commutatives et algèbres de Hecke à $q=0$ ", C. R. Acad. Sci. Paris, Sér. I Math., 322 (2): 107–112
^ Billera, Louis J.; Brenti, Francesco (2011), "Quasisymmetric functions and Kazhdan–Lusztig polynomials", Israel Journal of Mathematics, 184: 317–348, arXiv:0710.3965, doi:10.1007/s11856-011-0070-0
^ Aguiar, Marcelo; Bergeron, Nantel; Sottile, Frank (2006), "Combinatorial Hopf algebras and generalized Dehn–Sommerville relations", Compositio Mathematica, 142 (1): 1–30, arXiv:math/0310016, Bibcode:2003math.....10016A, doi:10.1112/S0010437X0500165X, S2CID 2635356
^ Stembridge, John R. (1997), "Enriched P-partitions", Trans. Amer. Math. Soc., 349 (2): 763–788, doi:10.1090/S0002-9947-97-01804-7
^ Malvenuto, Clauda; Reutenauer, Christophe (1995), "Duality between quasi-symmetric functions and the Solomon descent algebra", Journal of Algebra, 177 (3): 967–982, doi:10.1006/jabr.1995.1336
^ Aguiar, Marcelo; Mahajan, Swapneel Monoidal Functors, Species and Hopf Algebras CRM Monograph Series, no. 29. American Mathematical Society, Providence, RI, 2010.
^ Bergeron, Nantel; Zabrocki, Mike (2009), "The Hopf algebras of symmetric functions and quasi-symmetric functions in non-commutative variables are free and co-free", Journal of Algebra and Its Applications, 8 (4): 581–600, arXiv:math/0509265, doi:10.1142/S0219498809003485, S2CID 18601994

External links

BIRS Workshop on Quasisymmetric Functions

[EC2-1] Stanley, Richard P. Enumerative Combinatorics, Vol. 2, Cambridge University Press, 1999. ISBN 0-521-56069-1 (hardback) ISBN 0-521-78987-7 (paperback).

[Hiv-2] Hivert, Florent (2000), "Hecke Algebras, Difference Operators, and Quasi-Symmetric Functions", Advances in Mathematics, 155 (2): 181–238, doi:10.1006/aima.1999.1901

[Hiver-3] Hivert, Florent, Ph.D. Thesis, Marne-la-Vallée

[HLMvW1-4] Haglund, J.; Luoto, K.; Mason, S.; van Willigenburg, S. (2011), "Quasisymmetric Schur functions", Journal of Combinatorial Theory, Series A, 118 (2): 463–490, arXiv:0810.2489, doi:10.1016/j.jcta.2009.11.002

[BDHMN-5] Ballantine, Christina; Daughtery, Zajj; Hicks, Angela; Mason, Sarah; Niese, Elizabeth (2020), "On Quasisymmetric Power Sums", Journal of Combinatorial Theory, Series A, 175: 105273, arXiv:1710.11613, doi:10.1016/j.jcta.2020.105273, S2CID 51775423

[Luoto-6] Luoto, K. (2008), "A matroid-friendly basis for the quasisymmetric functions", Journal of Combinatorial Theory, Series A, 115 (5): 777–798, arXiv:0704.0836, Bibcode:2007arXiv0704.0836L, doi:10.1016/j.jcta.2007.10.003

[BJR-7] Billera, L.; Jia, N.; Reiner, V. (2009), "A quasisymmetric function for matroids", European Journal of Combinatorics, 30 (8): 1727–1757, arXiv:math/0606646, Bibcode:2006math......6646B, doi:10.1016/j.ejc.2008.12.007

[StanThesis-8] Stanley, Richard P. Ordered structures and partitions, Memoirs of the American Mathematical Society, No. 119, American Mathematical Society, 1972.

[Ppart-9] Gessel, Ira. Multipartite P-partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983), 289–317, Contemp. Math., 34, Amer. Math. Soc., Providence, RI, 1984.

[GesselReutenauer-10] Gessel, Ira; Reutenauer, Christophe (1993), "Counting permutations with given cycle structure and descent set", Journal of Combinatorial Theory, Series A, 64 (2): 189–215, doi:10.1016/0097-3165(93)90095-P

[Shareshian-11] Shareshian, John; Wachs, Michelle L. (2007), " $q$ -Eulerian polynomials: excedance number and major index", Electron. Res. Announc. Amer. Math. Soc., 13 (4): 33–45, arXiv:math/0608274, doi:10.1090/S1079-6762-07-00172-2, S2CID 15394306

[Shareshian2-12] Shareshian, John; Wachs, Michelle L. (2010), "Eulerian quasisymmetric functions", Advances in Mathematics, 225 (6): 2921–2966, arXiv:0812.0764, doi:10.1016/j.aim.2010.05.009

[Hyatt-13] Hyatt, Matthew (2012), "Eulerian quasisymmetric functions for the type B Coxeter group and other wreath product groups", Advances in Applied Mathematics, 48 (3): 465–505, arXiv:1007.0459, Bibcode:2010arXiv1007.0459H, doi:10.1016/j.aam.2011.11.005, S2CID 119118644

[StanCox-14] Stanley, Richard P. (1984), "On the number of reduced decompositions of elements of Coxeter groups", European Journal of Combinatorics, 5 (4): 359–372, doi:10.1016/s0195-6698(84)80039-6

[Ehrenborg-15] Ehrenborg, Richard (1996), "On posets and Hopf algebras", Advances in Mathematics, 119 (1): 1–25, doi:10.1006/aima.1996.0026

[HagBook-16] Haglund, James; The q,t-Catalan numbers and the space of diagonal harmonics. University Lecture Series, 41. American Mathematical Society, Providence, RI, 2008. viii+167 pp. ISBN 978-0-8218-4411-3; 0-8218-4411-3

[Billey-17] Billey, Sara C.; Jockusch, William; Stanley, Richard P. (1993), "Some combinatorial properties of Schubert polynomials" (PDF), Journal of Algebraic Combinatorics, 2 (4): 345–374, doi:10.1023/A:1022419800503

[Fomin-18] Fomin, Sergey; Stanley, Richard P. (1994), "Schubert polynomials and the nil-Coxeter algebra", Advances in Mathematics, 103 (2): 196–207, doi:10.1006/aima.1994.1009

[Assaf-19] Assaf, Sami (2010), Dual Equivalence Graphs I: A combinatorial proof of LLT and Macdonald positivity, arXiv:1005.3759, Bibcode:2010arXiv1005.3759A

[Duchamp-20] Duchamp, Gérard; Krob, Daniel; Leclerc, Bernard; Thibon, Jean-Yves (1996), "Fonctions quasi-symétriques, fonctions symétriques non commutatives et algèbres de Hecke à $q=0$ ", C. R. Acad. Sci. Paris, Sér. I Math., 322 (2): 107–112

[Billera-21] Billera, Louis J.; Brenti, Francesco (2011), "Quasisymmetric functions and Kazhdan–Lusztig polynomials", Israel Journal of Mathematics, 184: 317–348, arXiv:0710.3965, doi:10.1007/s11856-011-0070-0

[ABS-22] Aguiar, Marcelo; Bergeron, Nantel; Sottile, Frank (2006), "Combinatorial Hopf algebras and generalized Dehn–Sommerville relations", Compositio Mathematica, 142 (1): 1–30, arXiv:math/0310016, Bibcode:2003math.....10016A, doi:10.1112/S0010437X0500165X, S2CID 2635356

[Stem-23] Stembridge, John R. (1997), "Enriched P-partitions", Trans. Amer. Math. Soc., 349 (2): 763–788, doi:10.1090/S0002-9947-97-01804-7

[MR-24] Malvenuto, Clauda; Reutenauer, Christophe (1995), "Duality between quasi-symmetric functions and the Solomon descent algebra", Journal of Algebra, 177 (3): 967–982, doi:10.1006/jabr.1995.1336

[25] Aguiar, Marcelo; Mahajan, Swapneel Monoidal Functors, Species and Hopf Algebras CRM Monograph Series, no. 29. American Mathematical Society, Providence, RI, 2010.

[BZ-26] Bergeron, Nantel; Zabrocki, Mike (2009), "The Hopf algebras of symmetric functions and quasi-symmetric functions in non-commutative variables are free and co-free", Journal of Algebra and Its Applications, 8 (4): 581–600, arXiv:math/0509265, doi:10.1142/S0219498809003485, S2CID 18601994

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

Fahrer / Team für die Suche eingeben: