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 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
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] 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] Horn inequalities and quivers (2018) (https://arxiv.org/abs/1804.00431)
[3] Local systems on for a finite set, Compositio Math., Volume 129 (2001) no. 1, pp. 67-86 | Article | MR 1856023 | Zbl 1042.14031
[4] 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] Geometric proof of a conjecture of Fulton, Adv. Math., Volume 216 (2007) no. 1, pp. 346-357 | Article | MR 2353260 | Zbl 1129.14063
[6] 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] 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] 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] 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] 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] 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] 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] 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] 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] On the Littlewood–Richardson polynomials, J. Algebra, Volume 255 (2002) no. 2, pp. 247-257 | Article | MR 1935497 | Zbl 1018.16012
[16] 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] 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] 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] 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] Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, Volume 2, Springer-Verlag, Berlin, 1993, xii+362 pages | Article | MR 1261419 | Zbl 0837.05001
[21] Eigenvalues of sums of Hermitian matrices, Pacific J. Math., Volume 12 (1962), pp. 225-241 | Article | MR 140521 | Zbl 0112.01501
[22] Toric degeneration of branching algebras, Adv. Math., Volume 220 (2009) no. 6, pp. 1809-1841 | Article | MR 2493182 | Zbl 1179.22012
[23] 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] Small Littlewood–Richardson coefficients, J. Algebraic Combin., Volume 44 (2016) no. 1, pp. 1-29 | Article | MR 3514767 | Zbl 1342.05188
[25] 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] Crystalizing the -analogue of universal enveloping algebras, Comm. Math. Phys., Volume 133 (1990) no. 2, pp. 249-260 | Article | MR 1090425 | Zbl 0724.17009
[27] 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] Generalized Young tableaux and the general linear group, J. Mathematical Phys., Volume 11 (1970), pp. 280-293 | Article | MR 251972 | Zbl 0199.34604
[29] 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] 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] 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] 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] The multiplication of Schur-functions and extensions of -modules, J. London Math. Soc., Volume 43 (1968), pp. 280-284 | Article | MR 228481 | Zbl 0188.09504
[34] 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] The honeycomb model of 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] Honeycombs and sums of Hermitian matrices, Notices Amer. Math. Soc., Volume 48 (2001) no. 2, pp. 175-186 | MR 1811121 | Zbl 1047.15006
[37] The honeycomb model of 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] 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] 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] Littlewood–Richardson coefficients and weight crystals (2010) (http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/1689-07.pdf)
[41] Singular reduction and quantization, Topology, Volume 38 (1999) no. 4, pp. 699-762 | Article | MR 1679797 | Zbl 0928.37013
[42] Explicit proofs and the flip (2010) (https://arxiv.org/abs/1009.0246)
[43] Geometric complexity theory VI: The flip via positivity (2011) (http://gct.cs.uchicago.edu/gct6.pdf)
[44] 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] 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] 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] 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] Geometric complexity theory III, on deciding positivity of Littlewood–Richardson coefficients (2005) (https://arxiv.org/abs/cs/0501076) | Zbl 1271.03055
[49] Geometric complexity theory: Introduction (2007) (https://arxiv.org/abs/0709.0746)
[50] 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] The computation of Kostka numbers and Littlewood–Richardson coefficients is #P-complete (2005) (https://arxiv.org/abs/math/0501176)
[52] 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] General representations of quivers, Proc. London Math. Soc. (3), Volume 65 (1992) no. 1, pp. 46-64 | Article | MR 1162487 | Zbl 0795.16008
[54] 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] 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] Geometric proof of a conjecture of King, Tollu, and Toumazet (2015) (https://arxiv.org/abs/1505.06551)
[57] 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] 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] 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] 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