Skeleton ideals of graphs and their associated invariants

Abstract

Parking functions are multifaceted objects with applications in many areas of mathematics. For a graph G on n+1 vertices with a designated vertex as root, Postnikov and Shapiro associated a G-parking function ideal in the standard polynomial ring over a field with variables corresponding to the non-root vertices of G. The standard monomials of this ideal, given by the G-parking functions, are in bijective correspondence with the spanning tree of G. Recently, Dochtermann introduced and investigated the k-skeleton ideals, which are certain parameter-dependent subideals of the G-parking function ideal. We have studied the homological and combinatorial properties of these k-skeleton ideals. We have calculated all the multigraded Betti numbers of k-skeleton ideals of complete graphs. We give alternative proof for calculating the number of standard monomials of the k-skeleton ideal of complete multigraphs via Steck determinant evaluation. Dochtermann conjectured the existence of a bijective correspondence between the set of the spherical parking functions of the complete graph and the set of uprooted trees on the vertex set {1,2, . . . ,n}, preserving degree and surface inversions. We have proved this conjecture. Our proof involves the use of a modified version of the depth-first-search algorithm. We also give an extension of this map for the case of general simple graphs and show that this map is always an injection but not necessarily a surjection. For many classes of graphs, we explicitly describe the image of this extension map and compute the cardinality of the associated set of spherical parking functions. Dochtermann also conjectured that for a simple graph, the number of standard monomials of the 1-skeleton ideal is bounded below by the determinant of the reduced signless Laplacian of the graph. We extended this conjecture in a general framework of positive semidefinite matrices over nonnegative integers and obtained necessary and sufficient conditions for which the equality holds.