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

Back to manuscript

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.

Nearby in this section