Let $NC(n)$ denote the lattice of noncrossing partitions of $n$, and let $G$ denote the Hasse diagram of $NC(n)$ with respect to covering relations, viewed as an undirected graph.

I'm interested in the connectivity of graphs of geodesics between vertices of $G$. If $p$ and $q$ are two noncrossing partitions of $n$, let $G_{p,q}$ be the graph whose vertices are minimal-length paths (i.e. geodesics) in $G$ from $p$ to $q$, and where an edge is drawn between two paths $\alpha$ and $\beta$ when $\alpha$ and $\beta$ differ in precisely one element.

Is $G_{p,q}$ always connected, or is there an example of $(n,p,q)$ such that it's not?

If, for example, $p = id$ and $q = (12\ldots n)$ (as noncrossing permutations), then geodesics from $p$ to $q$ are maximal chains from $p$ to $q$, and in this case $G_{p,q}$ is known to be connected (e.g. Bessis "The dual braid monoid" Prop. 1.6.1, http://arxiv.org/pdf/math/0101158.pdf).

But how about if $p$ and $q$ are not comparable in the partial order? Is anything known about the connectivity of $G_{p,q}$?

EDIT: A definition and basic discussion of $NC(n)$ can be found at http://en.wikipedia.org/wiki/Noncrossing_partition.

EDIT 2: Using a computer program in Mathematica (with help from the package posets.m by Curtis Greene et al, http://www.haverford.edu/math/cgreene/posets.html), I've checked that $G_{p,q}$ is always connected for $n < 7$.

  • $\begingroup$ What is a noncrossing partition of a number $n$? You don't mean partitions of the set $[n]=\{1,2,\dots,n\}$? $\endgroup$ – bof Dec 22 '14 at 19:23
  • 1
    $\begingroup$ Yes, they are certain partitions of the set $\{1,2,\ldots,n\}$, but since the labels of these set elements don't really matter, one just talks about "noncrossing partitions of $n$." $\endgroup$ – Andy Manion Dec 22 '14 at 19:27
  • $\begingroup$ For users who aren't aware, Nc partitions seem to be a fairly topic in enumerative combinatorics and free probability theory with as many associations as the Catalan numbers. See review articles noted in the Wiki, McCammond's short intro, as well as the recent article by Ardila, Rincon, and Williams on "Positroids and noncrossing partitions" and Franz Lehner and coauthors on Nc partitions and cumulants. Andy, may I ask for some motivation behind your question? $\endgroup$ – Tom Copeland Dec 23 '14 at 8:21
  • $\begingroup$ Sure! The question is equivalent, after a little work, to a question about Khovanov's arc algebra $H^n$ (arxiv.org/abs/math/0103190). This algebra is defined over a ring $I_n$ of idempotents, which are in bijection with noncrossing partitions of $n$. Over $I_n$, there's a standard set of generators of $H_n$ in degrees 1 and 2, and the question is whether the relations in $H^n$ can be generated by linear-quadratic relations among these generators (so $H^n$ is a linear-quadratic algebra in the sense of Polishchuk-Positselski's book "Quadratic Algebras" (ch. 5)). $\endgroup$ – Andy Manion Dec 23 '14 at 18:07
  • 1
    $\begingroup$ It can also be phrased topologically: given two crossingless matchings $p$, $q$ of $2n$ points in $D^2$, let $\alpha$ and $\beta$ be two cobordisms embedded in $D^2 \times I$ restricting to $p$ on $D^2 \times 0$, $q$ on $D^2 \times 1$, and $2n$ vertical lines on $S^1 \times I$. Further assume that $\alpha$ and $\beta$ are both compositions of some elementary "saddle" cobordisms, and that topologically $\alpha$ and $\beta$ are both $\coprod^k D^2$. Then, is there a diffeotopy of the embeddings $(\coprod^k D^2, \partial) \to (D^2 \times I, \partial)$ which just swaps saddle heights a few times? $\endgroup$ – Andy Manion Dec 23 '14 at 18:15

Third attempt, this time I try to prove that $G_{p,q}$ is connected. Before the proof we need a simple observation about NC partitions.

Observation. Draw the elements of $\{1,\ldots,n\}$ on a circle. Any NC partition $p=(p_1,\ldots,p_k)$ of $\{1,\ldots,n\}$ either has a singleton part $|p_i|=1$ or a part that has at least two consecutive elements (such as $1$ and $2$).

Proof. There are two very similar cases, we start with the simpler. It will be convenient to imagine that the path goes from $q$ to $p$.

Case 1: $p$ has a singleton part $p_i=\{m\}$. Consider any path from $q$ to $p$. Suppose that it does not start with a partition move that separates $m$ from whichever part it belongs to in $q$. At some point, $p_i$ has to be created and thus $m$ separated from a part. But we could execute this separation already in the previous step and do the previous operation after this, as $p_i$ is a singleton and cannot cause any troubles (crossings). Thus, every such path is adjacent to another in $G_{p,q}$ that separates $m$ in an earlier step, and therefore, every path in $G_{p,q}$ is connected to another that starts with separating $m$. But then we can just delete $m$ from both $p$ and $q$ and use induction on $n$.

Case 2: $p$ has a part $p_i$ that contains two consecutive elements. Without loss of generality, we can suppose $1,2\in p_i$. If $1$ and $2$ are in the same part of $q$, then we could consider them as one element (as in every shortest path they must stay in the same parts) and we are again done by induction. Otherwise, let $1\in q_1$ and $2\in q_2$. Now we consider the step when the parts containing $1$ and $2$ are unioned together. If this is not the first step, then we could do it one step earlier as this can create no crossings. But, like in the previous case, we can suppose that we start with taking the union of $q_1$ and $q_2$, thus we are done again (either by joining $1$ and $2$ into a single element, or by induction on the length of the shortest $p$-$q$ path).

  • 2
    $\begingroup$ Thanks for the solution! If you want, I think you can reduce the work by half using the self-duality of the noncrossing partition lattice. A NC partition $p$ has a singleton part iff its dual contains two consecutive elements. So either case implies the other. The possibility in Case 2 that $1$ and $2$ are already joined in $q$ is dual to the possibility in Case 1 that $\{m\}$ is already isolated in $q$ (in either case, either the geodesic condition is violated or we can induct). $\endgroup$ – Andy Manion Jan 11 '15 at 5:27

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.