Counting arithmetical structures on paths and cycles

Benjamin Braun; Hugo Corrales; Scott Corry; Luis David García Puente; Darren Glass; Nathan Kaplan; Jeremy L. Martin; Gregg Musiker; Carlos E. Valencia

doi:10.1016/j.disc.2018.07.002

Counting arithmetical structures on paths and cycles

Benjamin Braun
, Hugo Corrales
, Scott Corry
, Luis David García Puente
, Darren Glass
, Nathan Kaplan
, Jeremy L. Martin
, Gregg Musiker
, Carlos E. Valencia

Mathematics

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients [Formula presented], and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Original language	English
Pages (from-to)	2949-2963
Number of pages	15
Journal	Discrete Mathematics
Volume	341
Issue number	10
DOIs	https://doi.org/10.1016/j.disc.2018.07.002
State	Published - Oct 2018

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.

Funding

This project began at the “Sandpile Groups” workshop at Casa Matemática Oaxaca (CMO) in November 2015, funded by Mexico’s Consejo Nacional de Ciencia y Tecnología (CONACYT). The authors thank CMO and CONACYT for their hospitality, as well as Carlos A. Alfaro, Lionel Levine, Hiram H. Lopez, and Criel Merino for helpful discussions and suggestions. The authors also thank the anonymous referees for their helpful suggestions. BB was supported by National Security Agency Grant H98230-16-1-0045. LDGP was supported by Simons Collaboration Grant #282241. NK was partially supported by an AMS-Simons Travel Grant and by NSA Young Investigator Grant H98230-16-10305. JLM was supported by Simons Collaboration Grant #315347. GM was supported by NSF Grant #13692980. CEV was partially supported by SNI. BB was supported by National Security Agency Grant H98230-16-1-0045 . LDGP was supported by Simons Collaboration Grant #282241 . NK was partially supported by an AMS-Simons Travel Grant and by NSA Young Investigator Grant H98230-16-10305 . JLM was supported by Simons Collaboration Grant #315347 . GM was supported by NSF Grant #13692980 . CEV was partially supported by SNI .

Funders	Funder number
AMS-Simons
Mexico’s Consejo Nacional de Ciencia y Tecnología
Simons Collaboration	282241
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	13692980
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China
California Health Care Safety Net Institute
National Security Agency	H98230-16-1-0045, H98230-16-10305, 315347
National Security Agency
Consejo Nacional de Ciencia, Tecnología e Innovación Tecnológica
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China	#13692980
U.S. Department of Energy Chinese Academy of Sciences Guangzhou Municipal Science and Technology Project Oak Ridge National Laboratory Extreme Science and Engineering Discovery Environment National Science Foundation National Energy Research Scientific Computing Center National Natural Science Foundation of China

Keywords

Arithmetical graph
Ballot number
Catalan number
Critical group
Laplacian
Sandpile group

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2018.07.002

Cite this

@article{9e534baea65b46e482994d4390e8f56b,

title = "Counting arithmetical structures on paths and cycles",

abstract = "Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients [Formula presented], and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.",

keywords = "Arithmetical graph, Ballot number, Catalan number, Critical group, Laplacian, Sandpile group",

author = "Benjamin Braun and Hugo Corrales and Scott Corry and Puente, \{Luis David Garc{\'i}a\} and Darren Glass and Nathan Kaplan and \{L. Martin\}, Jeremy and Gregg Musiker and Valencia, \{Carlos E.\}",

note = "Publisher Copyright: {\textcopyright} 2018 Elsevier B.V.",

year = "2018",

month = oct,

doi = "10.1016/j.disc.2018.07.002",

language = "English",

volume = "341",

pages = "2949--2963",

number = "10",

}

TY - JOUR

T1 - Counting arithmetical structures on paths and cycles

AU - Braun, Benjamin

AU - Corrales, Hugo

AU - Corry, Scott

AU - Puente, Luis David García

AU - Glass, Darren

AU - Kaplan, Nathan

AU - L. Martin, Jeremy

AU - Musiker, Gregg

AU - Valencia, Carlos E.

PY - 2018/10

Y1 - 2018/10

N2 - Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients [Formula presented], and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

AB - Let G be a finite, connected graph. An arithmetical structure on G is a pair of positive integer vectors d,r such that (diag(d)−A)r=0, where A is the adjacency matrix of G. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices (diag(d)−A)). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients [Formula presented], and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

KW - Arithmetical graph

KW - Ballot number

KW - Catalan number

KW - Critical group

KW - Laplacian

KW - Sandpile group

UR - https://www.scopus.com/pages/publications/85050548675

UR - https://www.scopus.com/pages/publications/85050548675#tab=citedBy

U2 - 10.1016/j.disc.2018.07.002

DO - 10.1016/j.disc.2018.07.002

M3 - Article

AN - SCOPUS:85050548675

SN - 0012-365X

VL - 341

SP - 2949

EP - 2963

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 10

ER -

Counting arithmetical structures on paths and cycles

Abstract

Bibliographical note

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this