Manuscript En08-A@1 · En08-A.tex · lemma · c688d76d
Lemma: Adjacent interchange
Legal schedules and a local record model › Finite histories · lines 470–483 · proof included or linked
En08-A@1#lem:interchange
Any two linear extensions of a finite partial order are connected by swaps of adjacent incomparable elements.
Proof. Find the first element of the second extension in the first. Every element preceding it there is incomparable with it: a predecessor would also have to precede it in the second extension, and a successor could not precede it in the first. Move it to the front by adjacent swaps, remove it, and apply induction.