Discrete Math Seminar: Yvan Le Borgne

In 2007, Baker and Norine stated a theorem which they called a version for graphs of a Riemann-Roch theorem. In this theorem,the rank is an integer parameter defined by an optimisation among some compositions on labeling of vertices by integers. In the case of complete graphs, we provide a greedy algorithm to compute the rank in linear time. Then we study the joint distribution of the rank and the other parameter in Baker and Norine theorem. This involves objects like parking functions, numbers like the Catalan numbers, and bijections, in a framework close to the sandpile model studied by Dhar. The interest in these classical notions is renewed by the addition of seemingly new parameters (orappearing in other contexts) deduced from the analysis of our greedy algorithm.

Joint work with Robert Cori.