Bernd S. W. Schröder,
Department of Mathematics,
Hampton University,
Hampton, VA 23668
e-mail: schroder@huajai.cs.hamptonu.edu
July 29, 1996
Abstract.
This survey exhibits various algorithms to decide the question
if a given ordered set P has the fixed point property
resp. if P has a fixed point free order-preserving self-map.
While a depth-first search algorithm for a fixed point free
map is easily written it is also quite inefficient. We
discuss a reduction algorithm by Xia which can be used to
speed up the search for a fixed point free self map.
The ideas used in creating this algorithm show close connections
to two problems: the decision whether an ordered set has a fixed point
free automorphism and the decision whether a given r-partite
graph has an r-clique. The latter two problems are shown to be
NP-complete using the work of Goddard, Lubiw and Williamson.
The problem to decide whether a given finite ordered set has a
fixed point free order-preserving self map has recently been shown to be
NP-complete, thus showing that the above close connection is not by
accident.
Retraction theorems leading to dismantling algorithms are another approach
to the problem. We present the classical dismantling procedure by
Rival and extensions by
Fofanova, Li, Milner, Rutkowski and
the author. These theorems give a polynomial algorithm to decide if an
ordered set has the fixed point property for some nice classes
of ordered sets (height 1, width 2), and structural insights
for other classes (chain-complete ordered sets with no
infinite antichains, sets of (interval) dimension 2).
The related issue of uniqueness of cores gives an insight into
Birkhoff's problem regarding cancellation of exponents.
Walker's relational fixed point property for which the
analogous problem has
a very satisfying solution also is discussed.
Another variation on the retraction theme is the use
of algebraic topology in deriving fixed point theorems
initiated by Baclawski and Björner and continued for example
by Constantin and Fournier. After a primer on the
basic concepts of (integer) homology
we present their retraction/dismantling
procedures, which always prove acyclicity
of the associated simplicial complex and then the fixed
point property via a Lefschetz-type fixed point theorem.
Differences and similarities with the above combinatorial
procedures are pointed out. The main problem in making these results
accessible to entirely combinatorial proofs
is the lack of a combinatorial/discrete analogue of the
continuous concept of a weak retract resp. a deformation retract.
We also present a class of ordered sets without the fixed point
property, such that all proper retracts have the fixed point property.
This class is induced via triangulations of n-spheres.
Finally we include an indication how
methods developed for work on the fixed point property can be used
in other areas.
For example,
the arguments by
Abian, Brown and Pelczar to prove that in a chain-complete
ordered set existence of a point p with 
implies existence of a fixed point
have recently found application to analysis in the work
of Carl, Heikkilä, Lakhshmikantham and others.
AMS subject classification (1991): 06A06, 05C85, 05C99, 68Q15, 68Q25,
45G10, 47G10, 52B05
Key words: fixed point property, algorithm,
complexity, (endomorphism) graph, NP-completeness,
(comparative) retraction,
dismantling, core, cancellation problem, structure theorem for
chain-complete sets with no infinite antichain, homology of an ordered
set, comparability graph, fixed clique property, fixed simplex property,
clique complex, acyclic, contractible, clique graph, k-null, iteration,
Hammerstein integral equation
