Forbidden retracts for finite ordered sets of width at most four (Q952633): Difference between revisions

Let \(\mathcal K\) be a concrete category with a forgetful functor \(U\). Let \( A\) be a \(\mathcal K\)-object. An endomorphism \(f\) of \(A\) is fixed-point free if \(Uf(a)\neq a\) for every element \(a\in UA\). We say that \(A\) has the fixed-point property if there exists no fixed-point free endomorphism of \(A\), and \(A\) is forbidden if there exists a fixed-point free automorphism of \(A\). If there exist \(\mathcal K\)-morphisms \(r:\to B\) and \(c:B\to A\) with \(r\circ c=1_B\) then \(B\) is a retract of \(A\) and if \(c\circ r\neq 1_A\) then \(B\) is a proper retract of \(A\). For a \(\mathcal K\)-object \(A\) such that \(UA\) is finite the following statements are equivalent: \(A\) fails to have the fixed-point property; there is a forbidden retract of \(A\); there is a forbidden retract \(B\) of \(A\) such that no proper retract of \(B\) is forbidden. This result is applied to finite posets and order-preserving mappings. It is proved that a finite poset \(P\) of width 2 is forbidden and no proper retract of \(P\) is forbidden if and only if \(P\) is antichain. Indecomposable forbidden posets of width \(4\) (or \( 3\) or \(2\)) are characterized. A linear-time algorithm deciding whether a poset of width \(\leq 3\) has a fixed point-free automorphism is presented.