Homomesies on permutations: An analysis of maps and statistics in the FindStat database

Elder, Jennifer; Lafrenière, Nadia; McNicholas, Erin; Striker, Jessica; Welch, Amanda

doi:10.1090/mcom/3866

Homomesies on permutations: An analysis of maps and statistics in the FindStat database
HTML articles powered by AMS MathViewer

by Jennifer Elder, Nadia Lafrenière, Erin McNicholas, Jessica Striker and Amanda Welch

Math. Comp. 93 (2024), 921-976

DOI: https://doi.org/10.1090/mcom/3866

Published electronically: June 22, 2023

HTML | PDF | Request permission

Abstract:

In this paper, we perform a systematic study of permutation statistics and bijective maps on permutations in which we identify and prove 122 instances of the homomesy phenomenon. Homomesy occurs when the average value of a statistic is the same on each orbit of a given map. The maps we investigate include the Lehmer code rotation, the reverse, the complement, the Foata bijection, and the Kreweras complement. The statistics studied relate to familiar notions such as inversions, descents, and permutation patterns, and also more obscure constructs. Besides the many new homomesy results, we discuss our research method, in which we used SageMath to search the FindStat combinatorial statistics database to identify potential homomesies.

References

Drew Armstrong, The sorting order on a Coxeter group, J. Combin. Theory Ser. A 116 (2009), no. 8, 1285–1305. MR 2568800, DOI 10.1016/j.jcta.2009.03.009
Eric Babson and Einar Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000), Art. B44b, 18. MR 1758852
Sara C. Billey and Bridget E. Tenner, Fingerprint databases for theorems, Notices Amer. Math. Soc. 60 (2013), no. 8, 1034–1039. MR 3113227, DOI 10.1090/noti1029
Sourav Chatterjee and Persi Diaconis, A central limit theorem for a new statistic on permutations, Indian J. Pure Appl. Math. 48 (2017), no. 4, 561–573. MR 3741694, DOI 10.1007/s13226-017-0246-3
Robert J. Clarke, Einar Steingrímsson, and Jiang Zeng, New Euler-Mahonian statistics on permutations and words, Adv. in Appl. Math. 18 (1997), no. 3, 237–270. MR 1436481, DOI 10.1006/aama.1996.0506
David Einstein, Miriam Farber, Emily Gunawan, Michael Joseph, Matthew Macauley, James Propp, and Simon Rubinstein-Salzedo, Noncrossing partitions, toggles, and homomesies, Electron. J. Combin. 23 (2016), no. 3, Paper 3.52, 26. MR 3576300, DOI 10.37236/5648
Chaim Even-Zohar, The writhe of permutations and random framed knots, Random Structures Algorithms 51 (2017), no. 1, 121–142. MR 3668848, DOI 10.1002/rsa.20704
Dominique Foata, On the Netto inversion number of a sequence, Proc. Amer. Math. Soc. 19 (1968), 236–240. MR 223256, DOI 10.1090/S0002-9939-1968-0223256-9
Dominique Foata and Marcel-Paul Schützenberger, Major index and inversion number of permutations, Math. Nachr. 83 (1978), 143–159. MR 506852, DOI 10.1002/mana.19780830111
Thomas Gobet and Nathan Williams, Noncrossing partitions and Bruhat order, European J. Combin. 53 (2016), 8–34. MR 3434422, DOI 10.1016/j.ejc.2015.10.007
Donald E. Knuth, The art of computer programming. Volume 3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching. MR 445948
G. Kreweras, Sur les partitions non croisées d’un cycle, Discrete Math. 1 (1972), no. 4, 333–350 (French). MR 309747, DOI 10.1016/0012-365X(72)90041-6
M. La Croix and T. Roby, Foatic actions of the symmetric group and fixed-point homomesy, Preprint, arXiv:2008.03292, 2020, pp. 1–17.
A. Lascoux and M.-P. Schützenberger, A new statistics on words, Ann. Discrete Math. 6 (1980), 251–255. MR 593537, DOI 10.1016/S0167-5060(08)70709-X
P. Luschny, Permutation trees, http://oeis.org/wiki/User:Peter_Luschny/PermutationTrees.
OEIS Foundation Inc., The on-line encyclopedia of integer sequences, http://oeis.org.
James Propp and Tom Roby, Homomesy in products of two chains, Electron. J. Combin. 22 (2015), no. 3, Paper 3.4, 29. MR 3367853, DOI 10.37236/3579
Tom Roby, Dynamical algebraic combinatorics and the homomesy phenomenon, Recent trends in combinatorics, IMA Vol. Math. Appl., vol. 159, Springer, [Cham], 2016, pp. 619–652. MR 3526426, DOI 10.1007/978-3-319-24298-9_{2}5
M. Rubey, C. Stump, et al., FindStat - the combinatorial statistics database, http://www.FindStat.org, Accessed April 27, 2022.
Joshua Sack and Henning Úlfarsson, Refined inversion statistics on permutations, Electron. J. Combin. 19 (2012), no. 1, Paper 29, 27. MR 2880660, DOI 10.37236/1993
SageMath Inc., Cocalc collaborative computation online, 2022, https://cocalc.com/.
E. Sheridan-Rossi, Homomesy for Foatic actions on the symmetric group, Ph.D. Thesis, University of Connecticut, 2020, pp. 1–106.
W. A. Stein et al., Sage Mathematics software (version 9.4), The Sage Development Team, 2022, http://www.sagemath.org.
Jessica Striker, Dynamical algebraic combinatorics: promotion, rowmotion, and resonance, Notices Amer. Math. Soc. 64 (2017), no. 6, 543–549. MR 3585535, DOI 10.1090/noti1539
Jessica Striker and Nathan Williams, Promotion and rowmotion, European J. Combin. 33 (2012), no. 8, 1919–1942. MR 2950491, DOI 10.1016/j.ejc.2012.05.003
Vincent Vajnovszki, Lehmer code transforms and Mahonian statistics on permutations, Discrete Math. 313 (2013), no. 5, 581–589. MR 3009422, DOI 10.1016/j.disc.2012.11.030