Trees, parking functions, and standard monomials of skeleton ideals

Abstract

Parking functions are a widely studied class of combinatorial objects, with connections to several branches of mathematics. On the algebraic side, parking functions can be identified with the standard monomials of $M_n$, a certain monomial ideal in the polynomial ring $S=\mathbb{K}[x_1,\dots ,x_n]$ where a set of generators are indexed by the nonempty subsets of $[n]=\{1,2,\dots ,n\}$. Motivated by constructions from the theory of chip-firing on graphs we study generalizations of parking functions determined by $M_n^{(k)}$, a subideal of $M_n$ obtained by allowing only generators corresponding to subsets of $[n]$ of size at most $k$. For each $k$ the set of standard monomials of $M_n^{(k)}$, denoted ${\text{stan}}_n^k$, contains the usual parking functions and has interesting combinatorial properties in its own right. For general $k$ we show that elements of ${\text{stan}}_n^k$ can be recovered as certain vector-parking functions, which in turn leads to a formula for their count via results of Yan. The symmetric group $S_n$ naturally acts on the set ${\text{stan}}_n^k$ and we also obtain a formula for the number of orbits under this action. For the case of $k=n-2$ we study combinatorial interpretations of ${\text{stan}}_n^{n-2}$ and relate them to properties of uprooted trees in terms of root degree and surface inversions. As a corollary we obtain a combinatorial identity for $n^n$ involving Catalan numbers, reminiscent of a result of Benjamin and Juhnke. For the case of $k=1$ we observe that the number of elements ${\text{stan}}_n^1$ is given by the determinant of the reduced `signless' Laplacian, which provides a weighted count for $|{\text{stan}}_n^1|$ in terms generalized spanning trees known as `spanning TU-subgraphs'. Our constructions naturally generalize to arbitrary graphs and lead to a number of open questions.

19 pages, 3 figures; results originally appeared as part of arXiv:1708.04712, here expanded with focus on combinatorial aspects; v2: Major revision with new title and additional author, Conjecture 3.1 is now Theorem 3.10, many other new results; v3: corrections and minor revisions, incorporating comments from referees; v4: fixed typos, corrected metadata

References in corpus (1)

• A Bijection Between the Recurrent Configurations of a Hereditary Chip-Firing Model and Spanning Trees