Graphs of gonality three
Algebraic Combinatorics, Tome 2 (2019) no. 6, pp. 1197-1217.

In 2013, Chan classified all metric hyperelliptic graphs, proving that divisorial gonality and geometric gonality are equivalent in the hyperelliptic case. We show that such a classification extends to combinatorial graphs of divisorial gonality three, under certain edge- and vertex-connectivity assumptions. We also give a construction for graphs of divisorial gonality three, and provide conditions for determining when a graph is not of divisorial gonality three.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/alco.80
Classification : 14T05, 05C05, 05C57
Mots clés : graph gonality, chip-firing, tropical geometry
Aidun, Ivan 1 ; Dean, Frances 2 ; Morrison, Ralph 2 ; Yu, Teresa 3 ; Yuan, Julie 4

1 Oberlin College Department of Mathematics 10 N. Professor St. Oberlin OH 44074, USA
2 Williams College Department of mathematics and statistics 33 Stetson Ct. Williamstown MA 01267, USA
3 Williams College Department of mathematics and statistics 33 Stetson Ct. Williamstown MA 01267 USA
4 University of Minnesota-Twin Cities School of mathematics 206 Church St SE Minneapolis MN 55455, USA
@article{ALCO_2019__2_6_1197_0,
     author = {Aidun, Ivan and Dean, Frances and Morrison, Ralph and Yu, Teresa and Yuan, Julie},
     title = {Graphs of gonality three},
     journal = {Algebraic Combinatorics},
     pages = {1197--1217},
     publisher = {MathOA foundation},
     volume = {2},
     number = {6},
     year = {2019},
     doi = {10.5802/alco.80},
     mrnumber = {4049843},
     zbl = {07140430},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/alco.80/}
}
TY  - JOUR
AU  - Aidun, Ivan
AU  - Dean, Frances
AU  - Morrison, Ralph
AU  - Yu, Teresa
AU  - Yuan, Julie
TI  - Graphs of gonality three
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 1197
EP  - 1217
VL  - 2
IS  - 6
PB  - MathOA foundation
UR  - http://www.numdam.org/articles/10.5802/alco.80/
DO  - 10.5802/alco.80
LA  - en
ID  - ALCO_2019__2_6_1197_0
ER  - 
%0 Journal Article
%A Aidun, Ivan
%A Dean, Frances
%A Morrison, Ralph
%A Yu, Teresa
%A Yuan, Julie
%T Graphs of gonality three
%J Algebraic Combinatorics
%D 2019
%P 1197-1217
%V 2
%N 6
%I MathOA foundation
%U http://www.numdam.org/articles/10.5802/alco.80/
%R 10.5802/alco.80
%G en
%F ALCO_2019__2_6_1197_0
Aidun, Ivan; Dean, Frances; Morrison, Ralph; Yu, Teresa; Yuan, Julie. Graphs of gonality three. Algebraic Combinatorics, Tome 2 (2019) no. 6, pp. 1197-1217. doi : 10.5802/alco.80. http://www.numdam.org/articles/10.5802/alco.80/

[1] Baker, Matthew Specialization of linear systems from curves to graphs, Algebra and Number Theory, Volume 2 (2008) no. 6, pp. 613-653 | DOI | MR | Zbl

[2] Baker, Matthew; Norine, Serguei Riemann–Roch and Abel–Jacobi theory on a finite graph, Advances in Mathematics, Volume 215 (2007), pp. 766-788 | DOI | MR | Zbl

[3] Baker, Matthew; Norine, Serguei Harmonic morphisms and hyperelliptic graphs, International Math Research Notices (2009), pp. 2914-2955 | Zbl

[4] Baker, Matthew; Shokrieh, Farbod Chip-firing games, potential theory on graphs, and spanning trees, Journal of Combinatorial Theory. Series A, Volume 120 (2013), pp. 164-182 | DOI | MR | Zbl

[5] Bodewes, Jelco M.; Bodlaender, Hans L.; Cornelissen, Gunther; van der Wegen, Marieke Recognizing Hyperelliptic Graphs in Polynomial Time, Graph-Theoretic Concepts in Computer Science - 44th International Workshop, WG 2018, Cottbus, Germany, June 27-29, 2018, Proceedings (2018), pp. 52-64 | Zbl

[6] Bodlaender, Hans L. Dynamic programming on graphs with bounded treewidth, Automata, languages and programming (Tampere, 1988) (Lecture Notes in Comput. Sci.), Volume 317, Springer, Berlin (1988), pp. 105-118 | DOI | MR | Zbl

[7] Bodlaender, Hans L.; Koster, Arie M.C.A. Treewidth computations II: lower bounds, Information and Computation, Volume 209 (2011), pp. 1103-1119 | DOI | MR | Zbl

[8] Chan, Melody Tropical hyperelliptic curves, Journal of Algebraic Combinatorics, Volume 37 (2013), pp. 331-359 | DOI | MR | Zbl

[9] Chartrand, Gary; Zhang, Ping A First Course in Graph Theory, Dover books on mathematics, Dover Publications, 2012

[10] Cools, Filip; Draisma, Jan On metric graphs with prescribed gonality, Journal of Combinatorial Theory. Series A, Volume 156 (2018), pp. 1-21 | DOI | MR | Zbl

[11] Cools, Filip; Draisma, Jan; Payne, Sam; Robeva, Elina A tropical proof of the Brill-Noether theorem, Advances in Mathematics, Volume 230 (2012) no. 2, pp. 759-776 | DOI | MR | Zbl

[12] Cornelissen, Gunther; Kato, Fumiharu; Kool, Janne A combinatorial Li–Yau inequality and rational points on curves, Mathematische Annalen, Volume 361 (2015), pp. 211-258 | DOI | MR | Zbl

[13] Corry, Scott; Perkinson, David Divisors and Sandpiles: An Introduction to Chip-Firing, Amer. Math. Soc., Providence, RI, 2018 | Zbl

[14] Dhar, Deepak Self-organized critical state of sandpile automaton models, Physical Review Letters, Volume 64 (1990) no. 14, pp. 1613-1616 | DOI | MR | Zbl

[15] Eisenbud, David The geometry of syzygies: a second course in commutative algebra and algebraic geometry, Graduate texts in mathematics, Springer, New York, 2005 | Zbl

[16] Frucht, R. Herstellung von Graphen mit vorgegebener abstrakter Gruppe, Compositio Math., Volume 6 (1939), pp. 239-250 | Numdam | MR | Zbl

[17] Gathmann, Andreas; Kerber, Michael A Riemann–Roch theorem in tropical geometry, Mathematische Zeitschrift, Volume 259 (2008), pp. 217-230 | DOI | MR | Zbl

[18] Gijswijt, Dion Computing divisorial gonality is hard (2015) (https://arxiv.org/abs/1504.06713v1)

[19] Luo, Ye Rank-determining sets of metric graphs, Journal of Combinatorial Theory. Series A, Volume 118 (2011), pp. 1775-1793 | DOI | MR | Zbl

[20] Mikhalkin, Grigory; Zharkov, Ilia Tropical curves, their Jacobians and theta functions, Curves and abelian varieties (Contemp. Math.), Volume 465, Amer. Math. Soc., Providence, RI, 2008, pp. 203-230 | DOI | MR | Zbl

[21] Urakawa, Hajime A discrete analogue of the harmonic morphism and Green kernel comparison theorems, Glasg. Math. J., Volume 42 (2000) no. 3, pp. 319-334 | DOI | MR | Zbl

[22] van der Wegen, Marieke Stable gonality of graphs, Masters thesis, Utrecht University (Netherlands) (2017)

[23] van Dobben de Bruyn, Josse Reduced divisors and gonality in finite graphs, Bachelor’s thesis, Mathematisch Instituut, Universiteit Leiden (Netherlands) (2012)

[24] van Dobben de Bruyn, Josse; Gijswijt, Dion Treewidth is a lower bound on graph gonality (2014) (https://arxiv.org/abs/1407.7055)

Cité par Sources :