Parking functions and chip-firing on hypergraphs
Timothy Blanton, Anton Dochtermann, Isabelle Hong, SuHo Oh, Zhan Zhan · 2025
Read Parking functions and chip-firing on hypergraphs by Timothy Blanton, Anton Dochtermann, Isabelle Hong, SuHo Oh, Zhan Zhan (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-09720.txt.
Introduction
Timothy Blanton and four co-authors extend a classic counting idea from graphs to hypergraphs in this 2025 paper. In a graph, edges join two points; in a hypergraph, an edge can join many. The idea they extend, parking functions, counts certain number patterns tied to a graph's cuts.
The authors define parking functions for hypergraphs using cuts and one sink point. They show the largest such patterns match special direction assignments with no cycles. They also define rooted spanning trees for hypergraphs and prove the patterns count those trees. A chip-firing game, where chips choose their path, has calm states that match the same patterns. Those states can also be rebuilt from a family of directed graphs linked to the hypergraph.
Catalog record
| CREATOR | Timothy Blanton, Anton Dochtermann, Isabelle Hong, SuHo Oh, Zhan Zhan |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-09720
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parking functions and chip-firing on hypergraphs Timothy Blanton, Anton Dochtermann, Isabelle Hong, SuHo Oh, Zhan Zhan Abstract . For a connected graph G G with sink vertex q q , a G G -parking function is a vector of nonnegative integers whose entries are determined by cut-sets in G G . Such objects also arise as the superstable configurations in the context of chip-firing. The set of all G G -parking functions have various algebraic and combinatorial properties; for instance they relate to evaluations of the Tutte polynomial and in particular are counted by spanning trees of G G . We extend these constructions to the setting of hypergraphs, where edges can have multiple vertices. For a hypergraph H H with sink q q , we define H H -parking functions in terms of cuts in H H and prove that the maximal such sequences are characterized by certain acyclic orientations of H H . We introduce a notion of a q q -rooted spanning tree for H H , and prove that the set of all such objects are counted by H H -parking functions. We also show how H H -parking functions can be recovered as the superstable configurations in a version of chip-firing on H H , where chips have a choice of where to go when fired. We prove that one can recover such configurations via chip-firing on a family of digraphs associated to H H . 1. Introduction Suppose G=(V,E) is a connected graph with specified sink vertex q\in V and nonsink vertices [n]=\{1,2,\dots,n\} . A G -parking function is a sequence \vec{c}\in{\mathbb{Z}}_{\geq 0}^{n} of nonnegative integers whose entries are bounded above by parameters associated to vertex cuts in G . Such objects were studied by Postnikov and Shapiro in [ 24 ] , and when G=K_{n+1} is the complete graph they recover the classical parking functions that originated in queing theory and have since been the subject of extensive study [ 28 ] . In this case, such objects have an easy description: a sequence is a parking function if and only if its nondecreasing rearrangement is coordinatewise bounded by the vector \vec{v}=(1,2,\dots,n) . This naturally leads to a more general notion of a vector parking function for other choices of \vec{v} . G -parking functions can also be understood in terms of chip-firing on the graph G , where the distribution rule is determined by the reduced Laplacian L_{G}=L_{G}^{q} . Here we consider configurations \vec{c}\in\mathbb{Z}_{\geq 0}^{n} of chips on the nonsink vertices of G . If a nonsink vertex has at least as many chips as its degree, it can fire, passing one chip to each of its neighbors. If no non-sink vertices can be fired, we say that the configuration is stable . A configuration \vec{c} is said to be superstable if no nonempty set of non-sink vertices can fire, so that subtracting from \vec{c} any nonempty collection of the columns of L_{G} results in a vector with a least one negative coordinate. For undirected graphs (and, more generally, Eulerian digraphs), the set of superstable configurations can be seen to coincide with the collection of G -parking functions. According to the definitions, to determine whether a given \vec{c}\in\mathbb{Z}_{\geq 0}^{n} is a G -parking function, one must test a condition for all nonempty subsets T\subset V\setminus q . However, Dhar’s burning algorithm [ 10 ] provides a polynomial-time way to check this condition. G -parking functions also have many pleasing combinatorial properties, and for instance the collection of all such sequences is in bijection with the set of spanning trees of G . In [ 8 ] , Chebikin and Pylyavskyy describe a family of such bijections between G -parking functions and spanning trees. They work in the more general setting of digraphs, where the relevant combinatorial objects are q -rooted spanning trees. For the case of undirected graphs, a particular specialization of their construction can be seen to recover Dhar’s algorithm. Varying the choice of sink vertex q will in general lead to a different set of G -parking functions for a given graph G . However, some parameters are invariant. As mentioned above, if G is connected then the set of G -parking functions is in bijection with the set of spanning trees of G . Furthermore, for a graph G with a specified sink q , the maximal G -parking functions are in bijection with acyclic orientations of G with a unique source q [ 6 ] . From this it follows that all maximal G -parking functions have the same degree. In [ 23 ] , Merino showed that the degree sequence of G -parking functions can be recovered as an evaluation of the Tutte polynomial of G (and hence is independent of the choice of q ). This then can be used [ 22 ] to establish a conjecture of Stanley regarding the h -vector of matroids for the special case of cographic matroids. 1.1. Our contributions In this work we seek to extend the constructions and results described above to the setting of hypergraphs , where edges can now have more than one ‘endpoint’. For this we fix a hypergraph H=(V,E) with a specified sink vertex q\in V and nonsink vertices [n]=\{1,2,\dots,n\} . We let B(H) denote its bipartite incidence graph, with vertex set {\mathcal{V}}=(E,V) and edges \{e,v\}\in{\mathcal{E}} whenever v\in e . Many of our constructions on hypergraphs will be phrased in terms of the graph B(H) . For any nonempty T\subset[n] and v\in T , we define the degree of v (with respect to T ) to be the number of hyperedges that contain v , and which are not contained in T . Note that this notion generalizes the concept of a cut set for classical graphs. As in the graph setting, we then define an H -parking function to be a sequence \vec{c}=(c_{1},c_{2},\dots,c_{n}) where for any T\subset[n] , we have some i\in T where c_{i} is strictly less than the degree of i with respect to T (see Definition 3.2 and Definition 3.3 ). In Proposition 3.4 we show how H -parking functions on a hypergraph H can be understood in terms of certain G -parking functions on the underlying incidence bipartite graph B(H) . By definition, the set of H -parking functions is an order ideal (meaning that subtracting 1 from an entry will result in another H -parking function, as long as that entry is nonnegative). To understand the maximal H -parking functions, in Definition 3.7 we define the notion of an orientation of a hypergraph H . This leads to a combinatorial characterization of maximal H -parking functions, analogous to the situation for graphs. Theorem ( Theorem 3.10 ) . There exists a bijection between the set of acyclic orientations of H with unique source q and the set of maximal H -parking functions on H . As a consequence, we see that for any hypergraph H , the degree sequence set of H -parking functions forms a pure O -sequence. We next study H -parking functions for complete hypergraphs K_{n+1}^{d} , by definition hypergraphs whose edge set consists of all d -subsets of [n+1] . It turns out that such