Equivalence between two definitions of shuffles

Question

The usual definition of a $(p,q)$-shuffle is a permutation $\sigma$ of the set $\{1,\dots, p+q\}$ such that $\sigma(1)<\cdots<\sigma(p)$ and $\sigma(p+1)<\cdots<\sigma(p+q)$. The signature of a $(p,q)$-shuffle s the signature of the permutation.

However, there are some equivalent definitions that I have found here. I am interested in the definition of a $(p,q)$-shuffle as a monotone map of partially ordered sets $[p+q]\to [p]\times[q]$ where $[p]=\{0<1<\cdots<p\}$. There is an interpretation of this as paths on a square grid of side $p+q$ and the signature is the number of $1\times 1$ squares below the path. This interpretation can be found in Section 1.1. here and in Hatcher's Algebraic Topology (p. 277-278).

The alternative definition is helpful for me when I want to triangulate products of simplies, but I can compute the signature more quickly using the first definition (for instance with the formula in page 6 here).

Therefore I would like to know how are these two notions equivalent.

Given the partially ordered set $[p+q]$, there are exactly $p+q$ inequality signs "$<$" and they are mapped to other $<$ signs in $[p]\times [q]$, so I have thought that I could define a $(p,q)$-shuffle permutation by labeling the signs and define the permutation this way. But I am not sure about how to systematically define this permutation. The main problem is that on $[p]\times [q]$ there are more $<$ signs and I don't know how I should label them.

For instance, if $p=q=1$, I have $[p+q]=\{0<1<2\}$ and $[p]\times[q]$ is partially ordered by alphabetical order, i.e. we have two paths of inequalities $(0,0)<(0,1)<(1,1)$ and $(0,0)<(1,0)<(1,1)$. I can send $0<1<2$ to any these paths, and each of them would represent one of the two $(1,1)$-shuffles which are the identity and the transposition of two elements.

I know that I have to send the identity to the map whose image is $(0,0)<(1,0)<(1,1)$ because they both have $0$ signature. But I don't know how would I know a priori that this is the image of the identity permutation. This is important, because when there are more than two shuffles, there will be several shuffles with the same signature, so that information is not enough.

Answer 1

The partial order on $[p]\times[q]$ is the product partial order, not the lexicographic order: $\langle a,b\rangle\le\langle c,d\rangle$ iff $a\le c$ and $b\le d$.

Let $\sigma$ be a $(p,q)$-shuffle. It corresponds to a path from $\langle 0,0\rangle$ to $\langle p,q\rangle$ consisting of $p$ right-steps and $q$ up-steps. If $1\le k\le p$, the $k$-th right-step is the $\sigma(k)$-th step of the path as a whole. If $p+1\le k\le p+q$, the $(k-p)$-th up-step is the $\sigma(k)$-th step of the path as a whole. This is perhaps best illustrated by an example.

$2351467$ is a $(3,4)$-shuffle. It corresponds to a path from $\langle 0,0\rangle$ to $\langle 3,4\rangle$ consisting of $3$ right-steps and $4$ up-steps. The right-steps are the $2$nd, $3$rd, and $5$th steps of the path, and the up-steps are the $1$st, $4$th, $6$th, and $7$th steps of the path. This path corresponds to the maximal chain $$\langle 0,0\rangle\overset{u}<\langle 0,1\rangle\overset{r}<\langle 1,1\rangle\overset{r}<\langle 2,1\rangle\overset{u}<\langle 2,2\rangle\overset{r}<\langle 3,2\rangle\overset{u}<\langle 3,3\rangle<\overset{u}\langle 3,4\rangle$$ in $[3]\times[4]$, in which I’ve marked the right-steps $r$ and the up-steps $u$.