Mathematics — Graph Theory · chip-firing-donations
Problem
Let D=(V,A,ψ) be a strongly connected multidigraph.
A wealth distribution on D shall mean a family (kv)v∈V of integers (one for each vertex v∈V). If k=(kv)v∈V is a wealth distribution, then we refer to each value kv as the wealth of the vertex v, and we define the total wealth of k to be the sum ∑v∈Vkv. We say that a vertex v is in debt in a given wealth distribution k=(kv)v∈V if its wealth kv is negative.
For any vertices v and w, we let av,w denote the number of arcs that have source v and w.
A donation is an operation that transforms a wealth distribution as follows: We choose a vertex v, and we decrease its wealth by its outdegree deg+v, and then increase the wealth of each vertex w∈V (including v itself) by av,w. (You can think of v as donating a unit of wealth for each arc that has source v. This unit flows to the target to this arc. Note that a donation does not change the total wealth.)
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 donations, we can ensure that no vertex is in debt.
[Hint: A donation will be called safe if its donor v (that is, the vertex chosen to lose wealth) satisfies kv≥deg+v, where k is the wealth distribution just before this donation. Start by showing that if the total wealth is larger than ∣A∣−∣V∣, then at least one vertex v has wealth ≥deg+v (and thus can make a safe donation). Next, show that for any given wealth distribution k, there are only finitely many wealth distributions that can be obtained from k by a sequence of safe donations. Finally, for any vertex v, find a rational quantity that increases every time that a donor distinct from v makes a donation. Conclude that in a sufficiently long sequence of safe donations, every vertex must appear as a donor. But a donor of a safe donation must be out of debt just before its safe donation, and will never go back into debt.]