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$.



For any two noncrossing partitions $p, q$ of $n$, is the graph of geodesics from $p$ to $q$ in $NC(n)$ connected?
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).


