10:00am - 12:00pmChip-firing and tropical curves
Chair(s): Chi Ho Yuen (University of Bern), Alejandro Vargas (University of Bern)
The chip-firing game on metric graphs is a simple combinatorial model that serves as a tropical analogue of divisor theory on algebraic curves, and it has been an active and fruitful research direction over the last decade. The behaviors of chip-firing resemble, but not always completely match, the classical situation in algebraic geometry. So on one hand, chip-firing can often be used to prove results (old and new) in algebraic geometry; while on the other hand, the combinatorics of chip-firing is interesting and surprising in its own right. We will focus on three main topics: (I) Tropical analogues (or failure thereof) of classical results of algebraic curves, (II) applications of chip-firing in algebraic geometry and other subjects, and (III) complexity issues of computational problems related to chip-firing.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Introduction to chip firing
Alejandro Vargas
University of Bern
This session is intended as a preamble, giving a quick outline on chip-firing and introducing concepts likely to appear in several of the talks to follow. These include: graphs, metric graphs, divisor theory (divisors, linear equivalence, rank), Jacobian group, reduced divisors, divisorial gonality, and related concepts. We illustrate with graphs of low genus.
Computing divisorial gonality is hard
Dion Gijswijt
TU Delft
The (divisorial) gonality of a graph G is the smallest degree of a divisor of positive rank in the sense of Baker-Norine. In terms of the classical chip-firing game of Björner-Lovász-Shor it relates to chip configurations that result in a finite game, even after adding a chip at an arbitrary position. We show that computing the gonality of a graph is NP-hard. In fact, it cannot be approximated to within an arbitrary factor in polynomial time (unless P=NP).
Recognizing hyperelliptic graphs
Marieke van der Wegen
University of Utrecht
Based on analogies between algebraic curves and graphs, a new multigraph parameter was defined. This parameter is called divisorial gonality and can be defined using a chip-firing game. In this talk we consider so-called hyperelliptic graphs, which are graphs with divisorial gonality 2. We will see that we can decide in polynomial time whether a graph is hyperelliptic or not.
Graphs of gonality three
Ralph Morrison
Williams College
In 2013, Chan classified all metric graphs of gonality two, 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-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.
