Rank of graph divisors
From Egres Open
The rank of divisor D is the smallest number G such that by subtracting a divisor of degree k+1 from D, we can get a divisor which is not linearly equivalent to an effective divisor.
Formally, let Div(G) denote the set of divisors on a graph G. A graph divisor D is effective if D(v)≥0 for all v∈V.
Definition(The rank of a divisor [1])
rank(D) = min {deg(E)−1: E∈Div(G), E is effective, D−E is not linearly equivalent to any effective divisor}.
Remarks
- If D is not linearly equivalent to an effective divisor, then rank(D)=−1.
- 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
