Skip to main content
Added details that might help
Source Link
coolpapa
  • 525
  • 2
  • 13

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.

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?

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.

Source Link
coolpapa
  • 525
  • 2
  • 13

Bijection directly from (n,n+1)-core partitions to parking functions?

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?