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
G
be a finite, connected, simple graph. The critical group
K
(
G
), also known as
the sandpile group, is the torsion subgroup of the cokernel of the graph Laplacian
cok
(
L
). 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
G
, generate
K
(
G
). 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 finite abelian group associated to a finite connected graph
G
, known as
the critical group of
G
. The critical group goes by different 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 definition of the critical
group involving chip-firing operations and its connections to graph-theoretic trees. In particular, for
a finite 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-firing, as well as the books by Klivans [20] and
Cory and Perkinson [14] for comprehensive considerations of chip-firing.
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
G
is isomorphic to the critical groups of the dual of
G
. 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
1
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 different base cycles. For
what follows
Hk,n
denotes the hinge graph with
k
vertices on each base shape and
n
copies of the
base shape. For different cycles,
Hk1−1,k2−1,...,kn−1
denotes the hinge graph with
ki
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 different 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 definitions and theorems, as well as introduce several definitions
pertaining to our specific case study. We begin by briefly 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
V
(
G
) and
E
(
G
) refer to the set of vertices and edges of a graph
G
, 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).
Definition 2.1. Adivisor (or chip configuration) on a graph
G
is a formal
Z
-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).
2
Definition 2.2. Afiring 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-firing move or chip-firing operation. We say that two divisors
D
and
D′
are chip-firing equivalent or linearly equivalent if
D′
can be obtained from
D
via a sequence
of chip-firing moves. The order of a divisor
D
is the smallest positive integer
z
with
zD
linearly
equivalent to the zero divisor.
In our specific case study, the number of edges between two vertices will always be at most 1.
Note also that the chip-firing operation is commutative, and hence firings 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
L
is defined as
A−M
, where
A
denotes the adjacency matrix of the graph,
and Mis the diagonal matrix with the valences of each vertex in V(G).
Definition 2.3. The critical group
K
(
G
) of a graph
G
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 definition of order of a divisor.
Theorem 2.4 (Corollary 3, [16]).The order of the critical group
K
(
G
)is the number of spanning
trees of G.
While it is sufficient 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-firing equivalence.
Definition 2.5. Let
K
(
G
) be the critical group of a graph
G
. We say a divisor
D
is a
q
-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
(
G
)
\ {q}
, if we take
D
(
v
) and fire every vertex
in V′, then some vertex in V′has associated integer r < 0.
Note that
q
-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 definitions specific to a particular family of graphs.
Definition 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
k
is the number of vertices of the base shape (including the pair of shared vertices) and
n
is
the number of copies of the base shape.
•
For different cycles, we instead use the notation
Hk1−1,k2−1,...,kn−1
, where
ki
refers to the
number of vertices of each base shape. (Note that this notation differs from identical base
shapes since we use
ki−
1 instead of
ki
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.
3
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 difference 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
different 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 definition of the
critical group, but its impact on our results is significant enough to warrant it as a proposition.
Theorem 2.8 (Theorem 11, [16]).For any finite connected graph
G
, the null space of the Laplacian
matrix of Gis generated by the vector 1.
As a consequence, borrowing from a vertex is equivalent to firing every other vertex (by adding
1to the vector r= (0
,
0
, . . .
0
,−
1
,
0
, . . .
0)
T
, the number of times each vertex is fired), where the
−
1 means borrowing from the
i
th vertex. Therefore, borrowing can be thought of as the inverse of
firing.
4
Proposition 2.9. Let aand bbe two vector representations of divisors for a graph
G
and let
M
be
the augmented matrix of
L
and a
−
b. If all entries in
M
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
A
x=b. When we employ this construction with the
graph Laplacian and augmenting the divisor in the final column, solving this equation is equivalent
to finding the vector r, which is the number of times each vertex must be fired 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 off the values in the final 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 firing
vertices an integral number of times. Combining this with Proposition 2.7, two divisors are linearly
equivalent if their difference 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
n
dbe the vector representation of a multiple
n
of a divisor
δ
on a graph
G
,
and let
M
be the augmented matrix of
L
and
n
d. If the non-unital entries of
M
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 different 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
j
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.
5
摘要：
展开>>
收起<<
ONTHECRITICALGROUPOFHINGEGRAPHSARENMARTINIANANDANDR´ESR.VINDAS-MEL´ENDEZAbstract.LetGbeafinite,connected,simplegraph.ThecriticalgroupK(G),alsoknownasthesandpilegroup,isthetorsionsubgroupofthecokernelofthegraphLaplaciancok(L).Weinvestigateafamilyofgraphswithrelativelysimplenon-cycliccriticalgroupwith...
声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！
相关推荐
-
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包05专题五 走进社会生活 遵守社会规则VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包05专题五 走进社会生活 遵守社会规则VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包03专题三 青春时光 做情绪情感的主人VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包03专题三 青春时光 做情绪情感的主人VIP免费
2024-11-21 3 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包02专题二 友谊的天空 师长情谊VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包02专题二 友谊的天空 师长情谊VIP免费
2024-11-21 4 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包01专题一 成长的节拍 生命的思考VIP免费
2024-11-21 1 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包01专题一 成长的节拍 生命的思考VIP免费
2024-11-21 2 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包《53中考》全国道德与法治资料包VIP免费
2024-11-21 5 -
曲一线系列初中《5中考3年模拟》2023专题解释全国道德与法治资料包07专题七 坚持宪法至上 崇尚法治精神VIP免费
2024-11-21 2
分类：图书资源
价格：10玖币
属性：24 页
大小：714.71KB
格式：PDF
时间：2025-05-02
作者详情
相关内容
-
2025年小学实践活动教案：（微课制作用）课件
分类：中学教育
时间：2025-06-08
标签：无
格式：PPT
价格：10 玖币
-
2025年教学资料：【通用版】一年级数学重点难点知识总结
分类：中学教育
时间：2025-06-08
标签：无
格式：PDF
价格：10 玖币
-
2025年教学资料：小学生心理健康教育主题班会ppt课件
分类：中学教育
时间：2025-06-08
标签：无
格式：PPTX
价格：10 玖币
-
2013年广东省地理中考试题无答案
分类：中学教育
时间：2025-06-08
标签：无
格式：DOC
价格：10 玖币
-
河南省2020年中考道德与法治试题
分类：中学教育
时间：2025-06-08
标签：无
格式：DOC
价格：10 玖币
渝公网安备50010702506394
