Computational aspects of order-preserving maps (fixed point property)

Abstract

The ordered sets field is an important part of the ongoing mathematical, algorithmic and combinatorics research. This young field identifies and addresses many unsolved problems, a considerable group of which were proven (NP). " Characterizing the finite ordered sets with fixed point property" is among those open unsolved problems. It was originally introduced and described by Rival (1984); and was later demonstrated to be NP-complete by Williamson. Since then, several researchers worked and published on the subject, describing a variety of algorithms and techniques to address and solve aspects of the problem. This thesis introduces a computational technique for identifying ordered sets with the fixed point property (FPP). The technique consists of generating all possible ordered sets of a given size up to isomorphism and duality, followed by a testing of each ordered set for the FPP. Algorithms for the generation of ordered sets, for isomorphic elimination, and for the FPP testing are presented. The results obtained from the research were summarized as a list of incidence matrices of all ordered sets with the FPP; irreducible elements free; and retractable elements free up to duality and isomorphism for set sizes ≤13 elements. This research expands on the results published by Rutkowski (1989) and Schroder (1993) for set sizes of 10 and 11, respectively, by identifying the set of complying ordered sets of sizes 12 and 13. The results can contribute to future research in the topic, particularly in the area of non-computational techniques, as a comparative data set for validation purposes.