# Repetitions of Pak-Stanley Labels in $G$-Shi Arrangements

Cara Bennett  School of Mathematics, Georgia Tech<EMAIL_ADDRESS>,
Lucy Martinez  Department of Mathematics, Rutgers University
<EMAIL_ADDRESS>,  Ava Mock  Department of Mathematics, Wellesley
College<EMAIL_ADDRESS>,  Gordon Rojas Kirby  Department of Mathematics
and Statistics, San Diego State University<EMAIL_ADDRESS>and  Robin Truax
Department of Mathematics, Stanford University<EMAIL_ADDRESS>
###### Abstract.

Given a simple graph $G$, one can define a hyperplane arrangement called the
$G$-Shi arrangement. The Pak-Stanley algorithm labels the regions of this
arrangement with $G_{\bullet}$-parking functions. When $G$ is a complete graph
we recover the full Shi arrangement, and the Pak-Stanley labels give a
bijection with ordinary parking functions. However, for proper subgraphs
$G\subset K_{n}$, while the Pak-Stanley labels still include every
$G_{\bullet}$-parking function, some appear more than once. These repetitions
of Pak-Stanley labels are a topic of interest in the study of $G$-Shi
arrangements and $G_{\bullet}$-parking functions. Furthermore,
$G_{\bullet}$-parking functions are connected to many other combinatorial
objects (for example, superstable configurations in chip-firing). In studying
these repetitions, we can draw on existing results about these objects such as
Dhar’s Burning Algorithm. Conversely, our results have implications for the
study of these objects as well.

The key insight of our work is the introduction of a combinatorial model
called the Three Rows Game. Analyzing the histories of this game and the ways
in which they can induce the same outcomes allows us to characterize the
multiplicities of the Pak-Stanley labels. Using this model, we develop a
classification theorem for the multiplicities of the Pak-Stanley labels of the
regions in the $P_{n}$-Shi arrangement, where $P_{n}$ is the path graph on $n$
vertices. Then, we generalize the Three Rows Game into the $T$-Three Rows
Game. This allows us to study the multiplicities of the Pak-Stanley labels of
the regions in $T$-Shi arrangements, where $T$ is any tree. Finally, we
discuss the possibilities and difficulties in applying our method to arbitrary
graphs. In particular, we analyze multiplicities in the case when $G$ is a
cycle graph, and prove a uniqueness result for maximal $G_{\bullet}$-parking
functions for all graphs using the Three Rows Game.

##  1\. Introduction

A hyperplane in $\mathbb{R}^{n}$ is an affine subspace of dimension $n-1$. A
hyperplane arrangement is a collection of finitely many hyperplanes. Given a
hyperplane arrangement $\mathcal{A}$, its complement
$\mathbb{R}^{n}\setminus\bigcup_{H\in\mathcal{A}}H$ splits into connected
components called regions. The focus of this paper is on the combinatorial
properties of the regions of the $G$-Shi arrangement and their labels by
$G_{\bullet}$-parking functions, as defined by Duval, Klivans, and Martin [2].
The $G$-Shi arrangement $\mathscr{S}(G)$ is defined for any graph $G=(V,E)$ by

$\mathscr{S}(G)=\\{x_{i}-x_{j}=0,1\mid\\{i,j\\}\in E\text{ with }i<j\\}.$

When $G=K_{n}$, the $G$-Shi arrangement is the Shi arrangement, which has
$(n+1)^{n-1}$ regions. See [3] for a survey of the Shi arrangement.

Since the regions of the Shi arrangement are equinumerous with parking
functions of length $n$, a natural problem is to find a bijection between
regions of the Shi arrangement and parking functions of length $n$. Pak and
Stanley (1996) and Athanasiadis and Linusson (1999) gave two such bijections
[6],[1]. The Pak-Stanley algorithm, defined later, labels the regions of the
$G$-Shi arrangement with $G_{\bullet}$-parking functions in such a way that
every $G_{\bullet}$-parking function appears. When $G$ is complete, each
$G_{\bullet}$-parking function appears exactly once as a Pak-Stanley label on
a region of the $G$-Shi arrangement. If $G$ is not complete, some
$G_{\bullet}$-parking functions appear more than once as Pak-Stanley labels in
the $G$-Shi arrangement. Consider the examples of $G=K_{3}$ and $G=P_{3}$ in
Figures 1(a) and 1(b) respectively.

(0,0,0)(0,1,0)(0,0,1)(1,0,0)(1,1,0)(2,0,0)(1,0,1)(0,0,2)(0,1,1)(0,2,0)(2,1,0)(2,0,1)(1,0,2)(0,1,2)(0,2,1)(1,2,0)

((a)) Labelling the $K_{3}$-Shi arrangement.

(0,1,1)(0,0,1)(1,0,1)(0,1,0)(0,0,0)(1,0,0)(0,2,0)(0,1,0)(1,1,0)

((b)) Labelling the $P_{3}$-Shi arrangement.

Figure 1. Example Pak-Stanley Labels for $G$-Shi Arrangements

Figures 1(a) and 1(b) depict $G$-Shi arrangements. Notice that on the left,
each label appears once (has multiplicity 1), but on the right, the label
$(0,1,0)$ appears twice (has multiplicity 2). In this paper, we work towards a
characterization of the “multiplicities” of the Pak-Stanley labels in $G$-Shi
arrangements by introducing a combinatorial model called the Three Rows Game
defined in Section 4.2

In Section 3, we introduce the Shi adjacency digraph to describe the
adjacencies of regions in the $G$-Shi arrangement and their relationship to
the Pak-Stanley labels of these regions. Section 4 introduces the Three Rows
game, a combinatorial model for analyzing multiplicities of Pak-Stanley labels
in $P_{n}$-Shi arrangements for path graphs $P_{n}$. In particular, we prove
the following result to characterize multiplicities of the Pak-Stanley labels
in $G$-Shi arrangements for path graphs.

######  Theorem (Path Multiplicity Theorem).

Suppose ${\bf p}=(p_{1},\dots,p_{n})$ is a Pak-Stanley label of a region of
$\mathscr{S}(P_{n})$. A run ${\bf r}$ of length $k$ in ${\bf p}$ is a section
of ${\bf p}$ of the form $(0,1,\dots,1,0)$ with $k$ $1$s. If the length of a
run ${\bf r}$ is denoted $\ell({\bf r})$, then the multiplicity of the label
${\bf p}$ in in the $P_{n}$-Shi arrangement is

$\mu({\bf p})=\prod_{\text{runs ${\bf r}$ in ${\bf p}$}}(\ell({\bf r})+1).$

Besides analyzing path graphs, we also study multiplicities of Pak-Stanley
labels in $G$-Shi arrangements for all trees in Section 5, for example
characterizing multiplicities for star graphs with a similar theorem. Then in
Section 6, we discuss how the Three Rows Game can be played on all graphs, not
just on trees, and the added complexity of such an extension. In particular,
we completely characterize multiplicities of the Pak-Stanley labels in $G$-Shi
arrangements for cycle graphs with an analogous Cycle Multiplicity Theorem.
Finally, we prove the following fact about multiplicities of the maximal
labels of regions of $G$-Shi arrangements.

######  Corollary.

Let $G$ be a graph and ${\bf p}$ a maximal $G_{\bullet}$-parking function.
Then $\bf p$ has multiplicity $1$.

##  2\. Background

We begin with a discussion of some prerequisite topics: the $G$-Shi
arrangement, the Pak-Stanley algorithm, chip-firing, and superstable
configurations. An important note is that for the remainder of the paper, all
of our graphs are assumed to be connected, finite, and simple.

###  2.1. The $G$-Shi Arrangement and the Pak-Stanley Algorithm

First, we formally define the $G$-Shi arrangement.

######  Definition 2.1 (Shi Arrangement).

The Shi arrangement $\mathscr{S}_{n}$ is the hyperplane arrangement in
$\mathbb{R}^{n}$ with hyperplanes $x_{i}-x_{j}=0$ and $x_{i}-x_{j}=1$ for each
$i,j\in\\{0,1,2,\dots,n-1\\}$ with $i<j$.

######  Definition 2.2 ($G$-Shi Arrangement).

Given a graph $G=(V,E)$ with $V=\\{0,\dots,n-1\\}$, the $G$-Shi arrangement
$\mathscr{S}(G)$ is the hyperplane arrangement in $\mathbb{R}^{n}$ with
hyperplanes $x_{i}-x_{j}=0$ and $x_{i}-x_{j}=1$ for each $\\{i,j\\}\in E$ with
$i<j$ [4]. In this case, $G$ is called the defining graph of the arrangement.

It is important to note that the $G$-Shi arrangement depends on the labelling
$0,\dots,n-1$ of the vertices of $G$. Indeed, consider the isomorphic graphs
$K_{4}\setminus\\{0,1\\}$ and $K_{4}\setminus\\{0,2\\}$. The former has a
$G$-Shi arrangement with 84 regions, whereas the latter has a $G$-Shi
arrangement with 85 regions. Over the course of this paper, we will
demonstrate that in certain special cases the multiplicities do not depend on
the labelling of the vertices.

Figure 1(a) illustrates a projection of the Shi arrangement onto the
hyperplane $x_{0}+x_{1}+x_{2}=0$, allowing us to visualize it in $2$
dimensions without losing any regions or adjacency relations. This projection
trick is also used in Figure 1(b).

Next, we discuss $G$-parking functions and the Pak-Stanley algorithm (which
surjectively assigns $G_{\bullet}$-parking functions to the regions of the
$G$-Shi arrangement).

######  Definition 2.3 (Outdegree).

Given a graph $G=(V,E)$, a subset $S$ of $V$, and a vertex $v$, the outdegree
$\operatorname{outdeg}_{S}(v)$ of $v$ with respect to $S$ is the number of
edges from $v$ to vertices outside $S$. In particular,
$\operatorname{outdeg}_{\varnothing}(v)$ is the outdegree of $v$ (which equals
$\deg(v)$ when $G$ is undirected).

######  Definition 2.4 ($G$-Parking Function).

Let $G$ be an undirected graph on vertices $V=\\{0,1,\ldots,n-1,q\\}$. In this
case, $q$ is called the sink. A $G$-parking function is an $n$-tuple
$(a_{0},a_{1},\ldots,a_{n-1})$ such that for any non-empty subset
$S\subseteq\\{0,\dots,n-1\\}$, there exists $v\in S$ such that
$a_{v}<\operatorname{outdeg}_{S}(v)$.

######  Definition 2.5 ($G_{\bullet}$).

Let $G=(V,E)$ be a graph. Then, $G_{\bullet}$ is the graph obtained from $G$
by adding a sink vertex $q$ and an edge between $q$ and each $v\in V$.

Next, we will discuss the Pak-Stanley algorithm [6], whose behavior is the
central topic of our paper.

######  Definition 2.6 (Pak-Stanley Algorithm).

The Pak-Stanley algorithm maps $G_{\bullet}$-parking functions to the regions
of the $G$-Shi arrangement [6]. It assigns each region $R$ an $n$-tuple
$\lambda(R)$ of nonnegative integers, called its Pak-Stanley label as follows:

  1. (1)

The region in which $x_{0}>x_{1}>\dots>x_{n-1}$ and $x_{0}-x_{n-1}<1$ is
called the base region and denoted $R_{0}$. Define
$\lambda(R_{0})=(0,0,\dots,0)$.

  2. (2)

Suppose $\lambda(R)$ has been defined, and that $R^{\prime}$ is a region such
that

    1. (a)

$R$ and $R^{\prime}$ share a boundary facet, which is part of a hyperplane
$H\in\mathscr{S}(G)$.

    2. (b)

$R$ lies in the same half-space of $H$ as $R_{0}$.

In this case, we define
$\lambda(R^{\prime})=\begin{cases}\lambda(R)+e_{i}&\text{if }H\text{ is given
by }x_{i}-x_{j}=0\text{ with }i<j,\\\ \lambda(R)+e_{j}&\text{if }H\text{ is
given by }x_{i}-x_{j}=1\text{ with }i<j.\end{cases}$

Here, $e_{i}$ denotes the $i$th standard basis vector of $\mathbb{R}^{n}$.

The set of Pak-Stanley labels for the regions of the $G$-Shi arrangement are
called the Pak-Stanley labels for $G$; these are the same as the
$G_{\bullet}$-parking functions [4].

The examples of $G=K_{3}$ and $G=P_{3}$ are displayed in Figures 1(a) and
1(b). Notice every $(K_{3})_{\bullet}$-parking function appears in Figure
1(a), and every $(P_{3})_{\bullet}$-parking function appears in Figure 1(b).
Furthermore, each $(K_{3})_{\bullet}$-parking function appears exactly once in
the $K_{3}$-Shi arrangement. As it turns out, both of these are general
patterns that are proved in [4]. Specifically, we have the following:

######  Theorem 2.7 ([4], Corollary 2.8).

Every $G_{\bullet}$-parking function occurs as a label in the Pak-Stanley
algorithm on the $G$-Shi arrangement.

It is well known that there are $(n+1)^{n-1}$ regions in the Shi arrangement
$\mathscr{S}_{n}$. Similarly, there are $(n+1)^{n-1}$ parking functions (and
therefore $(n+1)^{n-1}$ $(K_{n})_{\bullet}$-parking functions). Thus, every
$(K_{n})_{\bullet}$-parking function occurs as a label precisely once in the
Pak-Stanley algorithm on the $K_{n}$-Shi arrangement.

###  2.2. Chip-Firing, Superstable Configurations, and Dhar’s Burning
Algorithm

We begin this section by recounting some of the definitions in Chapter 2 of
The Mathematics of Chip-firing by Klivans [5]. For more detail, we refer the
reader to this book.

In this section, $G=(V,E)$ is a graph on $n+1$ vertices with sink vertex $q$.

######  Definition 2.8 (Chip Configuration).

A chip configuration for $G$ is a non-negative integer vector

${\bf c}=(c_{0},c_{1},\dots,c_{n-1})\in\mathbb{Z}^{n}_{\geq 0}$

where each coordinate of the vector corresponds to the number of “chips” at a
particular vertex. That is, the $i$th coordinate $c_{i}$ represents the number
of chips at the vertex $v_{i}$. Notice that we do not consider the number of
chips on the sink vertex $q$.

######  Definition 2.9 (Firing).

Given a chip configuration ${\bf c}$ for $G$, a non-sink vertex $v$ fires by
sending one chip to each of its neighbors (possibly including the sink). That
is, the configuration ${\bf c}$ is replaced by ${\bf
c^{\prime}}=(c_{0}^{\prime},\dots,c_{n-1}^{\prime})\in\mathbb{Z}^{n}$ where

$c_{i}^{\prime}=\begin{cases}c_{i}-\deg i&i=v\\\ c_{i}+1&\\{i,v\\}\in E\\\
c_{i}&\text{otherwise.}\end{cases}$

This is a legal fire if ${\bf c^{\prime}}$ is a chip configuration.

######  Definition 2.10 (Stable).

A chip configuration ${\bf c}$ is stable if there are no legal fires.

Now let us transition to discussing superstable configurations.

######  Definition 2.11 (Graph Laplacian).

Let $G=(V,E)$ be a graph on $n$ vertices $v_{0},\dots,v_{n-1}$. The graph
Laplacian $\Delta(G)$ is the $n\times n$ matrix given by

$\Delta_{ij}=\begin{cases}\deg(v_{i})&i=j\\\ -1&i\neq j\text{ and
}\\{v_{i},v_{j}\\}\in E\\\ 0&\text{otherwise.}\end{cases}$

######  Definition 2.12 (Reduced Laplacian).

Let $\Delta$ be the Laplacian of a graph $G$ with sink $q$. Then, the reduced
graph Laplacian of $G$ with respect to $q$, denoted $\Delta_{q}(G)$ or
$\Delta_{q}$, is the matrix obtained from $\Delta$ by deleting the row and
column corresponding to $q$.

######  Definition 2.13 (Cluster-Fire).

Let $G$ be a graph on $n+1$ vertices with sink $q$. Consider a chip
configuration ${\bf c}=(c_{0},\dots,c_{n-1})$. Let $S$ be a subset of the
vertices of $G$. A cluster-fire at $S$ replaces ${\bf c}$ with a new
configuration ${\bf c}^{\prime}$ given by sending a chip to each neighbor of
$v$ for each $v\in S$. Formally,

${\bf c}^{\prime}={\bf c}-\Delta_{q}(G)\chi_{S}$

where $\chi_{S}\in\mathbb{R}^{n}$ is the characteristic vector of $S$; that
is, $\chi_{S}$ has $i$th coordinate equal to $1$ if $i\in S$ and $0$ if
$i\not\in S$. Such a cluster-fire is called legal if ${\bf c^{\prime}}$ is
still a chip configuration.

######  Definition 2.14 (Superstable Configuration).

Let a graph $G$ be given with a chip configuration ${\bf c}$. The
configuration ${\bf c}$ is called superstable if there are no legal cluster-
fires from ${\bf c}$.

######  Example 2.15.

The left-hand configuration is not superstable, as one can fire at the three
vertices whose chip labels are bolded. However, the right-hand side is
superstable.

Figure 2. Non-Superstable and Superstable Configurations.

Now, the main reason why superstable configurations are central to our paper
is the following result:

######  Theorem 2.16 ([5], Theorem 3.6.3).

If $G$ is a graph with sink vertex $q$, then the $G$-parking functions of $G$
are precisely the set of superstable configurations of $G$.

###### Proof.

By definition; see Definitions 2.4 and 2.14. ∎

We conclude with a discussion of some important results about superstable
configurations. First, we will discuss Dhar’s Burning Algorithm.

######  Definition 2.17 (Dhar’s Burning Algorithm).

Let $G$ be a graph with sink $q$, and ${\bf c}$ be a chip configuration on
$G$. Envision the chips as firefighters protecting the vertices that they are
on. Then, light the sink $q$ on fire, and repeat the following process:

  1. (1)

If a vertex $v$ is on fire, the fire spreads along all the edges of $v$
towards $v$’s neighbors.

  2. (2)

Each firefighter can stop the fire along exactly one edge.

  3. (3)

A vertex $v^{\prime}$ does not light on fire as long as there is a firefighter
stopping the fire at each burning incident edge of $v^{\prime}$. However, if
there are more incident burning edges at $v^{\prime}$ than firefighters,
$v^{\prime}$ catches on fire.

######  Theorem 2.18 ([5], Theorem 2.6.24).

Let $G$ be a finite graph with sink $q$. Start a fire at $q$. A configuration
is superstable if and only if every vertex is eventually on fire.

###### Proof.

Begin with a chip configuration ${\bf c}$ and let $S$ denote the set of
vertices which are not on fire when the algorithm concludes. If
$S\neq\varnothing$, then there is a legal cluster-fire at $S$. To see why,
notice that each vertex $v\in S$ must start with
$\operatorname{outdeg}_{S}(v)$ firefighters to prevent itself from lighting on
fire, and it loses precisely $\operatorname{outdeg}_{S}(v)$ chips in a
cluster-fire at $S$. On the other hand, suppose $S=\varnothing$. Then, there
is no legal cluster-fire at any $U\subseteq V\setminus\\{q\\}$. For, if $u$ is
the first vertex of $U$ to catch on fire, ${\bf
c}_{u}<\operatorname{outdeg}_{U}(u)$, so a cluster-fire at $U$ would leave $u$
with negative chips. ∎

Next, we discuss a powerful concept called critical-superstable duality and
its implications.

######  Definition 2.19 (Critical Configurations).

A chip configuration ${\bf c}$ is called critical if it is stable and arises
from the chip-firing process from a configuration ${\bf c}^{\prime}$ in which
every vertex is ready to fire.

######  Theorem 2.20 ([5], Theorem 2.6.19).

Let ${\bf c}_{\text{max}}$ denote the configuration given by $({\bf
c}_{\text{max}})_{i}=\deg(i)-1$. Then, for any graph $G$, ${\bf c}$ is
critical if and only if ${\bf c}_{\text{max}}-{\bf c}$ is superstable.

######  Proposition 2.21 (Chips in Maximal Superstable Configurations).

Suppose that $G$ is a graph on $n$ vertices with $m$ edges. Then every maximal
superstable configuration on $G_{\bullet}$ has $m$ chips. Conversely, every
superstable configuration on $G_{\bullet}$ with $m$ chips is maximal.

###### Proof.

Since $G_{\bullet}$ has $m+n$ edges and $\deg(q)=n$, Proposition 2.6.22 of
Klivans yields that any minimal critical configuration on $G_{\bullet}$ has
$m$ chips [5]. On the other hand, the sum of the degrees of all non-sink
vertices of $G_{\bullet}$ is $2m+n$, and to compute ${\bf c}_{\text{max}}$ we
subtract $1$ for each of the $n$ non-sink vertices, then $c_{\text{max}}$ on
$G_{\bullet}$ has $2m$ chips. Therefore, by Theorem 2.20, we have that every
maximal superstable configuration has $2m-m=m$ chips. The converse follows
immediately. ∎

##  3\. The Shi Adjacency Digraph

In this section, we introduce the Shi adjacency digraph and discuss how we use
it to perform the Pak-Stanley algorithm.

###  3.1. Shi Adjacency Digraphs

When following the Pak-Stanley algorithm, we assign labels to new regions
based on the labels of adjacent regions. The order in which we assign the
labels depends on the placement of the regions with respect to the base region
$R_{0}$. To encode this information about region adjacency and the order of
assigning labels, we created the Shi adjacency digraph.

######  Definition 3.1 (Shi Adjacency Digraph).

Given a graph $G$, called the defining graph, we construct the Shi adjacency
digraph $\Gamma\mathscr{S}(G)$ from the $G$-Shi arrangement as follows:

  1. (1)

Each region $R_{i}$ in the $G$-Shi arrangement is mapped to the vertex $v_{i}$
in $\Gamma\mathscr{S}(G)$.

  2. (2)

Two vertices $v_{i}$ and $v_{j}$ are connected by a directed edge if and only
if they correspond to regions $R_{i}$ and $R_{j}$ which share a face given by
a hyperplane $H$.

    1. (a)

If $R_{0}$ and $R_{i}$ lie on the same side of $H$, the directed edge is
$(v_{i},v_{j})$.

    2. (b)

If $R_{0}$ and $R_{j}$ lie on the same side of $H$, the directed edge is
$(v_{j},v_{i})$.

Another way to think about the Shi adjacency digraph is to realize that the
$G$-Shi arrangement endows $\mathbb{R}^{n}$ with a natural cell structure, and
the Shi adjacency digraph (or rather, the undirected graph underlying it) is
the $1$-skeleton of the dual of that cell structure.

We can also label each of the directed edges with a value corresponding to the
Pak-Stanley algorithm so that we can recover the Pak-Stanley labels of
vertices directly from the graph. If a directed edge corresponds to hyperplane
$x_{i}-x_{j}=c$ separating adjacent regions then we label it $i$ if $c=0$ or
$j$ if $c=1$. Then, we label the source vertex $(0,0,\dots,0)$, and the label
of $v_{j}$ is equal to the label of $v_{i}$ incremented by 1 at the index
assigned to the edge $(v_{i},v_{j})$.

To generate these graphs, we created the SageMath class G_Shi. The class takes
in a defining graph $G$, constructs the Shi adjacency digraph, and uses the
above algorithm to compute the Pak-Stanley labels. The code and documentation
for this program is in Appendix A.

021100212120101202012

Figure 3. The $G$-Shi arrangement (left) and its Shi adjacency digraph (right)
of the defining graph $K_{3}$ with edges labelled by the index to be
incremented.

In this paper, Shi adjacency digraphs are mostly used as a computational tool,
but they do have a few interesting properties as graphs.
$\Gamma\mathscr{S}(G)$ is always acyclic. If $n$ is the number of vertices of
$G$, then $\Gamma\mathscr{S}(G)$ is $(n-1)$-edge connected. Finally, we have
the following result:

######  Theorem 3.2.

$\Gamma\mathscr{S}(G)$ is planar if and only if $G$ has $n\leq 3$ vertices.

###### Proof.

If $G$ has at most $3$ vertices, the $G$-Shi arrangement can be represented in
$\mathbb{R}^{2}$ by projecting onto the plane $x_{0}+x_{1}+x_{2}=0$; planarity
is then obvious. On the other hand, one may verify by brute force that
$\Gamma\mathscr{S}(G)$ is not planar if $n=4$. Yet if $H$ is a subgraph of
$G$, $\Gamma\mathscr{S}(H)$ is a subdivision of $\Gamma\mathscr{S}(G)$ by
construction. Therefore, by Kuratowski’s Theorem, if $\Gamma\mathscr{S}(H)$ is
not planar, then $\Gamma\mathscr{S}(G)$ is not planar. Thus, if $G$ has more
than $4$ vertices, $\Gamma\mathscr{S}(G)$ cannot be planar, as desired. ∎

###  3.2. The Shi Adjacency Digraphs of Trees

In this section, we consider the structure of the $G$-Shi arrangement and the
Shi adjacency digraph when $G$ is a tree.

When constructing the $G$-Shi arrangement, we include the pair of parallel
hyperplanes $x_{i}-x_{j}=0$ and $x_{i}-x_{j}=1$ for each edge $\\{i,j\\}$,
where $i<j$, in the defining graph $G$. Each of these pairs of hyperplanes
divides $\mathbb{R}^{n}$ into three distinct regions: a region
$0<x_{i}-x_{j}<1$ between the hyperplanes, and two regions $x_{i}-x_{j}<0$ and
$x_{i}-x_{j}>1$ on each side of the hyperplanes. Since trees are acyclic, this
choice is made independently for each pair of parallel hyperplanes. Thus, as a
tree on $n$ vertices has $n-1$ edges, the result is that the Shi adjacency
digraphs of trees take on the form of the subdivided $(n-1)$-dimensional cube
$[-1,1]^{n-1}$ with vertices $\\{-1,0,1\\}^{n-1}$, as demonstrated in Figure
4.

Furthermore, the base region lies between each pair of parallel hyperplanes;
that is, it lies in the region $0<x_{i}-x_{j}<1$ for each $\\{i,j\\}\in E$.
Therefore, whenever a vertex lies between a pair of parallel hyperplanes (that
is, it satisfies $0<x_{i}-x_{j}<1$), it has two outward-bound edges: one
pointing to a vertex satisfying $x_{i}-x_{j}<0$ and one pointing to a vertex
satisfying $x_{i}-x_{j}>1$. This demonstrates that the edges of the cube are
always directed towards the corners.

Figure 4. The Shi adjacency digraph of trees on 1, 2, 3, and 4 vertices.

##  4\. Path Graphs and the Three Rows Game

In this section, we introduce the Three Rows Game, a tool for analyzing
multiplicities in the Pak-Stanley labelling. We will use the specific case of
the path graph to demonstrate how the Three Rows Game translates the problem
of computing Pak-Stanley labels into a combinatorial model. Later, we will
generalize the Three Rows Game to be played on trees and general graphs.

For the remainder of this section, we label the vertices of the path graph
$P_{n}$ as follows unless otherwise stated.

$0$$1$$2$$n-2$$n-1$

###  4.1. Superstable Configurations on $(P_{n})_{\bullet}$

We begin by counting the number of superstable configurations on
$(P_{n})_{\bullet}$.

First, let $F_{n}$ denote the $n$th Fibonacci number, given by $F_{0}=F_{1}=1$
and $F_{n}=F_{n-1}+F_{n-2}$. We begin with two identities of Fibonacci
numbers.

######  Lemma 4.1.

Let $F_{n}$ denote the $n$th Fibonacci number. Then,

$F_{n}=2F_{n-1}-F_{n-3}\qquad\text{ and }\qquad F_{n}=3F_{n-2}-F_{n-4}.$

###### Proof.

By definition, $F_{n-2}+F_{n-3}=F_{n-1}$ implies $F_{n-2}=F_{n-1}-F_{n-3}$.
Combining these two equalities yields $F_{n}=2F_{n-1}-F_{n-3}$. Notice that
shifting indices yields $F_{n-1}=2F_{n-2}-F_{n-4}$. Thus,
$F_{n}=3F_{n-2}-F_{n-4}$. ∎

Next, we work through some determinant computations.

######  Lemma 4.2.

Let $M_{n}$ denote the $n\times n$ matrix given by

$\begin{bmatrix}3&-1&0&\cdots&0&0\\\ -1&3&-1&\cdots&0&0\\\
0&-1&3&\cdots&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&\cdots&3&-1\\\ 0&0&0&\cdots&-1&2\end{bmatrix}.$

That is, $M_{n}$ has a 2 in the $n$th row, $n$th column, 3’s along the
diagonal in rows $1,\dots n-1$. It has $-1$’s along the super and subdiagonal,
and 0’s elsewhere. Then, $\det(M_{n})=F_{2n+1}$ for any positive integer $n$.

###### Proof.

The result follows by induction. The base case $\det(M_{1})=F_{3}=2$ is
immediate. Therefore, assume that $\det(M_{k})=F_{2k+1}$ for all $k<n$. Then,
by cofactor expansion along the top row,

$\det(M_{n})=3\det(M_{n-1})+\begin{vmatrix}-1&-1&\cdots&0&0\\\
0&3&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots&\\\ 0&0&\cdots&3&-1\\\
0&0&\cdots&-1&2\end{vmatrix}=3\det(M_{n-1})-\det(M_{n-2}).$

Thus, $\det(M_{n})=3F_{2n-1}-F_{2n-3}=F_{2n+1}$ by Lemma 4.1, as desired. ∎

######  Lemma 4.3.

Let $M^{\prime}_{n}$ denote the $n\times n$ matrix given by

$\begin{bmatrix}2&-1&0&\cdots&0&0\\\ -1&3&-1&\cdots&0&0\\\
0&-1&3&\cdots&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\
0&0&0&\cdots&3&-1\\\ 0&0&0&\cdots&-1&2\end{bmatrix}.$

Then, $\det(M^{\prime}_{n})=F_{2n}$ for any positive integer $n$.

###### Proof.

The result follows from cofactor expansion. Indeed,

$\det(M^{\prime}_{n})=2\begin{vmatrix}3&-1&\cdots&0&0\\\ -1&3&\cdots&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&3&-1\\\
0&0&\cdots&-1&2\end{vmatrix}+\begin{vmatrix}-1&-1&\cdots&0&0\\\
0&3&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots&\\\ 0&0&\cdots&3&-1\\\
0&0&\cdots&-1&2\end{vmatrix}$

where the first summand is equal to $2\det(M_{n-1})$, while the second is
equal to $-\det(M_{n-2})$ from Lemma 4.2. But Lemma 4.2 shows that
$\det(M_{n-1})=F_{2n-1}$ and $-\det(M_{n-2})=-F_{2n-3}$. Thus,
$\det(M^{\prime}_{n})=2F_{2n-1}-F_{2n-3}=F_{2n}$ by Lemma 4.1. ∎

######  Theorem 4.4.

The number of superstable configurations of $(P_{n})_{\bullet}$ is $F_{2n}$
for any positive integer $n$.

###### Proof.

Theorem 4.2.2 of [5] states that the number of superstable configurations of
$(P_{n})_{\bullet}$ is equal to the determinant of the reduced Laplacian
$\Delta_{q}$ of $(P_{n})_{\bullet}$ [5]. By definition,
$\Delta_{q}((P_{n})_{\bullet})=M^{\prime}_{n}$. Thus, by Lemma 4.3,
$\Delta_{q}((P_{n})_{\bullet})$ has determinant $F_{2n}$. ∎

We refer the reader to Appendix B for a direct combinatorial proof.

Next, we offer a characterization of superstable configurations on
$(P_{n})_{\bullet}$.

######  Definition 4.5 ($2$-Free Block).

Given a sequence of integers ${\bf a}=(a_{1},\dots,a_{n})\in\\{0,1,2\\}^{n}$,
we call a maximal contiguous subsequence consisting of $0$’s and $1$’s that
occur to the left or right of a $2$ a $2$-free block. Note that we also
consider empty subsequences as 2-free blocks. Thus, if there are $m-1$
occurrences of $2$ in ${\bf a}$, then ${\bf a}$ has $m$ $2$-free blocks.

######  Example 4.6.

If ${\bf a}=(2,0,1,2,2,0,2)$, then the $2$-free blocks are $\pi_{1}=()$,
$\pi_{2}=(0,1)$, $\pi_{3}=()$, $\pi_{4}=(0)$, and $\pi_{5}=()$.

######  Lemma 4.7 (Superstability Criterion).

Suppose ${\bf a}\in\\{0,1,2\\}^{n}$ has 2-free blocks
$\pi_{1},\pi_{2},\cdots,\pi_{m}$. Then ${\bf a}$ is a superstable
configuration on $(P_{n})_{\bullet}$ if and only if there is a $0$ in each
2-free block $\pi_{i}$.

###### Proof.

For necessity, note that if any 2-free block $\pi_{i}$ contains only $1$s,
then firing at $\pi_{i}$ as well as its bordering $2$s is a legal cluster-
fire. For sufficiency, we use Dhar’s Burning Algorithm. Indeed, if the
Superstability Criterion holds, the fire spreads to each vertex with $0$
chips, and any vertex in any of the $2$-free blocks is eventually on fire. By
this point, any of the vertices with $2$ chips have $3$ incident burning
edges, so they light on fire too. Therefore, by Theorem 2.18, ${\bf a}$ is
superstable. ∎

###  4.2. The Three Rows Game

Next, we define the Three Rows Game, and explain why it encodes the labelling
of the regions of the $G$-Shi arrangement according to the Pak-Stanley
algorithm.

######  Definition 4.8 (Three Rows Game).

The Three Rows Game is played on the following board:

0 | 1 | 2 | 3 | $\cdots$ | $n-3$ | $n-2$
---|---|---|---|---|---|---
|  |  |  |  |  |
1 | 2 | 3 | 4 | $\cdots$ | $n-2$ | $n-1$

The game is played by choosing an entry in each column. The history ${\bf h}$
of the game is the sequence of squares chosen (top, middle, or bottom), and
the outcome ${\bf o}({\bf h})$ or ${\bf o}$ of the game is the multiset of
numbers chosen, ignoring any choice of middle squares.

In this section, our principal object of study is the multiplicity of an
outcome of the game.

######  Definition 4.9 (Equivalent Histories).

Two histories h and $\textbf{h}^{\prime}$ are equivalent, denoted
$\textbf{h}\sim{\bf h}^{\prime}$ if ${\bf o}(\textbf{h})={\bf
o}(\textbf{h}^{\prime})$. This gives an equivalence relation, the equivalence
classes of which are denoted $[{\bf h}]$.

######  Definition 4.10 (Multiplicity of an Outcome).

Given an outcome ${\bf o}$, the multiplicity $\mu({\bf o})$ of ${\bf o}$ is
the number of histories ${\bf h}$ such that ${\bf o}({\bf h})={\bf o}$.
Furthermore, we adopt the convention that $\mu({\bf h})$ denotes $\mu({\bf
o}({\bf h}))$. Notice that $\mu({\bf h})$ is the size of the equivalence class
$[{\bf h}]$.

######  Example 4.11.

Consider the following equivalent histories ${\bf h}\sim{\bf h^{\prime}}$ of
the Three Rows Game on 4 columns with ${\bf o}({\bf h})=\\{0,2,4\\}={\bf
o}({\bf h^{\prime}})$.

${\bf h}=$ 0 1 2 3 1 2 3 4 and ${\bf h}^{\prime}=$ 0 1 2 3 1 2 3 4

Moreover, one can verify that these are the only two histories that yield
outcome ${\bf o}=\\{0,2,4\\}$ so that $\mu({\bf o})=2$.

The reason why this game and the multiplicities of its outcomes are worth
studying is the following correspondence.

Histories of the Three Rows Game
---
Outcomes of the Three Rows Game
$\Longleftrightarrow$
---
$\Longleftrightarrow$

Regions/chambers in the $G$-Shi arrangement
---
Pak-Stanley labels in the $G$-Shi arrangement

In particular, repetitions of Pak-Stanley labels in the Shi adjacency digraph
correspond to instances where multiple histories of the Three Rows Game induce
the same outcome.

To understand this correspondence, recall that each edge $\\{i,i+1\\}$ in the
path graph $P_{n}$ gives a pair of parallel hyperplanes $x_{i}-x_{i+1}=0$ and
$x_{i}-x_{i+1}=1$. Each region is uniquely determined by whether or not it
lies “before” both of these hyperplanes (it satisfies $x_{i}-x_{i+1}<0$),
between these hyperplanes (it satisfies $0<x_{i}-x_{i+1}<1$), or “after” these
hyperplanes (it satisfies $x_{i}-x_{i+1}>1$), for $i=0,\dots,n-2$. Therefore,
choosing a region corresponds to choosing a square in each column of the
following table.

$x_{0}-x_{1}<0$ | $x_{1}-x_{2}<0$ | $\cdots$ | $x_{n-3}-x_{n-2}<0$ | $x_{n-2}-x_{n-1}<0$
---|---|---|---|---
$0<x_{0}-x_{1}<1$ | $0<x_{1}-x_{2}<1$ | $\cdots$ | $0<x_{n-3}-x_{n-2}<1$ | $0<x_{n-2}-x_{n-1}<1$
$x_{0}-x_{1}>1$ | $x_{1}-x_{2}>1$ | $\cdots$ | $x_{n-3}-x_{n-2}>1$ | $x_{n-2}-x_{n-1}>1$

However, notice that not all of this information is necessary to compute the
Pak-Stanley label. Indeed, choosing $x_{0}-x_{1}<0$ corresponds to crossing
the hyperplane $x_{0}-x_{1}=0$, which means incrementing the label in
coordinate $0$. Similarly, choosing $x_{0}-x_{1}>1$ means incrementing the
label in coordinate $1$, and choosing $0<x_{0}-x_{1}<1$ means that no
hyperplanes are crossed, and therefore none of the coordinates of the label
are incremented. Therefore, we replace each inequality with the coordinate of
the label that is incremented, which yields the familiar board of the Three
Rows Game in Definition 4.8.

Then, to compute the Pak-Stanley label corresponding to a particular outcome
${\bf o}$, we start with $(0,\dots,0)$ and increment the $i$th coordinate for
each occurence of $i$ in ${\bf o}$.

######  Example 4.12.

Continuing Example 4.11, consider playing the Three Rows Game on 4 columns,
and receiving the outcome $\\{0,2,4\\}$. This corresponds to crossing edges
labelled with a $0$, a $2$, and a $4$, and therefore incrementing each of the
coordinates $0$, $2$, and $4$ once to get the $G$-parking function $10101$.

This exact correspondence of regions and histories, labels and outcomes, shows
that the Three Rows Game is a concise combinatorial model that captures the
complexity of the behavior of the Pak-Stanley algorithm on path graphs. With
the language of the Three Rows Game, we can more easily spot patterns in the
behavior of the Pak-Stanley algorithm.

An example of one such pattern is that as we play the Three Rows Game, the
outcomes are independent of any permutation of the columns. This demonstrates
the following fact:

######  Proposition 4.13.

The multiplicities of the Pak-Stanley labels in the Shi adjacency digraph of
$P_{n}$ are independent of the vertex labelling up to permutation.

###  4.3. Uniqueness of Maximal Labels in the $P_{n}$-Shi Arrangement

In this section we study the multiplicities of maximal labels of regions of
the $P_{n}$-Shi arrangement.

######  Theorem 4.14.

The following are equivalent for a vertex $v$ in the Shi adjacency digraph of
$P_{n}$:

  1. (1)

$v$ is a sink.

  2. (2)

$v$ is labelled with a maximal $G_{\bullet}$-parking function.

  3. (3)

The history corresponding to $v$ has no entries from the middle row of the
Three Rows Game.

###### Proof.

(3) $\Rightarrow$ (2): In this case, the Pak-Stanley label ${\bf p}$ of $v$
has coordinate sum $n-1$, corresponding to a superstable configuration with
$n-1$ total chips: one for each column in the Three Rows Game. Thus, by
Proposition 2.21 and Theorem 2.16, ${\bf p}$ is maximal.

(2) $\Rightarrow$ (1): If $v$ is labelled with a maximal $G_{\bullet}$-parking
function, then $v$ must be a sink, as otherwise any children of $v$ would be
labelled with strictly larger $G_{\bullet}$-parking functions, a
contradiction.

(1) $\Rightarrow$ (3): Suppose that the history corresponding to $v$ has a
middle square in column $i$. This implies that $v$ satisfies
$0<x_{i}-x_{i+1}<1$, but as discussed in Section 3.2, any region between two
hyperplanes has outdegree at least $2$. It is the parent of the two regions
given by crossing the hyperplanes $x_{i}-x_{i+1}=0$ and $x_{i}-x_{i+1}=1$,
respectively), so it cannot be a sink. ∎

This discussion immediately demonstrates the following fact:

######  Proposition 4.15.

There are $2^{n-1}$ sinks in the Shi adjacency digraph of $P_{n}$.

######  Theorem 4.16 (Uniqueness of Maximal Outcomes).

Any outcome ${\bf o}$ of the Three Rows Game on $n$ columns with $|{\bf o}|=n$
has multiplicity $\mu({\bf o})=1$.

###### Proof.

Suppose ${\bf h}$ and ${\bf h}^{\prime}$ are two equivalent histories whose
shared outcome has cardinality $n$. Then ${\bf h}$ and ${\bf h}^{\prime}$ are
both length $n$ sequences of squares with labels in weakly increasing order,
which induce the same outcome if and only if they are equal, ${\bf h}={\bf
h}^{\prime}$. ∎

######  Corollary 4.17.

Any maximal $(P_{n})_{\bullet}$-parking function appears uniquely as a Pak-
Stanley label for $P_{n}$. In other words, the labels on all of the sinks of
the $P_{n}$-Shi adjacency digraph appear uniquely.

Now, while uniqueness is straightforward to prove for maximal outcomes, the
following example shows that it fails quite drastically for general outcomes.

######  Example 4.18.

Consider the Three Rows Game on $2n$ columns. Then the outcome ${\bf
o}=\\{1,3,5,\dots,2n-1\\}$ satisfies $\mu({\bf o})=2^{n}$. To see why, notice
that there are $n$ integers in this outcome, and for each of them we can
choose either $i\square$ (bottom and middle) or $\square i$ (middle and top).

This example is interesting because it shows that some outcomes of the Three
Rows Game can arise from exponentially many histories. Later, once we develop
further machinery, we will find the outcome (and therefore the Pak-Stanley
label) which occurs the maximum number of times.

###  4.4. Patterns in the Three Rows Game

To characterize why uniqueness fails for general outcomes, we introduce the
notion of patterns, which are particular sequences of moves in the Three Rows
Game.

######  Definition 4.19 (Ascents/Descents).

Given a history ${\bf h}=(h_{1},\dots,h_{n})$ of the Three Rows Game,
$(h_{i},h_{i+1})$ is called an ascent if $h_{i+1}$ is in a higher row than
$h_{i}$, and a descent if $h_{i+1}$ is in a lower row than $h_{i}$. Any
subsequence $(h_{i},h_{i+1},\dots,h_{j-1},h_{j})$ of ${\bf h}$ is called
weakly ascending (resp. descending) if it has no descent (resp. ascent).

Note that ascents and descents in a history are defined solely by the
placement of the blocks, rather than the values that they contain.

######  Definition 4.20 (Prepatterns and Patterns).

Given a history of the Three Rows Game, we split the history into blocks,
called prepatterns, by introducing breaks before any descent or before a
middle square appears twice in a block. Those prepatterns which contain a
middle square are called patterns. The length of a pattern ${\bf p}$ is
denoted $\ell({\bf p})$.

######  Example 4.21.

The following history is broken up into its 6 prepatterns:

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
---|---|---|---|---|---|---|---|---|---
|  |  |  |  |  |  |  |  |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10

$\quad\Rightarrow\quad$ 0 1 1 2 2 3 4 5 3 4 5 6 6 7 7 8 $8$ $9$ $9$ $10$

From those 6 prepatterns, we get the following patterns whose lengths are 1,
4, 2, and 1 respectively:

1
---
2

2 | 3 | 4 | 5
---|---|---|---
|  |  |
3 | 4 | 5 | 6

6 | 7
---|---
|
7 | 8

$8$
---
$9$

The importance of patterns comes when proving Theorem 4.26. The proof of this
theorem requires uniqueness of maximal outcomes as well as the following
series of technical lemmas in Section 4.5. Furthermore, these technical lemmas
will also prove useful in translating our results back into the language of
Pak-Stanley labels.

###  4.5. Technical Lemmas About Patterns

######  Lemma 4.22 (Gap Characterization Lemma).

Suppose that ${\bf h}=(h_{1},\dots,h_{n})$ is a history of the Three Rows Game
with outcome ${\bf o}$ and $i\in\\{0,1,\dots,n\\}$. Then the following are
equivalent:

  1. (1)

$i$ does not appear in the outcome ${\bf o}$.

  2. (2)

Either $(h_{i},h_{i+1})$ is a descent or both $h_{i}$ and $h_{i+1}$ are middle
squares.

###### Proof.

The only two places that $i$ appears is at the bottom column $i$ and the top
of column $(i+1)$. Therefore, $i$ does not appear in ${\bf o}$ if and only if
$h_{i}$ is not the bottom square and $h_{i+1}$ is not the top square; in this
case, either $(h_{i},h_{i+1})$ is a descent or both $h_{i}$ and $h_{i+1}$ are
middle squares. ∎

######  Lemma 4.23 (Splitting Lemma).

Suppose that ${\bf h}=(h_{1},\dots,h_{n})$ and ${\bf
h}^{\prime}=(h^{\prime}_{1},\dots,h^{\prime}_{n})$ are histories of the Three
Rows Game where ${\bf h}$ has outcome ${\bf o}$ with $i\not\in{\bf o}$. Then
${\bf h}\sim{\bf h^{\prime}}$ if and only if ${\bf
h}\sim(h^{\prime}_{1},\dots,h^{\prime}_{i},h_{i+1},\dots,h_{n})\sim(h_{1},\dots,h_{i},h_{i+1}^{\prime},\dots,h_{n}^{\prime})$.
That is, any replacement of ${\bf h}$ by an equivalent history can be broken
up into two independent replacements of $(h_{1},\dots,h_{i})$ and
$(h_{i+1},\dots,h_{n})$ by individually equivalent histories, so that

$\mu((h_{1},\dots,h_{n}))=\mu((h_{1},\dots,h_{i}))\cdot\mu((h_{i+1},\dots,h_{n})).$

###### Proof.

Suppose that $i\not\in{\bf o}$. Then, ${\bf o}$ can be split into two parts
${\bf o}_{1}$ and ${\bf o}_{2}$: those numbers which are strictly less than
$i$, and those numbers which are strictly greater than $i$. Hence, a
replacement of $h_{1},\dots,h_{i}$ by $h_{1}^{\prime},\dots,h_{i}^{\prime}$
can only affect ${\bf o}_{1}$, and a replacement of $h_{i+1},\dots,h_{n}$ by
$h_{i+1}^{\prime},\dots,h_{n}^{\prime}$ can only affect ${\bf o}_{2}$. The
result follows. ∎

######  Lemma 4.24 (Pattern Characterization Lemma).

Suppose that ${\bf h}=(h_{1},\dots,h_{n})$ is a history of the Three Rows Game
with outcome ${\bf o}$. Then, if $1\leq i<j\leq n$,
$(h_{i},h_{i+1},\dots,h_{j})$ is a pattern if and only if $i,i+1,\dots,j-1$
appear exactly once in ${\bf o}$ and $i-1,j\not\in{\bf o}$.

###### Proof.

Suppose that $(h_{i},h_{i+1},\dots,h_{j})$ is a pattern. Then
$(h_{i},h_{i+1},\dots,h_{j})$ takes the form:

$i-1$ |  |  |  |  | $\cdots$ | $j-1$
---|---|---|---|---|---|---
|  |  |  |  |  |
$i$ | $\cdots$ |  |  |  |  | $j$
$h_{i}$ |  | $h_{i+k}$ |  | $h_{j}$

That is, $(h_{i},h_{i+1},\dots,h_{j})$ begins with $k$ bottom squares, a
single middle square, and then $j-i-k$ top squares for some
$k\in\\{0,\dots,j-i\\}$. This establishes that $i,i+1,\dots,j-1$ appear
exactly once in ${\bf o}$. Then, since $h_{i-1}$ is not the bottom square (as
otherwise it would be in the pattern), $i-1\not\in{\bf o}$. Similarly, since
$h_{j+1}$ is not the top square, $j\not\in{\bf o}$.

Conversely, suppose $\\{i,i+1,\dots,j-1\\}\subseteq{\bf o}$ and
$i-1,j\not\in{\bf o}$. Then, since $j-i-1$ numbers appear from the $j-i$
columns $h_{i},h_{i+1},\dots,h_{j}$, there is one middle square among them.
Furthermore, there is no descent in $(h_{i},h_{i+1},\dots,h_{j})$ by Lemma
4.22. Now, since $i-1\not\in{\bf o}$, Lemma 4.22 shows that $(h_{i-1},h_{i})$
is either a descent or two middle squares. The same holds for
$(h_{j},h_{j+1})$ as $j\not\in{\bf o}$. Thus, $(h_{i},\dots,h_{j})$ is a
pattern: it is weakly ascending with exactly one middle square, and $h_{i-1}$
and $h_{j+1}$ cannot be included. ∎

######  Lemma 4.25 (Multiplicity of Patterns).

Suppose that ${\bf h}=(h_{1},\dots,h_{n})$ is a history of the Three Rows Game
which is also a pattern (that is, it is weakly ascending with exactly one
middle square). Then $\mu({\bf h})=n$, and all the histories in $[{\bf h}]$
are also patterns.

###### Proof.

First, by Lemma 4.24, ${\bf h}^{\prime}\sim{\bf h}$ if and only if ${\bf
h}^{\prime}$ is also a pattern. Now, as previously discussed, patterns take
the following form:

|  |  |  |  | $\cdots$ |
---|---|---|---|---|---|---
|  |  |  |  |  |
| $\cdots$ |  |  |  |  |

That is, the first $k\in\\{0,1,\dots,n-1\\}$ squares are chosen in the bottom
row, the next square is chosen in the middle row, and the remaining squares
are chosen in the top row. Since there are $n$ options for $k$, this
demonstrates that there are $n$ possible patterns of length $n$, as desired. ∎

###  4.6. The Pattern Multiplicity Theorem and Consequences

######  Theorem 4.26 (Pattern Multiplicity Theorem).

Suppose that ${\bf h}$ is a history of the Three Rows Game with patterns ${\bf
p}_{1},\dots,{\bf p}_{k}$. Then $\mu({\bf h})=\ell({\bf p}_{1})\cdots\ell({\bf
p}_{k})$.

###### Proof.

First, notice that by Lemma 4.22 and 4.23, if ${\bf p}^{\prime}_{1},\dots,{\bf
p}^{\prime}_{k^{\prime}}$ are the prepatterns of ${\bf h}$, then $\mu({\bf
h})=\mu({\bf p}^{\prime}_{1})\cdots\mu({\bf p}^{\prime}_{k^{\prime}})$. Now,
if ${\bf p}^{\prime}_{i}$ is not a pattern, then it has no middle squares. But
then by Theorem 4.16 (Uniqueness of Maximal Outcomes), $\mu({\bf
p}^{\prime}_{i})=1$. In other words, we can drop all the terms of the product
corresponding to prepatterns which are not patterns; this demonstrates that
$\mu({\bf h})=\mu({\bf p}_{1})\cdots\mu({\bf p}_{k})$. On the other hand, if
${\bf p}_{i}$ is a pattern, then by Lemma 4.25, $\mu({\bf p}_{i})=\ell({\bf
p}_{i})$. Therefore, $\mu({\bf h})=\ell({\bf p}_{1})\cdots\ell({\bf p}_{k})$.
∎

Now we will restate our work in terms of Pak-Stanley labellings. The key here
is that patterns take the form $(0,1,\dots,1,0)$ in the Pak-Stanley label.

######  Corollary 4.27.

Suppose that ${\bf o}$ is an outcome. A run ${\bf r}$ of length $k$ in ${\bf
o}$ is a sequence of $k$ consecutive positive integers
$i,i+1,\dots,i+k-1\in[n-1]$ each appearing exactly once in ${\bf o}$ such that
$i-1,i+k\not\in{\bf o}$. If the length of a run ${\bf r}$ is denoted
$\ell({\bf r})$, the number of histories inducing ${\bf o}$ is

$\mu({\bf o})=\prod_{\text{runs ${\bf r}$ in ${\bf o}$}}(\ell({\bf r})+1).$

###### Proof.

This follows directly from Theorem 4.26 and Lemma 4.24. ∎

######  Theorem 4.28 (Path Multiplicity Theorem).

Suppose ${\bf p}=(p_{1},\dots,p_{n})$ is a Pak-Stanley label on $P_{n}$. A run
${\bf r}$ of length $n$ in ${\bf p}$ is a section of ${\bf p}$ of the form
$(0,1,\dots,1,0)$ with $n$ $1$s. If the length of a run ${\bf r}$ is denoted
$\ell({\bf r})$, then the multiplicity of the label ${\bf p}$ in in the
$P_{n}$-Shi arrangement is

$\mu({\bf p})=\prod_{\text{runs ${\bf r}$ in ${\bf p}$}}(\ell({\bf r})+1).$

###### Proof.

This follows directly from Corollary 4.27 and the connection between histories
and Pak-Stanley labellings; namely, an outcome ${\bf o}$ corresponds to the
Pak-Stanley label ${\bf p}$ given by letting coordinate $i$ of the Pak-Stanley
label equal the number of occurences of $i$ in ${\bf o}$. ∎

Using the Path Multiplicity Theorem, we can further explore the structure of
the Pak-Stanley labels of the $P_{n}$-Shi arrangement. Indeed, we give two
opposite results: a characterization of all the labels which appear only once,
and a characterization of the labels which appear the maximum number of times
(and how many times they appear). The former follows from the Path
Multiplicity Theorem (Theorem 4.28).

######  Corollary 4.29.

Suppose ${\bf p}=(p_{1},\dots,p_{n})$ is a $(P_{n})_{\bullet}$-parking
function. Then ${\bf p}$ appears uniquely as a Pak-Stanley label for $P_{n}$
if and only if, for every nonconsecutive pair of $0$s in ${\bf p}$, there is a
$2$ between the $0$s.

The latter is a little more difficult, and involves the following optimization
problem: if $n_{1},\dots,n_{k}$ are positive integers which add up to $n$,
what is the largest possible value of $n_{1}\cdots n_{k}$?

######  Lemma 4.30.

Suppose that $n>1$ is a positive integer. Let

$S(n)=\sup_{\begin{subarray}{c}n_{1},\dots,n_{k}\in\mathbb{Z}^{+}\\\
n_{1}+\cdots+n_{k}=n\end{subarray}}n_{1}\cdots n_{k}.$

Then,

  1. (1)

if $n\equiv 0\bmod 3$, then $S(n)=3^{n/3}$,

  2. (2)

if $n\equiv 1\bmod 3$, then $S(n)=3^{(n-4)/3}\cdot 2^{2}$,

  3. (3)

if $n\equiv 2\bmod 3$, then $S(n)=3^{(n-2)/3}\cdot 2$.

###### Proof.

If $n_{i}\geq 4$, then $n_{i}$ can be replaced by $n_{i}-2$ and $2$, which
have product $2n_{i}-4\geq n_{i}$. Thus, we may assume that
$n_{i}\in\\{2,3\\}$ for each $i$. But $3+3=2+2+2$ yet $3^{2}>2^{3}$, so there
will never be three $2$s among the $n_{i}$. The result then follows in each
case by inspection. ∎

Using this optimization result, we can compute the Pak-Stanley labels which
appear the most often.

######  Proposition 4.31.

Suppose that $n>2$. Then, the following holds.

  1. (1)

If $n\equiv 1\bmod 3$, then the unique Pak-Stanley label for $P_{n}$ which
appears most often is $0110110\cdots 110$, and it is repeated $3^{(n-1)/3}$
times.

  2. (2)

If $n\equiv 2\bmod 3$, then any of the ${(n+1)/3\choose 2}$ Pak-Stanley labels
for $P_{n}$ starting with a $0$ and then containing $(n-5)/3$ copies of $110$
and $2$ copies of $10$ (for example, $01010110\cdots 110$) in any order appear
most often, and they are repeated $2^{2}\cdot 3^{(n-5)/3}$ times.

  3. (3)

If $n\equiv 0\bmod 3$, then any of the $\frac{n}{3}$ Pak-Stanley labels for
$P_{n}$ starting with a $0$ and then containing $(n-3)/3$ copies of $110$ and
$1$ copy of $10$ (for example, $010110\cdots 110$) in any order appear most
often, and they are repeated $2\cdot 3^{(n-3)/3}$ times.

###### Proof.

This result follows from the fact that repetitions are created by patterns, so
to achieve a label which has maximum multiplicity, we should construct a label
made entirely out of patterns. Such a label starts with a $0$ which is
followed by a number of runs of the form $1\cdots 10$. The total length of all
of these runs (including the $0$s) is $n-1$, and the product of their lengths
(including the final $0$ in each one) is the desired quantity. Therefore, this
problem reduces to the problem in Lemma 4.30 of finding $S(n-1)$. ∎

Notice that not only do we know the number of vertices with the label ${\bf
p}$, we also know how to list all vertices with label ${\bf p}$. This gives us
the ability to easily iterate over all such vertices if we so desire. We
discuss this further in the next section.

###  4.7. Iterating Over Regions with a Fixed Label

In this section, we discuss two related problems: first, the problem of
listing all regions with a fixed label, and second, the problem of finding
where the regions with a fixed label are located.

######  Question 1.

Given a Pak-Stanley label ${\bf p}$ for $P_{n}$, how can we list the regions
of the $P_{n}$-Shi arrangement with label ${\bf p}$?

######  Example 4.32.

Given the Pak-Stanley label of a certain region, we may reconstruct the
history of the Three Rows Game to determine which choices are fixed. For
example, given the Pak-Stanley label $(0,1,1,0,2,0)$, we may determine that
the outcome was $\\{1,2,4,4\\}$. Since $4$ only appears twice in the Three
Rows Game, and appears twice in the outcome, the following two columns are
fixed:

0 | 1 | 2 | 3 | 4
---|---|---|---|---
|  |  |  |
1 | 2 | 3 | 4 | 5

Now, notice that $\\{1,2\\}$ is a run in the sense of Corollary 4.27, and
therefore corresponds to a pattern of length $3$. This yields the following
three options for the first three rows:

0 | 1 | 2 | 3 | 4
---|---|---|---|---
|  |  |  |
1 | 2 | 3 | 4 | 5

0 | 1 | 2 | 3 | 4
---|---|---|---|---
|  |  |  |
1 | 2 | 3 | 4 | 5

0 | 1 | 2 | 3 | 4
---|---|---|---|---
|  |  |  |
1 | 2 | 3 | 4 | 5

Figure 5. Enumerating possible histories for the outcome $\\{1,2,4,4\\}$.

This example illustrates the general strategy. First, convert the Pak-Stanley
label to an outcome of the Three Rows Game. Then, consider all the prepatterns
which are not patterns; as discussed in the proof of Theorem 4.26, these have
only one option, so we fix this option. Then, for each of the remaining
patterns ${\bf p}$, there are $\ell({\bf p})$ options of the following form:

|  | $\cdots$ |
---|---|---|---
|  |  |
|  |  |

$\cdots$ $\cdots$ $\cdots$ $\cdots$ $\cdots$

By listing every possible combination of choices for the patterns, we are able
to list all the possible histories; by converting the cells back into
inequalities, this gives us the desired list of regions with a fixed label.
Next, instead of finding a single region, we would like to determine the
following.

######  Question 2.

Given a Pak-Stanley label ${\bf p}$ for $P_{n}$, how can we find the minimal
convex union of regions containing all the regions with label ${\bf p}$?

The method for solving this problem is similar to the first problem. First, we
consider columns in which there is exactly one entry we can can choose
corresponding to satisfying exactly one inequality of the form
$x_{i}-x_{i+1}<0$ (top), $0<x_{i}-x_{i+1}<1$ (middle), or $x_{i}-x_{i+1}>1$
(bottom). Then, there are some columns in which we can either choose the
bottom or middle entry and yield inequalities of the form $x_{i}-x_{i+1}>0$.
Similarly, there are some columns in which we can either choose the middle or
top entry and yield inequalities of the form $x_{i}-x_{i+1}<1$. Lastly, in
columns in which we can choose any entry we obtain no inequalities.

######  Example 4.33.

Continuing Example 4.32, take the Pak-Stanley label $(0,1,1,0,2,0)$, which
corresponds to the outcome $\\{1,2,4,4\\}$. By “overlapping” the possible
histories in Figure 5, we obtain the following board of possibilities for each
column:

0 | 1 | 2 | 3 | 4
---|---|---|---|---
|  |  |  |
1 | 2 | 3 | 4 | 5
Figure 6. Minimal convex union of regions.

This yields the following list of inequalities, which gives the desired
minimal convex union of regions: $x_{0}-x_{1}>0$, $x_{2}-x_{3}<1$,
$x_{3}-x_{4}>1$, and $x_{4}-x_{5}<0$.

##  5\. Trees and the $T$-Three Rows Game

###  5.1. Defining the $T$-Three Rows Game

In this section, we introduce the $T$-Three Rows Game to generalize our
results from path graphs to tree graphs.

######  Definition 5.1 ($T$-Three Rows Game).

Let $T=(V,E)$ be a tree with $n$ vertices. The $T$-Three Rows Game is played
on a board with $n-1$ columns and 3 rows. Each column corresponds to an edge
$\\{i,j\\}$: the top square has an $i$, the middle square is blank, and the
bottom square has a $j$.

$0$$1$$3$$2$$4$$\Rightarrow$ 0 | 1 | 2 | 2
---|---|---|---
|  |  |
1 | 2 | 3 | 4

As in the original Three Rows Game, exactly one square is chosen from each
column of the board. Histories and outcomes are defined analogously.

The same analogy as for path graphs holds between vertices (resp. labels) in
the Shi adjacency digraph $\Gamma\mathscr{S}(T)$ and histories (resp.
outcomes) of the $T$-Three Rows Game. Again, each column of the board
corresponds to a pair of parallel hyperplanes, and our choice determines the
region’s relation to these hyperplanes. Because $T$ is acyclic, fixing any of
these inequalities does not fix any of the other inequalities, just as in the
case of the path graph. This yields a few basic properties:

######  Proposition 5.2.

Let $T$ be a tree with $n$ vertices. There are $3^{n-1}$ vertices and
$2^{n-1}$ sinks (which are all labelled with maximal $T$-parking functions) in
the Shi adjacency digraph of $T$.

######  Proposition 5.3.

Let $T$ be a tree. The multiplicities of the Pak-Stanley labels in the Shi
adjacency digraph of $T$ are independent of the vertex labelling up to
permutation.

###  5.2. Uniqueness of Maximal Outcomes

In this section, we generalize one of our main results of the previous
sections, uniqueness of maximal outcomes for path graphs, to all trees.

######  Theorem 5.4 (Uniqueness of Maximal Outcomes).

Any outcome ${\bf o}$ of the $T$-Three Rows Game on $n$ columns with $|{\bf
o}|=n$ has multiplicity $\mu({\bf o})=1$.

###### Proof.

Notice that we can label the vertices of $T$ (using a depth-first search, for
example) in such a way that each column in the $T$-Three Rows Game after the
first contains exactly one vertex that has already appeared on the board, and
exactly one vertex that has not appeared on the board.

Given an outcome ${\bf o}$, let $m_{{\bf o}}(i)$ denote the number of
occurrences of $i$ in ${\bf o}$. Then, define distance between outcomes as
follows:

$d({\bf o},{\bf o}^{\prime})=\sum_{i=0}^{n-1}|m_{\bf o}(i)-m_{{\bf
o}^{\prime}}(i)|.$

Now, suppose that ${\bf h}$ and ${\bf h^{\prime}}$ are two distinct histories
of the $T$-Three Rows Game such that $|{\bf o}({\bf h})|=|{\bf o}({\bf
h}^{\prime})|=n$. Then, the history ${\bf h^{\prime}}$ can be reached from
${\bf h}$ through a nonempty series of “swaps” (that is, choosing the bottom
square instead of the top, or the top square instead of the bottom) at some
indices $i_{1}<\dots<i_{k}$.

Yet the first swap $i_{1}$ increases the distance between ${\bf o}({\bf h})$
and ${\bf o}({\bf h^{\prime}})$ by 2, and every subsequent swap $i_{j}$ does
not decrease the distance between ${\bf o}({\bf h})$ and ${\bf o}({\bf
h^{\prime}})$. To see why, notice that each column of the board contains at
least one new vertex $v^{\prime}$ and one possibly old vertex $v$. Since this
is the first time $v^{\prime}$ appears, the swap “displaces” $v^{\prime}$, and
even if it “corrects” $v$, the distance is preserved. That is, after each
swap, the distance $d({\bf o}({\bf h}),{\bf o}({\bf h}^{\prime}))$ is
increased either by $0$ or $2$. Thus, if ${\bf h}\neq{\bf h^{\prime}}$, then
$d({\bf o}({\bf h}),{\bf o}({\bf h^{\prime}}))\geq 2$, and in particular ${\bf
o}({\bf h})\neq{\bf o}({\bf h^{\prime}})$. ∎

###  5.3. An Example: Star Graphs

In this section, we use the $T$-Three Rows Game to characterize the
multiplicity of Pak-Stanley labels in the Shi arrangement for star graphs.

The star graph $S_{n}$ is a tree on $n+1$ vertices with a central vertex $0$
and $n$ “spokes” $1,\dots,n$, all connected to the central vertex. Thus, the
$S_{n}$-Three Rows Game is played on the following board:

0 | 0 | 0 | $\cdots$ | 0 | 0
---|---|---|---|---|---
|  |  |  |  |
1 | 2 | 3 | $\cdots$ | $n-1$ | $n$

######  Proposition 5.5.

Let ${\bf p}$ be a Pak-Stanley label in the $S_{n}$-Shi arrangement, and let
$c_{0}$ (resp. $c_{\square}$) count the number of $0$s (resp. number of middle
$\square$s) in any history inducing the label. Then,

$\mu({\bf p})=\binom{c_{0}+c_{\square}}{c_{0}}.$

###### Proof.

For each nonzero element $i$ in the outcome, there is exactly one column in
the $S_{n}$-Three Rows Games where that element appears. The row choice is
fixed for those columns. Since 0 and $\square$ appear in all columns,
determining a history amounts to choosing $c_{0}$ columns out of the remaining
$c_{0}+c_{\square}$ unfixed columns to be 0 (leaving the remaining columns to
be $\square$). Hence $\mu({\bf p})=\binom{c_{0}+c_{\square}}{c_{0}}$. ∎

######  Proposition 5.6.

The number of distinct Pak-Stanley labels of $S_{n}$ is

$\sum_{S\subseteq\\{1,\ldots,n\\}}n+1-|S|=(n+2)\cdot 2^{n-1}.$

###### Proof.

Let $S_{\bf o}$ denote the set of non-zero elements of a given outcome ${\bf
o}$. As in the previous proof, for any nonzero value appearing in the outcome,
the corresponding column is fixed in the $S_{n}$-Three Rows Game. The
remaining $n-|S_{\bf o}|$ columns are unfixed and can either contain $0$ or
$\square$; this implies that for any “nonzero set”
$S\subseteq\\{1,\dots,n\\}$, there are $n+1-|S|$ distinct outcomes with said
nonzero set. Therefore, the total number of distinct outcomes (i.e. distinct
Pak-Stanley labels) is

$\displaystyle\sum_{S\subseteq\\{1,\ldots,n\\}}n+1-|S|$
$\displaystyle=(n+1)\cdot 2^{n}-n\cdot 2^{n-1}=(n+2)\cdot 2^{n-1}.$

∎

##  6\. Extending the Three Rows Game

###  6.1. Superstable Configurations on Cycle Graphs

First, we compute the number of superstable configurations on a cycle graph.
We begin with two easier determinant computations:

######  Proposition 6.1.

Let $M_{n}$ be the $n\times n$ matrix

$\begin{bmatrix}3&-1&0&\cdots&0&0&0\\\ -1&3&-1&\cdots&0&0&0\\\
0&-1&3&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&3&-1&0\\\ 0&0&0&\cdots&-1&3&-1\\\
0&0&0&\cdots&0&-1&3\end{bmatrix}.$

Then $\det(M_{n})=F_{2n+2}$ for any positive integer $n$.

###### Proof.

First, notice that $\det(M_{1})=3=F_{4}$ and $\det(M_{2})=8=F_{6}$. Therefore,
it suffices to establish that $\det(M_{n})=3\det(M_{n-1})-\det(M_{n-2})$ by
Lemma 4.1. By cofactor expansion along the top row twice,

$\displaystyle\det(M_{n})$
$\displaystyle=3\det(M_{n-1})+\begin{vmatrix}-1&-1&\cdots&0&0\\\
0&3&\cdots&0&0\\\ \vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&3&-1\\\
0&0&\cdots&-1&3\\\
\end{vmatrix}=3\det(M_{n-1})-\det(M_{n-2})+\begin{vmatrix}0&\cdots&0&0\\\
\vdots&\ddots&\vdots&\vdots\\\ 0&\cdots&3&-1\\\ 0&\cdots&-1&3\\\
\end{vmatrix}.$

It follows that $\det(M_{n})=3\det(M_{n-1})-\det(M_{n-2})$ as desired. ∎

######  Proposition 6.2.

Let $M^{\prime}_{n}$ be the $n\times n$ matrix

$\begin{bmatrix}0&-1&0&\cdots&0&0&0\\\ 0&3&-1&\cdots&0&0&0\\\
0&-1&3&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&3&-1&0\\\ 0&0&0&\cdots&-1&3&-1\\\
-1&0&0&\cdots&0&-1&3\end{bmatrix}.$

That is, $M^{\prime}_{n}$ has a -1 in the $nth$ row, first column, 3’s along
the diagonal in rows $2,\cdots,n$. It has $-1$’s along the superdiagonal,
$-1$’s along the subdiagonal in rows $3,\cdots,n$, and 0’s elsewhere. Then
$\det(M^{\prime}_{n})=-1$ for any positive integer $n$.

###### Proof.

Notice $\det(M^{\prime}_{1})=-1$. Furthermore, by cofactor expansion along the
top row,

$\det(M^{\prime}_{n})=\begin{vmatrix}0&-1&\cdots&0&0\\\ 0&3&\cdots&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&\cdots&3&-1\\\ -1&0&\cdots&-1&3\\\
\end{vmatrix}=\det(M^{\prime}_{n-1}).$

∎

Next, we have the following final determinant calculation:

######  Proposition 6.3.

Let $M^{\prime\prime}_{n}$ be the $n\times n$ matrix

$\begin{bmatrix}3&-1&0&\cdots&0&0&-1\\\ -1&3&-1&\cdots&0&0&0\\\
0&-1&3&\cdots&0&0&0\\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\
0&0&0&\cdots&3&-1&0\\\ 0&0&0&\cdots&-1&3&-1\\\
-1&0&0&\cdots&0&-1&3\end{bmatrix}.$

Then $\det(M^{\prime\prime}_{n})=3F_{2n}-2F_{2n-2}-2$.

###### Proof.

First, by cofactor expansion along the top row,

$\det(M^{\prime\prime}_{n})=3\det(M_{n-1})+\begin{vmatrix}-1&-1&0&\cdots&0&0\\\
0&3&-1&\cdots&0&0\\\ 0&-1&3&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\cdots&3&-1\\\
-1&0&0&\cdots&-1&3\\\
\end{vmatrix}+(-1)^{n}\begin{vmatrix}-1&3&-1&\cdots&0&0\\\
0&-1&3&\cdots&0&0\\\ 0&0&-1&\cdots&0&0\\\
\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\\ 0&0&0&\cdots&-1&3\\\
-1&0&0&\cdots&0&-1\\\ \end{vmatrix}.$

For the second $(n-1)\times(n-1)$ determinant, cofactor expansion along the
top row yields

$-\det(M_{n-2})+\det(M^{\prime}_{n-2})=-F_{2n-2}-1.$

For the third $(n-1)\times(n-1)$ determinant, cofactor expansion along the
first column yields

$\displaystyle-\begin{vmatrix}-1&3&\cdots&0&0&0\\\ 0&-1&\cdots&0&0&0\\\
\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\\ 0&0&\cdots&-1&3&-1\\\
0&0&\cdots&0&-1&3\\\ 0&0&\cdots&0&0&-1\end{vmatrix}+(-1)^{n-1}\det(M_{n-2}).$

Now, the remaining $(n-2)\times(n-2)$ determinant is an upper triangular
matrix, so its determinant can be computed as $(-1)^{n-2}$. Combining the
previous together, we get that the third $(n-1)\times(n-1)$ determinant is
$(-1)^{n-1}+(-1)^{n-1}\det(M_{n-2})=(-1)^{n-1}F_{2n-2}+(-1)^{n-1}$. Therefore,

$\det(M^{\prime\prime}_{n})=3\det(M_{n-1})-F_{2n-2}-1+(-1)^{n}((-1)^{n-1}F_{2n-2}+(-1)^{n-1})=3F_{2n}-2F_{2n-2}-2.$

∎

######  Theorem 6.4.

The number of superstable configurations of $(C_{n})_{\bullet}$ is
$3F_{2n}-2F_{2n-2}-2=F_{2n+2}-F_{2n-2}-2$.

###### Proof.

In the same vein as Theorem 4.4, this follows from the above determinant
calculation, and Theorem 4.2.2 of Klivans’ book in light of the definition of
the reduced Laplacian [5]. The equality follows from the second identity in
Lemma 4.1. ∎

######  Lemma 6.5 (Superstability Criterion for Cycle Graphs).

Let ${\bf a}\in\\{0,1,2\\}^{n}$. Consider the entries of ${\bf a}$ arranged on
a circle so that entries $a_{1}$ and $a_{n}$ are adjacent. Suppose ${\bf a}$
has 2-free blocks $\pi_{1},\pi_{2},\cdots,\pi_{m}$ so that $\pi_{1}=\pi_{m}$.
Then ${\bf a}$ is a superstable configuration on $(C_{n})_{\bullet}$ if and
only if there is a $0$ in each $2$-free block ${\bf\pi}_{i}$.

###### Proof.

The proof follows just as in Lemma 4.7. ∎

###  6.2. The Cyclical Three Rows Game

Next, we define the Cyclical Three Rows Game to analyze multiplicity in the
Pak-Stanley labels for the cycle graph $C_{n}$. The Cyclical Three Rows is
similar to the $T$-Three Rows Game with only a minor modification: the concept
of legal and illegal histories.

######  Definition 6.6 (Cyclical Three Rows Game).

The Cyclical Three Rows Game is played on the following board:

0 | 1 | 2 | $\cdots$ | $n-3$ | $n-2$ | 0
---|---|---|---|---|---|---
|  |  |  |  |  |
1 | 2 | 3 | $\cdots$ | $n-2$ | $n-1$ | $n-1$

As in the original Three Rows Game, exactly one square is chosen from each
column of the board, with outcomes and histories being defined analogously.
Furthermore, every choice except the final one is called a path choice, and
the final choice is called the cycle choice.

To understand the idea of legal and illegal histories we will consider an
example.

######  Example 6.7.

Consider the following history of the Cyclical Three Rows Game on $3$ columns:

0 | 1 | 0
---|---|---
|  |
1 | 2 | 2

If we convert this history into the sequence of corresponding inequalities, we
get the following:

$x_{0}-x_{1}<0\qquad x_{1}-x_{2}<0\qquad x_{0}-x_{2}>1.$

However, the first two inequalities yield $x_{0}-x_{2}<0$, a contradiction to
the last inequality. Therefore, this history determines a region which does
not exist. This is the core idea of illegal histories: because the analogy
between histories and regions breaks down, we define a particular class of
histories, “legal histories”, which do preserve this analogy.

######  Definition 6.8 (Legal History).

A legal history (of the Cyclical Three Rows Game) is a history such that, when
the history is converted to a list of inequalities defining a region using the
following rules, the region is nonempty (that is, the system of inequalities
can be solved):

  1. (1)

A choice of the form  $i$ $j$ is converted to the inequality $x_{i}-x_{j}<0$.

  2. (2)

A choice of the form  $i$ $j$ is converted to the inequality
$0<x_{i}-x_{j}<1$.

  3. (3)

A choice of the form  $i$ $j$ is converted to the inequality $x_{i}-x_{j}>1$.

An illegal history is a history of the Cyclical Three Rows Game which is not
legal.

Next, let us provide an alternate classification of legal histories.

######  Proposition 6.9 (Classification of Legal Histories).

Let “$T$” denote the top choice, “$M$” denote the middle choice, and “$B$”
denote the bottom choice, so that a history of the Cyclical Three Rows Game on
$n$ columns is a tuple ${\bf h}=\\{T,M,B\\}^{n}$. Then, a history ${\bf
h}\in\\{T,M,B\\}^{n}$ of the Cyclical Three Rows Game is a legal history if
and only if it follows these three rules:

  1. (1)

If all of the path choices are $T$, the cycle choice must be $T$.

  2. (2)

If all of the path choices are $T$ except for one $M$, the cycle choice cannot
be $B$.

  3. (3)

If all of the path choices are $M$ or $B$, the cycle choice must be $B$ unless
every path choice is $M$ (in which case the cycle choice can also be $M$).

###### Proof.

There are a few insights which make our casework simpler. Firstly, notice that
the path choices are independent, so it suffices to determine when particular
cycle choices are impossible. Secondly, if $T$ and $B$ both occur as path
choices, then the remaining path choices cannot be used to create an
inequality that restricts the cycle choice. This leaves us with the following
cases:

  1. (1)

All of the path choices are $T$.

  2. (2)

All of the path choices are $T$ or $M$.

  3. (3)

All of the path choices are $M$.

  4. (4)

All of the path choices are $M$ or $B$.

  5. (5)

All of the path choices are $B$.

In the first case, notice that by summing the series of inequalities given by
all of our path choices being $T$, namely
$x_{0}-x_{1}<0,x_{1}-x_{2}<0,\dots,x_{n-2}-x_{n-1}<0$, we achieve the
inequality $x_{0}-x_{n-1}<0$. This forces the cycle choice to be $T$. In the
second case, notice that if there are at least two $M$s, then the cycle choice
can be $T$, $M$, or $B$. Therefore, the only interesting case is that of a
single $M$; in this case, the cycle choice can be $T$ or $M$, but not $B$. In
the third case, notice that the cycle choice can be $M$ or $B$ but not $T$. In
the fourth and fifth cases, notice that if all the path choices are $M$ or
$B$, and there is at least one $B$, then the cycle choice must be $B$.
Reorganizing gives us the list of three rules in the statement of the theorem,
as desired. ∎

This classification allows us to deduce the following facts:

######  Corollary 6.10.

There are $2^{n}-2$ sinks in the Shi adjacency graph of $C_{n}$.

###### Proof.

The Classification of Legal Histories demonstrates that whenever there is an
$M$ in a legal history, it can be transformed into a $T$ or a $B$ (and
sometimes both) to result in another legal history. In other words, the sinks
correspond to the legal histories without $M$s. Now, there are $2^{n}$ such
histories, and the Classification of Legal Histories demonstrates that there
are two illegal ones: $T\cdots TB$ and $B\cdots BT$. This leaves $2^{n}-2$
such legal histories. ∎

######  Corollary 6.11.

There are $3^{n}-2^{n}-n$ legal histories of the Cyclical Three Rows Game on
$n$ columns; in particular, there are $3^{n}-2^{n}-n$ regions in the
$C_{n}$-Shi arrangement.

###### Proof.

This follows from simple counting. There are $3^{n}$ histories of the Cyclical
Three Rows Game. The first rule yields $2$ illegal histories, the second rule
yields $n-1$ illegal histories, and the third rule yields $2^{n-1}\cdot 2-1$
illegal histories for a total of $2+(n-1)+(2^{n}-1)=2^{n}+n$ illegal
histories. ∎

Finally, our classification of the illegal histories in the Cyclical Three
Rows Game, in conjunction with Theorem 4.26, can be used to give a method for
computing the set of regions $\mathscr{R}$ which give rise to a given Pak-
Stanley label for $C_{n}$, as follows:

  1. (1)

Given a Pak-Stanley label ${\bf p}$ for $C_{n}$, convert it to an outcome
${\bf o}$ of the Cyclical Three Rows Game on $n$ columns.

  2. (2)

Using the Pattern Multiplicity Theorem, enumerate the histories of the Three
Rows Game on $n-1$ columns inducing ${\bf o}$. Check which of these path
choices are legal when a cycle choice $M$ is appended. Convert the ones which
pass back into regions and add them to $\mathscr{R}$.

  3. (3)

If ${\bf o}$ has a $0$, create a new outcome ${\bf o}^{\prime}$ which is
identical to ${\bf o}$ with one less $0$. Then, using the Pattern Multiplicity
Theorem, enumerate the histories of the Three Rows Game on $n-1$ columns
inducing ${\bf o}^{\prime}$. Check which of these path choices are legal when
a cycle choice $T$ is appended. Convert the ones which pass back into regions
and add them to $\mathscr{R}$.

  4. (4)

If ${\bf o}$ has an $n-1$, create a new outcome ${\bf o}^{\prime\prime}$ which
is identical to ${\bf o}$ with one less $n-1$. Then, using the Pattern
Multiplicity Theorem, enumerate the histories of the Three Rows Game on $n-1$
columns inducing ${\bf o}^{\prime\prime}$. Check which of these path choices
are legal when a cycle choice $B$ is appended. Convert the ones which pass
back into regions and add them to $\mathscr{R}$.

The final list $\mathscr{R}$ will contain precisely those regions of $C_{n}$
with the Pak-Stanley label ${\bf p}$. This procedure is not quite as simple as
it is for the Three Rows Game, but it can be done with only a slight slowdown,
and is certainly much better than a naive search.

###  6.3. Defining the $G$-Three Rows Game

The $G$-Three Rows Game combines the lessons from studying the $T$-Three Rows
Game and the Cyclical Three Rows Game into a single concept which subsumes
both of them.

######  Definition 6.12 ($G$-Three Rows Game).

Suppose that $G$ is a graph with $n$ vertices and $m$ edges. Then, the
$G$-Three Rows Game is played on $m$ columns and $3$ rows. Each column
corresponds to an edge $\\{i,j\\}$; the top square has an $i$, the middle
square is blank, and the bottom square has a $j$. Subsequent definitions,
including (legal and illegal) histories, outcomes, multiplicity, and so on are
defined analogously.

Immediately, there are a few open problems which we have yet to answer (either
with an efficient algorithm or a formula):

######  Problem 1.

Given a graph $G$, how many legal histories of the $G$-Three Rows Game that do
not use the middle square are there?

######  Problem 2.

Given a graph $G$, how many legal histories of the $G$-Three Rows Game are
there?

######  Problem 3.

Given a legal history ${\bf h}$ of the $G$-Three Rows Game, what is $\mu({\bf
h})$?

The last two questions correspond to the problems of (1) determining the
number of regions in the $G$-Shi arrangement and (2) determining the number of
times a given $G_{\bullet}$-parking functions appears as a Pak-Stanley label
of said regions, respectively. However, despite the fact that these
fundamental questions (among others) are still open, we are able to prove an
interesting fact about the $G$-Three Rows Game: every maximal outcome appears
uniquely.

###  6.4. Uniqueness of Maximal Outcomes

In this section, we give a proof of uniqueness for maximal outcomes in the
$G$-Three Rows Game, analogous to the proofs of uniqueness of maximal outcomes
in the $T$-Three Rows Game and ordinary Three Rows Game given earlier. This
theorem generalizes both of those facts.

######  Proposition 6.13.

Suppose that $G$ is a graph with $m$ edges and ${\bf h}$ is a history of the
$G$-Three Rows Game. Then ${\bf o}$ is a maximal outcome (i.e. corresponds to
a maximal $G_{\bullet}$-parking function ${\bf p}$) if and only if ${\bf h}$
does not ever choose the middle square.

###### Proof.

By Proposition 2.21 and Theorem 2.16, ${\bf p}$ is maximal if and only if
$|{\bf o}|=m$ if and only if we choose a square with a number (as opposed to a
middle square, which has no number) in each column of the $G$-Three Rows Game.
∎

######  Theorem 6.14.

Let $G$ be a graph and ${\bf o}$ a maximal outcome of the $G$-Three Rows Game.
Then $\mu({\bf o})=1$.

###### Proof.

Suppose ${\bf h}$ is a legal history of the $G$-Three Rows Game with maximal
outcome ${\bf o}$, and ${\bf h}^{\prime}$ is another history with ${\bf
h}^{\prime}\sim{\bf h}$. Since ${\bf o}$ is maximal, both ${\bf h}$ and ${\bf
h}^{\prime}$ only use the top and bottom rows, so ${\bf h}$ can be transformed
into ${\bf h}^{\prime}$ by a sequence of “swaps” from a top choice to a bottom
choice and vice versa. Since ${\bf h}\neq{\bf h}^{\prime}$, there is at least
one swap, say $a_{1}\to a_{2}$. Then the region $R$ corresponding to ${\bf
h}^{\prime}$ satisfies $x_{a_{1}}>x_{a_{2}}$. Yet now $a_{2}$ appears too many
times in ${\bf o}({\bf h}^{\prime})$, so there must be another swap $a_{2}\to
a_{3}$ (so $R$ satisfies $x_{a_{2}}>x_{a_{3}}$). Now $a_{3}$ appears too many
times in ${\bf o}({\bf h}^{\prime})$, so there must be another swap $a_{3}\to
a_{4}$, and so on. Since there are only finitely many possible swaps,
$a_{i}=a_{j}$ for some $i<j$. But then $R$ satisfies the unsolvable sequence
of inequalities $x_{a_{i}}>x_{a_{i+1}}>\cdots>x_{a_{j}}=x_{a_{i}}$, so $R$ is
empty and ${\bf h}^{\prime}$ is illegal, as desired. ∎

######  Corollary 6.15.

Let $G$ be a graph and ${\bf p}$ a maximal $G_{\bullet}$-parking function.
Then $\mu({\bf p})=1$.

However, this raises a question which is particular to our new, generalized,
situation. For it is still clear that if $v$ is labelled with a maximal
$G_{\bullet}$-parking function, then $v$ is a sink of the Shi adjacency
digraph, but the converse is no longer clear. The existence and prevalence of
illegal histories means that it is not clear that we can always “eliminate any
occurrence of blank middle squares”; as a result, it is not clear that every
sink of the Shi adjacency digraph of $G$ is labelled with a maximal
$G_{\bullet}$-parking function. This is our final open problem:

######  Problem 4.

If $G$ is an arbitrary graph, is every sink of the Shi adjacency digraph of
$G$ labelled with a maximal $G_{\bullet}$-parking function?

##  7\. Conclusion

There is still much to discover about the nature of multiplicities in the Pak-
Stanley labels of $G$-Shi arrangements. In particular, a better understanding
of the ways that cycles interact could lead to solutions to the open problems
discussed in Section 6.3. Even in the acyclic case, there is much room to
study different classes of trees or find a fast algorithms for playing the
$T$-Three Rows Game for all trees. Nonetheless, our work provides the first
step towards understanding the complicated relationship between
$G_{\bullet}$-parking functions, superstable configurations, and regions in
the $G$-Shi arrangement provides by the Pak-Stanley algorithm, and we hope
that it encourages further interest in the topic.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant No. DMS-1929284 while the authors were in residence at the
Institute for Computational and Experimental Research in Mathematics (ICERM)
in Providence, RI, during the Summer@ICERM program. The authors would like to
thank the Summer@ICERM program for bringing us together to work on this
project and ICERM for hosting us as we completed our research. We also thank
Pamela E. Harris and Susanna Fishel for their mentorship and guidance.

## References

  * [1] Christos A. Athanasiadis and Svante Linusson  “A simple bijection for the regions of the Shi arrangement of hyperplanes” Selected papers in honor of Henry W. Gould  In _Discrete Mathematics_ 204.1, 1999, pp. 27–39  DOI: https://doi.org/10.1016/S0012-365X(98)00365-3
  * [2] Art Duval, Caroline Klivans and Jeremy Martin  “The G-Shi arrangement, and its relation to G-parking functions”, 2011  URL: http://www.math.utep.edu/Faculty/duval/papers/nola.pdf
  * [3] Susanna Fishel  “A survey of the Shi arrangement”  In _Recent trends in algebraic combinatorics_ 16, Assoc. Women Math. Ser.  Springer, Cham, 2019, pp. 75–113  DOI: 10.1007/978-3-030-05141-9“˙3
  * [4] Sam Hopkins and David Perkinson  “Bigraphical Arrangements ”  In _Transactions of the AMS_ American Mathematical Society, 2018  URL: https://www.ams.org/journals/tran/2016-368-01/S0002-9947-2015-06341-7/S0002-9947-2015-06341-7.pdf
  * [5] Caroline J. Klivans  “The Mathematics of Chip-Firing”  ChapmanHall/CRC, 2018
  * [6] R.P. Stanley  “Hyperplane arrangements, interval orders, and trees”  In _Proceedings of the NAS_ 93.6, 1996, pp. 2620–2625  DOI: 10.1073/pnas.93.6.2620

##  Appendix A Computational Tools for Analyzing Shi Adjacency Graphs

###  A.1. Method Descriptions

The G_Shi class takes in a Graph object and uses it to generate the Shi
adjacency digraph and Pak-Stanley labels. In this section, we will describe
the functionality of some of the primary methods.

  * •

make_adjacency_graph()

Returns the undirected Shi adjacency graph.

This function creates a list of the visited and unvisited regions in the
$G$-Shi arrangement. It then iterates through the unvisited regions list, and
checks which visited regions the unvisited region is adjacent to. Each pair of
adjacent regions is stored in a list. A graph is created with the list of all
regions as vertices, and the list of adjacent regions as edges.

Example:

⬇

G = graphs.CompleteGraph(3)

Q = G_Shi(G)

adjacency_graph = Q.make_adjacency_graph()

adjacency_graph.show(spring=True, vertex_labels=False)

Output:

  * •

make_adjacency_digraph()

Returns the Shi adjacency digraph.

This function iterates through the edges of the undirected Shi adjacency graph
and creates a list of directed edges. For each undirected edge, it directs the
new edge depending on the relative position of the base region. It creates and
returns a digraph using the original vertices and a new list of directed
edges.

Example:

⬇

G = graphs.CompleteGraph(3)

Q = G_Shi(G)

adjacency_digraph = Q.make_adjacency_digraph()

adjacency_digraph.show(spring=True, vertex_labels=False)

Output:

  * •

assign_edge_labels()

Returns a dictionary with the edges and edge labels.

This helper method iterates through the edges of the Shi adjacency digraph and
assigns a label to each edge. If the edge corresponds to the hyperplane
$x_{i}-x_{j}=0$, the edge is labelled $i$. If the edge corresponds to the
hyperplane $x_{i}-x_{j}=1$, the edge is labelled $j$.

  * •

make_pak_stanley_labels()

Returns a dictionary with the regions and Pak-Stanley labels.

This helper method iterates through the vertices of the Shi adjacency digraph
and assigns a label to each vertex using the Pak-Stanley algorithm.

  * •

make_pak_stanley_graph_of_regions()

Returns the Shi adjacency digraph with Pak-Stanley labels on the vertices.

This function creates the Shi adjacency digraph and assigns a label to each
edge in the graph. To avoid issues with repeated labels, it uses the inner
class AdvancedVertex to replace the existing vertices.

Example:

⬇

G = graphs.CompleteGraph(3)

Q = G_Shi(G)

pak_stanley_graph = Q.make_pak_stanley_graph_of_regions()

pak_stanley_graph.show(spring=True)

Output:

  * •

count_labels()

Returns a dictionary with the number of occurrences of each Pak-Stanley label.

This function iterates through the list of Pak-Stanley labels and adds one to
the count for each occurrence of a given label.

Example:

⬇

G = graphs.CompleteGraph(3)

Q = G_Shi(G)

print(Q.count_labels())

Output:

{(0, 0, 0): 1, (0, 0, 1): 1, (0, 1, 0): 1, (1, 0, 0): 1, (1, 1, 0): 1, (0, 2,
0): 1, (2, 1, 0): 1, (1, 2, 0): 1, (0, 0, 2): 1, (0, 1, 1): 1, (0, 2, 1): 1,
(0, 1, 2): 1, (1, 0, 2): 1, (2, 0, 0): 1, (1, 0, 1): 1, (2, 0, 1): 1}

###  A.2. Code

Displayed below is our code for the G_Shi class.

⬇

class G_Shi:

def init(self, graph):

"""Initializes an instance of the class for a given graph."""

self.arrangement = hyperplane_arrangements.G_Shi(graph)

self.regions = self.arrangement.regions()

self.n = len(self.regions[0].vertices()[0])

self.base_region = self.find_base_region()

self.graph_of_regions = self.make_adjacency_graph()

self.digraph_of_regions = self.make_adjacency_digraph()

self.pak_stanley_edge_labels = self.assign_edge_labels()

self.pak_stanley_labels = self.make_pak_stanley_labels()

self.pak_stanley_graph_of_regions = self.make_pak_stanley_graph_of_regions()

self.label_count = self.count_labels()

def is_base_region(self, region):

"""Checks if this region is the base region."""

return region.contains(((self.n - i) / self.n for i in range(self.n)))

def find_base_region(self):

"""Uses is_base_region to find and return the base region."""

for region in self.regions:

if self.is_base_region(region):

return region

return False

def share_face(self, region1, region2):

"""Checks if two regions share a face."""

if self.arrangement.distance_between_regions(region1, region2) == 1:

return True

return False

def make_adjacency_graph(self):

"""Creates the undirected Shi adjacency graph."""

unvisited_regions = list(self.regions)

unvisited_regions.remove(self.base_region)

vertices = [self.base_region]

edges = []

# Iterate through all of the regions in the arrangement

while unvisited_regions:

for region in unvisited_regions:

for vertex in vertices:

# Check if two regions are adjacent

if self.share_face(region, vertex):

if region not in vertices:

unvisited_regions.remove(region)

vertices.append(region)

edges.append((vertex, region))

return Graph([vertices, edges])

def boundary_inequality(self, region1, region2):

"""Returns the inequality which divides two adjacent regions, or False if no
such inequality exists."""

for ineq1 in region1.inequalities():

for ineq2 in region2.inequalities():

if ineq1.A() == -1 * ineq2.A() and ineq1.b() == -1 * ineq2.b():

return ineq1

return False

def make_adjacency_digraph(self):

"""Creates the Shi adjacency digraph."""

# Initialize the graph

initial_graph = self.graph_of_regions

vertices = initial_graph.vertices()

undirected_edges = initial_graph.edges()

directed_edges = []

# Define the base point to be used to find the location of the base region

base_point = vector((self.n - i) / self.n for i in range(self.n))

# Direct the edges

for edge in undirected_edges:

inequality = self.boundary_inequality(edge[0], edge[1])

if inequality.eval(base_point) >= 0:

directed_edges.append((edge[0], edge[1]))

else:

directed_edges.append((edge[1], edge[0]))

return DiGraph([vertices, directed_edges])

def assign_edge_labels(self):

"""Finds the index that is incremented along each edge in the Shi adjacency
digraph."""

digraph = self.digraph_of_regions

edges = digraph.edges()

edge_labels = {}

# Label each edge depending on the corresponding inequality

for edge in edges:

inequality = self.boundary_inequality(edge[0], edge[1])

if inequality.b() == 0:

for i in range(len(inequality.A())):

if inequality.A()[i] != 0:

edge_labels[edge] = i

break

else:

for i in range(len(inequality.A())):

if inequality.A()[len(inequality.A()) - 1 - i] != 0:

edge_labels[edge] = len(inequality.A()) - 1 - i

break

return edge_labels

def make_pak_stanley_labels(self):

"""Assigns Pak-Stanley labels to vertices of the Shi adjacency digraph."""

digraph = self.digraph_of_regions

unvisited_vertices = digraph.vertices()

unvisited_vertices.remove(self.base_region)

vertex_labels = {self.base_region: [0] * self.n}

new_vertices = [self.base_region]

# Assign the labels iterating outwards using a breadth-first traversal of the
graph

while unvisited_vertices:

for vertex in new_vertices:

new_vertices.remove(vertex)

for edge in digraph.outgoing_edges(vertex):

if edge[1] in unvisited_vertices:

vertex_labels[edge[1]] = vertex_labels[edge[0]].copy()

vertex_labels[edge[1]][self.pak_stanley_edge_labels[edge]] += 1

new_vertices.append(edge[1])

unvisited_vertices.remove(edge[1])

for vertex in vertex_labels:

vertex_labels[vertex] = tuple(vertex_labels[vertex])

return vertex_labels

def make_pak_stanley_graph_of_regions(self):

"""Creates the Shi adjacency digraph with Pak-Stanley vertex labels."""

class AdvancedVertex(tuple):

def __init__(self, v):

self.vertex = v

def str(self):

return str(self.vertex[-1])

digraph = self.digraph_of_regions

# Create basic graph with non-injective vertex labels

vertices = [AdvancedVertex((vertex, self.pak_stanley_labels[vertex])) for
vertex in digraph.vertices()]

edges = [(AdvancedVertex((edge[0], self.pak_stanley_labels[edge[0]])),
AdvancedVertex((edge[1], self.pak_stanley_labels[edge[1]]))) for edge in
digraph.edges()]

graph = DiGraph([vertices, edges])

# Add edge labels

for edge in digraph.edges():

graph.set_edge_label(AdvancedVertex((edge[0],
self.pak_stanley_labels[edge[0]])), AdvancedVertex((edge[1],
self.pak_stanley_labels[edge[1]])), self.pak_stanley_edge_labels[edge])

return graph

def count_labels(self):

"""Counts the number of occurrences of each Pak-Stanley label."""

labels = [tuple(label) for label in self.pak_stanley_labels]

counter = {}

for label in labels:

if label in counter:

counter[label] += 1

else:

counter[label] = 1

return counter

##  Appendix B Computing Superstable Configurations for $P_{n}$

In this section, we detail another proof of Theorem 4.4. First, we establish a
basic identity of Fibonacci numbers to be used later.

######  Lemma B.1 (Even Fibonacci Numbers).

Let $F_{n}$ denote the $n$th Fibonacci number. Then,

$F_{2n}=2F_{2n-2}+F_{2n-4}+F_{2n-6}+\cdots+F_{4}+2F_{2}.$

for any positive integer $n$.

###### Proof.

This result follows by repeated application of the identity
$F_{n}=F_{n-1}+F_{n-2}$; indeed,

$\displaystyle F_{2n}$
$\displaystyle=F_{2n-1}+F_{2n-2}=2F_{2n-2}+F_{2n-3}=2F_{2n-2}+F_{2n-4}+F_{2n-5}$
$\displaystyle=2F_{2n-2}+F_{2n-4}+\cdots+F_{4}+F_{3}=2F_{2n-2}+F_{2n-4}+\cdots+F_{4}+2F_{2}$

where the penultimate equality comes from repeated application of the
recurrence relation to the smallest Fibonacci number remaining, and the final
equality comes from $F_{3}=2=2F_{2}$. ∎

The essential idea of this proof is that if a sequence $\\{a_{n}\\}$ satisfies
the initial condition $a_{1}=F_{2}$ and the recurrence
$a_{n}=2a_{n-1}+a_{n-2}+\cdots+a_{2}+2a_{1}$, then necessarily we have
$a_{n}=F_{2n}$. This fact follows from Lemma B.1.

######  Theorem B.2.

The number of superstable configurations of $(P_{n})_{\bullet}$ is $F_{2n}$
for any positive integer $n$.

###### Proof.

Let $s_{n}$ denote the number of superstable configurations of
$(P_{n})_{\bullet}$. Then $s_{1}=1=F_{2}$; the only superstable configuration
on $(P_{1})_{\bullet}$ is $(0)$. Therefore, it suffices to establish the
recurrence $s_{n}=2s_{n-1}+s_{n-2}+\cdots+s_{2}+2s_{1}.$

For this, we will partition the collection of superstable configurations. Say
that a superstable configuration ${\bf a}=(a_{1},\dots,a_{n})$ belongs to
bucket $i$ if $i$ is the largest non-negative integer strictly less than $n$
such that $(a_{1},\dots,a_{i})$ is a superstable configuration on
$(P_{i})_{\bullet}$. Then, we will show that (1) there are $2s_{n-1}$
configurations in bucket $n-1$, (2) there are $s_{i}$ configurations in bucket
$i$ for $i\in\\{1,\dots,n-2\\}$, and (3) there are $s_{1}=1$ configurations in
bucket $0$. This suffices to establish the recurrence relation, so we will
prove these facts now:

(1): Suppose that ${\bf a}=(a_{1},\dots,a_{n})$ is a superstable configuration
belonging to bucket $n-1$. Then there are $s_{n-1}$ options for
$(a_{1},\dots,a_{n-1})$. By the Superstability Criterion, we cannot have
$a_{n}=2$ but choosing $a_{n}=0$ or $a_{n}=1$ results in a superstable
configuration regardless of which superstable configuration is chosen for
$(a_{1},\dots,a_{n-1})$). Therefore, there are $2s_{n-1}$ configurations in
this bucket.

(2): Suppose that ${\bf a}=(a_{1},\dots,a_{n})$ is a superstable configuration
belonging to bucket $i$ for some $i\in\\{1,\dots,n-2\\}$. In particular,
$(a_{1},\dots,a_{i})$ is superstable but $(a_{1},\dots,a_{i+1})$ is not. Now,
by the Superstability Criterion, we must have $a_{i+1}=2$. Then, there cannot
exist any $j>i+1$ with $a_{j}=2$, since then by the Superstability Criterion
there would exist a $0$ between $a_{i+1}$ and $a_{j}$ and then
$(a_{1},\dots,a_{j-1})$ is a superstable configuration. Yet since $j-1>i$,
this contradicts the fact that ${\bf a}$ belongs to bucket $i$. Similarly,
there cannot exist any $i+1<j<n$ with $a_{j}=0$, since then by the
Superstability Criterion $(a_{1},\dots,a_{j})$ is a superstable configuration,
a contradiction for the same reason. Thus, $a_{i+2},\dots,a_{n-1}=1$, and the
Superstability Criterion forces $a_{n}=0$. In summary, superstable
configurations in bucket $i$ are uniquely determined by the superstable
configuration consisting of their first $i$ entries. Therefore, there are
$s_{i}$ configurations in this bucket.

(3): Suppose that ${\bf a}=(a_{1},\dots,a_{n})$ is a superstable configuration
belonging to bucket $0$. Now, $a_{1}$ cannot be $2$ (since then ${\bf a}$ is
not superstable), but in fact there cannot exist any $i>1$ with $a_{i}=2$. To
see why, notice that by the Superstability Criterion there would exist a $0$
before $a_{i}$ and then $(a_{1},\dots,a_{i-1})$ would be superstable, a
contradiction with the fact that ${\bf a}$ belongs to bucket $0$. Thus ${\bf
a}$ consists of only $0$s and $1s$. Yet then there cannot exist any $i<n$ with
$a_{i}=0$, as then by the Superstability Criterion $(a_{1},\dots,a_{i})$ is
superstable, a contradiction for the same reason. On the other hand, the
Superstability Criterion requires that there is at least one zero. This forces
${\bf a}=(1,\dots,1,0)$, so there is a unique such configuration as desired. ∎