$({\frak{S}}_{p}\times{\frak{S}}_{q})$-Invariant Graphical Parking Functions

Abstract

Graphical parking functions, or G-parking functions, are a generalization of classical parking functions that depend on a connected multigraph G with a distinguished root vertex. Gaydarov and Hopkins established a connection between G-parking functions and a vector-dependent generalization of parking functions known as u-parking functions. The central component of their result was the classification of all graphs G for which the set of G-parking functions is invariant under the action of the symmetric group ${\frak{S}}_{n}$, where n + 1 is the order of G. In this work, we present a higher dimensional analogue of Gaydarov and Hopkins’ results by characterizing the intersection between G-parking functions and 2-dimensional U-parking functions, which are pairs of integer sequences whose order statistics are bounded by certain weights along lattice paths in the plane. Our key result is a complete characterization of all G for which the set of G-parking functions is invariant under the action of ${\frak{S}}_{p}\times{\frak{S}}_{q}$, where p + q +1 is the order of G.

Keywords

G-parking functions / 2-dimensional parking functions / action of symmetric group / acyclic orientations / 05C57 / 05A05 / 05E18

References

[1] Adeniran A., Snider L., Yan C., Multivariate difference Gončarov polynomials. Integers, 2021, 21A: Paper No. A1, 21 pp.

[2] Bak P, Tang C, Wiesenfeld K. Self-organized criticality: An explanation of the 1/f noise. Phys. Rev. Lett., 1987, 59(4): 381-384.

[3] Benson B, Chakrabarty D, Tetali P. G-parking functions, acyclic orientations and spanning trees. Discrete Math., 2010, 310(8): 1340-1353.

[4] Cori R, Poulalhon D. Enumeration of (p, q)-parking functions. Discrete Math., 2002, 256(3): 609-623.

[5] Dhar D. Self-organized critical state of sandpile automaton models. Phys. Rev. Lett., 1990, 64(14): 1613-1616.

[6] Gaydarov P, Hopkins S. Parking functions and tree inversions revisited. Adv. in Appl. Math., 2016, 80: 151-179.

[7] Greene C, Zaslavsky T. On the interpretation of Whitney numbers through arrangements of hyperplanes, zonotopes, non-Radon partitions, and orientations of graphs. Trans. Amer. Math. Soc., 1983, 280(1): 97-126.

[8] Haglund J. The q, t-Catalan Numbers and the Space of Diagonal Harmonics, 2008. Providence, RI, American Mathematical Society. 41

[9] Khare N, Lorentz R, Yan C. Bivariate Gončarov polynomials and integer sequences. Sci. China Math., 2014, 57(8): 1561-1578.

[10] Konheim AG, Weiss B. An occupancy discipline and applications. SIAM J. Appl. Math., 1966, 14(6): 1266-1274.

[11] Kung JPS, Yan C. Gončarov polynomials and parking functions. J. Combin. Theory Ser. A, 2003, 102(1): 16-37.

[12] Lefèvre C, Picard P. Polynomials, random walks and risk processes: a multivariate framework. Stochastics, 2016, 88(8): 1147-1172.

[13] Lefèvre C., Picard P., Abel–Gontcharoff polynomials, parking trajectories and ruin probabilities. Depend. Model., 2023, 11(1): Paper No. 20230107, 17 pp.

[14] Lorentz R, Tringali S, Yan CH. Multivariate delta Gončarov and Abel polynomials. J. Math. Anal. Appl., 2017, 446(1): 663-680.

[15] Lorentz R, Yan C. Bivariate affine Gončarov polynomials. Discrete Math., 2016, 339(9): 2371-2383.

[16] Postnikov A, Shapiro B. Trees, parking functions, syzygies, and deformations of monomial ideals. Trans. Amer. Math. Soc., 2004, 356(8): 3109-3142.

[17] Snider L., Yan C., U-parking functions and (p, q)-parking functions. Adv. in Appl. Math., 2022, 134: Paper No. 102309, 28 pp.

[18] Snider L., Yan C., $({\frak{S}}_{p}\times{\frak{S}}_{q})$-invariant graphical parking functions. 2025, arXiv:2305. 03651

[19] Stanley RP. Hyperplane arrangements, parking functions and tree inversions. Mathematical Essays in Honor of Gian-Carlo Rota (Cambridge, MA, 1996), 1998. Boston, MA, Birkhäuser Boston: 359-375. 161

[20] Yan C. Parking functions. Handbook of Enumerative Combinatorics, 2015. Boca Raton, FL, CRC Press: 835-893

RIGHTS & PERMISSIONS

Peking University