We define a -theoretic analogue of Fomin’s dual graded graphs, which we call dual filtered graphs. The key formula in the definition is . Our major examples are -theoretic analogues of Young’s lattice, of shifted Young’s lattice, and of the Young–Fibonacci lattice. We suggest notions of tableaux, insertion algorithms, and growth rules whenever such objects are not already present in the literature. (See the table below.) We also provide a large number of other examples. Most of our examples arise via two constructions, which we call the Pieri construction and the Möbius construction. The Pieri construction is closely related to the construction of dual graded graphs from a graded Hopf algebra, as described in [1, 19, 16]. The Möbius construction is more mysterious but also potentially more important, as it corresponds to natural insertion algorithms.
Revised: 2018-05-04
Accepted: 2018-05-09
Published online: 2018-09-10
DOI: https://doi.org/10.5802/alco.21
Classification: 05E99, 05E05
Keywords: dual graded graphs, insertion algorithms, -theory, symmetric functions
@article{ALCO_2018__1_4_441_0, author = {Patrias, Rebecca and Pylyavskyy, Pavlo}, title = {Dual filtered graphs}, journal = {Algebraic Combinatorics}, pages = {441--500}, publisher = {MathOA foundation}, volume = {1}, number = {4}, year = {2018}, doi = {10.5802/alco.21}, mrnumber = {3875073}, zbl = {1397.05202}, language = {en}, url = {https://alco.centre-mersenne.org/item/ALCO_2018__1_4_441_0/} }
Patrias, Rebecca; Pylyavskyy, Pavlo. Dual filtered graphs. Algebraic Combinatorics, Volume 1 (2018) no. 4, pp. 441-500. doi : 10.5802/alco.21. https://alco.centre-mersenne.org/item/ALCO_2018__1_4_441_0/
[1] Combinatorial Hopf algebras and towers of algebras–dimension, quantization and functorality, Algebr. Represent. Theory, Volume 15 (2012) no. 4, pp. 675-696 | Article | MR 2944437 | Zbl 1281.16036
[2] Rings of differential operators, North-Holland mathematical Library, Volume 21, North-Holland, 1979, xvii+374 pages | MR 549189
[3] The Möbius function of subword order, Invariant theory and tableaux (Minneapolis, USA, 1988) (The IMA Volumes in Mathematics and its Applications) Volume 19, Springer, 1990, pp. 118-124 | Zbl 0706.06007
[4] An analogue of Young’s lattice for compositions (2005) (https://arxiv.org/abs/math/0508043 )
[5] A Littlewood–Richardson rule for the K-theory of Grassmannians, Acta Math., Volume 189 (2002) no. 1, pp. 37-78 | Article | MR 1946917 | Zbl 1090.14015
[6] Stable Grothendieck polynomials and K-theoretic factor sequences, Math. Ann., Volume 340 (2008) no. 2, pp. 359-382 | Article | MR 2368984 | Zbl 1157.14036
[7] K-theory of minuscule varieties, J. Reine Angew. Math., Volume 719 (2016), pp. 133-171 | MR 3552494 | Zbl 06636676
[8] K-theoretic Schubert calculus for OG and jeu de taquin for shifted increasing tableaux, J. Reine Angew. Math., Volume 690 (2014), pp. 51-63 | MR 3200334 | Zbl 1348.14127
[9] Generalized Robinson–Schensted–Knuth correspondence, J. Sov. Math., Volume 41 (1988) no. 2, pp. 979-991 | Article | MR 869582 | Zbl 0698.05003
[10] Duality of graded graphs, J. Algebr. Comb., Volume 3 (1994) no. 4, pp. 357-404 | Article | MR 1293822 | Zbl 0810.05005
[11] Schensted algorithms for dual graded graphs, J. Algebr. Comb., Volume 4 (1995) no. 1, pp. 5-45 | Article | MR 1314558 | Zbl 0817.05077
[12] Shifted Hecke insertion and the K-theory of OG, J. Comb. Theory, Ser. A, Volume 151 (2017), pp. 207-240 | Article | MR 3663495 | Zbl 1366.05118
[13] Permutations, matrices, and generalized Young tableaux, Pac. J. Math., Volume 34 (1970) no. 3, pp. 709-727 | Article | MR 272654 | Zbl 0199.31901
[14] Quantized dual graded graphs, Electron. J. Comb., Volume 17 (2010) no. 1, 11 pages | MR 2661391 | Zbl 1230.05163
[15] Combinatorial Hopf algebras and -homology of Grassmanians, Int. Math. Res. Not., Volume 2007 (2007) no. 24, 48 pages | Zbl 1134.16017
[16]
(unpublished)[17] Dual graded graphs for Kac–Moody algebras, Algebra Number Theory, Volume 1 (2007) no. 4, pp. 451-488 | Article | MR 2368957 | Zbl 1200.05249
[18] Symmetric functions and Hall polynomials, Oxford Science Publications, Clarendon Press, 1998, x+475 pages | Zbl 0899.05068
[19] Dual graded graphs and Fomin’s -correspondences associated to the Hopf algebras of planar binary trees, quasi-symmetric functions and noncommutative symmetric functions (2006) (in Formal Power Series and Algebraic Combinatorics (San Diego, 2006), available at http://garsia.math.yorku.ca/fpsac06/papers/53.pdf)
[20] Theory of non-commutative polynomials, Ann. Math., Volume 34 (1933), pp. 480-508 | Article | MR 1503119 | Zbl 0007.15101
[21] Combinatorics of K-theory via a K-theoretic Poirier–Reutenauer bialgebra, Discrete Mathematics, Volume 339 (2016) no. 3, pp. 1095-1115 | Article | MR 3433916 | Zbl 1328.05193
[22] Algèbres de Hopf de tableaux, Ann. Sci. Math. Qué., Volume 19 (1995) no. 1, pp. 79-90 | Zbl 0835.16035
[23] On the representations of the symmetric group, Am. J. Math., Volume 60 (1938), pp. 745-760 | Article | Zbl 0019.25102
[24] Shifted tableaux, Schur -functions, and a conjecture of R. Stanley, J. Comb. Theory, Ser. A, Volume 45 (1987) no. 1, pp. 62-103 | Article | MR 883894 | Zbl 0661.05010
[25] Longest increasing and decreasing subsequences, Classic Papers in Combinatorics (Modern Birkhäuser Classics), Birkhäuser, 2009, pp. 299-311 | Article
[26] Differential posets, J. Am. Math. Soc., Volume 1 (1988) no. 4, pp. 919-961 | Article | MR 941434 | Zbl 0658.05006
[27] Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, Volume 62, Cambridge University Press, 1999, xii+581 pages | MR 1676282 | Zbl 0928.05001
[28] Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, Volume 49, Cambridge University Press, 2012, xiii+626 pages | Zbl 1247.05003
[29] A jeu de taquin theory for increasing tableaux, with applications to K-theoretic Schubert calculus, Algebra Number Theory, Volume 3 (2009) no. 2, pp. 121-148 | Article | MR 2491941 | Zbl 1229.05285
[30] The direct sum map on Grassmannians and jeu de taquin for increasing tableaux, Int. Math. Res. Not., Volume 2011 (2011) no. 12, pp. 2766-2793 | MR 2806593 | Zbl 1231.05280
[31] Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Adv. Appl. Math., Volume 46 (2011) no. 1-4, pp. 610-642 | Article | MR 2794040 | Zbl 1227.05262
[32] A theory of shifted Young tableaux (1984) (Ph. D. Thesis) | MR 2941073
[33] Qualitative substitutional analysis (third paper), Proc. Lond. Math. Soc., Volume 28 (1927), pp. 255-292 | MR 1575854 | Zbl 54.0150.01