Increasing and decreasing sequences in fillings of moon polyominoes. (English) Zbl 1225.05029
Summary: We present an adaptation of jeu de taquin and promotion for arbitrary fillings of moon polyominoes. Using this construction we show various symmetry properties of such fillings taking into account the lengths of longest increasing and decreasing chains. In particular, we prove a conjecture of Jakob Jonsson. We also relate our construction to the one recently employed by Christian Krattenthaler, thus generalising his results.
Keywords:
jeu de taquin; promotion; evacuation; plactic monoid; growth diagrams; moon polyominoes; L-convex polyominoes; crossings and nestingsReferences:
| [1] | Backelin, J.; West, J.; Xin, G., Wilf-equivalence for singleton classes, Adv. in Appl. Math., 38, 133-148 (2007) · Zbl 1127.05002 |
| [2] | Castiglione, G.; Restivo, A., Reconstruction of \(L\)-convex polyominoes, (9th International Workshop on Combinatorial Image Analysis. 9th International Workshop on Combinatorial Image Analysis, Electron. Notes Discrete Math., vol. 12 (2003), Elsevier: Elsevier Amsterdam), 12 pp. (electronic) · Zbl 1173.68761 |
| [3] | Chen, W. Y.C.; Deng, E. Y.P.; Du, R. R.X.; Stanley, R. P.; Yan, C. H., Crossings and nestings of matchings and partitions, Trans. Amer. Math. Soc., 359, 1555-1575 (2007), (electronic) · Zbl 1108.05012 |
| [4] | Chen, W. Y.C.; Poznanović, S.; Yan, C. H.; Yang, A. L.B., Major index for 01-fillings of moon polyominoes (2009), preprint · Zbl 1231.05069 |
| [5] | de Mier, A., \(k\)-noncrossing and \(k\)-nonnesting graphs and fillings of Ferrers diagrams, Combinatorica, 27, 699-720 (2007) · Zbl 1164.05002 |
| [6] | de Sainte-Catherine, M.; Viennot, G., Enumeration of certain Young tableaux with bounded height, (Combinatoire énumérative. Combinatoire énumérative, Montreal, Que., 1985/Quebec, Que., 1985. Combinatoire énumérative. Combinatoire énumérative, Montreal, Que., 1985/Quebec, Que., 1985, Lecture Notes in Math., vol. 1234 (1986), Springer: Springer Berlin), 58-67 · Zbl 0615.05009 |
| [7] | Elizalde, S., A bijection between 2-triangulations and pairs of non-crossing Dyck paths, J. Combin. Theory Ser. A, 114, 1481-1503 (2007) · Zbl 1125.05006 |
| [8] | Fomin, S. V., The generalized Robinson-Schensted-Knuth correspondence, Zap. Nauchn. Sem. Leningrad. Otdel. Mat. Inst. Steklov. (LOMI), 155, 156-175 (1986), Differentsialnaya Geometriya, Gruppy Li i Mekh. VIII, 195 · Zbl 0661.05004 |
| [9] | Fomin, S. V., Duality of graded graphs, J. Algebraic Combin., 3, 357-404 (1994) · Zbl 0810.05005 |
| [10] | Fomin, S. V., Schensted algorithms for dual graded graphs, J. Algebraic Combin., 4, 5-45 (1995) · Zbl 0817.05077 |
| [11] | Greene, C., An extension of Schenstedʼs theorem, Adv. Math., 14, 254-265 (1974) · Zbl 0303.05006 |
| [12] | Jonsson, J., Generalized triangulations and diagonal-free subsets of stack polyominoes, J. Combin. Theory Ser. A, 112, 117-142 (2005) · Zbl 1084.05017 |
| [13] | Jonsson, J.; Welker, V., A spherical initial ideal for Pfaffians, Illinois J. Math., 51, 1397-1407 (2007) · Zbl 1148.13012 |
| [14] | Kasraoui, A., Ascents and descents in 01-fillings of moon polyominoes, European J. Combin., 31, 87-105 (2010) · Zbl 1193.05056 |
| [15] | Krattenthaler, C., Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes, Adv. in Appl. Math., 37, 404-431 (2006) · Zbl 1108.05095 |
| [16] | C.M. Nicolás, Another bijection between 2-triangulations and pairs of non-crossing Dyck paths, in: Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics, Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, pp. 699-710.; C.M. Nicolás, Another bijection between 2-triangulations and pairs of non-crossing Dyck paths, in: Proceedings of the 21st International Conference on Formal Power Series and Algebraic Combinatorics, Discrete Mathematics and Theoretical Computer Science, DMTCS, 2009, pp. 699-710. |
| [17] | Reifegerste, A., Permutation sign under the Robinson-Schensted correspondence, Ann. Comb., 8, 103-112 (2004) · Zbl 1053.05123 |
| [18] | T. Roby, Applications and extensions of Fominʼs generalization of the Robinson-Schensted correspondence to differential posets, Ph.D. thesis, M.I.T., Cambridge, Massachusetts, 1991.; T. Roby, Applications and extensions of Fominʼs generalization of the Robinson-Schensted correspondence to differential posets, Ph.D. thesis, M.I.T., Cambridge, Massachusetts, 1991. |
| [19] | Roby, T.; Sottile, F.; Stroomer, J.; West, J., Complementary algorithms for tableaux, J. Combin. Theory Ser. A, 96, 127-161 (2001) · Zbl 1014.05067 |
| [20] | Sagan, B. E., The Symmetric Group (1987), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Pacific Grove, California |
| [21] | Stanley, R. P., Enumerative Combinatorics, vol. 2, Cambridge Stud. Adv. Math., vol. 62 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
