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.
Bibliographical noteFunding Information:
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 .
- Arithmetical graph
- Ballot number
- Catalan number
- Critical group
- Sandpile group