It is well-known that the increasing parking functions are counted by the Catalan numbers. The Catalan numbers also count the dominant alcoves in the Shi arrangement of type $A_{n}$. Athanasiadis-Linusson gave a bijection between these two (and in fact between the sets of all Shi alcoves and all parking functions.) In addition, Fishel-Vazirani gave a bijection from dominant Shi alcoves to partitions which are both $n$ and $n+1$-core. This (composed with Athanasiadis-Linusson) gives a bijection from such partitions to increasing parking functions. Has anyone made this direct map explicit?

Edit: In conversations in the comments, I've vaguely remembered something that might be helpful in solving this. Somewhere I recall reading about "Inversion-labelled Dyck paths" or something like that. The idea is to turn a Dyck path into a partition in the usual way, but label the partitions in a different way. Specifically, label the diagonal of the partition with a permutation $\phi$, but with the restriction that if $i<j$, then $\phi_{i} > \phi_{j}$ can only occur if there is not a removable box where $i$ and $j$ meet. (This means the Dyck path has no valley there.) So the partition consisting of a single box could be labelled as 123,213, or 132. Since the box aligns with the first and third entries of the permutation, $\phi_{1} < \phi_{3}$. Similarly, the partition 2 can be labelled as 123,213, or 312. Now, the second box in the first row is removable, forcing $\phi_{2} < \phi_{3}$. There are the same number of these labellings as there are parking functions.

Unfortunately, I don't see a reference to something like this in the OEIS entry for parking functions, and I don't immediately see a bijection with parking functions. I'm sure this isn't my original idea, either - I suspect it's due to some subset of Haiman/Haglund/Loehr/Remmel but I'm not finding it right now. I think finding the reference for this idea would be quite helpful. Apologies for the vagueness of my memories of it.

  • $\begingroup$ The answer to the question posed in my edit is in Haglund and Loehr's "A conjectured combinatorial formula for the Hilbert series for diagonal harmonics." (ams.org/mathscinet/search/…), section 3. I am not sure if those ideas can be used to answer the overall question, but it seems quite possible at this point. $\endgroup$ – coolpapa May 30 '17 at 19:12
  • $\begingroup$ You might be interested in this paper: arxiv.org/abs/1604.06554 $\endgroup$ – Sam Hopkins Jun 6 '18 at 2:26

Increasing parking functions are in (more or less canonical) bijection with Dyck paths (see, e.g., here), so your question can be rephrased as

Is there a direct bijection between (n,n+1)-cores and Dyck paths?

Indeed, you find this bijection in Partitions which are simultaneously t1- and t2-core by Jaclyn Anderson, where a bijection beween rational Dyck paths and coprime bicores is constructed.

You find this also recalled and generalized in Rank complement of rational Dyck paths and conjugation of (m,n)-core partitions by Guoce Xin.

(I am sure I have seen several more papers on that, so let me know if you need more references.)

  • $\begingroup$ Thank you very much for the pointers. But I think Anderson's bijection matches up with the Pak-Stanley labelling of the Shi arrangement. I'll summarize my thinking briefly here in case I've done something incorrectly. For $(3,4)$-core partitions, Anderson tells us to look at the integer lattice: $\begin{array}{cccc} 1 & -2 & -5 & -8 \\ 5 & 2 & -1 & -4 \end{array}$. Then for, say, the partition (3,1,1), she would mark the hook numbers 5,2,1. That gives the Dyck path that alternates up and down steps, which corresponds to the parking function (1,2,3), since it must have no repeated values. $\endgroup$ – coolpapa May 30 '17 at 16:40
  • $\begingroup$ However, This is where the Pak-Stanley and Athanasiadis-Linusson bijections differ. P-S assigns the parking function (1,2,3) to the dominant alcove of the Shi arrangement farthest from the origin, and (1,1,1) to the fundamental alcove. A-L does the exact opposite. So I am looking for a direct way to turn the 3-core $(3,1,1)$ into the parking function $(1,1,1)$, and the 3-core $\emptyset$ into the parking function $(1,2,3)$. $\endgroup$ – coolpapa May 30 '17 at 16:45
  • $\begingroup$ Oh, I see. I was missing that indeed. $\endgroup$ – Christian Stump May 30 '17 at 16:47
  • $\begingroup$ I admit this idea is half-baked, but it might work. Parking functions are an indexing of maximal chains of non-crossing partitions (Stanley here: combinatorics.org/ojs/index.php/eljc/article/view/v4i2r20/pdf), and the Athanasiadis-Linusson bijection uses non-nesting partitions of a very particular type. I wonder if the non-crossing/non-nesting correspondence can be brought to bear somehow to make a circuitous link between Pak-Stanley and Athanasiadis-Linusson? $\endgroup$ – coolpapa May 30 '17 at 17:12
  • $\begingroup$ This answer contains most of what is needed - thanks very much for your help! The last step is described in my answer below. $\endgroup$ – coolpapa May 31 '17 at 17:08

After Christian Stump's restatement of your question, in the language of Dyck paths, let's one more reference here which extends the discussion to multi-core partitions, posets and lattice paths (with a notion of generalized Dyck paths).


I believe I have as much of an answer as I'm going to get. An $(n,n+1)$-core turns into an $n$-abacus diagram (this map is at the heart of Anderson's paper Partitions which are simultaneously t1- and t2-core, as pointed out by Christian Stump). Then, we read the abacus diagram as a Dyck path. But now, the bijection from Dyck paths to nonnesting partitions (See Stanley's solution to part uu of Exercise 6.19, where he phrases the bijection essentially in terms of the root poset $\Phi^{+}$) comes into play. Rotate the Dyck path 45 degrees to get the outline of a partition that fits inside the partition $(n,n-1,n-2,\ldots 2,1)$. If this partition has a removable box in row $i$ (counting down from the top starting at $n$) and column $j$ (counting from the left starting at 1), then connect $i$ and $j$ in the resulting set partition. Then, read this set partition as in Athanaisdis-Linusson's paper - $f(x)$ is defined to be the smallest element in the block of the set partition containing $x$.

For example, the $(3,4)$-core $(3,1,1)$ becomes the $3$-abacus diagram with beads at 5,2,1 - corresponding to the hook lengths of the first column. This gives the partition $(2,1)$. This partition has two removable boxes, at positions $(1,2)$ and $(2,3)$, which gives us the set partition $\{\{1,2,3\}\}$. By the A-L map, this is the parking function $(1,1,1)$.

Conversely, the $(3,4)$-core $\emptyset$ becomse the $3$-abacus diagram with no beads, which gives the empty partition. This in turn corresponds to the finest set partition $\{\{1\},\{2\},\{3\}\}$, which A-L interprets as the parking function $(1,2,3)$.

The key insight is that the removable boxes of the Abacus diagram (considered as a partition as we have just done) essentially do same work as the affine symmetric group action in Fishel-Vazirani. Both encode the affine "floors" of the corresponding Shi chamber - the removable boxes label them directly (the connection $(i,j)$ in the set partition means the hyperplane $x_{i} - x_{j} = 1$ is a boundary of the Shi chamber at hand), while F-V connects the floors to roots in the inversion set of the corresponding affine symmetric group element.

(I should acknowledge some debt to Armstrong-Rhoades' paper The Shi Arrangement and the Ish Arrangement - a remark there pointed me to the connection between the A-L correspondence and floors of Shi chambers.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.