Skip to main content
1 of 6
Will Sawin
  • 148.4k
  • 9
  • 324
  • 563

For two such functions $f$ and $g$, the difference $f-g$ is invariant under chip-firing, i.e. it factors through a function from the cokernel of the Laplacian to $\mathbb Z/k$. Conversely, for such a function $f$, adding any function from the cokernel of the Laplacian to $\mathbb Z/k$ produces another such function.

So if there are any such functions, they are classified by functions from the cokernel of the Laplacian to $\mathbb Z/k$.

Thus, the main problem is the existence problem. For the existence problem, the main thing is the kernel of the Laplacian.

I claim that such $f$ exists if and only if $k$ divides the sum of the entries of all vectors in $\mathbb Z^n$ that lie in the kernel of the Laplacian. For instance, for connected undirected graphs, this happens if $k$ divides $n$, as Sam Hopkins points out in the comments.

The "only if" argument is straightforward, and was essentially given by Sam Hopkins - when we perform these chip-firing operations, each vector in the kernel of the Laplacian gives a sequence of operations (and inverse operations) we can perform to get back to our starting configuration, and the total number of operations had better be a multiple of $k$.

The converse isn't too much harder. Fix, for each coset of $\mathbb Z^{n+1}$ mod the image of the Laplacian, a representative. Define $f(x)$ to be the number of steps (minus the number of inverse steps) it takes to get from the representative of the coset of $x$ to $x$. This is well-defined because $k$ divides the entry sum of each vector in the kernel - if we have two different paths to $x$, their difference lies in the kernel.

For an outdegree-regular graph, the kernel of the Laplacian consists of linear combinations of stationary distributions for the random walk on the graph. In a generic situation, there will be a unique stationary distribution, which necessarily has rational probabilities, and the condition is that $k$ should divide the least common denominator of the probabilities occurring in it.

Will Sawin
  • 148.4k
  • 9
  • 324
  • 563