Rank of graph divisors
From Egres Open
The rank of divisor [math]D[/math] is the smallest number [math]G[/math] such that by subtracting a divisor of degree [math]k+1[/math] from [math]D[/math], we can get a divisor which is not linearly equivalent to an effective divisor.
Formally, let [math]Div(G)[/math] denote the set of divisors on a graph [math]G[/math]. A graph divisor [math]D[/math] is effective if [math]D(v) \ge 0 [/math] for all [math]v \in V[/math].
Definition(The rank of a divisor [1])
rank(D) = min {[math]\deg(E) - 1[/math]: [math]E \in Div(G)[/math], [math]E[/math] is effective, [math]D-E[/math] is not linearly equivalent to any effective divisor}.
Remarks
- If [math]D[/math] is not linearly equivalent to an effective divisor, then [math] \rm{rank}(D) = -1[/math].
- Determining the rank of a graph divisor is NP-hard, even on simple undirected graphs [2].
- The most well-known theorem about this rank function is the Riemann-Roch-theorem of Baker and Norine [1].
References
- ↑ 1.0 1.1 M. Baker, S. Norine, Riemann--Roch and Abel--Jacobi theory on a finite graph, DOI link, ArXiv Link
- ↑ V. Kiss, L. Tóthmérész, Chip-firing games on Eulerian digraphs and the NP-hardness of computing the rank of a divisor on a graph, DOI link, EGRES Technical Report
