# 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