The fixed point property for ordered sets of interval dimension 2

DOI10.1007/S11083-016-9401-4MaRDI QIDQ2407685zbMATH OpenOpenAlexFDO

Authors Bernd Schröder

Publication date 6 October 2017

Published in Order (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s11083-016-9401-4

zbMATH Keywords

connectedly collapsibledimension 2fixed point propertyinterval dimension 2ordered set

Mathematics Subject Classification ID

Partial orders, general (06A06) Combinatorics of partially ordered sets (06A07) Analysis of algorithms and problem complexity (68Q25)

Review text

In this paper, the author provides a polynomial time algorithm that determines if a given finite ordered set of interval dimension 2 has the fixed-point property. The following results are proved. For any ordered set \(P\), \(\mathrm{D2CCcheck}_{P} (P_1, \ldots, P_n)\) terminates in at most \(13|P|^5\) steps. Let \(P\) be a finite ordered set. Then the following holds. 1. \(P\) is d2-connectedly collapsible iff \(E(\mathcal{D}_{P} (P )) = \{\mathrm{TRUE}\}\). 2. \(P\) is d2-collapsible, but not d2-connectedly collapsible iff \(E(D_{P} (P )) = \{\mathrm{TRUE}, \mathrm{AC}\}\). 3. \(P\) is not d2-collapsible iff \(E(D_{P} (P )) \supseteq \{\mathrm{NO}\}\).

Recommendations

• Dimension two, fixed points and dismantlable ordered sets
• Algorithms for the fixed point property
• On The Fixed Point Property of Finite Ordered Sets
• Fixed point property and formal concept analysis
• On the fixed point property for \((3 + 1)\)-free ordered sets

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
• Ordered sets. An introduction with connections from combinatorics to topology
• Retracts and the Fixed Point Problem for Finite Partially Ordered Sets
• The complexity of the fixed point property
• The Complexity of the Partial Order Dimension Problem
• The fixed point property for small sets
• The fixed point property in ordered sets of width two
• The uniqueness of the core
• The use of retraction in the fixed point theory for ordered sets
• Uniqueness of the core for chain-complete ordered sets

Cited in

(5)

• Fixed point property and formal concept analysis
• Dimension two, fixed points and dismantlable ordered sets
• Performance guarantees and applications for Xia's algorithm
• Fixed point property for finite ordered sets that contain no crowns with 6 or more elements
• scientific article; zbMATH DE number 1528627 (Why is no real title available?)

This page was built for publication: The fixed point property for ordered sets of interval dimension 2

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