Duality between chip-firing games and graph divisor theory
There is a duality between the notion of graph divisor theory and chip-firing, which was discovered by Baker and Norine [1].
Let [math]G [/math] be a graph and let [math]K^+ = K^+_G[/math] be the chip-distribution with [math]K^+(v)=d(v) - 1[/math] for each vertex [math]v[/math].
For a divisor [math]D\in Div(G)[/math] with [math]D(v)\leq d(v)-1[/math] for each [math]v\in V(G)[/math], we call [math]K^+ - D\geq 0[/math] the dual pair of [math] D [/math]. Note that each chip-distribution is a dual pair of some divisor.
The following proposition of Baker and Norine is the key ingredient of the duality:
Theorem[1]. For a divisor [math] D\in Div(G)[/math] with [math]D(v)\leq d(v)-1[/math] for each [math]v\in V(G)[/math], there exists an effective divisor equivalent to [math]D[/math] if and only if [math]K^+ - D[/math] is a terminating chip-distribution.
The following is a straightforward consequence of the above theorem.
Theorem. Let [math]D \in Div(G)[/math] be a divisor with [math]f(v)\leq d(v)-1[/math] for each [math]v\in V(G)[/math], and let [math]x \in Chip(G)[/math] be its dual pair. Then [math]rank(f) = dist(x) - 1[/math].
References
- ↑ 1.0 1.1 M. Baker, S. Norine, Riemann--Roch and Abel--Jacobi theory on a finite graph, DOI link, ArXiv Link
