EXPLORING CHIP-FIRING GAMES ON EULERIAN AND HERMITIAN GRAPHS APPROACH

Kavita Hiremath; Namrata Kaushal; Jyoti Gupta

doi:10.29121/shodhkosh.v5.i1.2024.5931

Authors

Kavita Hiremath Department of Mathematics, Faculty of Science , Mansarovar Global University, Billkisganj, Sehore, Madhya Pradesh
Namrata Kaushal Department of Mathematics, Indore Institute of Science and Technology, Indore, MP, India
Jyoti Gupta Department of Mathematics, Indore Institute of Science and Technology, Indore, MP, India

DOI:

https://doi.org/10.29121/shodhkosh.v5.i1.2024.5931

Keywords:

Graph, Lattice, Uld Lattice, Walk, Markov Chain

Abstract [English]

Based on the graph structure and chip distribution on its vertices, three distinct types of dynamic models emerge. Among these, Chip-Firing Games have garnered significant attention due to their wide applicability across various mathematical fields, including algebra, combinatorics, dynamical systems, statistics, algorithms, and computational complexity. In this paper, we explore the characterization properties of configuration spaces, which are organized by predecessor relations. We introduce Chip-Firing Games (CFGs) as a method, termed the "Probability Abacus," to compute absorbing probabilities through vector addition techniques. We demonstrate that the termination state of any CFG within an absorbing Markov chain, characterized by a rational transition matrix, which is independent of the firing order and critical loading reappearing at the termination state.

References

A.Bjorner, L.Lovasz,“Chip-firing games on directed graphs”. J. Algebraic Combinatory. 1, (1992), 304-328. DOI: https://doi.org/10.1023/A:1022467132614

A.Bjorner, L.Lovasz, W. Shor,“Chip-firing games on graphs” E.J. Combinatorics.12 ,(1991), 283-291. DOI: https://doi.org/10.1016/S0195-6698(13)80111-4

A.Engel, “The probabilistic abacus”Educ.Stud. In Math. 6 (1975), 1-22. DOI: https://doi.org/10.1007/BF00590021

A.Engel, “Why does the probabilistic abacus work”Educ. Stud. In Math. 7, (1976), 59-69. DOI: https://doi.org/10.1007/BF00144359

A. Kelley, “Chip Firing Games”, April 24, (2016).

C. Magnien, H.D.Phan, L.Vuillon,“Characterization of lattices induced by (extended) chip-firing Games”. Discrete Mathematics. Theory of Computer Science, (2001), 229–244. DOI: https://doi.org/10.46298/dmtcs.2277

Criel Merino, “The chip-firing game”, Discrete Mathematics 302 (2005), 188 – 210. DOI: https://doi.org/10.1016/j.disc.2004.07.033

H. Zhong, “Introduction to the chip-firing game”, August 29, (2022).

J.Esparza, M.Nielsen, “Decidability issues for petrinets” a survey, Bulletin of the European Association for Theoretical Computer Science 52 (1994), 245–262.

J.Propp,“A whirling tour of chip-firing and rotor-routing”,DIMACS Workshop on Puzzling Mathematics and Mathematical Puzzles (2007).

Kimmo Eriksson, “Strongly Convergent Games and Coxeter Groups”.PhD thesis, Kungl Tekniska Hogskolan, Sweden, (1993).

M. Baker, F. Shokrieh, “Chip-firing games, potential theory on graphs, and spanning trees”, Journal of Combinatorial Theory, Series A, 120 (1), (2013), 164-182 DOI: https://doi.org/10.1016/j.jcta.2012.07.011

M.Kleber,“Goldbug variations”Mathematical Intelligencer, 27 (1), (2005), 1-20 DOI: https://doi.org/10.1007/BF02984814

M.Latapy, H.D. Phan,“The lattice structure of chipfiring games”. Physica D, 115, (2001), 69–82. DOI: https://doi.org/10.1016/S0167-2789(01)00236-6

R.M.Karp,R. E.Miller, “Parallel program schemata”, J. Computer System Science,3, (1969), 147-195. DOI: https://doi.org/10.1016/S0022-0000(69)80011-5

W.Reisig,“Petrinets”, EATCS Monographs on Theoretical Computer Science,4,(1985).

W.Feller, “An Introduction to Probability Theory”, 1,(1957). DOI: https://doi.org/10.1515/jbnst-1958-1700125

Ziv Scully, Tian-Yi Jiang, Yan X Zhang, “Firing Patterns in the Parallel Chip-Firing Game”, Discrete Mathematics and Theoretical Computer Science proc., (2014), 537-548. DOI: https://doi.org/10.46298/dmtcs.2421