next up previous contents index
Next: Complexity Up: Algorithms for the Previous: Contents

Introduction

An ordered set   tex2html_wrap_inline7820 is a pair of a set P and a reflexive, antisymmetric and transitive relation tex2html_wrap_inline7824 on P. We will usually omit the pair notation and call P an ordered set also. We will call tex2html_wrap_inline7830 comparable   and write tex2html_wrap_inline7832   iff tex2html_wrap_inline7836 or tex2html_wrap_inline7838 . Every tex2html_wrap_inline7840 is an ordered set with the induced order from P and will be called an ordered subset of P.   All subsets of ordered sets will be viewed as ordered subsets. A subset S of an ordered set P has an upper bound x (denoted tex2html_wrap_inline7852 )   iff for all tex2html_wrap_inline7856 we have tex2html_wrap_inline7858 .   y is the supremum   or lowest upper bound of S (denoted tex2html_wrap_inline7864 )   iff tex2html_wrap_inline7868 and for all tex2html_wrap_inline7852 we have tex2html_wrap_inline7872 . Lower bounds  and infima  resp. greatest lower bounds (denoted tex2html_wrap_inline7874 )  are defined dually. An ordered set is a chain iff any two points in it are comparable.   A mapping tex2html_wrap_inline7878 is called order-preserving   iff for all tex2html_wrap_inline7830 we have that tex2html_wrap_inline7836 implies tex2html_wrap_inline7884 . An ordered set P is said to have the fixed point property   iff each order-preserving self map tex2html_wrap_inline7878 has a fixed point, i.e., there is a point tex2html_wrap_inline7890 with   p=f(p).   An order-preserving map without a fixed point is called fixed point free.
The main object of this paper is the following - somewhat vague - open question that is for example to be found on ORDER's problem list.

  tex2html_wrap7910
The recorded history of this problem seems to start in the papers [68] by Knaster in the twenties and then in [127] by Tarski and [24] by Davis in the fifties, where the question is answered for lattices (a lattice   is an ordered set in which any finite subset has a supremum and an infimum, it is complete   iff every subset has a supremum and an infimum): A lattice has the fixed point property iff it is complete (also cf. [131], Exercise 1J, Tarski's remarks in [127] and the remarks in [96] footnote 2 on p. 284). After that there were papers by Abian and Brown ([2])   and Pelczar ([84]), which recorded one of today's standard tools: If P is a chain-complete ordered set (i.e., every nonempty chain has a supremum and an infimum),   tex2html_wrap_inline7878 is order-preserving and there is a tex2html_wrap_inline7890 such that tex2html_wrap_inline7900 , then f has a fixed point. Problem 1.1 seems to have been first raised in the text [23] by Crawley and Dilworth. The next milestone then is Rival's characterization of the fixed point property for finite ordered sets of height 1 in [95]. Since then the fixed point problem has drawn more and more attention in many papers as the list of references shows. The vague formulation of the problem has inspired many possible approaches. Among them are the following
  1. One can try as in the above mentioned theorems to characterize the fixed point property for certain classes of ordered sets. This is done for example by Fofanova and Rutkowski in [43] (sets of width 2), by Höft and Höft in [61]-[63] (lexicographic sums), by Rival as mentioned in [95] (sets of height 1), by Ewacha and Rival in [38], Rutkowski in [110], the author in [116] (``small" sets), Davis and Tarski in [24] and [127] (lattices) and possibly most importantly by Roddy in [104], where the fixed point problem is solved for finite products of finite ordered sets with a beautiful argument.
  2.   One can prove fixed point theorems that do not necessarily handle an established class of ordered sets, but that provide new insights through possible reductions (for example done by Constantin and Fournier in [18], by Rival in [95], and by the author in [116], [117]) or through the identification of substructures that force the fixed point property (done for example by Baclawski and Björner in [7], by Edelman in [37], and by Rutkowski in [108]).
  3.   One can try to prove results about forbidden retracts, which can be done in special cases (for example by Fofanova and Rutkowski in [43], or by Rutkowski and the author in [113]), but which might be too complicated in general (cf. section 4.8).
  4.   One can relate the problem to its analogue in topology. (When does a topological space have the fixed point property?) This is done for example by Baclawski and Björner in [7], and by Constantin and Fournier in [18].
  5.   One can devise algorithms that check whether an arbitrary finite ordered set has the fixed point property (done for example by Pickering, Roddy and Stadel in [86] and by Xia in [134]).
Approach 5 leads to the question how efficient such an algorithm might be, on which we focus in section 2. We will demonstrate that the efficiency problem is very similar to other decision problems that are NP-complete. Shortly before the deadline for this article the author received the preprint [29] by Duffus and Goddard in which it is shown that the decision problem 2.3 is NP-complete (cf. Definition 2.12). [29] is still being refereed as this is written. The author considers the arguments given in [29] valid and can thus no longer consider problem 2.3 open in its full generality. Efficient algorithmic approaches to the problem are still interesting, as they now actually have a wider scope than before. Also there are still interesting classes of ordered sets for which the complexity of problem 2.3 is not known (e.g., truncated lattices, ordered sets of height 2 or width 3). We will discuss the algorithmic ramifications of approach 2 of reducing the ordered set in section 3 and of approach 4 of relating the problem to topology in section 4. We devote section 5 to the interesting ``spin-offs" that the investigation of the fixed point property has produced. Proofs that were omitted were either considered simple by the author or a reference to the proof is given. Sections 2, 3 and 4 are (aside from references to related results) independent of each other and can be read in any order.


next up previous contents index
Next: Complexity Up: Algorithms for the Previous: Contents

Bernd.S.W.Schroder