Georgia Institute of Technology College of Sciences

The Jacobian group Jac(G) of a finite graph G is a finite abelian group whose cardinality is the number of spanning trees of G. It is natural to wonder whether there is a canonical simply transitive action of Jac(G) on the set of spanning trees which "explains" this numerical coincidence. Surprisingly, this turns out to be related to topological embeddings: we will explain a certain precise sense in which the answer is yes if and only if G is planar. We will also explain how tropical geometry sheds an interesting new light on this picture.

We will present the solution to a statistical mechanics model on random lattices. More precisely, we consider the Potts model on the set of planar triangulations (embedded planar graph such that every face has degree 3). The partition function of this model is the generating function of vertex-colored triangulations counted according to the number of monochromatic edges and dichromatic edges. We characterize this partition function by a simple system of differential equations. Some special cases, such as properly 4-colored triangulations, lead to particularly simple equations waiting for a more direct combinatorial explanation. This is joint work with Mireille Bousquet-Melou.

In a recent series of papers a strong connection has been established between standard models of sexual evolution in mathematical biology and Multiplicative Weights Updates Algorithm, a ubiquitous model of online learning and optimization. These papers show that mathematical models of biological evolution are tantamount to applying discrete replicator dynamics, a close variant of MWUA on coordination games. We show that in the case of coordination games, under minimal genericity assumptions, discrete replicator dynamics converge to pure Nash equilibria for all but a zero measure of initial conditions. This result holds despite the fact that mixed Nash equilibria can be exponentially (or even uncountably) many, completely dominating in number the set of pure Nash equilibria. Thus, in haploid organisms the long term preservation of genetic diversity needs to be safeguarded by other evolutionary mechanisms, such as mutation and speciation. This is joint work with Ruta Mehta and Ioannis Panageas.

The famous Doignon-Bell-Scarf theorem is a Helly-type result about the existence of integer solutions on systems linear inequalities. The purpose of this paper is to present the following ``weighted'' generalization: Given an integer k, we prove that there exists a constant c(k,n), depending only on the dimension n and k, such that if a polyhedron {x : Ax <= b} contains exactly k integer solutions, then there exists a subset of the rows of cardinality no more than c(k,n), defining a polyhedron that contains exactly the same k integer solutions. We work on both upper and lower bounds for this constant. This is joint work with Quentin Louveaux, Iskander Aliev and Robert Bassett.