Fixed-point property

for (partially) ordered sets

A (partially) ordered set (cf. Partially ordered set; Ordered set) is said to have the fixed-point property if and only if each order-preserving mapping (order-preserving means that implies ) has a fixed point . The fixed-point property is a comparability invariant for finite ordered sets [a4]. The most famous results regarding this property likely are the Knaster–Tarski–Davis theorem that a lattice has the fixed-point property if and only if it is complete (cf. Complete lattice; [a3], [a14]), and the Abian–Brown–Pelczar theorem that in a chain-complete ordered set the existence of a point comparable to its image is equivalent to the existence of a fixed point [a1], [a10]. In both these results, existence of a fixed point is proved by successive approximation: One starts with a point such that (without loss of generality) , and sets , taking suprema when reaching limit ordinals. This process eventually will find a fixed point. Applications of this process to analysis can be found in, e.g., [a7]. The problem to characterize all (finite) ordered sets with the fixed-point property has drawn attention in many ways. The -version of the characterization problem is:

Instance) A finite ordered set.

Question) Is there an order-preserving self-mapping without a fixed point?

It is -complete when considered in the class of ordered sets of height [a5]. The most efficient algorithm for this problem to date (1996) is given in [a15].

One of the standard tools used in the investigation of the fixed-point property are retractions (idempotent order-preserving mappings). If has the fixed-point property and is a retraction, then also has the fixed-point property. If is chain complete and is a comparative retraction (i.e., each point is comparable to its image ), then has the fixed-point property if and only if has the fixed-point property. This leads to the notion of dismantlability ([a2], [a11]): A chain-complete ordered set is dismantlable if and only if there is a finite sequence of sets such that is a singleton and there are comparative retractions with (). Every dismantlable ordered set has the fixed-point property. Since a finite ordered set has a comparative retraction if and only if it has an irreducible point (a point with a unique upper or lower cover), dismantlability for finite ordered sets can be checked in polynomial time. For finite ordered sets of height or width the fixed-point property is equivalent to dismantlability and thus can be verified in polynomial time [a6], [a11].

An infinitary generalization of the dismantling approach has led to the following structure theorem [a9]: A chain-complete ordered set with no infinite anti-chain can be dismantled to a finite set in finitely many steps (i.e., the "core" is finite but not necessarily a singleton). This finite core is unique up to isomorphism. Another consequence is the following cancellation result, related to the Birkhoff cancellation problem: If , , are finite ordered sets, , have no irreducible points and is dismantlable, then isomorphism of and implies isomorphism of and (since is the core of and is the core of ).

Satisfying characterizations (many of them derived via retraction results) of the fixed-point property exist for the following classes of ordered sets (infinite sets included unless otherwise stated): height ; chain-complete width ; ordered sets that have a retraction onto a subset for some ; chain-complete lexicographic sums; and finite ordered sets of (interval) dimension .

Algebraic topology can be invoked to investigate the fixed-point property via the chain complex of a finite ordered set (every chain is considered a simplex, cf. [a2]). If this simplicial complex is acyclic, or if its topological realization has the topological fixed-point property, then every simplicial mapping of fixes a simplex. This, in turn, implies that every graph endomorphism of the comparability graph of fixes a clique, which implies that every order-preserving self-mapping of has a fixed point. These methods produced the surprising fact that every finite truncated non-complemented lattice has the fixed-point property. A simple combinatorial proof for this fact is still not available.

Clique graphs provide another criterion for the fixed-point property: If the th iterated clique graph of the comparability graph of is a one-point graph, then has the fixed-point property.

The fixed-point property is productive in the finite setting, i.e., if , are finite ordered sets with the fixed-point property, then also has the fixed-point property [a12].

Future investigations will address the fixed-point property for sets of height or width , truncated complemented lattices, products of infinite sets, infinite powers of finite sets, and the number of order-preserving mappings of an ordered set that is guaranteed to have a fixed point.

A survey with a fairly complete list of references is [a13].

References

[a1]	S. Abian, A.B. Brown, "A theorem on partially ordered sets with applications to fixed point theorems" Canadian J. Math. , 13 (1961) pp. 78–82
[a2]	K. Baclawski, A. Björner, "Fixed points in partially ordered sets" Adv. Math. , 31 (1979) pp. 263–287
[a3]	A.C. Davis, "A characterization of complete lattices" Pacific J. Math. , 5 (1955) pp. 311–319
[a4]	B. Dreesen, W. Poguntke, P. Winkler, "Comparability invariance of the fixed point property" Order , 2 (1985) pp. 269–274
[a5]	D. Duffus, T. Goddard, "The complexity of the fixed point property" Order , 13 (1996) pp. 209–218
[a6]	T. Fofanova, A. Rutkowski, "The fixed point property in ordered sets of width two" Order , 4 (1987) pp. 101–106
[a7]	S. Heikkilä, V. Lakhshmikantham, "Monotone iterative techniques for discontinuous nonlinear differential equations" , M. Dekker (1994)
[a8]	H. Höft, M. Höft, "Fixed point free components in lexicographic sums with the fixed point property" Demonstratio Math. , XXIV (1991) pp. 294–304
[a9]	B. Li, E.C. Milner, "From finite posets to chain complete posets having no infinite antichain" Order , 12 (1995) pp. 159–171
[a10]	A. Pelczar, "On the invariant points of a transformation" Ann. Polonici Math. , XI (1961) pp. 199–202
[a11]	I. Rival, "A fixed point theorem for finite partially ordered sets" J. Combin. Th. A , 21 (1976) pp. 309–318
[a12]	M. Roddy, "Fixed points and products" Order , 11 (1994) pp. 11–14
[a13]	B. Schröder, "Algorithms vs. the fixed point property" I. Rival (ed.) , Proc. 1996 ORDAL conference (1996) (To appear in: Theor. Comput. Sci.)
[a14]	A. Tarski, "A lattice-theoretical fixpoint theorem and its applications" Pacific J. Math. , 5 (1955) pp. 285–309
[a15]	W. Xia, "Fixed point property and formal concept analysis" Order , 9 (1992) pp. 255–264