4
$\begingroup$

For a definition of the cyclic sieving phenomena, see "The cyclic sieving phenomenon: a survey", by B. Sagan.

A matching of $[2n] = \{1,2,\dots, 2n \}$ is a graph with vertex set $[2n]$ and with $n$ non-incident edges. A matching is noncrossing if there are no edges $ab$ and $cd$ such that

$$a<c<b<d.$$

We denote the set of noncrossing matchings on $2n$ points by $\text{NCM}(2n)$

The cyclic group of order $2n$ has a natural group action on $\text{NCM}(2n)$ by rotation, see the picture from Sagan's survey: rotation of noncrossing matchings.

I have seen several sources saying that the triple $(\text{NCM}(2n), C_{2n}, \text{Cat}_n(q))$ exhibits the cyclic sieving phenomena but I have not seen a proof of this fact anywhere. I know how to evaluate $\text{Cat}_n(q)$ in $2n$:th roots of unity but I cannot figure out how to compute the fixpoints of $\text{NCM}(2n)$ under some rotation.

Either an explanation of how to compute the fixpoints under some rotation or a link to some proof of this fact would be much appreciated!

EDIT: As was pointed out in the comments, the $q$-Catalan numbers can refer to more than one family of polynomials. The one that we are using, in this case, is indeed

$$\text{Cat}_n(q)=\frac{1}{[1+n]_q}\left[2n \atop n\right]_q $$

$\endgroup$
  • $\begingroup$ Based on mathoverflow.net/questions/128891/…, there are multiple $q$-analogs of the Catalan numbers, so can you define $\text{Cat}_n(q)$? $\endgroup$ – Mike Earnest Sep 11 '18 at 15:08
  • 2
    $\begingroup$ @MikeEarnest In this case $\text{Cat}_n(q) = \frac{1}{[n+1]_q} \left[2n \atop n\right]_q$. $\endgroup$ – Misha Lavrov Sep 11 '18 at 15:12
4
$\begingroup$

Let $\def\ncm{\operatorname{NCM}}\ncm_k$ be the set of noncrossing matchings on $[2n]$ which are invariant under rotation by $k$. Whenever $k<2n$ is a divisor of $2n$, I claim that $$|\!\ncm_k(2n)|=\binom{k}{k/2}.$$

Consider a $k$-rotationally invariant noncrossing partition. An important initial observation is that every element is matched to one which is less than $k$ places to its right or less than $k$ places to its left. We will say that a the left endpoint of a matched pair $(x,y)$ is $x$ if $y\equiv x+i\pmod{2n}$ for some $0\le i <k$. We will in fact show that for every subset $S$ of $[k]$ of size $k/2$, there is exactly one element of $\ncm_k(2n)$ where every element in $S$ is a left endpoint.

Here is the correspondence between subsets of $k$ of size $k/2$ and $\ncm_k(2n)$. Given such a subset, $S$, consider a circle of $k$ symbols, where the $i^{th}$ symbol is an arrow $\rightarrow$ pointing clockwise if $i\in S$, and is an arrow $\leftarrow$ pointing counterclockwise if $i\notin S$. There will exist a $\rightarrow$ which is followed clockwise by a $\leftarrow$, so that the arrows are pointing to each other. If the $\rightarrow$ is the $i^{th}$ symbol, then $i$ and $i+1$ are matched to each other (and therefore, $i+mk$ is matched to $i+1+mk$ for all $m$). Now, delete these matching arrows to make a smaller circle, and repeat this process until all elements of $[k]$ (and therefore of $[2n]$) are matched.

Here is an example when $k=12$ and $S=\{1,4,5,9,10,12\}$.

Circular arrow drawing:

$ \begin{array}{cccccc} 1& & 2 & 3 & &4 \\ & \nearrow &\leftarrow & \leftarrow & \searrow & \\ 12 & \uparrow & & & \downarrow & 5\\ 11 & \downarrow & & & \uparrow & 6\\ & \nwarrow &\leftarrow & \rightarrow & \nearrow & \\ 10& & 9 & 8 & &7 \end{array} $

Resulting matching:

─────────────────────┐  ┌──────────
──────┐  ┌────────┐  │  │        ┌
┌──┐  │  │  ┌──┐  │  │  │   ┌──┐ │  
1  2  3  4  5  6  7  8  9  10 11 12

The above picture must be extended periodically to all of $[2n]$, by placing $2n/12$ copies in a circle. Note that $12$ is matched to $12+3=15$ and $9$ is matched to $8+12=20$, while $3$ is matched to $2n$ and $8$ is matched to $2n-3$.

I leave it to you to verify that this construction is does indeed uniquely represent each element of $\ncm_k(2n)$ as a subset of $k/2$ elements of $[k]$, and that this count agrees with $\text{Cat}_n(\omega)$ where $\omega$ is an appropriate root of unity.

$\endgroup$
  • 1
    $\begingroup$ Nice! This does however not work when $k$ is odd. But this can only happen when $n=k$ is odd, in which case there must be a diagonal $D$ between some point $i$ and $i+n$. We can choose $D$ in $k$ ways and the edges in $\text{Cat}_n$ ways, since $D$ cuts the remaining points into two halves and choosing one halve determines the other. We thus obtain $k \cdot \text{Cat}_n=\binom{k}{\frac{k+1}{2}} = \text{Cat}_n(-1)$. $\endgroup$ – Joakim Uhlin Sep 11 '18 at 20:10

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.