Prime graphical parking functions and strongly recurrent configurations of the Abelian sandpile model

Thomas Selig, Haoyue Zhu · 2025

Read Prime graphical parking functions and strongly recurrent configurations of the Abelian sandpile model by Thomas Selig, Haoyue Zhu (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-2506-23237.txt.

Introduction

Thomas Selig and Haoyue Zhu linked two classic chip-firing puzzles in a 2025 combinatorics paper. Parking functions describe cars that all find spots on a one-way street, and the sandpile model describes grains that topple when a pile grows too tall. On a general graph the two ideas mirror each other exactly, a fact known for two decades.

Selig and Zhu define prime parking functions, the ones that cannot be split into smaller blocks. On the sandpile side those match a new class they call strongly recurrent piles. They work out the match on wheels, complete graphs, and several other families. The link gives both puzzles a shared building-block view.

Catalog record

CREATORThomas Selig, Haoyue Zhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE85 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-23237

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Prime graphical parking functions and strongly recurrent configurations of the Abelian sandpile model Thomas Selig, Haoyue Zhu Abstract . This work investigates the duality between two discrete dynamical processes: parking functions, and the Abelian sandpile model (ASM). Specifically, we are interested in the extension of classical parking functions, called G G -parking functions, introduced by Postnikov and Shapiro in 2004. G G -parking functions are in bijection with recurrent configurations of the ASM on G G . In this work, we define a notion of prime G G -parking functions. These are parking functions that are in a sense “indecomposable”. Our notion extends the concept of primeness for classical parking functions, as well as the notion of prime ( p , q ) (p,q) -parking functions introduced by Armon et al. in recent work. We show that from the ASM perspective, prime G G -parking functions correspond to certain configurations of the ASM, which we call strongly recurrent . We study this new connection on a number of graph families, including wheel graphs, complete graphs, complete multi-partite graphs, and complete split graphs. 1. Introduction and definitions 1.1. Introduction This paper investigates the connection between parking functions and sandpile models, two dynamical processes in Discrete Mathematics. We begin with an informal introduction to these two processes, with more formal definitions being given in Sections 1.2 and 1.3 (these also contain detailed surveys of the literature). Parking functions were originally introduced by Konheim and Weiss [ 40 ] in their study of a hashing technique known as linear probing . Informally, consider the following problems. We have n cars which enter a street sequentially, and each car has a preferred parking spot in the street. What happens if a car’s preferred spot is already occupied when it enters, i.e. if a previous car has parked there? In hashing terminology, this is known as a collision . Konheim and Weiss’s classical parking model dictates that in such a case, the car simply drives forward to the next available parking spot. A (classical) parking function is an assignment of preferences which allows all cars to park through this process. Since their introduction, parking functions have become a rich source of research topics in Mathematics and Theoretical Computer Science, with connections to a variety of different fields. In particular, there have been a number of parking functions considered and studied in the literature. Some of these are based on a modification of the collision rule. Others modify or generalise various characterisations of classical parking functions. A more detailed review of the existing literature around parking functions and their variations is given in Section 1.2 . In this paper, we are interested in so-called graphical parking functions , or G -parking functions. These extend the parking process to a given graph G . G -parking functions were introduced by Postnikov and Shapiro [ 42 ] , who showed a rich connection to another discrete dynamical process called the Abelian sandpile model (ASM) on G . In the ASM, each vertex of G is assigned a number of grains of sand. At each step of the process, a vertex v of G is selected at random, and an extra grain added to it. If this causes the number of grains at v to exceed a certain threshold (usually the degree of v ), we say that v is unstable . Unstable vertices topple , sending grains to their neighbours in the graph. This may cause some neighbours to become unstable, and we topple these in turn. A special vertex, the sink , allows excess grains to exit the system, and so this process eventually stabilises. Of central importance in ASM research are the so-called recurrent configurations of the model, which appear infinitely often in its long-time running. Section 1.3 gives more details on results relating to these recurrent configurations. Notably, Postnikov and Shapiro [ 42 ] exhibited a straightforward bijection between recurrent configurations for the ASM on G and G -parking functions (see Theorem 1.9 ). It is this duality between the ASM and parking functions that we explore further in this paper. More precisely, we will be interested in a notion of primeness for parking functions. In this context, prime parking functions are parking functions which cannot be “decomposed” into smaller parking functions. We extend the notion of primeness to G -parking functions, and connect prime G -parking functions to a subset of recurrent configurations for the ASM, which we refer to as strongly recurrent . Our paper is organised as follows. In the remainder of this section, we formally introduce parking functions and their variations, and the Abelian sandpile model. We survey some of the relevant literature relating to these two processes. In Section 2 , we introduce the concepts of prime G -parking functions and strongly recurrent configurations , and show that these are in bijection with each other (Theorem 2.11 ). In Section 3 , we study these concepts in more depth on specific families of graphs, obtaining various enumerative and bijective results. In particular, we will see that our notion of primeness extends the classical prime parking functions (see [ 55 , Exercise 5.49] ) and a more recent concept of prime (p,q) -parking functions introduced by Armon et al. [ 3 ] . Finally, Section 4 summarises our main result and discusses possible future research directions. Let us now fix some basic notation. We denote by \mathbb{Z} the set of integers, and \mathbb{N} the set of (strictly) positive integers. Throughout this paper, n\in\mathbb{N} denotes a positive integer, and we let [n]:=\{1,\dots,n\} . We are interested in two processes related to graphs. Here, we consider graphs G=(V,E) which are undirected, finite, connected, with possible multiple edges (but no loops), and rooted at a special vertex s\in V , called the sink . We sometimes write G=(\Gamma,s) for clarity ( \Gamma is the un-rooted graph), and will simply call G a graph . The set of non-sink vertices will be denoted \tilde{V}:=V\setminus\{s\} . For two vertices v,w\in V , we denote \mathop{\mathrm{mult}}\left(vw\right) the number of edges between v and w (this can be 0 ). For v\in V and A\subseteq V , we denote N^{A}(v) the multi-set of neighbours of v in A , and \mathop{\mathrm{deg}^{A}}\left(v\right):=|N^{A}(v)|=\sum\limits_{w\in A}\mathop{\mathrm{mult}}\left(vw\right) . For simplicity, we usually just write \mathop{\mathrm{deg}}\left(v\right)=\mathop{\mathrm{deg}^{V}}\left(v\right) for the degree of the vertex v . Finally, we denote \mathrm{\mathbf{deg}}:V\rightarrow\mathbb{N},v\mapsto\mathop{\mathrm{deg}}\left(v\right) the degree function of G . Finally, for A\subseteq V , we write G[A] for the induced subgraph of G on A : this is the graph with vertex set A , and edge set the set of edges with both end-points in A . 1.2. Parking functions We begin by formally introducing the notion of parking functions. Consider a one-way street with n parking spots labelled 1 to n , and n cars, also labelled 1 to n , which want to park in the street. For each i\in[n] , car i has a preferred parking spot p_{i}\in[n] , and we say that p=(p_{1},\dots p_{n}) is a parking preference. Cars enter the street sequentially in order 1,\dots,n , and first drive to find their preferred spots. If a car i ’s preferred spot p_{i} is

Read the complete text