Linear extensions of a finite poset: existence, prescribed initial ideals, and adjacent-swap connectivity

Clause (1). Suppose that $P\mathrm{\ne }\mathrm{\varnothing }$ has no minimal element. Fix a listing $P=\{p_1,\dots ,p_n\}$ of the finite set and define a sequence by $x_0:=p_1$ and, given $x_k=x\in P$, let $j$ be the least index with $p_j\prec x$ (it exists because $x$ is not minimal) and put $x_{k+1}:=p_j$. This recursion is well defined on $\mathbb{N}$ using only the order of the indices. It satisfies $x_{k+1}\prec x_k$ for every $k$, so for $i<j$ transitivity gives $x_j\prec x_i$, in particular $x_i\mathrm{\ne }{x}_j$; the infinite sequence therefore has pairwise distinct terms, contradicting the finiteness of $P$. Hence some element of $P$ is minimal.

Two basic facts about linear extensions. (i) Every finite poset $Q$ has a linear extension: if $Q=\mathrm{\varnothing }$ take the empty tuple, and otherwise repeatedly remove a minimal element of the induced poset on the remaining set, which exists by clause (1) applied to that nonempty finite subposet, and list the removed elements in their order of removal; if $a\prec b$ in $Q$ and $b$ were removed before $a$, then at the moment $b$ was removed the element $a$ still belonged to the remaining set and satisfied $a\prec b$, contradicting minimality of $b$ there. (ii) If $(z_1,\dots ,z_r)$ is a linear extension of $Q$ and the consecutive entries $z_i,z_{i+1}$ are incomparable in $Q$, then interchanging them yields a linear extension: every pair of entries other than $\{z_i,z_{i+1}\}$ keeps its relative order, and the pair $\{z_i,z_{i+1}\}$ is incomparable, so no order relation is violated.

Clause (2). Let $\tau =(y_1,\dots ,y_{n-m})$ be a linear extension of the induced poset on $P\setminus I$, which exists by step 2.1(i) since $P\setminus I$ is a finite poset. The concatenation $\pi =(x_1,\dots ,x_m,y_1,\dots ,y_{n-m})$ is a linear extension of $P$: within each block the order of the respective induced poset is respected, and a relation crossing the blocks would have to run from the second block to the first, of the form $y_j\prec x_i$; but $x_i\in I$, so the ideal property would give $y_j\in I$, contradicting $y_j\in P\setminus I$. Hence $\sigma$ extends to a linear extension $\pi$ of $P$ whose first $m$ entries are exactly the elements of $I$, and applying the same concatenation to an arbitrary linear extension $\tau$ of the induced poset on $P\setminus I$ gives the dual assertion of clause (2). In particular step 2.1(i) proves the first sentence of clause (2).

Clause (3), the reduction. Let $\pi$ and $\sigma$ be linear extensions of $P$ and let $a$ be the last entry of $\pi$. Then $a$ is maximal in $P$: if $a\prec y$ for some $y\in P$, then $y$ occurs after $a$ in $\pi$, contradicting that $a$ is last. Every entry occurring after $a$ in $\sigma$ is incomparable with $a$: if $y\prec a$ then $y$ occurs before $a$ in $\sigma$, and if $a\prec y$ then $a$ is not maximal. Consequently moving $a$ to the last position of $\sigma$ by successively interchanging it with the entry immediately to its right is a sequence of interchanges of consecutive incomparable entries, each of which yields a linear extension by step 2.1(ii); the resulting list ${\sigma }_1$ is a linear extension of $P$ ending in $a$, obtained from $\sigma$ by finitely many such interchanges.

Clause (3), the induction. Induct on $n=\mathrm{\mid }P\mathrm{\mid }$: for $n=0$ both linear extensions are empty and no interchange is needed. For $n\ge 1$ let $\pi$, $\sigma$, $a$ and ${\sigma }_1$ be as in step 3.2, and delete the common last entry $a$ from $\pi$ and ${\sigma }_1$. The resulting tuples ${\pi }^{\mathrm{\prime }}$ and ${\sigma }_1^{\mathrm{\prime }}$ are linear extensions of the induced poset on $Q:=P\setminus \{a\}$, a finite poset with $n-1<n$ elements, so by the induction hypothesis ${\sigma }_1^{\mathrm{\prime }}$ is obtained from ${\pi }^{\mathrm{\prime }}$ by finitely many interchanges of consecutive entries that are incomparable in $Q$. Two elements of $Q$ are comparable in $Q$ exactly when they are comparable in $P$, so each of these interchanges is also an interchange of consecutive entries incomparable in $P$, and inserting them into $\pi$ and ${\sigma }_1$ produces linear extensions of $P$. Hence $\pi$ is connected to ${\sigma }_1$ by such interchanges, and step 3.2 connects ${\sigma }_1$ to $\sigma$; thus $\sigma$ is obtained from $\pi$ by finitely many interchanges of consecutive entries that are incomparable in $P$.