Grinberg-Introduction-Graph-Theory · Problem 5.22

Trees and arborescences

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 \in V

(including

v

itself) by

a_{v,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. For instance, for the digraph

\begin{array}{cc} 3 & 4 \\ 1 & 2 \end{array}

with wealth distribution

(k_1, k_2, k_3, k_4) = (0, 0, -1, 2)

, no sequence of donations and clawbacks will result in every vertex being out of debt (since the wealth difference

k_4 - k_3

is preserved under any donation or clawback, but this difference is too large to come from a debt-free distribution with total weight 1). ] [Hint: Show that any donation is equivalent to an appropriately chosen composition of clawbacks. Something we know about the Laplacian may come useful here.]

Browse the problem library