Riemann-Roch and Abel-Jacobi theory on a finite graph.(English)Zbl 1124.05049
Summary: It is well known that a finite graph can be viewed, in many respects, as a discrete analogue of a Riemann surface. In this paper, we pursue this analogy further in the context of linear equivalence of divisors. In particular, we formulate and prove a graph-theoretic analogue of the classical Riemann-Roch theorem. We also prove several results, analogous to classical facts about Riemann surfaces, concerning the Abel-Jacobi map from a graph to its Jacobian. As an application of our results, we characterize the existence or non-existence of a winning strategy for a certain chip-firing game played on the vertices of a graph.
MSC:
| 05C38 | Paths and cycles |
| 14H55 | Riemann surfaces; Weierstrass points; gap sequences |
| 05C25 | Graphs and abstract algebra (groups, rings, fields, etc.) |
Cite
References:
| [1] | Bacher, R.; de la Harpe, P.; Nagnibeda, T., The lattice of integral flows and the lattice of integral cuts on a finite graph, Bull. Soc. Math. France, 125, 2, 167-198 (1997) ·Zbl 0891.05062 |
| [2] | Biggs, N., Algebraic Graph Theory, Cambridge Math. Lib. (1993), Cambridge Univ. Press: Cambridge Univ. Press Cambridge |
| [3] | Biggs, N., Algebraic potential theory on graphs, Bull. London Math. Soc., 29, 6, 641-682 (1997) ·Zbl 0892.05033 |
| [4] | Biggs, N., Chip-firing and the critical group of a graph, J. Algebraic Combin., 9, 1, 25-45 (1999) ·Zbl 0919.05027 |
| [5] | Biggs, N., The Tutte polynomial as a growth function, J. Algebraic Combin., 10, 2, 115-133 (1999) ·Zbl 0943.05048 |
| [6] | N. Biggs, P. Winkler, Chip-firing and the chromatic polynomial, preprint, 1997, 9 pp; N. Biggs, P. Winkler, Chip-firing and the chromatic polynomial, preprint, 1997, 9 pp |
| [7] | Björner, A.; Lovász, L., Chip-firing games on directed graphs, J. Algebraic Combin., 1, 4, 305-328 (1992) ·Zbl 0805.90142 |
| [8] | Björner, A.; Lovász, L.; Shor, P. W., Chip-firing games on graphs, European J. Combin., 12, 4, 283-291 (1991) ·Zbl 0729.05048 |
| [9] | Bollobás, B., Modern Graph Theory, Grad. Texts in Math., vol. 184 (1998), Springer-Verlag: Springer-Verlag New York ·Zbl 0902.05016 |
| [10] | Chebikin, D.; Pylyavskyy, P., A family of bijections between \(G\)-parking functions and spanning trees, J. Combin. Theory Ser. A, 110, 1, 31-41 (2005) ·Zbl 1070.05006 |
| [11] | Edixhoven, S. J., On Néron models, divisors and modular curves, J. Ramanujan Math. Soc., 13, 2, 157-194 (1998) ·Zbl 0931.11021 |
| [12] | Farkas, H. M.; Kra, I., Riemann Surfaces, Grad. Texts in Math., vol. 71 (1992), Springer-Verlag: Springer-Verlag New York ·Zbl 0475.30001 |
| [13] | Fulton, W., Introduction to Toric Varieties, Ann. of Math. Stud., vol. 131 (1993), Princeton Univ. Press: Princeton Univ. Press Princeton, NJ, The William H. Roever Lectures in Geometry ·Zbl 0813.14039 |
| [14] | S. Gaubert, Two lectures on max-plus algebra, preprint, available at http://citeseer.ist.psu.edu/gaubert98two.html; S. Gaubert, Two lectures on max-plus algebra, preprint, available at http://citeseer.ist.psu.edu/gaubert98two.html |
| [15] | Godsil, C.; Royle, G., Algebraic Graph Theory, Grad. Texts in Math., vol. 207 (2001), Springer-Verlag: Springer-Verlag New York ·Zbl 0968.05002 |
| [16] | Griffiths, P.; Harris, J., Principles of Algebraic Geometry, Wiley Classics Library (1994), Wiley: Wiley New York, reprint of the 1978 original ·Zbl 0836.14001 |
| [17] | Hartshorne, R., Algebraic Geometry, Grad. Texts in Math., vol. 52 (1977), Springer-Verlag: Springer-Verlag New York ·Zbl 0367.14001 |
| [18] | Horton, M.; Stark, H.; Terras, A., What are zeta functions of graphs and what are they good for?, (Quantum Graphs and Their Applications. Quantum Graphs and Their Applications, Contemp. Math., vol. 415 (2006), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 173-189 ·Zbl 1222.11109 |
| [19] | Kotani, M.; Sunada, T., Zeta functions of finite graphs, J. Math. Sci. Univ. Tokyo, 7, 1, 7-25 (2000) ·Zbl 0978.05051 |
| [20] | Lorenzini, D. J., Arithmetical graphs, Math. Ann., 285, 3, 481-501 (1989) ·Zbl 0662.14008 |
| [21] | Lorenzini, D. J., A finite group attached to the Laplacian of a graph, Discrete Math., 91, 3, 277-282 (1991) ·Zbl 0755.05079 |
| [22] | Lorenzini, D. J., Arithmetical properties of Laplacians of graphs, Linear Multilinear Algebra, 47, 4, 281-306 (2000) ·Zbl 0959.05072 |
| [23] | Mazur, B., Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. (47), 33-186 (1978), 1977 ·Zbl 0394.14008 |
| [24] | Merino, C., The chip-firing game, Discrete Math., 302, 1-3, 188-210 (2005) ·Zbl 1139.91314 |
| [25] | Merino López, C., Chip firing and the Tutte polynomial, Ann. Comb., 1, 3, 253-259 (1997) ·Zbl 0901.05004 |
| [26] | G. Mikhalkin, Tropical geometry and its applications, preprint, available at http://www.math.toronto.edu/mikha/icm.pdf; G. Mikhalkin, Tropical geometry and its applications, preprint, available at http://www.math.toronto.edu/mikha/icm.pdf ·Zbl 1103.14034 |
| [27] | Miranda, R., Algebraic Curves and Riemann Surfaces, Grad. Stud. Math., vol. 5 (1995), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI ·Zbl 0820.14022 |
| [28] | Nagnibeda, T., The Jacobian of a finite graph, (Harmonic Functions on Trees and Buildings. Harmonic Functions on Trees and Buildings, New York, 1995. Harmonic Functions on Trees and Buildings. Harmonic Functions on Trees and Buildings, New York, 1995, Contemp. Math., vol. 206 (1997), Amer. Math. Soc.: Amer. Math. Soc. Providence, RI), 149-151 ·Zbl 0883.05069 |
| [29] | J. Plautz, R. Calderer, \(G\) http://www.math.umn.edu/ |
| [30] | Postnikov, A.; Shapiro, B., Trees, parking functions, syzygies, and deformations of monomial ideals, Trans. Amer. Math. Soc., 356, 8, 3109-3142 (2004), (electronic) ·Zbl 1043.05038 |
| [31] | Raynaud, M., Spécialisation du foncteur de Picard, Inst. Hautes Études Sci. Publ. Math. (38), 27-76 (1970) ·Zbl 0207.51602 |
| [32] | Ribet, K. A., On modular representations of \(Gal(\overline{Q} / Q)\) arising from modular forms, Invent. Math., 100, 2, 431-476 (1990) ·Zbl 0773.11039 |
| [33] | Stark, H. M.; Terras, A. A., Zeta functions of finite graphs and coverings, Adv. Math., 121, 1, 124-165 (1996) ·Zbl 0874.11064 |
| [34] | Stark, H. M.; Terras, A. A., Zeta functions of finite graphs and coverings. II, Adv. Math., 154, 1, 132-195 (2000) ·Zbl 0972.11086 |
| [35] | Stark, H. M.; Terras, A. A., Zeta functions of finite graphs and coverings. III, Adv. Math., 208, 1, 467-489 (2007) ·Zbl 1207.05083 |
| [36] | Tardos, G., Polynomial bound for a chip firing game on graphs, SIAM J. Discrete Math., 1, 3, 397-398 (1988) ·Zbl 0652.68089 |
| [37] | M. Thorup, Firing games, preprint, available at http://citeseer.ist.psu.edu/thorup96firing.html; M. Thorup, Firing games, preprint, available at http://citeseer.ist.psu.edu/thorup96firing.html |
| [38] | Urakawa, H., A discrete analogue of the harmonic morphism and Green kernel comparison theorems, Glasg. Math. J., 42, 3, 319-334 (2000) ·Zbl 1002.05049 |
| [39] | van den Heuvel, J., Algorithmic aspects of a chip-firing game, Combin. Probab. Comput., 10, 6, 505-529 (2001) ·Zbl 0987.05093 |
| [40] | Zhang, S., Admissible pairing on a curve, Invent. Math., 112, 1, 171-193 (1993) ·Zbl 0795.14015 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
