The paper by M. Baker and S. Norine in 2007 introduced a new parameter on configurations of graphs and gave a new result in the theory of graphs which has an algebraic geometry flavor. This result was called Riemann-Roch formula for graphs since it defines a combinatorial version of divisors and their ranks in terms of configurations on graphs. The so called chip firing game on graphs and the sandpile model in physics play a central role in this theory. In this paper we present an algorithm for the determination of the rank of configurations for the complete graph $K_n$. This algorithm has linear arithmetic complexity. The analysis of number of iterations in a less optimized version of this algorithm leads to an apparently new parameter which we call the prerank. This parameter and the parameter dinv provide an alternative description to some well known $q,t$-Catalan numbers. Restricted to a natural subset of configurations, the two natural statistics degree and rank lead to a distribution which is described by a generating function which, up to a change of variables and a rescaling, is a symmetric fraction involving two copies of Carlitz $q$-analogue of the Catalan numbers. In annex, we give an alternative presentation of the theorem of Baker and Norine in purely combinatorial terms.
@article{10_37236_4350,
author = {Robert Cori and Yvan Le Borgne},
title = {On computation of {Baker} and {Norine's} rank on complete graphs},
journal = {The electronic journal of combinatorics},
year = {2016},
volume = {23},
number = {1},
doi = {10.37236/4350},
zbl = {1331.05117},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4350/}
}
TY - JOUR
AU - Robert Cori
AU - Yvan Le Borgne
TI - On computation of Baker and Norine's rank on complete graphs
JO - The electronic journal of combinatorics
PY - 2016
VL - 23
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/4350/
DO - 10.37236/4350
ID - 10_37236_4350
ER -
%0 Journal Article
%A Robert Cori
%A Yvan Le Borgne
%T On computation of Baker and Norine's rank on complete graphs
%J The electronic journal of combinatorics
%D 2016
%V 23
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/4350/
%R 10.37236/4350
%F 10_37236_4350
Robert Cori; Yvan Le Borgne. On computation of Baker and Norine's rank on complete graphs. The electronic journal of combinatorics, Tome 23 (2016) no. 1. doi: 10.37236/4350
