Dual filtered graphs
Algebraic Combinatorics, Tome 1 (2018) no. 4, pp. 441-500.

We define a K-theoretic analogue of Fomin’s dual graded graphs, which we call dual filtered graphs. The key formula in the definition is DU-UD=D+I. Our major examples are K-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 [, , ]. The Möbius construction is more mysterious but also potentially more important, as it corresponds to natural insertion algorithms.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.21
Classification : 05E99, 05E05
Mots-clés : dual graded graphs, insertion algorithms, K-theory, symmetric functions
Patrias, Rebecca 1 ; Pylyavskyy, Pavlo 2

1 Laboratoire de Combinatoire et d’Informatique Mathématique Université du Québec à Montréal 201 Président-Kennedy Montréal, Québec H2X 3Y7, Canada
2 Department of Mathematics University of Minnesota 127 Vincent Hall 206 Church Street Minneapolis, MN 5545, USA
@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 = {http://www.numdam.org/articles/10.5802/alco.21/}
}
TY  - JOUR
AU  - Patrias, Rebecca
AU  - Pylyavskyy, Pavlo
TI  - Dual filtered graphs
JO  - Algebraic Combinatorics
PY  - 2018
SP  - 441
EP  - 500
VL  - 1
IS  - 4
PB  - MathOA foundation
UR  - http://www.numdam.org/articles/10.5802/alco.21/
DO  - 10.5802/alco.21
LA  - en
ID  - ALCO_2018__1_4_441_0
ER  - 
%0 Journal Article
%A Patrias, Rebecca
%A Pylyavskyy, Pavlo
%T Dual filtered graphs
%J Algebraic Combinatorics
%D 2018
%P 441-500
%V 1
%N 4
%I MathOA foundation
%U http://www.numdam.org/articles/10.5802/alco.21/
%R 10.5802/alco.21
%G en
%F ALCO_2018__1_4_441_0
Patrias, Rebecca; Pylyavskyy, Pavlo. Dual filtered graphs. Algebraic Combinatorics, Tome 1 (2018) no. 4, pp. 441-500. doi : 10.5802/alco.21. http://www.numdam.org/articles/10.5802/alco.21/

[1] Bergeron, Nantel; Lam, Thomas; Li, Huilan Combinatorial Hopf algebras and towers of algebras–dimension, quantization and functorality, Algebr. Represent. Theory, Volume 15 (2012) no. 4, pp. 675-696 | DOI | MR | Zbl

[2] Björk, Jan-Erik Rings of differential operators, North-Holland mathematical Library, 21, North-Holland, 1979, xvii+374 pages | MR

[3] Björner, Anders 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

[4] Björner, Anders; Stanley, Richard P. An analogue of Young’s lattice for compositions (2005) (https://arxiv.org/abs/math/0508043)

[5] Buch, Anders Skovsted A Littlewood–Richardson rule for the K-theory of Grassmannians, Acta Math., Volume 189 (2002) no. 1, pp. 37-78 | DOI | MR | Zbl

[6] Buch, Anders Skovsted; Kresch, Andrew; Shimozono, Mark; Tamvakis, Harry; Yong, Alexander Stable Grothendieck polynomials and K-theoretic factor sequences, Math. Ann., Volume 340 (2008) no. 2, pp. 359-382 | DOI | MR | Zbl

[7] Buch, Anders Skovsted; Samuel, Matthew J K-theory of minuscule varieties, J. Reine Angew. Math., Volume 719 (2016), pp. 133-171 | MR | Zbl

[8] Clifford, Edward; Thomas, Hugh; Yong, Alexander K-theoretic Schubert calculus for OG(n,2n+1) and jeu de taquin for shifted increasing tableaux, J. Reine Angew. Math., Volume 690 (2014), pp. 51-63 | MR | Zbl

[9] Fomin, Sergei Vladimirovich Generalized Robinson–Schensted–Knuth correspondence, J. Sov. Math., Volume 41 (1988) no. 2, pp. 979-991 | DOI | MR | Zbl

[10] Fomin, Sergey Duality of graded graphs, J. Algebr. Comb., Volume 3 (1994) no. 4, pp. 357-404 | DOI | MR | Zbl

[11] Fomin, Sergey Schensted algorithms for dual graded graphs, J. Algebr. Comb., Volume 4 (1995) no. 1, pp. 5-45 | DOI | MR | Zbl

[12] Hamaker, Zachary; Keilthy, Adam; Patrias, Rebecca; Webster, Lillian; Zhang, Yinuo; Zhou, Shuqi Shifted Hecke insertion and the K-theory of OG(n,2n+1), J. Comb. Theory, Ser. A, Volume 151 (2017), pp. 207-240 | DOI | MR | Zbl

[13] Knuth, Donald Permutations, matrices, and generalized Young tableaux, Pac. J. Math., Volume 34 (1970) no. 3, pp. 709-727 | DOI | MR | Zbl

[14] Lam, Thomas Quantized dual graded graphs, Electron. J. Comb., Volume 17 (2010) no. 1, R88, 11 pages | MR | Zbl

[15] Lam, Thomas; Pylyavskyy, Pavlo Combinatorial Hopf algebras and K-homology of Grassmanians, Int. Math. Res. Not., Volume 2007 (2007) no. 24, rnm125, 48 pages | Zbl

[16] Lam, Thomas; Shimozono, Mark (unpublished)

[17] Lam, Thomas; Shimozono, Mark Dual graded graphs for Kac–Moody algebras, Algebra Number Theory, Volume 1 (2007) no. 4, pp. 451-488 | DOI | MR | Zbl

[18] Macdonald, Ian Grant Symmetric functions and Hall polynomials, Oxford Science Publications, Clarendon Press, 1998, x+475 pages | Zbl

[19] Nzeutchap, Janvier Dual graded graphs and Fomin’s r-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] Ore, Oystein Theory of non-commutative polynomials, Ann. Math., Volume 34 (1933), pp. 480-508 | DOI | MR | Zbl

[21] Patrias, Rebecca; Pylyavskyy, Pavlo Combinatorics of K-theory via a K-theoretic Poirier–Reutenauer bialgebra, Discrete Mathematics, Volume 339 (2016) no. 3, pp. 1095-1115 | DOI | MR | Zbl

[22] Poirier, Stéphane; Reutenauer, Christophe Algèbres de Hopf de tableaux, Ann. Sci. Math. Qué., Volume 19 (1995) no. 1, pp. 79-90 | Zbl

[23] Robinson, Gilbert de B. On the representations of the symmetric group, Am. J. Math., Volume 60 (1938), pp. 745-760 | DOI | Zbl

[24] Sagan, Bruce E. Shifted tableaux, Schur Q-functions, and a conjecture of R. Stanley, J. Comb. Theory, Ser. A, Volume 45 (1987) no. 1, pp. 62-103 | DOI | MR | Zbl

[25] Schensted, Craige Longest increasing and decreasing subsequences, Classic Papers in Combinatorics (Modern Birkhäuser Classics), Birkhäuser, 2009, pp. 299-311 | DOI | Zbl

[26] Stanley, Richard P. Differential posets, J. Am. Math. Soc., Volume 1 (1988) no. 4, pp. 919-961 | DOI | MR | Zbl

[27] Stanley, Richard P. Enumerative Combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, 62, Cambridge University Press, 1999, xii+581 pages | MR | Zbl

[28] Stanley, Richard P. Enumerative Combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, 49, Cambridge University Press, 2012, xiii+626 pages | Zbl

[29] Thomas, Hugh; Yong, Alexander 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 | DOI | MR | Zbl

[30] Thomas, Hugh; Yong, Alexander 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 | Zbl

[31] Thomas, Hugh; Yong, Alexander Longest increasing subsequences, Plancherel-type measure and the Hecke insertion algorithm, Adv. Appl. Math., Volume 46 (2011) no. 1-4, pp. 610-642 | DOI | MR | Zbl

[32] Worley, Dale Raymond A theory of shifted Young tableaux, Ph. D. Thesis, Massachusetts Institute of Technology (USA) (1984) | MR

[33] Young, Alfred Qualitative substitutional analysis (third paper), Proc. Lond. Math. Soc., Volume 28 (1927), pp. 255-292 | MR | Zbl

  • Huang, Daoji; Shimozono, Mark; Yu, Tianyi A row analogue of Hecke column insertion, Combinatorial Theory, Volume 4 (2024) no. 2, p. 23 (Id/No 11) | DOI:10.5070/c64264239 | Zbl:1547.05304
  • Hamaker, Zachary; Morales, Alejandro H.; Pak, Igor; Serrano, Luis; Williams, Nathan Bijecting hidden symmetries for skew staircase shapes, Algebraic Combinatorics, Volume 6 (2023) no. 4, pp. 1095-1118 | DOI:10.5802/alco.285 | Zbl:1529.05161
  • Marberg, Eric; Tong, Kam Hung Highest weight crystals for Schur Q-functions, Combinatorial Theory, Volume 3 (2023) no. 2, p. 59 (Id/No 6) | DOI:10.5070/c63261984 | Zbl:1527.05173
  • Marberg, Eric Shifted insertion algorithms for primed words, Combinatorial Theory, Volume 3 (2023) no. 3, p. 80 (Id/No 14) | DOI:10.5070/c63362797 | Zbl:1534.05004
  • Mansour, Toufik; Schork, Matthias On ore-Stirling numbers defined by normal ordering in the Ore algebra, Filomat, Volume 37 (2023) no. 18, p. 6115 | DOI:10.2298/fil2318115m
  • Hiroshima, Toya Queer supercrystal structure for increasing factorizations of fixed-point-free involution words, Journal of Algebraic Combinatorics, Volume 58 (2023) no. 1, pp. 37-67 | DOI:10.1007/s10801-023-01240-8 | Zbl:1518.05201
  • Schork, Matthias File placements, fractional matchings, and normal ordering, Annals of Combinatorics, Volume 26 (2022) no. 4, pp. 857-871 | DOI:10.1007/s00026-022-00599-y | Zbl:1503.05007
  • Marberg, Eric Bumping operators and insertion algorithms for queer supercrystals, Selecta Mathematica. New Series, Volume 28 (2022) no. 2, p. 62 (Id/No 36) | DOI:10.1007/s00029-021-00752-0 | Zbl:1487.05274
  • Marberg, Eric; Tong, Kam Hung Highest weight crystals for Schur Q-functions, Séminaire Lotharingien de Combinatoire, Volume 86B (2022), p. 12 (Id/No 69) | Zbl:1515.05200
  • Yeliussizov, Damir Enumeration of plane partitions by descents, Journal of Combinatorial Theory. Series A, Volume 178 (2021), p. 19 (Id/No 105367) | DOI:10.1016/j.jcta.2020.105367 | Zbl:1457.05114
  • Yeliussizov, Damir Positive specializations of symmetric Grothendieck polynomials, Advances in Mathematics, Volume 363 (2020), p. 35 (Id/No 107000) | DOI:10.1016/j.aim.2020.107000 | Zbl:1432.05119
  • Marberg, Eric A symplectic refinement of shifted Hecke insertion, Journal of Combinatorial Theory. Series A, Volume 173 (2020), p. 50 (Id/No 105216) | DOI:10.1016/j.jcta.2020.105216 | Zbl:1435.05236
  • Guo, Ting; Poznanović, Svetlana Hecke insertion and maximal increasing and decreasing sequences in fillings of stack polyominoes, Journal of Combinatorial Theory. Series A, Volume 176 (2020), p. 24 (Id/No 105304) | DOI:10.1016/j.jcta.2020.105304 | Zbl:1447.05223
  • van Willigenburg, S. Dual graphs from noncommutative and quasisymmetric Schur functions, Proceedings of the American Mathematical Society, Volume 148 (2020) no. 3, pp. 1063-1078 | DOI:10.1090/proc/14786 | Zbl:1431.05149
  • Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Involution pipe dreams, Séminaire Lotharingien de Combinatoire, Volume 82B (2019), p. 12 (Id/No 63) | Zbl:1435.05235
  • van Willigenburg, Stephanie Dual graphs from noncommutative and quasisymmetric Schur functions, arXiv (2019) | DOI:10.48550/arxiv.1907.13094 | arXiv:1907.13094
  • Yeliussizov, Damir Symmetric Grothendieck polynomials, skew Cauchy identities, and dual filtered Young graphs, arXiv (2017) | DOI:10.48550/arxiv.1711.09544 | arXiv:1711.09544
  • Hamaker, Zachary; Marberg, Eric; Pawlowski, Brendan Schur P-positivity and involution Stanley symmetric functions, arXiv (2017) | DOI:10.48550/arxiv.1701.02824 | arXiv:1701.02824
  • Pechenik, Oliver; Yong, Alexander Genomic Tableaux, arXiv (2016) | DOI:10.48550/arxiv.1603.08490 | arXiv:1603.08490
  • Hamaker, Zachary; Keilthy, Adam; Patrias, Rebecca; Webster, Lillian; Zhang, Yinuo; Zhou, Shuqi Shifted Hecke insertion and the K-theory of OG(n,2n+1), arXiv (2015) | DOI:10.48550/arxiv.1510.08972 | arXiv:1510.08972

Cité par 20 documents. Sources : Crossref, NASA ADS, zbMATH