Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Computation of polarized metrized graph invariants by using discrete Laplacian matrix


Author: Zubeyir Cinkir
Journal: Math. Comp. 84 (2015), 2953-2967
MSC (2010): Primary 14G40, 90C35, 94C15; Secondary 11G50, 11G35, 11G30
DOI: https://doi.org/10.1090/mcom/2981
Published electronically: May 8, 2015
MathSciNet review: 3378856
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: Several invariants of polarized metrized graphs and their applications in Arithmetic Geometry have been studied recently. In this paper, we give fast algorithms to compute these invariants by expressing them in terms of the discrete Laplacian matrix and its pseudo inverse. The algorithm we give can be used for both symbolic and numerical computations. We present various examples to illustrate the implementation of these algorithms.


References [Enhancements On Off] (What's this?)

  • [1] Matthew Baker and Xander Faber, Metrized graphs, Laplacian operators, and electrical networks, Quantum graphs and their applications, Contemp. Math., vol. 415, Amer. Math. Soc., Providence, RI, 2006, pp. 15-33. MR 2277605 (2007j:05136), https://doi.org/10.1090/conm/415/07857
  • [2] Matt Baker and Robert Rumely, Harmonic analysis on metrized graphs, Canad. J. Math. 59 (2007), no. 2, 225-275. MR 2310616 (2008h:43019), https://doi.org/10.4153/CJM-2007-010-2
  • [3] R. B. Bapat, Resistance matrix of a weighted graph, MATCH Commun. Math. Comput. Chem. 50 (2004), 73-82. MR 2037425 (2004k:05129)
  • [4] R. B. Bapat, Resistance distance in graphs, Math. Student 68 (1999), no. 1-4, 87-98. MR 1836414 (2002d:05049)
  • [5] Enrico Bombieri and Walter Gubler, Heights in Diophantine geometry, New Mathematical Monographs, vol. 4, Cambridge University Press, Cambridge, 2006. MR 2216774 (2007a:11092)
  • [6] Z. Cinkir, The Tau Constant of Metrized Graphs, Thesis at University of Georgia, Athens, GA, 2007.
  • [7] Zubeyir Cinkir, The tau constant of a metrized graph and its behavior under graph operations, Electron. J. Combin. 18 (2011), no. 1, Paper 81, 42. MR 2788698 (2012c:05088)
  • [8] Zubeyir Cinkir, The tau constant and the edge connectivity of a metrized graph, Electron. J. Combin. 19 (2012), no. 4, Paper 46, 32. MR 3007181
  • [9] Zubeyir Cinkir, Zhang's conjecture and the effective Bogomolov conjecture over function fields, Invent. Math. 183 (2011), no. 3, 517-562. MR 2772087 (2012c:14057), https://doi.org/10.1007/s00222-010-0282-7
  • [10] Zubeyir Cinkir, The tau constant and the discrete Laplacian matrix of a metrized graph, European J. Combin. 32 (2011), no. 4, 639-655. MR 2780862 (2012a:05180), https://doi.org/10.1016/j.ejc.2011.01.008
  • [11] P. Courrieu, Fast Computation of Moore-Penrose Inverse Matrices, Neural Information Processing - Letters and Reviews, Volume 8, No 2, (2005), 25-29.
  • [12] Ted Chinburg and Robert Rumely, The capacity pairing, J. Reine Angew. Math. 434 (1993), 1-44. MR 1195689 (94b:14019), https://doi.org/10.1515/crll.1993.434.1
  • [13] Don Coppersmith and Shmuel Winograd, Matrix multiplication via arithmetic progressions, J. Symbolic Comput. 9 (1990), no. 3, 251-280. MR 1056627 (91i:68058), https://doi.org/10.1016/S0747-7171(08)80013-2
  • [14] X. W. C. Faber, The geometric Bogomolov conjecture for curves of small genus, Experiment. Math. 18 (2009), no. 3, 347-367. MR 2555704 (2010k:11103)
  • [15] X. W. C. Faber, Topics in Arithmetic Geometry over Function Fields, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)-Columbia University. MR 2711474
  • [16] Marc Hindry and Joseph H. Silverman, Diophantine Geometry, An Introduction. Graduate Texts in Mathematics, vol. 201, Springer-Verlag, New York, 2000. MR 1745599 (2001e:11058)
  • [17] Robin de Jong, Admissible constants for genus 2 curves, Bull. Lond. Math. Soc. 42 (2010), no. 3, 405-411. MR 2651934 (2011k:14026), https://doi.org/10.1112/blms/bdp132
  • [18] Robin de Jong, Second variation of Zhang's $ \lambda $-invariant on the moduli space of curves, Amer. J. Math. 135 (2013), no. 1, 275-290. MR 3022965, https://doi.org/10.1353/ajm.2013.0008
  • [19] D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81-95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566 (94d:94041), https://doi.org/10.1007/BF01164627
  • [20] The MathWorks Inc., Matlab, Version R2011a, Natick, Massachusetts, (2011).
  • [21] Atsushi Moriwaki, Bogomolov conjecture over function fields for stable curves with only irreducible fibers, Compositio Math. 105 (1997), no. 2, 125-140. MR 1440719 (98d:14036), https://doi.org/10.1023/A:1000139117766
  • [22] Atsushi Moriwaki, Bogomolov conjecture for curves of genus $ 2$ over function fields, J. Math. Kyoto Univ. 36 (1996), no. 4, 687-695. MR 1443744 (98e:14029)
  • [23] Wolfram Research, Inc., Mathematica, Version 8.0, Champaign, IL, 2010.
  • [24] C. Radhakrishna Rao and Sujit Kumar Mitra, Generalized Inverse of Matrices and Its Applications, John Wiley&Sons, Inc., New York-London-Sydney, 1971. MR 0338013 (49 #2780)
  • [25] G. Kirchhoff, Uber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Ströme geführt wird, Ann. Phys. Chem. 72 (1847), 497-508; for a reprint (Engl. transl.), see: I.R.E. Trans. Circuit Theory, 5, (1958), 4.
  • [26] D. J. Klein and M. Randić, Resistance distance, J. Math. Chem. 12 (1993), no. 1-4, 81-95. Applied graph theory and discrete mathematics in chemistry (Saskatoon, SK, 1991). MR 1219566 (94d:94041), https://doi.org/10.1007/BF01164627
  • [27] Kazuhiko Yamaki, Graph invariants and the positivity of the height of the Gross-Schoen cycle for some curves, Manuscripta Math. 131 (2010), no. 1-2, 149-177. MR 2574996 (2011b:14022), https://doi.org/10.1007/s00229-009-0305-0
  • [28] Kazuhiko Yamaki, Effective calculation of the geometric height and the Bogomolov conjecture for hyperelliptic curves over function fields, J. Math. Kyoto Univ. 48 (2008), no. 2, 401-443. MR 2436745 (2009h:14042)
  • [29] Kazuhiko Yamaki, Geometric Bogomolov's conjecture for curves of genus 3 over function fields, J. Math. Kyoto Univ. 42 (2002), no. 1, 57-81. MR 1932737 (2003j:14025)
  • [30] A. J. Stothers, On the Complexity of Matrix Multiplication, Thesis at University of Edinburgh, Edinburgh, 2010.
  • [31] Volker Strassen, Gaussian elimination is not optimal, Numer. Math. 13 (1969), 354-356. MR 0248973 (40 #2223)
  • [32] L. Szpiro, Séminaire sur les pinceaux de courbes de genre au moins deux, Astérisque 86 (1981), no. 3, 44-78.
  • [33] L. Szpiro, Sur les propriétés numériques du dualisant relatif d'une surface arithmétique, The Grothendieck Festschrift, Vol. III, Progr. Math., vol. 88, Birkhäuser Boston, Boston, MA, 1990, pp. 229-246 (French). MR 1106917 (92c:14017), https://doi.org/10.1007/978-0-8176-4576-2_9
  • [34] Virginia Vassilevska Williams, Multiplying matrices faster than Coppersmith-Winograd, STOC'12--Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 887-898. MR 2961552, https://doi.org/10.1145/2213977.2214056
  • [35] Shouwu Zhang, Admissible pairing on a curve, Invent. Math. 112 (1993), no. 1, 171-193. MR 1207481 (94h:14023), https://doi.org/10.1007/BF01232429
  • [36] Shou-Wu Zhang, Gross-Schoen cycles and dualising sheaves, Invent. Math. 179 (2010), no. 1, 1-73. MR 2563759 (2012a:14016), https://doi.org/10.1007/s00222-009-0209-3

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 14G40, 90C35, 94C15, 11G50, 11G35, 11G30

Retrieve articles in all journals with MSC (2010): 14G40, 90C35, 94C15, 11G50, 11G35, 11G30


Additional Information

Zubeyir Cinkir
Affiliation: Department of Mathematics, Zirve University, 27260, Gaziantep, Turkey
Address at time of publication: Department of Industrial Engineering, Abdullah Gul University, 38080, Kayseri, Turkey
Email: zubeyir.cinkir@agu.edu.tr

DOI: https://doi.org/10.1090/mcom/2981
Keywords: Metrized graph, polarized metrized graph, invariants of polarized metrized graphs, the tau constant, resistance function, the discrete Laplacian matrix, pseudo inverse and relative dualizing sheaf
Received by editor(s): February 24, 2012
Received by editor(s) in revised form: April 4, 2014
Published electronically: May 8, 2015
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society