Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

The classical parking function story is as follows: we have cars $v_1,\ldots,v_n$ who approach a line of spaces marked $0,\ldots,n-1$ in order. Each car $v_i$ has space preference $a_i$. A car will drive until it reaches its preferred spot; if its preferred spot is empty, it will park there, otherwise it will park in the first empty spot after this space. If there is no empty spot after its preferred space, the car cannot park. A parking function is a list $(a_1,\ldots,a_n)$ such that all the cars get to park.

Say we add car $v_0$, space $-1$, and dictate that $v_0$ always prefers spot $-1$. A reformulation of the parking story is now as follows. Repeat the following as long as you can: look through the cars $v_i$ that have yet to park in order, and park the first one you come to whose preference is less than the number of cars that have yet parked. It is easy to see that if all the cars park, this gives the same parking order as above, and if the process here fails (i.e. not all cars park), then the process above fails as well.

Now it is pretty clear how to translate this to graphs. For background on the Abelian sandpile model, see http://arxiv.org/abs/1112.6163. Let $G$ be a graph on vertices $v_0,\ldots,v_n$, with $v_0$ identified as a sink. Consider some configuration $c := \sum c_i v_i$ on the vertices of $G$ with $c_0 = -1$ and $c_i \geq 0$ for $i > 0$. Let $c_{\mathrm{max}} := \sum (\mathrm{deg}(v_i) - 1)v_i$, and dualize your configuration to $b := c_{\mathrm{max}} - c$. Repeat the following as long as you can: look through the vertices $v_i$ that have yet to fire in order, and fire the first one you come to that is unstable. By Dhar's algorithm, the configuration $b$ is recurrent if and only if all of the vertices fire, and in this case $c$ is superstable, i.e. a $G$-parking function. We have thus a nice translation of the parking story to graphs; the dictionary between terms in the two stories looks like:

  • parking preference of $v_i$ ---> number of grains of sand on $v_i$
  • order that cars approach spaces ---> firing preference order
  • order that cars park ---> order that vertices fire
  • all the cars park ---> all the vertices fire

There is a cute way to count classical parking functions. Add a space $n$ and put the parking spaces in a circle instead of a line. Allow preference for spot $n$. All the cars will now be able to park, and one space will be empty. But such a "circular" parking function is only a real parking function when space $n$ is empty. And (you can convince yourself of this by considering $(a_1 + j, \ldots, a_n + j)$ reduced mod $n$) over all circular parking functions, each spot is equally likely to be left blank. So the number of parking functions is $1/(n+1) \cdot (n+1)^{n} = (n+1)^{n-1}$, Cayley's formula for the number of spanning trees of $K_{n+1}$.

My question is, can we translate this circle parking story to graphs so that the above dictionary of terms still makes sense? We cannot hope for a nice formula for the number of graphical parking functions because in general this number is the number of spanning trees of $G$ (which is the determinant of the reduced Laplacian). But perhaps this circle parking story will tell us something algebraic. In particular, I think that adding an extra spot corresponds in some way to considering the graph $G_{\bullet}$, the graph obtained from $G$ by adding an extra vertex $q$ connected by an edge to every vertex in $G$ and with $q$ now regarded as the sink. If so, the circle parking story might tell us how the superstable group of $G$ sits inside the stable semigroup of $G_{\bullet}$. For the connection between $G_{\bullet}$-parking functions and $G$-parking functions, see: http://arxiv.org/abs/1112.5421.

share|improve this question
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.