A linear extension is a total ordering of the elements of a partially ordered set that preserves all its comparisons. For a finite set it can be recorded as a list. If two adjacent elements in that list are incomparable, their interchange is again a linear extension.
Two linear extensions of a finite partially ordered set can be joined using as many admissible adjacent swaps as the inversion count of their relative permutation. Label the current list by the desired positions in the target. An adjacent descent consists of incomparable elements, since comparable elements have the same order in both lists. Swap that descent; its inversion count decreases by one. Iteration sorts the list and gives a path of minimal Coxeter length.
Articles by others on the same topic
There are currently no matching articles.