Fixed point property for finite ordered sets that contain no crowns with 6 or more elements

DOI10.1007/S11083-019-09498-ZMaRDI QIDQ2183104zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 26 May 2020

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-019-09498-z

zbMATH Keywords

crownd2-collapsibledimension 2fixed point propertyirreducible pointordered setretractable point

Mathematics Subject Classification ID

Partial orders, general (06A06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Review text

A poset has the fixed point property if every endomorphism has a fixed point. The problem of determining whether a finite poset has the fixed point property is co-NP-complete. This paper proves that the problem of determining whether a finite poset which omits crowns of six or more elements has the fixed point property is in P. This result is established by first proving that every finite, connected poset which omits crowns of six or more elements either has (i) an element of rank one that has a unique lower cover or (ii) a retractable minimal element.

Recommendations

• On the fixed point property for \((3 + 1)\)-free ordered sets
• On The Fixed Point Property of Finite Ordered Sets
• The fixed point property for small sets
• The fixed point property for ordered sets
• The fixed point property in ordered sets of width two

Cites work

• 3-interval irreducible partially ordered sets
• A fixed point theorem for finite partially orderes sets
• Dimension two, fixed points and dismantlable ordered sets
• Fixed point property for 11-element sets
• Forbidden retracts for finite ordered sets of width at most four
• scientific article; zbMATH DE number 53952 (Why is no real title available?)
• On the fixed point property for \((3 + 1)\)-free ordered sets
• Ordered sets. An introduction with connections from combinatorics to topology
• Performance guarantees and applications for Xia's algorithm
• The complexity of the fixed point property
• The fixed point property for ordered sets of interval dimension 2
• The fixed point property in ordered sets of width two

Cited in

(2)

• The complexity of the fixed point property
• A 2-element antichain that is not contained in any finite retract

This page was built for publication: Fixed point property for finite ordered sets that contain no crowns with 6 or more elements

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2183104)