zbMATH — the first resource for mathematics

Fixed point property for finite ordered sets that contain no crowns with 6 or more elements. (English) Zbl 1455.06001
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.
06A06 Partial orders, general
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDF BibTeX Cite
Full Text: DOI
[1] Donalies, M.; Schröder, B., Performance guarantees and applications for Xia’s algorithm, Discret. Math., 213, 67-86 (2000) · Zbl 0952.68065
[2] Duffus, D.; Goddard, T., The complexity of the fixed point property, Order, 13, 209-218 (1996) · Zbl 0866.06002
[3] Felsner, S., 3-interval irreducible partially ordered sets, Order, 11, 97-125 (1994) · Zbl 0814.06006
[4] Fofanova, T.; Rutkowski, A., The fixed point property in ordered sets of width two, Order, 4, 101-106 (1987) · Zbl 0632.06002
[5] Fofanova, T.; Rival, I.; Rutkowski, A., Dimension 2, fixed points and dismantlable ordered sets, Order, 13, 245-253 (1994) · Zbl 0867.06003
[6] Niederle, J., Forbidden retracts for finite ordered sets of width at most four, Discrete Math., 308, 1774-1784 (2008) · Zbl 1154.06002
[7] Rival, I., A fixed point theorem for finite partially ordered sets, J. Comb. Theory (A), 21, 309-318 (1976) · Zbl 0357.06003
[8] Schröder, B., Fixed point property for 11-element sets, Order, 10, 329-347 (1993) · Zbl 0796.06002
[9] Schröder, B., Ordered Sets—an Introduction with Connections from Combinatorics to Topology, 2nd edn (2016), Birkhäuser Verlag: Boston, Birkhäuser Verlag · Zbl 1414.06001
[10] Schröder, B., The fixed point property for ordered sets of interval dimension 2, Order, 34, 307-322 (2016) · Zbl 1385.06001
[11] Trotter, WT, Combinatorics and Partially Ordered Sets: Dimension Theory (1992), Baltimore: Johns Hopkins University Press, Baltimore
[12] Zaguia, I., On the fixed point property for (3 + 1)-free ordered sets, Order, 28, 465-479 (2011) · Zbl 1238.06003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.