Forbidden retracts for finite ordered sets of width at most four (Q952633)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Forbidden retracts for finite ordered sets of width at most four
scientific article

    Statements

    Forbidden retracts for finite ordered sets of width at most four (English)
    0 references
    0 references
    12 November 2008
    0 references
    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.
    0 references
    0 references
    poset
    0 references
    fixed-point property
    0 references
    forbiden retract
    0 references
    concrete category
    0 references
    width of poset
    0 references
    linear-time algorithm
    0 references
    0 references