Signed combinatorial interpretations in algebraic combinatorics

Pak, Igor; Robichaux, Colleen

doi:10.5802/alco.413

Pak, Igor ¹; Robichaux, Colleen ¹

¹ University of California, Los Angeles Department of Mathematics 520 Portola Plaza Los Angeles CA 90095 (USA)

Algebraic Combinatorics, Volume 8 (2025) no. 2, pp. 495-519.

Abstract

We prove the existence of signed combinatorial interpretations for several large families of structure constants. These families include standard bases of symmetric and quasisymmetric polynomials, as well as various bases in Schubert theory. The results are stated in the language of computational complexity, while the proofs are based on the effective Möbius inversion.

Received: 2024-07-10
Revised: 2024-12-21
Accepted: 2024-12-24
Published online: 2025-04-24

DOI: 10.5802/alco.413

Classification: 05E05, 05E10, 05E14, 68Q15
Keywords: symmetric functions, quasisymmetric functions, Schubert polynomials, combinatorial interpretation, structure constants, $\#{\sf P}$, ${\sf GapP}$

Author's affiliations:

Pak, Igor ¹; Robichaux, Colleen ¹

¹ University of California, Los Angeles Department of Mathematics 520 Portola Plaza Los Angeles CA 90095 (USA)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@article{ALCO_2025__8_2_495_0,
     author = {Pak, Igor and Robichaux, Colleen},
     title = {Signed combinatorial interpretations in algebraic combinatorics},
     journal = {Algebraic Combinatorics},
     pages = {495--519},
     publisher = {The Combinatorics Consortium},
     volume = {8},
     number = {2},
     year = {2025},
     doi = {10.5802/alco.413},
     language = {en},
     url = {https://alco.centre-mersenne.org/articles/10.5802/alco.413/}
}

TY  - JOUR
AU  - Pak, Igor
AU  - Robichaux, Colleen
TI  - Signed combinatorial interpretations in algebraic combinatorics
JO  - Algebraic Combinatorics
PY  - 2025
SP  - 495
EP  - 519
VL  - 8
IS  - 2
PB  - The Combinatorics Consortium
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.413/
DO  - 10.5802/alco.413
LA  - en
ID  - ALCO_2025__8_2_495_0
ER  -

%0 Journal Article
%A Pak, Igor
%A Robichaux, Colleen
%T Signed combinatorial interpretations in algebraic combinatorics
%J Algebraic Combinatorics
%D 2025
%P 495-519
%V 8
%N 2
%I The Combinatorics Consortium
%U https://alco.centre-mersenne.org/articles/10.5802/alco.413/
%R 10.5802/alco.413
%G en
%F ALCO_2025__8_2_495_0

Pak, Igor; Robichaux, Colleen. Signed combinatorial interpretations in algebraic combinatorics. Algebraic Combinatorics, Volume 8 (2025) no. 2, pp. 495-519. doi : 10.5802/alco.413. https://alco.centre-mersenne.org/articles/10.5802/alco.413/

References
Cited by

[1] Alexandersson, Per The symmetric functions catalog, Online https://www.symmetricfunctions.com

[2] Alexandersson, Per; Uhlin, Joakim Cyclic sieving, skew Macdonald polynomials and Schur positivity, Algebr. Comb., Volume 3 (2020) no. 4, pp. 913-939 | Numdam | MR | Zbl

[3] Aliniaeifard, Farid; Wang, Victor; van Willigenburg, Stephanie $P$ -partition power sums, European J. Combin., Volume 110 (2023), Paper no. 103688, 16 pages | MR | Zbl

[4] Allen, Edward E.; Mason, Sarah A combinatorial interpretation of the noncommutative inverse Kostka matrix, Sém. Lothar. Combin., Volume 89B (2023), Paper no. 59, 12 pages | MR

[5] Assaf, Sami; Searles, Dominic Schubert polynomials, slide polynomials, Stanley symmetric functions and quasi-Yamanouchi pipe dreams, Adv. Math., Volume 306 (2017), pp. 89-122 | DOI | MR | Zbl

[6] Ballantine, Cristina; Daugherty, Zajj; Hicks, Angela; Mason, Sarah; Niese, Elizabeth On quasisymmetric power sums, J. Combin. Theory Ser. A, Volume 175 (2020), Paper no. 105273, 37 pages | MR | Zbl

[7] Berg, Chris; Bergeron, Nantel; Saliola, Franco; Serrano, Luis; Zabrocki, Mike A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions, Canad. J. Math., Volume 66 (2014) no. 3, pp. 525-565 | DOI | MR | Zbl

[8] Bergeron, Nantel; Billey, Sara RC-graphs and Schubert polynomials, Experiment. Math., Volume 2 (1993) no. 4, pp. 257-269 | DOI | MR | Zbl

[9] Billey, Sara C. Kostant polynomials and the cohomology ring for $G / B$ , Duke Math. J., Volume 96 (1999) no. 1, pp. 205-224 | MR | Zbl

[10] Billey, Sara C.; Jockusch, William; Stanley, Richard P. Some combinatorial properties of Schubert polynomials, J. Algebraic Combin., Volume 2 (1993) no. 4, pp. 345-374 | DOI | MR | Zbl

[11] Blass, Andreas; Sagan, Bruce E. Möbius functions of lattices, Adv. Math., Volume 127 (1997) no. 1, pp. 94-123 | DOI | MR | Zbl

[12] Borodin, Alexei Longest increasing subsequences of random colored permutations, Electron. J. Combin., Volume 6 (1999), Paper no. 13, 12 pages | MR | Zbl

[13] Bravyi, Sergey; Chowdhury, Anirban; Gosset, David; Havlíček, Vojtěch; Zhu, Guanyu Quantum Complexity of the Kronecker Coefficients, PRX Quantum, Volume 5 (2024), Paper no. 010329, 12 pages | DOI

[14] Brion, Michel Positivity in the Grothendieck group of complex flag varieties, J. Algebra, Volume 258 (2002) no. 1, pp. 137-159 | DOI | MR | Zbl

[15] Brylawski, Thomas The lattice of integer partitions, Discrete Math., Volume 6 (1973), pp. 201-219 | DOI | MR | Zbl

[16] Bürgisser, Peter; Ikenmeyer, Christian The complexity of computing Kronecker coefficients, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (Discrete Math. Theor. Comput. Sci. Proc.), Volume AJ, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2008, pp. 357-368 | MR | Zbl

[17] Bürgisser, Peter; Ikenmeyer, Christian Deciding positivity of Littlewood-Richardson coefficients, SIAM J. Discrete Math., Volume 27 (2013) no. 4, pp. 1639-1681 | DOI | MR | Zbl

[18] Carbonara, Joaquin O. A combinatorial interpretation of the inverse $t$ -Kostka matrix, Discrete Math., Volume 193 (1998) no. 1-3, pp. 117-145 | DOI | MR | Zbl

[19] Chan, Swee Hong; Pak, Igor Equality cases of the Alexandrov–Fenchel inequality are not in the polynomial hierarchy, Forum Math. Pi, Volume 12 (2024), Paper no. e21, 38 pages | Zbl

[20] Chen, Young-Ming; Garsia, Adriano M.; Remmel, Jeffrey Algorithms for plethysm, Combinatorics and algebra (Boulder, Colo., 1983) (Contemp. Math.), Volume 34, Amer. Math. Soc., Providence, RI, 1984, pp. 109-153 | DOI | MR | Zbl

[21] Christandl, Matthias; Doran, Brent; Walter, Michael Computing multiplicities of Lie group representations, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science—FOCS 2012, IEEE Computer Soc., Los Alamitos, CA, 2012, pp. 639-648 | DOI | MR

[22] Colmenarejo, Laura; Orellana, Rosa; Saliola, Franco; Schilling, Anne; Zabrocki, Mike The mystery of plethysm coefficients, Open problems in algebraic combinatorics (Proc. Sympos. Pure Math.), Volume 110, Amer. Math. Soc., Providence, RI, 2024, pp. 275-292 | DOI

[23] De Loera, Jesús A.; McAllister, Tyrrell B. On the computation of Clebsch-Gordan coefficients and the dilation effect, Experiment. Math., Volume 15 (2006) no. 1, pp. 7-19 | DOI | MR | Zbl

[24] Doran, William F. IV A plethysm formula for $p_{μ} (\underset{̲}{x}) \circ h_{λ} (\underset{̲}{x})$ , Electron. J. Combin., Volume 4 (1997) no. 1, Paper no. 14, 10 pages | MR | Zbl

[25] Duan, Haibao On the inverse Kostka matrix, J. Combin. Theory Ser. A, Volume 103 (2003) no. 2, pp. 363-376 | DOI | MR | Zbl

[26] Eğecioğlu, Ömer; Remmel, Jeffrey B. A combinatorial interpretation of the inverse Kostka matrix, Linear and Multilinear Algebra, Volume 26 (1990) no. 1-2, pp. 59-84 | MR | Zbl

[27] Egge, Eric; Loehr, Nicholas A.; Warrington, Gregory S. From quasisymmetric expansions to Schur expansions via a modified inverse Kostka matrix, European J. Combin., Volume 31 (2010) no. 8, pp. 2014-2027 | DOI | MR | Zbl

[28] Féray, Valentin Cyclic inclusion-exclusion, SIAM J. Discrete Math., Volume 29 (2015) no. 4, pp. 2284-2311 | DOI | MR | Zbl

[29] Féray, Valentin; Śniady, Piotr Asymptotics of characters of symmetric groups related to Stanley character formula, Ann. of Math. (2), Volume 173 (2011) no. 2, pp. 887-906 | DOI | Zbl

[30] Fischer, Nick; Ikenmeyer, Christian The computational complexity of plethysm coefficients, Comput. Complexity, Volume 29 (2020) no. 2, Paper no. 8, 43 pages | MR | Zbl

[31] Fomin, Sergey; Kirillov, Anatol N. Grothendieck polynomials and the Yang-Baxter equation, Formal power series and algebraic combinatorics/Séries formelles et combinatoire algébrique, DIMACS, Piscataway, NJ, 1996, pp. 183-189

[32] Fortnow, Lance Counting complexity, Complexity theory retrospective, II, Springer, New York, 1997, pp. 81-107 | DOI | Zbl

[33] Gessel, Ira M. Multipartite $P$ -partitions and inner products of skew Schur functions, Combinatorics and algebra (Boulder, Colo., 1983) (Contemp. Math.), Volume 34, Amer. Math. Soc., Providence, RI, 1984, pp. 289-317 | DOI | MR | Zbl

[34] Goulden, Ian P.; Jackson, David M.; Vakil, Ravi Towards the geometry of double Hurwitz numbers, Adv. Math., Volume 198 (2005) no. 1, pp. 43-92 | DOI | MR | Zbl

[35] Greene, Curtis A class of lattices with Möbius function $\pm 1, 0$ , European J. Combin., Volume 9 (1988) no. 3, pp. 225-240 | DOI | MR | Zbl

[36] Greene, Curtis; Kleitman, Daniel J. Longest chains in the lattice of integer partitions ordered by majorization, European J. Combin., Volume 7 (1986) no. 1, pp. 1-10 | DOI | MR | Zbl

[37] 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 pages | MR

[38] Haglund, James; Haiman, Mark; Loehr, Nicholas A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc., Volume 18 (2005) no. 3, pp. 735-761 | DOI | MR | Zbl

[39] Haglund, James; Luoto, Kurt; Mason, Sarah; van Willigenburg, Stephanie Quasisymmetric Schur functions, J. Combin. Theory Ser. A, Volume 118 (2011) no. 2, pp. 463-490 | DOI | MR

[40] Haiman, Mark; Grojnowski, Ian Affine Hecke algebras and positivity of LLT and Macdonald polynomials, Online, pp. 29, 2006 https://math.berkeley.edu/~mhaiman/ftp/llt-positivity/new-version.pdf

[41] Hemaspaandra, Lane A.; Ogihara, Mitsunori The complexity theory companion, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2002, xiv+369 pages | DOI | MR

[42] Hivert, Florent Hecke algebras, difference operators, and quasi-symmetric functions, Adv. Math., Volume 155 (2000) no. 2, pp. 181-238 | DOI | MR | Zbl

[43] Ikenmeyer, Christian; Mulmuley, Ketan D.; Walter, Michael On vanishing of Kronecker coefficients, Comput. Complexity, Volume 26 (2017) no. 4, pp. 949-992 | DOI | MR | Zbl

[44] Ikenmeyer, Christian; Pak, Igor What is in #P and what is not?, 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS) (2022), pp. 860-871 | DOI | MR

[45] Ikenmeyer, Christian; Pak, Igor; Panova, Greta Positivity of the symmetric group characters is as hard as the polynomial time hierarchy, Int. Math. Res. Not. IMRN (2024) no. 10, pp. 8442-8458 | DOI | MR | Zbl

[46] Ikenmeyer, Christian; Subramanian, Sathyawageeswar A remark on the quantum complexity of the Kronecker coefficients, 27th Quantum Information Processing (QIP) (2024) arxiv:2307.02389 (13 pp.)

[47] Jack, Henry A class of symmetric polynomials with a parameter, Proc. Roy. Soc. Edinburgh Sect. A, Volume 69 (1970/71), pp. 1-18 | MR | Zbl

[48] Jagger, Mick; Richards, Keith You can’t always get what you want, in Let It Bleed, The Rolling Stones, 1969 (5 min.)

[49] James, Gordon; Kerber, Adalbert The representation theory of the symmetric group, Encyclopedia of Mathematics and its Applications, 16, Addison-Wesley Publishing Co., Reading, MA, 1981, xxviii+510 pages | MR

[50] Kahn, Jeff On lattices with Möbius function $\pm 1, 0$ , Discrete Comput. Geom., Volume 2 (1987) no. 1, pp. 1-8 | DOI | MR | Zbl

[51] Knutson, Allen Schubert calculus and quiver varieties, ICM—International Congress of Mathematicians. Vol. 6. Sections 12–14, EMS Press, Berlin, 2023, pp. 4582-4605 | DOI | Zbl

[52] Knutson, Allen; Tao, Terence The honeycomb model of ${GL}_{n} (C)$ tensor products. I. Proof of the saturation conjecture, J. Amer. Math. Soc., Volume 12 (1999) no. 4, pp. 1055-1090 | DOI | MR | Zbl

[53] Knutson, Allen; Zinn-Justin, Paul Schubert puzzles and integrability III: separated descents, 2023 | arXiv

[54] Kohnert, Axel Weintrauben, Polynome, Tableaux, Bayreuth. Math. Schr. (1991) no. 38, pp. 1-97 (Dissertation, Universität Bayreuth, Bayreuth, 1990) | MR | Zbl

[55] Larsen, Michael; Shalev, Aner Characters of symmetric groups: sharp bounds and applications, Invent. Math., Volume 174 (2008) no. 3, pp. 645-687 | DOI | MR | Zbl

[56] Lascoux, Alain Transition on Grothendieck polynomials, Physics and combinatorics, 2000 (Nagoya), World Sci. Publ., River Edge, NJ, 2001, pp. 164-179 | DOI | MR

[57] Lascoux, Alain; Leclerc, Bernard; Thibon, Jean-Yves Ribbon tableaux, Hall-Littlewood functions, quantum affine algebras, and unipotent varieties, J. Math. Phys., Volume 38 (1997) no. 2, pp. 1041-1068 | DOI | MR | Zbl

[58] Lascoux, Alain; Schützenberger, Marcel-Paul Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math., Volume 294 (1982) no. 13, pp. 447-450 | MR | Zbl

[59] Lascoux, Alain; Schützenberger, Marcel-Paul Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math., Volume 295 (1982) no. 11, pp. 629-633 | MR | Zbl

[60] Lascoux, Alain; Schützenberger, Marcel-Paul Keys & standard bases, Invariant theory and tableaux (Minneapolis, MN, 1988) (IMA Vol. Math. Appl.), Volume 19, Springer, New York, 1990, pp. 125-144 | MR | Zbl

[61] Littlewood, Dudley E. On certain symmetric functions, Jack, Hall-Littlewood and Macdonald polynomials (Contemp. Math.), Volume 417, Amer. Math. Soc., Providence, RI, 2006, pp. 43-56 Reprinted from Proc. London Math. Soc. (3) 11 (1961), 485–498 [MR0130308] | DOI | Zbl

[62] Loehr, Nicholas A.; Remmel, Jeffrey B. A computational and combinatorial exposé of plethystic calculus, J. Algebraic Combin., Volume 33 (2011) no. 2, pp. 163-198 | DOI | MR | Zbl

[63] Macdonald, Ian G. Symmetric functions and Hall polynomials, Oxford Mathematical Monographs, The Clarendon Press, Oxford University Press, New York, 1979, viii+180 pages | MR

[64] Macdonald, Ian G. A new class of symmetric functions., Séminaire Lotharingien de Combinatoire, Volume 20 (1988), Paper no. B20a, 41 pages http://eudml.org/doc/120965 | Zbl

[65] Mason, Sarah An explicit construction of type A Demazure atoms, J. Algebraic Combin., Volume 29 (2009) no. 3, pp. 295-313 | DOI | MR | Zbl

[66] Melczer, Stephen; Michelen, Marcus; Mukherjee, Somabha Asymptotic bounds on graphical partitions and partition comparability, Int. Math. Res. Not. IMRN (2021) no. 4, pp. 2842-2860 | DOI | MR | Zbl

[67] Nadeau, Philippe; Spink, Hunter; Tewari, Vasu Quasisymmetric divided differences, 2024 | arXiv

[68] Nadeau, Philippe; Tewari, Vasu $P$ -partitions with flags and back stable quasisymmetric functions, Comb. Theory, Volume 4 (2024) no. 2, Paper no. 4, 22 pages | MR | Zbl

[69] Nava, Oscar; Rota, Gian-Carlo Plethysm, categories, and combinatorics, Adv. in Math., Volume 58 (1985) no. 1, pp. 61-88 | DOI | MR | Zbl

[70] Okounkov, Andrei; Vershik, Anatoly A new approach to representation theory of symmetric groups, Selecta Math. (N.S.), Volume 2 (1996) no. 4, pp. 581-605 | DOI | MR | Zbl

[71] Pak, Igor Ribbon tile invariants, Trans. Amer. Math. Soc., Volume 352 (2000) no. 12, pp. 5525-5561 | MR | Zbl

[72] Pak, Igor Combinatorial inequalities, Notices Amer. Math. Soc., Volume 66 (2019) no. 7, pp. 1109-1112 (an expanded version of the paper is available at tinyurl.com/py8sv5v6) | MR | Zbl

[73] Pak, Igor What is a combinatorial interpretation?, Open problems in algebraic combinatorics (Proc. Sympos. Pure Math.), Volume 110, Amer. Math. Soc., Providence, RI, 2024, pp. 191-260

[74] Pak, Igor; Panova, Greta Strict unimodality of $q$ -binomial coefficients, C. R. Math. Acad. Sci. Paris, Volume 351 (2013) no. 11-12, pp. 415-418 | Numdam | MR | Zbl

[75] Pak, Igor; Panova, Greta On the complexity of computing Kronecker coefficients, Comput. Complexity, Volume 26 (2017) no. 1, pp. 1-36 | MR | Zbl

[76] Pak, Igor; Panova, Greta Bounds on Kronecker coefficients via contingency tables, Linear Algebra Appl., Volume 602 (2020), pp. 157-178 | MR | Zbl

[77] Pak, Igor; Panova, Greta; Yeliussizov, Damir On the largest Kronecker and Littlewood-Richardson coefficients, J. Combin. Theory Ser. A, Volume 165 (2019), pp. 44-77 | MR | Zbl

[78] Pan, Jianping; Yu, Tianyi A bijection between $K$ -Kohnert diagrams and reverse set-valued tableaux, Electron. J. Combin., Volume 30 (2023) no. 4, Paper no. 4.26, 38 pages | MR | Zbl

[79] Panova, Greta Complexity and asymptotics of structure constants, Open problems in algebraic combinatorics (Proc. Sympos. Pure Math.), Volume 110, Amer. Math. Soc., Providence, RI, 2024, pp. 61-85 | DOI

[80] Pittel, Boris Confirming two conjectures about the integer partitions, J. Combin. Theory Ser. A, Volume 88 (1999) no. 1, pp. 123-135 | DOI | MR | Zbl

[81] Postnikov, Alexander; Stanley, Richard P. Chains in the Bruhat order, J. Algebraic Combin., Volume 29 (2009) no. 2, pp. 133-174 | DOI | MR | Zbl

[82] Roichman, Yuval Upper bound on the characters of the symmetric groups, Invent. Math., Volume 125 (1996) no. 3, pp. 451-485 | DOI | MR | Zbl

[83] Ross, Colleen; Yong, Alexander Combinatorial rules for three bases of polynomials, Sém. Lothar. Combin., Volume 74 (2015–2018), Paper no. B74a, 11 pages | MR | Zbl

[84] Sagan, Bruce E. The symmetric group: Representations, combinatorial algorithms, and symmetric functions, Graduate Texts in Mathematics, 203, Springer-Verlag, New York, 2001, xvi+238 pages | DOI | MR

[85] Sagan, Bruce E.; Vatter, Vincent The Möbius function of a composition poset, J. Algebraic Combin., Volume 24 (2006) no. 2, pp. 117-136 | DOI | MR | Zbl

[86] Schwer, Christoph Galleries, Hall-Littlewood polynomials, and structure constants of the spherical Hecke algebra, Int. Math. Res. Not. (2006), Paper no. 75395, 31 pages | MR | Zbl

[87] Serre, Jean-Pierre Linear representations of finite groups, Graduate Texts in Mathematics, 42, Springer-Verlag, New York-Heidelberg, 1977, x+170 pages | DOI | MR

[88] Stanley, Richard P. Positivity problems and conjectures in algebraic combinatorics, Mathematics: frontiers and perspectives, Amer. Math. Soc., Providence, RI, 2000, pp. 295-319 | Zbl

[89] Stanley, Richard P. Enumerative combinatorics. vol. 1 (Second ed.) and vol. 2, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, Cambridge, 2012 and 1999, 626 pp. and 581 pp pages | MR

[90] Stanton, Dennis W.; White, Dennis E. A Schensted algorithm for rim hook tableaux, J. Combin. Theory Ser. A, Volume 40 (1985) no. 2, pp. 211-247 | DOI | MR | Zbl

[91] Stembridge, John R. The partial order of dominant weights, Adv. Math., Volume 136 (1998) no. 2, pp. 340-364 | DOI | MR | Zbl

[92] van Willigenburg, Stephanie The shuffle conjecture, Bull. Amer. Math. Soc. (N.S.), Volume 57 (2020) no. 1, pp. 77-89 | DOI | MR | Zbl

[93] White, Dennis Orthogonality of the characters of $S_{n}$ , J. Combin. Theory Ser. A, Volume 40 (1985) no. 2, pp. 265-275 | DOI | MR | Zbl

[94] White, Dennis E. A bijection proving orthogonality of the characters of $S_{n}$ , Adv. in Math., Volume 50 (1983) no. 2, pp. 160-186 | DOI | MR | Zbl

[95] Yamaguchi, Kohei A Littlewood-Richardson rule for Koornwinder polynomials, J. Algebraic Combin., Volume 56 (2022) no. 2, pp. 335-381 | DOI | MR | Zbl

[96] Yang, Mei An algorithm for computing plethysm coefficients, Proceedings of the 7th Conference on Formal Power Series and Algebraic Combinatorics (Noisy-le-Grand, 1995) (180) (1998) no. 1-3, pp. 391-402 | Zbl

[97] Yip, Martha A Littlewood-Richardson rule for Macdonald polynomials, Math. Z., Volume 272 (2012) no. 3-4, pp. 1259-1290 | MR | Zbl

Cited by Sources: