Skeleton ideals of graphs and their associated invariants

Abstract

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