Set $\mathbb{N} := \{0,1,2,\ldots\}$. A parking function of length $n$ is a sequence $(\alpha_1,\ldots,\alpha_n) \in \mathbb{N}^n$ whose weakly increasing rearrangement $\alpha_{i_1} \leq \alpha_{i_2} \leq \cdots \leq \alpha_{i_n}$ satisfies $\alpha_{i_j} \leq j-1$ for all $1 \leq j \leq n$. Let $\mathrm{PF}(n)$ denote the set of parking functions of length $n$. Let $K_{n}$ denote the complete graph on $n$ vertices. It is very well-known that $$\#\mathrm{PF}(n) = \#\textrm{ of spanning trees of }K_{n+1}=(n+1)^{n-1}.$$ (This sequence is http://oeis.org/A000272.) Moreover, there are many explicit bijections between parking functions and labeled trees, with interesting properties. I am interested in a bipartite analog of this result. Let $K_{m,m}$ denote the complete bipartite graph with $m$ vertices in one part and $m$ in the other part. It is not hard to show that $$ \#\{(\alpha_1,\ldots,\alpha_{2m-1}) \in \mathrm{PF}(2m-1)\colon \alpha_i \textrm{ is even for all }i\} = \#\textrm{ of spanning trees of }K_{m,m} = m^{2m-2}.$$ (This sequence is http://oeis.org/A068087.) I wonder if there is a simple bijective proof of this last equality. This problem is a special case of (3) in Section 5 of http://arxiv.org/abs/1506.03470.
-
$\begingroup$ Any idea how this would look like for $K_{n,m}$ ? $\endgroup$– darij grinbergCommented Feb 3, 2016 at 22:35
-
1$\begingroup$ The number of spanning trees of $K_{n,m}$ is $n^{m-1}m^{n-1}$ (oeis.org/A072590). Whereas the even parking functions described are (after dividing by two) $(2m-1,m)$-rational parking functions; it is known that the number of $(a,b)$-parking functions with $\mathrm{gcd}(a,b)=1$ is $b^{a-1}$. (The same classical proof of Pollak works to show this.) So to answer your question, no I don't know what it would look like for $K_{n,m}$. $\endgroup$– Sam HopkinsCommented Feb 3, 2016 at 22:52
2 Answers
Let $n=2m$ and let $(\alpha_1,\dots,\alpha_{2m-1})$ be an even parking function. Apply Pollak's map: $c=(\alpha_2-\alpha_1,\dots,\alpha_{2m-1}-\alpha_{2m-2})\mod 2m$.
Thus $c$ is an $(2m-2)$-tuple of even numbers between $0$ and $2m-1$. Let $a=(c_1/2,\dots,c_{m-1}/2)$ and let $b=(c_m/2+m,\dots,c_{2m-2}/2+m)$.
Then $(a,b)$ is the 'bipartite' Prüfer code of a spanning tree of $K_{m,m}$, where the vertices of one block are labelled $0,\ldots,m-1$ and the vertices of the other block are labelled $m,\ldots,2m-1$.
-
$\begingroup$ I agree that something like this "should" work. Basically you are composing bijective proofs that the number is $m^{2m-2}$. But somehow I could hope for a more "tree-like" proof akin to known proofs for the non-bipartite case. For instance, we could require a bijection in the classical case that restricts to the bipartite case... $\endgroup$ Commented Feb 7, 2016 at 1:52
-
$\begingroup$ I think it would be good if you could make more precise what you want in the question. At least, the bijection described in this answer is the straightforward analog of the classical bijection: the first step is identical to the classical case, the second step is the bipartite analogue. $\endgroup$ Commented Feb 7, 2016 at 9:49
-
$\begingroup$ I am accepting this answer. However, I still think a desirable property for a bijection from even parking functions to spanning trees of $K_{m,m}$ would be that it is obtained by restricting a (simple) bijection form parking functions to spanning trees of $K_{2m}$. I don't think this map has that property. $\endgroup$ Commented Feb 7, 2016 at 15:07
This is far from an answer, but only a possible first part of such a bijection. (There were two plainly wrong bijection parts in the first version that cannot be fixed.)
The bijection between factorizations of the long cycle $(1,\ldots,2m)$ and parking functions of length $2m-1$ described in my answer https://mathoverflow.net/a/94241/21291 restricts to a bijection with the desired property:
First: To fit the context of the other answer, I use $1 \leq \alpha_{i_j} \leq j$ rather than your $0 \leq \alpha_{i_j} < j$ and consider thus parking functions of length $2m-1$ with all parts being odd.
Lemma: A parking function $p = p_1\cdots p_{2m-1}$ has all parts odd if and only if the factorization $\Psi^{-1}(p) = (i_1j_1)\cdots(i_{2m-1}j_{2m-1})$ has the property that all first entries $i_1,\ldots,i_{2m-1}$ are odd.
Corollary: The bijection $\Psi$ restricts to a bijection between factorizations of the long cycle $(1,\ldots,2m)$ into transpositions $(i_kj_k)$ with all $i_k$ odd and parking functions of length $2m-1$ with all parts being odd.
Using this observation it would be thus left to find a bijection between such factorizations and spanning trees of $K_{m,m}$.
