REPETITIONS OF PAK-STANLEY LABELS IN G-SHI ARRANGEMENTS CARA BENNETT LUCY MARTINEZ AVA MOCK GORDON ROJAS KIRBY AND ROBIN TRUAX Abstract. Given a simple graph G one can dene a hyperplane arrangement called the G-Shi

2025-04-29 0 0 624.39KB 34 页 10玖币

侵权投诉

REPETITIONS OF PAK-STANLEY LABELS IN G-SHI ARRANGEMENTS

CARA BENNETT, LUCY MARTINEZ, AVA MOCK, GORDON ROJAS KIRBY, AND ROBIN TRUAX

Abstract.

Given a simple graph

, one can deﬁne a hyperplane arrangement called the

-Shi

arrangement. The Pak-Stanley algorithm labels the regions of this arrangement with

G•

-parking

functions. When

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⊂Kn

while the Pak-Stanley labels still include every

G•

-parking function, some appear more than once.

These repetitions of Pak-Stanley labels are a topic of interest in the study of

-Shi arrangements and

G•

-parking functions. Furthermore,

G•

-parking functions are connected to many other combinatorial

objects (for example, superstable conﬁgurations in chip-ﬁring). 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 classiﬁcation theorem for the multiplicities of the Pak-Stanley labels of the regions in the

-Shi arrangement, where

is the path graph on

vertices. Then, we generalize the Three Rows

Game into the

-Three Rows Game. This allows us to study the multiplicities of the Pak-Stanley

labels of the regions in

-Shi arrangements, where

is any tree. Finally, we discuss the possibilities

and diﬃculties in applying our method to arbitrary graphs. In particular, we analyze multiplicities

in the case when

is a cycle graph, and prove a uniqueness result for maximal

G•

-parking functions

for all graphs using the Three Rows Game.

1. Introduction

Ahyperplane in

is an aﬃne subspace of dimension

n−

1. A hyperplane arrangement is a collection

of ﬁnitely many hyperplanes. Given a hyperplane arrangement

, its complement

Rn\SH∈A H

splits into connected components called regions. The focus of this paper is on the combinatorial

properties of the regions of the

-Shi arrangement and their labels by

G•

-parking functions, as

deﬁned by Duval, Klivans, and Martin [2]. The

-Shi arrangement

(

) is deﬁned for any graph

G= (V, E) by

S(G) = {xi−xj= 0,1| {i, j} ∈ Ewith i<j}.

When

, the

-Shi arrangement is the Shi arrangement, which has (

+ 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

, a

natural problem is to ﬁnd a bijection between regions of the Shi arrangement and parking functions

of length

. Pak and Stanley (1996) and Athanasiadis and Linusson (1999) gave two such bijections

[6],[1]. The Pak-Stanley algorithm, deﬁned later, labels the regions of the

-Shi arrangement with

G•

-parking functions in such a way that every

G•

-parking function appears. When

is complete,

each

G•

-parking function appears exactly once as a Pak-Stanley label on a region of the

-Shi

arrangement. If

is not complete, some

G•

-parking functions appear more than once as Pak-Stanley

labels in the

-Shi arrangement. Consider the examples of

and

in Figures 1a and

1b respectively.

Date: October 26, 2022.

arXiv:2210.13613v1 [math.CO] 24 Oct 2022

(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 K3-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 P3-Shi arrangement.

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

Figures 1a and 1b depict

-Shi arrangements. Notice that on the left, each label appears once

(has multiplicity 1), but on the right, the label (0

0) appears twice (has multiplicity 2). In this

paper, we work towards a characterization of the “multiplicities” of the Pak-Stanley labels in

-Shi

arrangements by introducing a combinatorial model called the Three Rows Game deﬁned in Section

4.2

In Section 3, we introduce the Shi adjacency digraph to describe the adjacencies of regions in the

-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

-Shi arrangements for path graphs

. 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

= (

p1, . . . , pn

) is a Pak-Stanley label of a region

(

). A run

of length

is a section of

of the form (0

,...,

0) with

1s. If the

length of a run

is denoted

(

), then the multiplicity of the label

in in the

-Shi arrangement is

µ(p) = Y

runs rin p

(`(r) + 1).

Besides analyzing path graphs, we also study multiplicities of Pak-Stanley labels in

-Shi arrange-

ments 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

-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 Gbe a graph and pa maximal G•-parking function. Then phas multiplicity 1.

2. Background

We begin with a discussion of some prerequisite topics: the

-Shi arrangement, the Pak-Stanley

algorithm, chip-ﬁring, and superstable conﬁgurations. An important note is that for the remainder

of the paper, all of our graphs are assumed to be connected, ﬁnite, and simple.

2.1.

The G-Shi Arrangement and the Pak-Stanley Algorithm.

First, we formally deﬁne the

G-Shi arrangement.

Deﬁnition 2.1

(Shi Arrangement)

The Shi arrangement

is the hyperplane arrangement in

with hyperplanes xi−xj= 0 and xi−xj= 1 for each i, j ∈ {0,1,2, . . . , n −1}with i<j.

Deﬁnition 2.2

(

-Shi Arrangement)

Given a graph

= (

V, E

) with

{

, . . . , n −

}

, the

-Shi arrangement

(

) is the hyperplane arrangement in

with hyperplanes

xi−xj

= 0 and

xi−xj

= 1 for each

{i, j} ∈ E

with

i < j

[4]. In this case,

is called the deﬁning graph of the

arrangement.

It is important to note that the

-Shi arrangement depends on the labelling 0

, . . . , n −

1 of the

vertices of

. Indeed, consider the isomorphic graphs

K4\ {

}

and

K4\ {

}

. The former has a

-Shi arrangement with 84 regions, whereas the latter has a

-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 1a illustrates a projection of the Shi arrangement onto the hyperplane

= 0,

allowing us to visualize it in 2 dimensions without losing any regions or adjacency relations. This

projection trick is also used in Figure 1b.

Next, we discuss

-parking functions and the Pak-Stanley algorithm (which surjectively assigns

G•-parking functions to the regions of the G-Shi arrangement).

Deﬁnition 2.3

(Outdegree)

Given a graph

= (

V, E

), a subset

, and a vertex

, the

outdegree

outdegS

(

)of

with respect to

is the number of edges from

to vertices outside

. In

particular, outdeg∅(v) is the outdegree of v(which equals deg(v) when Gis undirected).

Deﬁnition 2.4

(

-Parking Function)

Let

be an undirected graph on vertices

{

, . . . , n −

, q}

. In this case,

is called the sink. A

-parking function is an

-tuple (

a0, a1, . . . , an−1

) such

that for any non-empty subset S⊆ {0, . . . , n −1}, there exists v∈Ssuch that av<outdegS(v).

Deﬁnition 2.5

(

G•

)

Let

= (

V, E

) be a graph. Then,

G•

is the graph obtained from

adding a sink vertex qand an edge between qand each v∈V.

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

Deﬁnition 2.6

(Pak-Stanley Algorithm)

The Pak-Stanley algorithm maps

G•

-parking functions

to the regions of the

-Shi arrangement [6]. It assigns each region

-tuple

(

) of nonnegative

integers, called its Pak-Stanley label as follows:

(1)

The region in which

x0> x1>· · · > xn−1

and

x0−xn−1<

1 is called the base region and

denoted R0. Deﬁne λ(R0) = (0,0,...,0).

(2) Suppose λ(R) has been deﬁned, and that R0is a region such that

(a) Rand R0share a boundary facet, which is part of a hyperplane H∈S(G).

(b) Rlies in the same half-space of Has R0.

In this case, we deﬁne λ(R0) = (λ(R) + eiif His given by xi−xj= 0 with i < j,

λ(R) + ejif His given by xi−xj= 1 with i < j.

Here, eidenotes the ith standard basis vector of Rn.

The set of Pak-Stanley labels for the regions of the

-Shi arrangement are called the Pak-Stanley

labels for G; these are the same as the G•-parking functions [4].

The examples of

and

are displayed in Figures 1a and 1b. Notice every (

)

•

-parking

function appears in Figure 1a, and every (

)

•

-parking function appears in Figure 1b. Furthermore,

each (

)

•

-parking function appears exactly once in the

-Shi arrangement. As it turns out, both

of these are general patterns that are proved in [4]. Speciﬁcally, we have the following:

Theorem 2.7

([4], Corollary 2.8)

Every

G•

-parking function occurs as a label in the Pak-Stanley

algorithm on the G-Shi arrangement.

It is well known that there are (

+ 1)

n−1

regions in the Shi arrangement

. Similarly, there

are (

+ 1)

n−1

parking functions (and therefore (

+ 1)

n−1

(

)

•

-parking functions). Thus, every

(

)

•

-parking function occurs as a label precisely once in the Pak-Stanley algorithm on the

-Shi

arrangement.

2.2.

Chip-Firing, Superstable Conﬁgurations, and Dhar’s Burning Algorithm.

We begin

this section by recounting some of the deﬁnitions in Chapter 2 of The Mathematics of Chip-ﬁring

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.

Deﬁnition 2.8 (Chip Conﬁguration).Achip conﬁguration for Gis a non-negative integer vector

c= (c0, c1, . . . , cn−1)∈Zn

≥0

where each coordinate of the vector corresponds to the number of “chips” at a particular vertex.

That is, the

th coordinate

represents the number of chips at the vertex

. Notice that we do not

consider the number of chips on the sink vertex q.

Deﬁnition 2.9

(Firing)

Given a chip conﬁguration

for

, a non-sink vertex

ﬁres by sending

one chip to each of its neighbors (possibly including the sink). That is, the conﬁguration

replaced by c0= (c0

0, . . . , c0

n−1)∈Znwhere

i=









ci−deg i i =v

ci+ 1 {i, v} ∈ E

ciotherwise.

This is a legal ﬁre if c0is a chip conﬁguration.

Deﬁnition 2.10 (Stable).A chip conﬁguration cis stable if there are no legal ﬁres.

Now let us transition to discussing superstable conﬁgurations.

Deﬁnition 2.11

(Graph Laplacian)

Let

= (

V, E

) be a graph on

vertices

v0, . . . , vn−1

. The

graph Laplacian ∆(G) is the n×nmatrix given by

∆ij =









deg(vi)i=j

−1i6=jand {vi, vj} ∈ E

0 otherwise.

Deﬁnition 2.12

(Reduced Laplacian)

Let ∆ be the Laplacian of a graph

with sink

. Then,

the reduced graph Laplacian of

with respect to

, denoted ∆

(

) or ∆

, is the matrix obtained

from ∆ by deleting the row and column corresponding to q.

Deﬁnition 2.13

(Cluster-Fire)

Let

be a graph on

+ 1 vertices with sink

. Consider a chip

conﬁguration

= (

c0, . . . , cn−1

). Let

be a subset of the vertices of

. A cluster-ﬁre at

replaces

with a new conﬁguration

given by sending a chip to each neighbor of

for each

v∈S

. Formally,

c0=c−∆q(G)χS

where

χS∈Rn

is the characteristic vector of

; that is,

χS

has

th coordinate equal to 1 if

i∈S

and 0 if i6∈ S. Such a cluster-ﬁre is called legal if c0is still a chip conﬁguration.

Deﬁnition 2.14

(Superstable Conﬁguration)

Let a graph

be given with a chip conﬁguration

The conﬁguration cis called superstable if there are no legal cluster-ﬁres from c.

Example 2.15.

The left-hand conﬁguration is not superstable, as one can ﬁre at the three vertices

whose chip labels are bolded. However, the right-hand side is superstable.

Figure 2. Non-Superstable and Superstable Conﬁgurations.

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

Theorem 2.16

([5], Theorem 3.6.3)

is a graph with sink vertex

, then the

-parking

functions of Gare precisely the set of superstable conﬁgurations of G.

Proof. By deﬁnition; see Deﬁnitions 2.4 and 2.14. 

We conclude with a discussion of some important results about superstable conﬁgurations. First,

we will discuss Dhar’s Burning Algorithm.

Deﬁnition 2.17

(Dhar’s Burning Algorithm)

Let

be a graph with sink

, and

be a chip

conﬁguration on

. Envision the chips as ﬁreﬁghters protecting the vertices that they are on. Then,

light the sink qon ﬁre, and repeat the following process:

(1) If a vertex vis on ﬁre, the ﬁre spreads along all the edges of vtowards v’s neighbors.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

REPETITIONSOFPAK-STANLEYLABELSING-SHIARRANGEMENTSCARABENNETT,LUCYMARTINEZ,AVAMOCK,GORDONROJASKIRBY,ANDROBINTRUAXAbstract.GivenasimplegraphG,onecandeneahyperplanearrangementcalledtheG-Shiarrangement.ThePak-StanleyalgorithmlabelstheregionsofthisarrangementwithG-parkingfunctions.WhenGisacompletegraph...

展开>> 收起<<

REPETITIONS OF PAK-STANLEY LABELS IN G-SHI ARRANGEMENTS CARA BENNETT LUCY MARTINEZ AVA MOCK GORDON ROJAS KIRBY AND ROBIN TRUAX Abstract. Given a simple graph G one can dene a hyperplane arrangement called the G-Shi.pdf

共34页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

REPETITIONS OF PAK-STANLEY LABELS IN G-SHI ARRANGEMENTS CARA BENNETT LUCY MARTINEZ AVA MOCK GORDON ROJAS KIRBY AND ROBIN TRUAX Abstract. Given a simple graph G one can dene a hyperplane arrangement called the G-Shi

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: