# ALGEBRAIC COMBINATORICS

Generalized Littlewood–Richardson coefficients for branching rules of GL$\left(n\right)$ and extremal weight crystals
Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1365-1400.

Following the methods used by Derksen–Weyman in [16] and Chindris in [9], we use quiver theory to represent the generalized Littlewood–Richardson coefficients for the branching rule for the diagonal embedding of $\text{GL}\left(n\right)$ as the dimension of a weight space of semi-invariants. Using this, we prove their saturation and investigate when they are nonzero. We also show that for certain partitions the associated stretched polynomials satisfy the same conjectures as single Littlewood–Richardson coefficients. We then provide a polytopal description of this multiplicity and show that its positivity may be computed in strongly polynomial time. Finally, we remark that similar results hold for certain other generalized Littlewood–Richardson coefficients.

Revised: 2020-07-08
Accepted: 2020-08-10
Published online: 2020-12-04
DOI: https://doi.org/10.5802/alco.143
Classification: 16G20,  05E15
Keywords: Quiver representations, semi-invariants, Littlewood–Richardson coefficients, Horn’s Conjecture, branching rule, hive model.
@article{ALCO_2020__3_6_1365_0,
author = {Collins, Brett},
title = {Generalized Littlewood--Richardson coefficients for branching rules of GL<span class="mathjax-formula">$(n)$</span> and extremal weight crystals},
journal = {Algebraic Combinatorics},
pages = {1365--1400},
publisher = {MathOA foundation},
volume = {3},
number = {6},
year = {2020},
doi = {10.5802/alco.143},
language = {en},
url = {alco.centre-mersenne.org/item/ALCO_2020__3_6_1365_0/}
}
Collins, Brett. Generalized Littlewood–Richardson coefficients for branching rules of GL$(n)$ and extremal weight crystals. Algebraic Combinatorics, Volume 3 (2020) no. 6, pp. 1365-1400. doi : 10.5802/alco.143. https://alco.centre-mersenne.org/item/ALCO_2020__3_6_1365_0/

[1] Agnihotri, Samar; Woodward, Christopher Eigenvalues of products of unitary matrices and quantum Schubert calculus, Math. Res. Lett., Volume 5 (1998) no. 6, pp. 817-836 | Article | MR 1671192 | Zbl 1004.14013

[2] Baldoni, Velleda; Vergne, Michèle; Walter, Michael Horn inequalities and quivers (2018) (https://arxiv.org/abs/1804.00431)

[3] Belkale, Prakash Local systems on ${ℙ}^{1}-S$ for $S$ a finite set, Compositio Math., Volume 129 (2001) no. 1, pp. 67-86 | Article | MR 1856023 | Zbl 1042.14031

[4] Belkale, Prakash Geometric proofs of Horn and saturation conjectures, J. Algebraic Geom., Volume 15 (2006) no. 1, pp. 133-173 | Article | MR 2177198 | Zbl 1090.14014

[5] Belkale, Prakash Geometric proof of a conjecture of Fulton, Adv. Math., Volume 216 (2007) no. 1, pp. 346-357 | Article | MR 2353260 | Zbl 1129.14063

[6] Buch, Anders Skovsted The saturation conjecture (after A. Knutson and T. Tao), Enseign. Math. (2), Volume 46 (2000) no. 1-2, pp. 43-60 (With an appendix by William Fulton) | MR 1769536 | Zbl 0979.20041

[7] Bürgisser, Peter; Ikenmeyer, Christian A max-flow algorithm for positivity of Littlewood–Richardson coefficients, 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009) (Discrete Math. Theor. Comput. Sci. Proc., AK), Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2009, pp. 265-276 | MR 2721518 | Zbl 1392.05112

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

[9] Chindris, Calin Quivers, long exact sequences and Horn type inequalities, J. Algebra, Volume 320 (2008) no. 1, pp. 128-157 | Article | MR 2417982 | Zbl 1207.16011

[10] Chindris, Calin Quivers, long exact sequences and Horn type inequalities. II, Glasg. Math. J., Volume 51 (2009) no. 2, pp. 201-217 | Article | MR 2500745 | Zbl 1210.16016

[11] Crawley-Boevey, William; Geiss, Christof Horn’s problem and semi-stability for quiver representations, Representations of algebra. Vol. I, II, Beijing Norm. Univ. Press, Beijing, 2002, pp. 40-48 | MR 2067369 | Zbl 1086.16514

[12] 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 | Article | MR 2229381 | Zbl 1115.17005

[13] Derksen, Harm; Schofield, Aidan; Weyman, Jerzy On the number of subrepresentations of a general quiver representation, J. Lond. Math. Soc. (2), Volume 76 (2007) no. 1, pp. 135-147 | Article | MR 2351613 | Zbl 1146.16007

[14] Derksen, Harm; Weyman, Jerzy Semi-invariants of quivers and saturation for Littlewood–Richardson coefficients, J. Amer. Math. Soc., Volume 13 (2000) no. 3, pp. 467-479 | Article | MR 1758750 | Zbl 0993.16011

[15] Derksen, Harm; Weyman, Jerzy On the Littlewood–Richardson polynomials, J. Algebra, Volume 255 (2002) no. 2, pp. 247-257 | Article | MR 1935497 | Zbl 1018.16012

[16] Derksen, Harm; Weyman, Jerzy The combinatorics of quiver representations, Ann. Inst. Fourier (Grenoble), Volume 61 (2011) no. 3, pp. 1061-1131 | Article | Numdam | MR 2918725 | Zbl 1271.16016

[17] Fei, Jiarui Cluster algebras and semi-invariant rings I. Triple flags, Proc. Lond. Math. Soc. (3), Volume 115 (2017) no. 1, pp. 1-32 | Article | MR 3669931 | Zbl 1396.13019

[18] Fulton, William Young tableaux. With applications to representation theory and geometry, London Mathematical Society Student Texts, Volume 35, Cambridge University Press, Cambridge, 1997, x+260 pages | MR 1464693 | Zbl 0878.14034

[19] Fulton, William Eigenvalues of sums of Hermitian matrices (after A. Klyachko), Séminaire Bourbaki (Astérisque) Volume 1997/98, Société Mathématique de France, 1998 no. 252, pp. 255-269 (Exp. No. 845) | MR 1685640 | Zbl 0929.15006

[20] Grötschel, Martin; Lovász, László; Schrijver, Alexander Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, Volume 2, Springer-Verlag, Berlin, 1993, xii+362 pages | Article | MR 1261419 | Zbl 0837.05001

[21] Horn, Alfred Eigenvalues of sums of Hermitian matrices, Pacific J. Math., Volume 12 (1962), pp. 225-241 | Article | MR 140521 | Zbl 0112.01501

[22] Howe, Roger; Jackson, Steven; Lee, Soo Teck; Tan, Eng-Chye; Willenbring, Jeb Toric degeneration of branching algebras, Adv. Math., Volume 220 (2009) no. 6, pp. 1809-1841 | Article | MR 2493182 | Zbl 1179.22012

[23] Howe, Roger; Tan, Eng-Chye; Willenbring, Jeb F. Stable branching rules for classical symmetric pairs, Trans. Amer. Math. Soc., Volume 357 (2005) no. 4, pp. 1601-1626 | Article | MR 2115378 | Zbl 1069.22006

[24] Ikenmeyer, Christian Small Littlewood–Richardson coefficients, J. Algebraic Combin., Volume 44 (2016) no. 1, pp. 1-29 | Article | MR 3514767 | Zbl 1342.05188

[25] Kac, Victor G. Infinite root systems, representations of graphs and invariant theory. II, J. Algebra, Volume 78 (1982) no. 1, pp. 141-162 | Article | MR 677715 | Zbl 0497.17007

[26] Kashiwara, Masaki Crystalizing the $q$-analogue of universal enveloping algebras, Comm. Math. Phys., Volume 133 (1990) no. 2, pp. 249-260 | Article | MR 1090425 | Zbl 0724.17009

[27] King, Alastair D. Moduli of representations of finite-dimensional algebras, Quart. J. Math. Oxford Ser. (2), Volume 45 (1994) no. 180, pp. 515-530 | Article | MR 1315461 | Zbl 0837.16005

[28] King, Ronald C. Generalized Young tableaux and the general linear group, J. Mathematical Phys., Volume 11 (1970), pp. 280-293 | Article | MR 251972 | Zbl 0199.34604

[29] King, Ronald C. Modification rules and products of irreducible representations of the unitary, orthogonal, and symplectic groups, J. Mathematical Phys., Volume 12 (1971), pp. 1588-1598 | Article | MR 287816 | Zbl 0239.20061

[30] King, Ronald C.; Tollu, Christophe; Toumazet, Frédéric Stretched Littlewood–Richardson and Kostka coefficients, Symmetry in physics (CRM Proc. Lecture Notes) Volume 34, Amer. Math. Soc., Providence, RI, 2004, pp. 99-112 | Article | MR 2056979 | Zbl 1055.05004

[31] King, Ronald C.; Tollu, Christophe; Toumazet, Frédéric The hive model and the factorisation of Kostka coefficients, Sém. Lothar. Combin., Volume 54A (2005/07), Art. B54Ah, 22 pages | MR 2264935 | Zbl 1178.05101

[32] King, Ronald C.; Tollu, Christophe; Toumazet, Frédéric The hive model and the polynomial nature of stretched Littlewood–Richardson coefficients, Sém. Lothar. Combin., Volume 54A (2005/07), Art. B54Ad, 19 pages | MR 2264931 | Zbl 1178.05100

[33] Klein, Therese The multiplication of Schur-functions and extensions of $p$-modules, J. London Math. Soc., Volume 43 (1968), pp. 280-284 | Article | MR 228481 | Zbl 0188.09504

[34] Klyachko, Alexander A. Stable bundles, representation theory and Hermitian operators, Selecta Math. (N.S.), Volume 4 (1998) no. 3, pp. 419-445 | Article | MR 1654578 | Zbl 0915.14010

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

[36] Knutson, Allen; Tao, Terence Honeycombs and sums of Hermitian matrices, Notices Amer. Math. Soc., Volume 48 (2001) no. 2, pp. 175-186 | MR 1811121 | Zbl 1047.15006

[37] Knutson, Allen; Tao, Terence; Woodward, Christopher The honeycomb model of ${\mathrm{GL}}_{n}\left(ℂ\right)$ tensor products. II. Puzzles determine facets of the Littlewood–Richardson cone, J. Amer. Math. Soc., Volume 17 (2004) no. 1, pp. 19-48 | Article | MR 2015329 | Zbl 1043.05111

[38] Koike, Kazuhiko On the decomposition of tensor products of the representations of the classical groups: by means of the universal characters, Adv. Math., Volume 74 (1989) no. 1, pp. 57-86 | Article | MR 991410 | Zbl 0681.20030

[39] Kwon, Jae-Hoon Differential operators and crystals of extremal weight modules, Adv. Math., Volume 222 (2009) no. 4, pp. 1339-1369 | Article | MR 2554938 | Zbl 1189.17015

[40] Kwon, Jae-Hoon Littlewood–Richardson coefficients and weight crystals (2010) (http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1689-07.pdf)

[41] Meinrenken, Eckhard; Sjamaar, Reyer Singular reduction and quantization, Topology, Volume 38 (1999) no. 4, pp. 699-762 | Article | MR 1679797 | Zbl 0928.37013

[42] Mulmuley, Ketan Explicit proofs and the flip (2010) (https://arxiv.org/abs/1009.0246)

[43] Mulmuley, Ketan Geometric complexity theory VI: The flip via positivity (2011) (http://gct.cs.uchicago.edu/gct6.pdf)

[44] Mulmuley, Ketan Geometric complexity theory V: Efficient algorithms for Noether normalization, J. Amer. Math. Soc., Volume 30 (2017) no. 1, pp. 225-309 | Article | MR 3556292 | Zbl 1402.14078

[45] Mulmuley, Ketan; Narayanan, Hariharan; Sohoni, Milind Geometric complexity theory III: on deciding nonvanishing of a Littlewood–Richardson coefficient, J. Algebraic Combin., Volume 36 (2012) no. 1, pp. 103-110 | Article | MR 2927658 | Zbl 1271.03055

[46] Mulmuley, Ketan; Sohoni, Milind Geometric complexity theory. I. An approach to the P vs. NP and related problems, SIAM J. Comput., Volume 31 (2001) no. 2, pp. 496-526 | Article | MR 1861288 | Zbl 0992.03048

[47] Mulmuley, Ketan; Sohoni, Milind Geometric complexity theory, P vs. NP and explicit obstructions, Advances in algebra and geometry (Hyderabad, 2001), Hindustan Book Agency, New Delhi, 2003, pp. 239-261 | Article | MR 1988959 | Zbl 1046.68057

[48] Mulmuley, Ketan; Sohoni, Milind Geometric complexity theory III, on deciding positivity of Littlewood–Richardson coefficients (2005) (https://arxiv.org/abs/cs/0501076) | Zbl 1271.03055

[49] Mulmuley, Ketan; Sohoni, Milind Geometric complexity theory: Introduction (2007) (https://arxiv.org/abs/0709.0746)

[50] Mulmuley, Ketan; Sohoni, Milind Geometric complexity theory. II. Towards explicit obstructions for embeddings among class varieties, SIAM J. Comput., Volume 38 (2008) no. 3, pp. 1175-1206 | Article | MR 2421083 | Zbl 1168.03030

[51] Narayanan, Hariharan The computation of Kostka numbers and Littlewood–Richardson coefficients is #P-complete (2005) (https://arxiv.org/abs/math/0501176)

[52] Rassart, Etienne A polynomiality property for Littlewood–Richardson coefficients, J. Combin. Theory Ser. A, Volume 107 (2004) no. 2, pp. 161-179 | Article | MR 2078884 | Zbl 1060.05098

[53] Schofield, Aidan General representations of quivers, Proc. London Math. Soc. (3), Volume 65 (1992) no. 1, pp. 46-64 | Article | MR 1162487 | Zbl 0795.16008

[54] Schofield, Aidan; van den Bergh, Michel Semi-invariants of quivers for arbitrary dimension vectors, Indag. Math. (N.S.), Volume 12 (2001) no. 1, pp. 125-138 | Article | MR 1908144 | Zbl 1004.16012

[55] Schrijver, Alexander Combinatorial optimization. Polyhedra and efficiency. Vol. C, Algorithms and Combinatorics, Volume 24, Springer-Verlag, Berlin, 2003, p. i-xxxiv and 1219–1881 (Disjoint paths, hypergraphs, Chapters 70–83) | MR 1956926 | Zbl 1041.90001

[56] Sherman, Cass Geometric proof of a conjecture of King, Tollu, and Toumazet (2015) (https://arxiv.org/abs/1505.06551)

[57] Sherman, Cass Quiver generalization of a conjecture of King, Tollu, and Toumazet, J. Algebra, Volume 480 (2017), pp. 487-504 | Article | MR 3633317 | Zbl 1411.16016

[58] Tardos, Éva A strongly polynomial algorithm to solve combinatorial linear programs, Oper. Res., Volume 34 (1986) no. 2, pp. 250-256 | Article | MR 861043 | Zbl 0626.90053

[59] Weyl, Hermann Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung), Math. Ann., Volume 71 (1912) no. 4, pp. 441-479 | Article | MR 1511670 | Zbl 43.0436.01

[60] Zelevinsky, Andrei Littlewood–Richardson semigroups, New perspectives in algebraic combinatorics (Berkeley, CA, 1996–97) (Math. Sci. Res. Inst. Publ.) Volume 38, Cambridge Univ. Press, Cambridge, 1999, pp. 337-345 | MR 1731821 | Zbl 0935.05094