Enumeration of certain subsets of uprooted trees and spherical parking functions
Pith reviewed 2026-06-27 12:27 UTC · model grok-4.3
The pith
For graphs G_ℓ formed by deleting ℓ edges from the complete graph K_{n+1}, the number of uprooted trees on [n] with vertex 1 nonadjacent to F_ℓ equals (n-1)^{n-ℓ-2}(n-2)^ℓ(n-ℓ-1), and the number of spherical G_ℓ-parking functions equals (n-
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The uprooted spanning trees of G_ℓ minus vertex 0 stand in bijection with the set U_n^{1 not sim F_ℓ} of labeled uprooted trees on [n] in which vertex 1 shares no edge with any vertex of F_ℓ, and the cardinality of this set is (n-1)^{n-ℓ-2}(n-2)^ℓ(n-ℓ-1). As a direct consequence, the spherical G_ℓ-parking functions, which arise exactly as the distinguished standard monomials of the skeleton ideals of the G-parking-function ideal, are counted by (n-1)^{n-3}(n-ℓ-1)^2.
What carries the argument
The explicit bijection between the uprooted spanning trees of the punctured graph G_ℓ minus vertex 0 and the restricted set U_n^{1 not sim F_ℓ}, together with the identification of spherical parking functions as the distinguished standard monomials extracted from the skeleton ideals of the G-parking-function ideal.
If this is right
- The matrix-tree theorem applied to the Laplacian of G_ℓ recovers the same product formula, yielding combinatorial identities as corollaries.
- When ℓ=0 the formula reduces to the known count of all uprooted trees on n vertices.
- The spherical-parking-function count is independent of the precise choice of which ℓ edges are deleted, depending only on the size ℓ.
- The same skeleton-ideal construction produces spherical parking functions whose enumeration is given by a simple closed product for every member of the family G_ℓ.
Where Pith is reading between the lines
- The same deletion construction and matrix-tree counting technique could be applied to graphs obtained by removing edges incident to more than one vertex.
- The product formulas may admit natural q-analogues or generating-function lifts that encode additional statistics on the trees or parking functions.
- Because the counts are explicit polynomials in n and ℓ, they supply exact asymptotics for large n with ℓ fixed or growing slowly with n.
Load-bearing premise
The uprooted spanning trees of G_ℓ minus vertex 0 are in exact bijection with the restricted uprooted trees on [n] avoiding edges from vertex 1 to F_ℓ, and spherical parking functions arise exactly as the distinguished subset of standard monomials from the skeleton ideals.
What would settle it
Direct enumeration of the restricted uprooted trees for n=4 and ℓ=1 should yield exactly (4-1)^{4-1-2}(4-2)^1(4-1-1)=3^1 * 2 * 2=12; any mismatch with the hand count of such trees on four labeled vertices would falsify the claimed formula.
Figures
read the original abstract
Spherical $G$-parking functions are a distinguished subset of standard monomials, arising from the skeleton ideals of the $G$-parking function ideal. Explicit enumeration formulas for spherical $G$-parking functions are known only for a few classes of graphs. In this paper, we consider a family of graphs $G_{\ell}$ ($1\leq \ell \leq n-2$), obtained from the complete graph $K_{n+1}$ by deleting the $\ell$ edges joining vertex $1$ to the vertices in $F_{\ell}= \{n-\ell+1, \ldots, n\}$. The uprooted spanning trees of $G_{\ell}-\{0\}$ correspond to the set $\mathcal{U}_n^{1\not\sim F_{\ell}}$ of uprooted trees with vertex set $[n]$ in which vertex $1$ is not adjacent to any vertex in $F_{\ell}$, and we establish that $|\mathcal{U}_n^{1\not\sim F_{\ell}}| = (n-1)^{n-\ell-2}(n-2)^{\ell}(n-\ell-1)$. We derive this formula combinatorially and independently recover it as an application of the matrix tree theorem, obtaining some combinatorial identities as consequences. Finally, we determine the number of spherical $G_{\ell}$-parking functions as $|\mathrm{sPF}(G_{\ell})| = (n-1)^{n-3}(n-\ell-1)^2$.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper claims to enumerate the set Τ_n^{1≁F_ℓ} of uprooted trees on [n] in which vertex 1 is not adjacent to any vertex in F_ℓ, establishing the closed form (n-1)^{n-ℓ-2}(n-2)^ℓ(n-ℓ-1) via a direct combinatorial argument; it independently recovers the same count by applying the matrix-tree theorem to the Laplacian of G_ℓ−{0}. It then determines the number of spherical G_ℓ-parking functions as (n-1)^{n-3}(n-ℓ-1)^2.
Significance. If the formulas held, the work would supply explicit enumerations for spherical parking functions on the family of graphs obtained from K_{n+1} by deleting ℓ edges incident to a fixed vertex, together with combinatorial identities arising from the matrix-tree application. The dual combinatorial and algebraic derivations would be a methodological strength.
major comments (1)
- [Abstract] Abstract: the claimed formula |U_n^{1≁F_ℓ}| = (n-1)^{n-ℓ-2}(n-2)^ℓ(n-ℓ-1) is inconsistent with known counts. When ℓ=0 the expression reduces to (n-1)^{n-1}, whereas G_0−{0} is K_n and the number of its spanning trees is n^{n-2} by Cayley's formula. For the concrete case n=4, ℓ=1 the formula yields 12, but K_4 minus one edge has exactly 8 spanning trees (equivalently 2n^{n-3}=8). Because the paper asserts both a combinatorial derivation and an independent matrix-tree recovery of this same expression, the mismatch shows that either the bijection with spanning trees of G_ℓ−{0} or the closed-form derivation itself is incorrect; this error is load-bearing for both the tree enumeration and the subsequent spherical-parking-function count.
Simulated Author's Rebuttal
We thank the referee for their detailed review and for identifying the inconsistency between the claimed formula and standard results such as Cayley's formula. We agree that the stated enumeration is incorrect and that this affects the core claims of the paper. We will revise the manuscript to correct the formula and the subsequent parking-function count.
read point-by-point responses
-
Referee: [Abstract] Abstract: the claimed formula |U_n^{1≁F_ℓ}| = (n-1)^{n-ℓ-2}(n-2)^ℓ(n-ℓ-1) is inconsistent with known counts. When ℓ=0 the expression reduces to (n-1)^{n-1}, whereas G_0−{0} is K_n and the number of its spanning trees is n^{n-2} by Cayley's formula. For the concrete case n=4, ℓ=1 the formula yields 12, but K_4 minus one edge has exactly 8 spanning trees (equivalently 2n^{n-3}=8). Because the paper asserts both a combinatorial derivation and an independent matrix-tree recovery of this same expression, the mismatch shows that either the bijection with spanning trees of G_ℓ−{0} or the closed-form derivation itself is incorrect; this error is load-bearing for both the tree enumeration and the subsequent spherical-parking-function count.
Authors: We concur with the referee's observation. The formula does not reduce to n^{n-2} when ℓ=0, nor does it match the known count of 8 spanning trees for the n=4, ℓ=1 case. This demonstrates that at least one of the two derivations (combinatorial or matrix-tree) contains an error. We will revise the manuscript by deriving the correct closed form for |U_n^{1≁F_ℓ}| (and the induced count for |sPF(G_ℓ)|) via a verified application of the matrix-tree theorem to the Laplacian of the appropriate graph, together with any necessary corrections to the combinatorial argument. revision: yes
Circularity Check
No significant circularity; derivation relies on external matrix-tree theorem and claimed combinatorial bijection.
full rationale
The paper claims a bijection between uprooted spanning trees of G_ℓ−{0} and U_n^{1≁F_ℓ}, then states the enumeration formula is derived combinatorially and independently recovered via the matrix tree theorem on the Laplacian of the graph (an external, non-self-referential result). The spherical parking-function count is obtained from this tree enumeration using the algebraic definition of spherical G-parking functions as a subset of standard monomials. No step reduces a claimed prediction to a fitted input, self-citation, or definitional equivalence within the paper; the central claims rest on independent external tools and the stated bijection rather than internal redefinition.
Axiom & Free-Parameter Ledger
axioms (1)
- standard math Matrix tree theorem counts the spanning trees of a graph via any cofactor of its Laplacian matrix.
Reference graph
Works this paper leans on
-
[1]
Aigner,A course in enumeration, Graduate Texts in Mathematics, vol
M. Aigner,A course in enumeration, Graduate Texts in Mathematics, vol. 238, Springer, 2007
2007
-
[2]
Backman, C
S. Backman, C. Charbonneau, N. A. Loehr, P. Mullins, M. O’Connor, and G. S. Warrington,Skeletal gener- alizations of chip-firing games, parking functions, and Dyck paths, Combin. Theory5(2025), no. 4, #6
2025
-
[3]
R. B. Bapat,Graphs and matrices, Universitext, Springer-Verlag, London, 2010
2010
-
[4]
Chauve, S
C. Chauve, S. Dulucq, and O. Guibert,Enumeration of some labelled trees, In: D. Krob, A. A. Mikhalev, and A. V. Mikhalev (eds.), Formal Power Series and Algebraic Combinatorics, Springer, Berlin, 2000, pp. 146– 157
2000
-
[5]
Chebikin and P
D. Chebikin and P. Pylyavskyy,A family of bijections betweenG-parking functions and spanning trees, J. Combin. Theory Ser. A110(2005), no. 1, 31–41
2005
-
[6]
N. S. Deepthi and C. Kumar,Combinatorial identities using the matrix tree theorem, Ars Comb.165(2025), 45–61
2025
-
[7]
Dhar,Self-organized critical state of sandpile automaton models, Phys
D. Dhar,Self-organized critical state of sandpile automaton models, Phys. Rev. Lett.64(1990), no. 14, 1613– 1616
1990
-
[8]
A. Dochtermann,One-skeleta ofG-parking function ideals: resolutions and standard monomials, arXiv:1708.04712 (2017)
Pith/arXiv arXiv 2017
-
[9]
Dochtermann and W
A. Dochtermann and W. King,Trees, parking functions, and standard monomials of skeleton ideals, Australas. J. Combin.81(2021), no. 1, 126–151
2021
-
[10]
Gaydarov and S
P. Gaydarov and S. Hopkins,Parking functions and tree inversions revisited, Adv. Appl. Math.80(2016), 151–179
2016
-
[11]
Guedes de Oliveira and M
A. Guedes de Oliveira and M. Las Vergnas,Parking functions and labeled trees, S´ em. Lothar. Combin.65 (2011), B65e
2011
-
[12]
Kirchhoff,Ueber die aufl¨ osung der gleichungen, auf welche man bei der untersuchung der linearen ver- theilung galvanischer str¨ ome gef¨ uhrt wird, Ann
G. Kirchhoff,Ueber die aufl¨ osung der gleichungen, auf welche man bei der untersuchung der linearen ver- theilung galvanischer str¨ ome gef¨ uhrt wird, Ann. Phys.148(1847), 497–508. (English transl. IRE Trans. Circuit Theory CT-5 (1958), 4-7.)
1958
-
[13]
A. G. Konheim and B. Weiss,An occupancy discipline and applications, SIAM J. Appl. Math.14(1966), no. 6, 1266–1274
1966
-
[14]
Kreweras,Une famille de polynˆ omes ayant plusieurs propri´ et´ es ´ enumeratives, Period
G. Kreweras,Une famille de polynˆ omes ayant plusieurs propri´ et´ es ´ enumeratives, Period. Math. Hung.11 (1980), 309–320
1980
-
[15]
Kumar, G
C. Kumar, G. Lather, and A. Roy,Standard monomials of 1-skeleton ideals of graphs and generalized signless Laplacians, Linear Algebra Appl.637(2022), 24–48. ENUMERATION OF UPROOTED TREES AND SPHERICAL PARKING FUNCTIONS 43
2022
-
[16]
Kumar, G
C. Kumar, G. Lather, and Sonica,Skeleton ideals of certain graphs, standard monomials and spherical parking functions, Electron. J. Comb.28(2021), no. 1, #P1.53
2021
-
[17]
J. W. Moon,Counting labelled trees, Canadian Mathematical Monographs, vol. 1, Canadian Mathematical Congress, Montreal, 1970
1970
-
[18]
Perkinson, Q
D. Perkinson, Q. Yang, and K. Yu,G-parking functions and tree inversions, Combinatorica37(2017), no. 2, 269–282
2017
-
[19]
Postnikov and B
A. Postnikov and B. Shapiro,Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc.356(2004), no. 8, 3109–3142
2004
-
[20]
Riordan,Ballots and trees, J
J. Riordan,Ballots and trees, J. Combin. Theory6(1969), no. 4, 408–411
1969
-
[21]
R. P. Stanley,Hyperplane arrangements, interval orders, and trees, Proc. Natl. Acad. Sci. U.S.A.93(1996), no. 6, 2620–2625. Department of Mathematical Sciences, IISER Mohali, Knowledge City, Sector 81, SAS Nagar, Punjab, 140-306, India Email address:nayanashibu@iisermohali.ac.in Department of Mathematical Sciences, IISER Mohali, Knowledge City, Sector 81,...
1996
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.