Generalized Riemann functions, their weights, and the complete graph

Nicolas Folinsbee¹ ; Joel Friedman¹

¹University of British Columbia

The electronic journal of combinatorics, Tome 30 (2023) no. 2

Résumé

By a Riemann function we mean a function $f:\mathbb{Z}^n\to\mathbb{Z}$ such that $f(\mathbf{d})$ is equals $0$ for $d_1+\cdots+d_n$ sufficiently small, and equals $d_1+\cdots+d_n+C$ for a constant, $C$, for $d_1+\cdots+d_n$ sufficiently large. By adding $1$ to the Baker-Norine rank function of a graph, one gets an equivalent Riemann function, and similarly for related rank functions. To each Riemann function we associate a related function $W: \mathbb{Z}^n\to \mathbb{Z}$ via Möbius inversion that we call the weight of the Riemann function. We give evidence that the weight seems to organize the structure of a Riemann function in a simpler way: first, a Riemann function $f$ satisfies a Riemann-Roch formula iff its weight satisfies a simpler symmetry condition. Second, we will calculate the weight of the Baker-Norine rank for certain graphs and show that the weight function is quite simple to describe; we do this for graphs on two vertices and for complete graphs. For complete graphs, we build on the work of Cori and Le Borgne who gave a linear time method to compute the Baker-Norine rank of the complete graph. The associated weight function has a simple formula and is extremely sparse (i.e., mostly zero). Our computation of the weight function leads to a new linear time algorithm to compute the Baker-Norine rank, via a new formula likely related to one of Cori and Le Borgne, but seemingly simpler for general $\mathbf{d}\in \mathbb{Z}^n$, namely$$r_{{\rm BN},K_n}(\mathbf{d}) =-1+\biggl| \biggl\{ i=0,\ldots,\deg(\mathbf{d}) \ \Bigm|\ \sum_{j=1}^{n-2} \bigl( (d_j-d_{n-1}+i) \bmod n \bigr) \le \deg(\mathbf{d})-i\biggr\} \biggr|.$$However, the formula of Cori and Le Borgne, which requires $\mathbf{d}\in \mathbb{Z}^n$ to be a sorted parking function, is easier to evaluate for such $\mathbf{d}$. Our study of weight functions leads to a natural generalization of Riemann functions, with many of the same properties exhibited by Riemann functions.

Détail

DOI : 10.37236/11281

Classification : 14C40, 14H10, 14H51
Mots-clés : Riemann-Roch like theorem, Baker-Norine rank, Riemann-Roch formula