Let $k$ be an integer. Traditionally a partition $\pi=V_1\cup \dots \cup V_n$ of the set $[k]:=\{1,\dots, k\}$ is called crossing when there exist $a,c\in V_i$ and $b,d\in V_j\not= V_i$ such that $a<b<c<d$. For example, the partition $\{1,3\}\cup\{2,4,5\}$ (which, for convenience, I will just denote by $(12122)$) is a crossing partition of $[5]$ whereas $(21122)$ is a non-crossing partition.

For my needs I am interested in a different notion of crossing, namely only those crossings that can't be resolved in an even number of permutations. For example, in my stricter notion of crossing $(1223123)$ would not have a crossing between $1$ and $2$ since for resolving this crossing, we would have to move $1$ past an even number of $2$'s. It would, however, still have crossings between $1$,$3$ and $2$,$3$.

Is this notion known? Do there exist results on the combinatorics of this stricter notion of crossing?

  • $\begingroup$ How does $(12122)$ denote $\{1,3\}\cup\{2,4,5\}$? $\endgroup$ Sep 25, 2014 at 23:36
  • 1
    $\begingroup$ @GerryMyerson : Given a word $a_1a_2a_3a_4a_5$, put $i$ and $j$ in the same subset if and only if $a_i = a_j$. $\endgroup$ Sep 26, 2014 at 2:16
  • $\begingroup$ Given $n$, compute the number of strongly non-crossing partitions (which can't be resolved), and plug into OEIS. You might find references there, and if not, it is most likely new. $\endgroup$ Sep 26, 2014 at 7:30
  • $\begingroup$ Instead of "even number of permutations" I think you mean "even number of transpositions within each pair $i,j$", right? E.g. in your example, the total number of transpositions would be even+odd+odd=even, which is not what you mean. $\endgroup$
    – Wolfgang
    Sep 26, 2014 at 7:43
  • $\begingroup$ I just noticed: in your example, if you move the last 1 to the right, you obtain 1223213, so the 1-2-crossing is removed. So I wonder how to come up with a well-defined parity of the "resolving number". $\endgroup$
    – Wolfgang
    Sep 26, 2014 at 7:49


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.