ON THE CRITICAL GROUP OF HINGE GRAPHS AREN MARTINIAN AND ANDR ES R. VINDAS-MEL ENDEZ Abstract. LetGbe a finite connected simple graph. The critical group KG also known as

2025-05-02 0 0 714.71KB 24 页 10玖币

侵权投诉

ON THE CRITICAL GROUP OF HINGE GRAPHS

AREN MARTINIAN AND ANDR´

ES R. VINDAS-MEL´

ENDEZ

Abstract.

Let

be a ﬁnite, connected, simple graph. The critical group

(

), also known as

the sandpile group, is the torsion subgroup of the cokernel of the graph Laplacian

cok

(

). We

investigate a family of graphs with relatively simple non-cyclic critical group with an end goal of

understanding whether multiple divisors, i.e., formal linear combinations of vertices of

, generate

(

). These graphs, referred to as hinge graphs, can be intuitively understood by taking multiple

base shapes and “gluing” them together by a single shared edge and two corresponding shared

vertices. In the case where all base shapes are identical, we compute the explicit structure of the

critical group. Additionally, we compute the order of three special divisors. We prove the structure

of the critical group of hinge graphs when variance in the number of vertices of each base shape is

allowed, generalizing many of the aforementioned results.

1. Introduction

In this paper we study a ﬁnite abelian group associated to a ﬁnite connected graph

, known as

the critical group of

. The critical group goes by diﬀerent names (e.g., the Jacobian group, sandpile

group, component group) and is studied in various mathematical areas (e.g., algebraic geometry,

statistical physics, combinatorics) [16]. We focus on the combinatorial deﬁnition of the critical

group involving chip-ﬁring operations and its connections to graph-theoretic trees. In particular, for

a ﬁnite connected graph, the order of the critical group equals the number of spanning trees of the

graph. For the interested reader, we recommend the survey paper by Glass and Kaplan [16] as an

introduction to the study of critical groups and chip-ﬁring, as well as the books by Klivans [20] and

Cory and Perkinson [14] for comprehensive considerations of chip-ﬁring.

There are many results on the group structure of the critical group and the relationship with the

structure of an associated graph, see for instance [2,7,9,13]. Determining the critical group for certain

families of graphs continues to be an active area of research. There exists work where the critical

group has been partially determined for some families of graphs, for instance see [5,11,17,22,29

–

31].

Additionally, there is a growing body of work where the complete critical group structure for families

of graphs is determined, see for instance [8,10,12,18,21,23–28].

The family of graphs that we study are those which we call hinge graphs. These are graphs that

can be intuitively understood by taking multiple base shapes and “gluing” them together on a single

shared edge and two corresponding shared vertices. In [13], Cori and Rossin show that the critical

group of a planar graph

is isomorphic to the critical groups of the dual of

. It so happens that

hinge graphs are dual to a family of graphs known as thick cycle graphs, which are cycle graphs

where multiple edges are allowed, and were studied in [1,4]. Furthermore, thick cycle graphs can be

seen as specializations of outerplanar graphs studied in [3].

The study of hinge graphs arose independently and was motivated primarily in attempt to answer

the question proposed in [16] on how divisors generate critical groups in cases where the group

is non-cyclic. Hinge graphs, especially those containing identical copies of the same base shape,

are some of the simplest examples of graphs with non-cyclic critical groups, and whose behavior

can be thoroughly studied. In addition, the study of hinge graphs has led to observations about

proving linear equivalence and the order of divisors which provides a streamlined approach to the

investigation of divisors and critical groups of graphs more generally. As mentioned before, hinge

arXiv:2210.01793v3 [math.CO] 20 Sep 2023

graphs can be observed to be the dual graphs of thick cycle graphs, thus the critical group of a hinge

graph is isomorphic to the critical group of a thick cycle graph, whose complete structure is given

in Theorem 2.29 in [4] and Theorem 1 in [1]. Despite there being literature about the structure of

the critical groups of thick cycle graphs, and hence an alternate route to the study of hinge graphs,

this connection was not previously made. We provide a novel approach using divisors that generate

the critical group of hinge graphs which is not explored in the existing literature. We emphasize

that the proofs in this paper are new and rely solely on generating divisors and were written with a

deliberate choice to avoid using the theory of reduced divisors.

Our main contributions include proofs of formulas for the order and structure of the critical group

of hinge graphs with same base shapes, and using tools such as the graph Laplacian, to determine

the orders of important group elements. Using similar techniques to those used to prove these

results, we generalize some to the case where we have hinge graphs with diﬀerent base cycles. For

what follows

Hk,n

denotes the hinge graph with

vertices on each base shape and

copies of the

base shape. For diﬀerent cycles,

Hk1−1,k2−1,...,kn−1

denotes the hinge graph with

vertices on each

base shape. The critical group of a graph Gis denoted K(G).

Theorem 3.1.Given a hinge graph Hk,n, the order of the critical group K(Hk,n)is

|K(Hk,n)|= (k−1)n−2(k−1)(k+n−1).

Theorem 3.6.The critical group K(Hk,n)is isomorphic to

(Z/(k−1)Z)n−2⊕(Z/(k−1)(k+n−1)Z).

Theorem 4.1.Consider a hinge graph with diﬀerent base shapes Hk1−1,...,kn−1, the order of

K(Hk1−1,...,kn−1)is

|K(Hk1−1,...,kn−1)|=a+a/(k1−1) + · · · +a/(kn−1),

where a:= (k1−1) · · · (kn−1).

This paper is organized as follows. In Section 2we provide background and preliminaries on

divisors, the critical group, and hinge graphs. In Section 3we prove several results for hinge graphs

where each base shape is an identical cycle, including the explicit structure of the critical group and

the behavior of some noteworthy divisors (see Proposition 3.3). In Section 4we generalize many of

the aforementioned results to hinge graphs where the number of vertices on each base shape can

vary (see Theorem 4.9). We conclude in Section 5with some directions for future research.

2. Preliminaries

In this section we review some key deﬁnitions and theorems, as well as introduce several deﬁnitions

pertaining to our speciﬁc case study. We begin by brieﬂy detailing divisors and critical groups on

graphs. We take our graphs to be connected, undirected, and any two vertices are connected by at

most one edge. Note that a consequence of these conditions is that graphs cannot contain loops.

These are the conditions under which much of the existing critical group literature has focused on.

Let

(

) and

(

) refer to the set of vertices and edges of a graph

, respectively. A cycle

graph is a graph where every vertex has valence two. These are most often thought of as regular

polygons (a convention we will adopt).

Deﬁnition 2.1. Adivisor (or chip conﬁguration) on a graph

is a formal

-linear combination of

vertices of G,

D=X

v∈V(G)

v·D(v).

The degree of a divisor Dis the integer deg(D) := Pv∈V(G)D(v).

Deﬁnition 2.2. Aﬁring of a vertex is the operation taking the divisor Dto a divisor D′where

D′(v) = (D(v)−val(v),if v=w,

D(v) + # edges between vand w, if v̸=w.

This is referred to as a chip-ﬁring move or chip-ﬁring operation. We say that two divisors

and

D′

are chip-ﬁring equivalent or linearly equivalent if

D′

can be obtained from

via a sequence

of chip-ﬁring moves. The order of a divisor

is the smallest positive integer

with

linearly

equivalent to the zero divisor.

In our speciﬁc case study, the number of edges between two vertices will always be at most 1.

Note also that the chip-ﬁring operation is commutative, and hence ﬁrings can be thought of as

happening simultaneously. By convention, if a divisor consists of a 0 associated with a vertex, that

vertex is left blank.

The graph Laplacian

is deﬁned as

A−M

, where

denotes the adjacency matrix of the graph,

and Mis the diagonal matrix with the valences of each vertex in V(G).

Deﬁnition 2.3. The critical group

(

) of a graph

is the torsion subgroup of the cokernel of

the graph Laplacian cok(L).

Note that elements of the critical group necessarily have degree 0, and have order consistent with

the deﬁnition of order of a divisor.

Theorem 2.4 (Corollary 3, [16]).The order of the critical group

(

)is the number of spanning

trees of G.

While it is suﬃcient to consider any divisor as an element of the critical group, we are mainly

interested in a particular type of divisor that can be thought of as a representative element modulo

chip-ﬁring equivalence.

Deﬁnition 2.5. Let

(

) be the critical group of a graph

. We say a divisor

is a

-reduced

divisor if for any vertex qof D,

(1) D(v)≥0 for all v̸=qand

(2)

for every nonempty subset of vertices

V′⊆V

(

)

\ {q}

, if we take

(

) and ﬁre every vertex

in V′, then some vertex in V′has associated integer r < 0.

Note that

-reduced divisors are not used explicitly in this paper, but it is worth mentioning that

all divisors discussed will be multiples of q-reduced divisors.

Next, we introduce deﬁnitions speciﬁc to a particular family of graphs.

Deﬁnition 2.6. Ahinge graph is a graph constructed by “adjoining” or “gluing” several cycle

graphs via a shared edge and consequent pair of vertices. We call the cycles used to construct the

hinge graph the base shapes, and will sometimes refer to them as cycles of the hinge graph.

•

In the case when all base shapes are identical, these hinge graphs are denoted

Hk,n

, where

is the number of vertices of the base shape (including the pair of shared vertices) and

the number of copies of the base shape.

•

For diﬀerent cycles, we instead use the notation

Hk1−1,k2−1,...,kn−1

, where

refers to the

number of vertices of each base shape. (Note that this notation diﬀers from identical base

shapes since we use

ki−

1 instead of

for its usefulness in the proofs of forthcoming results.)

Refer to Figure 1for examples of hinge graphs. In the case of cycles with four vertices, which are

taken as squares, these graphs are called book graphs as their structure resembles that of several

pages.

In what follows, attaching another copy of the base shape to an existing graph with the same

shared hinge will be referred to as adding a copy of the base shape. In cases where spanning trees

are counted, the deletion of an edge while retaining both vertices will be referred to as removing an

edge.

Figure 1. Types of divisors studied: δx,y (left), ϵx,y (center), and ηx,y (right).

We will focus our attention on three distinct types of divisors on these graphs, which will be

referred to as

δx,y

ϵx,y

, and

ηx,y

, following the notation in [16]. All three divisors have degree 0, with

zeroes assigned to all vertices except two, which are assigned a 1 and

−

1. The diﬀerence between

these divisors lies in the location of the vertices associated with nonzero values. The divisor

•δx,y consists of a 1 and −1 on the shared pair of vertices,

•ϵx,y consists of a 1 and −1 on a shared vertex and an adjacent vertex on a cycle, and

•ηx,y

consists of a 1 and

−

1 on two vertices adjacent to the same shared vertex, but on

diﬀerent cycles.

When enumeration of these divisors is important, as in Lemma 3.4 when choosing a minimal

generating set of

ηx,y

’s or Theorem 4.4 where the order of

ϵx,y

depends on the base shape chosen,

we will denote the divisors for each base shape by

ϵx,y,i

and

ηx,y,i

. Examples of all three divisors

can be seen in Figure 1. As we shall see, the distinction of which vertex is assigned a positive or

negative value is irrelevant.

Some of the following propositions are well-known in the literature, but we reiterate them here as

they will be useful in the forthcoming proofs.

Proposition 2.7. The sum of two divisors (via summing integers at each vertex) corresponds

identically to the sum of two elements in the critical group.

We note that the aforementioned statement follows as a consequence of the deﬁnition of the

critical group, but its impact on our results is signiﬁcant enough to warrant it as a proposition.

Theorem 2.8 (Theorem 11, [16]).For any ﬁnite connected graph

, the null space of the Laplacian

matrix of Gis generated by the vector 1.

As a consequence, borrowing from a vertex is equivalent to ﬁring every other vertex (by adding

1to the vector r= (0

, . . .

,−

, . . .

, the number of times each vertex is ﬁred), where the

−

1 means borrowing from the

th vertex. Therefore, borrowing can be thought of as the inverse of

ﬁring.

Proposition 2.9. Let aand bbe two vector representations of divisors for a graph

and let

the augmented matrix of

and a

−

b. If all entries in

after row reduction are integers, aand b

are linearly equivalent.

Proof.

It is a widely known fact in linear algebra that augmenting any matrix with a vector is

equivalent to solving the vector equation

x=b. When we employ this construction with the

graph Laplacian and augmenting the divisor in the ﬁnal column, solving this equation is equivalent

to ﬁnding the vector r, which is the number of times each vertex must be ﬁred to obtain the divisor.

Since the graph Laplacian has kernel of dimension 1, by Theorem 2.8, there will be a last row of

zeroes in the matrix, and every value will be expressible in terms of the last column, hence we

can simply read oﬀ the values in the ﬁnal column. If all of these values are integers, we know the

divisor is linearly equivalent to the zero divisor, since that means the divisor can be formed by ﬁring

vertices an integral number of times. Combining this with Proposition 2.7, two divisors are linearly

equivalent if their diﬀerence is linearly equivalent to the zero divisor, and hence we can use this

method to check if any two divisors are linearly equivalent. □

Proposition 2.10. Let

dbe the vector representation of a multiple

of a divisor

on a graph

and let

be the augmented matrix of

and

d. If the non-unital entries of

after row reduction

are integers with greatest common divisor 1, and furthermore if this greatest common divisor is

invariant under addition of the vector 1, then n=|δ|.

Proof.

Using the construction outlined in Proposition 2.9, if we multiply the divisor, augment the

graph Laplacian with the multiplied divisor, and take its Reduced Row Echelon Form, we will

obtain the corresponding vector r, unique up to addition of 1. Note that rwill only have integer

entries if the divisor is linearly equivalent to the zero divisor. Through this process, if we obtain a

set of integers whose greatest common divisor equals 1, and furthermore adding a multiple of 1does

not change this greatest common divisor, we have discovered the smallest multiple of the divisor

for which we have linear equivalence to the zero divisor. This is because if there is no common

divisor, dividing by any integer leaves us with fractional components of r, and adding or subtracting

multiples of 1does not change this fact. Therefore, we can use this result to prove the order of any

divisor. □

As the following lemma is useful to prove results for hinge graphs with diﬀerent base shapes

Hk1−1,...kn−1, we consider ki−1 rather than ki.

Lemma 2.11. Let b= lcm(k1−1...,kn−1). Then

gcd(b/(k1−1), . . . , b/(kn−1)) = 1.

For completeness, we detail the proof below.

Proof. Let

g:= gcd(b/(k1−1), . . . , b/(kn−1)).

Then gdivides b/(kj−1) for all 1 ≤j≤n. Hence, for each jthere exists some djsuch that

g·dj=b/(kj−1),

so g·dj(kj−1) = band gdivides b. Dividing through by gwe see that

(kj−1)(dj) = b/g,

and therefore (

kj−

1) divides

b/g

, but this was true for all

and hence

b/g

must be a multiple of

all kj−1. Since bis the least common multiple that means g= 1. □

Remark 2.12. This lemma holds if we eliminate one of the

ki−

1 provided that the least common

multiple does not change, which we make use of in the proof of Theorem 4.4.

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

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

10 玖币 0人已下载

立即下载

摘要：

ONTHECRITICALGROUPOFHINGEGRAPHSARENMARTINIANANDANDR´ESR.VINDAS-MEL´ENDEZAbstract.LetGbeafinite,connected,simplegraph.ThecriticalgroupK(G),alsoknownasthesandpilegroup,isthetorsionsubgroupofthecokernelofthegraphLaplaciancok(L).Weinvestigateafamilyofgraphswithrelativelysimplenon-cycliccriticalgroupwith...

展开>> 收起<<

ON THE CRITICAL GROUP OF HINGE GRAPHS AREN MARTINIAN AND ANDR ES R. VINDAS-MEL ENDEZ Abstract. LetGbe a finite connected simple graph. The critical group KG also known as.pdf

共24页,预览5页

还剩页未读，继续阅读

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

ON THE CRITICAL GROUP OF HINGE GRAPHS AREN MARTINIAN AND ANDR ES R. VINDAS-MEL ENDEZ Abstract. LetGbe a finite connected simple graph. The critical group KG also known as

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: