Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.09720 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909735814430720 |
|---|---|
| author | Blanton, Timothy Dochtermann, Anton Hong, Isabelle Oh, SuHo Zhan, Zhan |
| author_facet | Blanton, Timothy Dochtermann, Anton Hong, Isabelle Oh, SuHo Zhan, Zhan |
| contents | For a connected graph $G$ with sink vertex $q$, a $G$-parking function is a vector of nonnegative integers whose entries are determined by cut-sets in $G$. Such objects also arise as the superstable configurations in the context of chip-firing. The set of all $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$. We extend these constructions to the setting of hypergraphs, where edges can have multiple vertices. For a hypergraph $H$ with sink $q$, we define $H$-parking functions in terms of cuts in $H$ and prove that the maximal such sequences are characterized by certain acyclic orientations of $H$. We introduce a notion of a $q$-rooted spanning tree for $H$, and prove that the set of all such objects are counted by $H$-parking functions. We also show how $H$-parking functions can be recovered as the superstable configurations in a version of chip-firing on $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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09720 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Parking functions and chip-firing on hypergraphs Blanton, Timothy Dochtermann, Anton Hong, Isabelle Oh, SuHo Zhan, Zhan Combinatorics 05A15, 05A19, 05C65 For a connected graph $G$ with sink vertex $q$, a $G$-parking function is a vector of nonnegative integers whose entries are determined by cut-sets in $G$. Such objects also arise as the superstable configurations in the context of chip-firing. The set of all $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$. We extend these constructions to the setting of hypergraphs, where edges can have multiple vertices. For a hypergraph $H$ with sink $q$, we define $H$-parking functions in terms of cuts in $H$ and prove that the maximal such sequences are characterized by certain acyclic orientations of $H$. We introduce a notion of a $q$-rooted spanning tree for $H$, and prove that the set of all such objects are counted by $H$-parking functions. We also show how $H$-parking functions can be recovered as the superstable configurations in a version of chip-firing on $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$. |
| title | Parking functions and chip-firing on hypergraphs |
| topic | Combinatorics 05A15, 05A19, 05C65 |
| url | https://arxiv.org/abs/2508.09720 |