×
Baker, Matthew; Norine, Serguei

Riemann-Roch and Abel-Jacobi theory on a finite graph. (English) Zbl 1124.05049

Adv. Math. 215, No. 2, 766-788 (2007).
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.

Cited in 31 Reviews
Cited in 193 Documents

MSC:

05C38 Paths and cycles
14H55 Riemann surfaces; Weierstrass points; gap sequences
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)

Keywords:

Graph; Riemann surface; Riemann-Roch theorem; Jacobian of a finite graph; chip-firing games
PDF BibTeX XML Cite
\textit{M. Baker} and \textit{S. Norine}, Adv. Math. 215, No. 2, 766--788 (2007; Zbl 1124.05049)
Full Text: DOI arXiv

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)
[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
[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
[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
[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
[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
[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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.