In Polynomials, meanders, and paths in the lattice of noncrossing partitions, they talk about sequences of non-crossing matchings related by "flips".

Savitt counts "maximal chains of 2-divisible noncrossing partitions to the set of necklaces" and there seems to be some relation to parking functions.

What do these bijections look like?


The bijection between the set of "necklaces" and the set of "maximal chains of 2-divisible noncrossing partitions" is given in Theorem 6.10(1) of the paper of mine that you cite, and the construction is fairly natural.

Let me quickly review some terminology. I'll refer the reader to Wikipedia for the definition of a noncrossing partition; a noncrossing matching is a noncrossing partition in which all the blocks have size two. Two noncrossing matchings $M$, $M'$ on the set $\{ 0,...,2n-1\}$ are said to be flips of one another if all but two of the pairs in $M$ are also paired in $M'$; or in other words if $M'$ can be obtained from $M$ by taking two pairs $\{i,j\},\{k,l\}$ of $M$ and replacing them with $\{i,l\},\{j,k\}$.

If $M$ is a noncrossing matching on $\{ 0,...,2n-1\}$, I'll let $M(k)$ denote the noncrossing matching obtained by rotating $M$ by $k$ spots; so if $i,j$ are matched in $M$, then $i+k,j+k$ are matched in $M(k)$ (with indices taken modulo $2n$).

Then a necklace is a sequence of noncrossing matchings $M_1,\ldots,M_n$ with $M_{i+1}$ a flip of $M_i$ for all $i$, and $M_n = M_1(-1)$. (It's a theorem that one cannot get from $M_1$ to $M_1(-1)$ in fewer than $n-1$ flips.)

On the other side of the bijection you mention, a maximal chain of 2-divisible noncrossing partitions on $\{ 0,...,2n-1\}$ is a sequence $P_1,\ldots,P_n$ where each $P_i$ is a noncrossing partition of $\{ 0,...,2n-1\}$ all of whose blocks have even size, where $P_i$ has exactly $n+1-i$ blocks, and $P_i$ is a refinement of $P_{i+1}$. (So $P_1$ is a noncrossing matching, $P_2$ is obtained by lumping together two of the pairs from $P_1$ but still required to be noncrossing, etc, and $P_n$ is the partition with a single block containing all of $0,\ldots,2n-1$.

Here's the bijection from necklaces to maximal chains of 2-divisible noncrossing partitions. Start with a necklace $M_1,\ldots,M_n$. Then $P_i$ is the set of equivalence classes under the coarsest equivalence relation on $\{ 0,...,2n-1\}$ in which elements paired in $M_1$ are related and elements paired in $M_i$ are related. (It's a pleasant exercise to check that $P_n$ is the whole set.)

The relationship between maximal chains of 2-divisible noncrossing partitions (or $k$-divisible noncrossing partitions) and parking functions is a basically unrelated story, as far as I know. There's a bijection between maximal chains of $k$-divisible noncrossing partitions of $\{0,\ldots,kn-1\}$ and $k$-parking functions of length $n-1$, where the latter is a tuple of positive integers $(a_1,\ldots,a_{n-1})$ (not necessarily in increasing order) such that the $i$th smallest integer in the collection is no greater than $ki$. To go from a chain $P_1,\ldots,P_n$ to a parking function, do the following: suppose that $B$ and $B'$ are the blocks of $P_i$ that are merged in $P_{i+1}$, and without loss of generality suppose that $ \min B < \min B' = b_i$. Then take $a_i$ to be the largest element of $B$ that is less than $b_i$. (See Theorems 3.1 and 5.1 of this paper by Richard Stanley, for instance, though I can't speak to the original attribution.)


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.