Mathematics — Graph Theory · chip-firing-clawbacks
Problem
We continue with the setting and terminology of Exercise 5.21.
A clawback is an operation that transforms a wealth distribution as follows: We choose a vertex v, and we increase its wealth by its outdegree deg+v, and then decrease the wealth of each vertex w∈V (including v itself) by av,w. (Thus, a clawback is the inverse of a donation.)
Let k be a wealth distribution on D whose total wealth is larger than ∣A∣−∣V∣. Prove that by an appropriately chosen finite sequence of clawbacks, we can ensure that no vertex is in debt.
[Remark: Note that we are still assuming D to be strongly connected. Otherwise, the truth of the claim is not guaranteed.]
[Hint: Show that any donation is equivalent to an appropriately chosen composition of clawbacks. Something we know about the Laplacian may come useful here.]