I have been studying the following situation, and I have a claim I believe to be true, but am unsure on how to approach it. I would appreciate any references I could look into where others have studied similar situations!
Background: Let $(\Sigma, \prec)$ be some (irreflexive) partially ordered set, and take some finite subset $A \subseteq \Sigma$. We consider lists to be totally ordered sequences (hence just the usual linked-list type in programming). We say a list $l$ is a list representation of $A$ if every $a \in A$ appears in $l$ exactly once. We say the list order $<_l$ is the total order of the elements in $l$ from the head (left) to the tail (right). For example, if $l = \langle a_1, \dots, a_k \rangle$, then the index $i$ on elements $a_i$ encodes the list order: $a_i <_l a_j \iff i < j$. We say that the order $<_l$ respects $\prec$ if $a_i \prec a_j \implies a_i <_l a_j$. Elements which are incomparable wrt to $\prec$ are denoted $a \| a' \iff \neg(a \prec a') \land \neg (a' \prec a)$.
Now, let $l$ and $l'$ be two list representations of $A$ which both respect $\prec$. It is clear that $l$ and $l'$ are permutations of each other, hence there is some bijective map on indices (a permutation) $\sigma$ so that if $l = \langle a_1, \dots, a_k \rangle$ and $l' = \langle a'_1, \dots, a'_k \rangle$, then $$\sigma(l) = \langle a_{\sigma(1)}, \dots, a_{\sigma(k)} \rangle = \langle a'_1, \dots a'_k \rangle = l'.$$
Since both $l$ and $l'$ respect $\prec$, it must be the case that $\sigma$ "respects" $\prec$ in the following sense: $a_i \prec a_j \implies (a_i <_{l} a_j) \land (a_{\sigma(i)} <_{l'} a_{\sigma(j)})$. Intuitively, $\sigma$ may only "permute" the $\prec$-incomparable elements. In other words, if $a_i \| a_j$, then either $a_i, a_j$ may appear in $l$, $l'$ in either order.
Here is the general question.
Has this sort of permutation been studied anywhere? Are there any facts or techniques that I could use to characterize the behavior of this partial-order respecting permutation?
More specifically, it is well known that permutations can be decomposed into a product of (adjacent) transpositions, hence $\sigma = \tau_1\cdots\tau_n$ and each $\tau_r$ $(1 \leq r \leq n)$ swaps two adjacent elements.
Here is the claim:
Claim: For any pair $l$, $l'$ which are $\prec$-respecting list representations of $A$, there is a permutation $\sigma$ which decomposes into $n$ adjacent transpositions $\tau_1, \dots, \tau_n$ s.t. each $\tau_i$ only swaps the adjacent $\prec$-incomparable elements. That is, if $\tau_i$ swaps $a$ and $a'$, then $a \| a'$ is true. In other words, we can "transform" $l$ into $l'$ in $n$ steps which always respects $\prec$. That is, set $l = l_1$ and $l' = l_{n+1}$, then define $l_i \xrightarrow{\tau_i} l_{i+1}$ iff the list $l_{i+1}$ arises by applying $\tau_i$ to $l_i$. Then, each list order $<_{l_i}$ respects $\prec$.
if you are interested in how I am approaching this, here is a proof attempt.
Proof attempt: By induction on the number of transpositions $n$.
If $n = 0$, then $\sigma$ is the identity, and the claim is true.
Suppose now the claim holds for all sequences of $m \leq n$ adjacent transpositions. Let $l, l'$ be $\prec$-respecting list representations of $A$ s.t. $l'$ is obtained by applying some sequence of $n+1$ adjacent transpositions, say $\tau_1, \dots, \tau_{n}, \tau_{n+1}$, yielding intermediate lists $(l_i)_{i = 1}^{n+2}$ where $l = l_1$ and $l' = l_{n+2}$. Suppose, for contradiction, that there is some $\prec_{l_j}$ ($2 \leq j < n+1$) which does not respect $\prec$. Since $\tau_j$ is an adjacent transposition, it must swap two adjacent elements $a_i$ and $a_{i+1}$ in $l_{j-1}$ s.t. $a_{i} \prec a_{i+1}$ and $a_{i} <_{l_{j-1}} a_{i+1}$ but then $a_{i+1} <_{l_{j}} a_i$. We call $\tau_j$ a "bad step" since while $l_{j-1}$ respects $\prec$, the result $l_j$ does not. Since at the end of this sequence of transpositions, $l_{n+2} = l'$, and $<_{l'}$ respects $\prec$, it must be the case that $a_{i} <_{n+2} a_{i+1}$ holds. Hence there must be a particular adjacent transposition $\tau_{r}$ with $r > j$ s.t. $a_{i+1} <_{r-1} a_{i}$ but then $a_i <_{r} a_{i+1}$. We call this transition a "good step". In other words, for every "bad step" $j$, there is a corresponding "good step" $r > j$. The steps $x \in [j, r]$ then must merely "shuttle" $a_{i+1}$ and $a_i$ up and down the lists without crossing $a_{i+1}$ over $a_i$ (since otherwise, $x$ itself is a "good step").
- Here is where I am not sure. Sub-claim: Critically, "bad steps" and "good steps" are inverses of each other. So instead of performing the $\tau_j$ (bad) step, then shuttling all the list elements around, and then performing the $\tau_r$ (good) step, we may delete $\tau_j$ and $\tau_r$ from the sequence $\tau_1, \dots \tau_n, \tau_{n+1}$ and rewrite the remaining sequence using at most $n$ transpositions, which simply permutes the elements of the list in the same way without breaking the relative order of $a_i$ and $a_{i+1}$ wrt $\prec$. If we imagine the element $a_{i+1}$ as "walking" around the list, and the other $a_j$ holding their relative positions, it is more "efficient" to prevent $a_{i+1}$ from walking "past" $a_i$, since it is forced to make a "return trip" again by crossing paths with $a_i$ again. I believe we can thus "cut out" all these steps. My confusion lies in the fact that I don't know if by doing so, we must add too many transpositions for the other $a_j$ (what if it is somehow most efficient to take this "round-trip?").
If the above sub-claim holds, then we can transform $l$ into $l'$ using at most $m \leq n$ adjacent transpositions, apply the induction hypothesis, and conclude.
