# Fixed-point property

A (partially) ordered set $(P,{\le})$ (cf. Partially ordered set; Ordered set) is said to have the fixed-point property if and only if each order-preserving mapping $f : P \rightarrow P$ (order-preserving means that $x \le y$ implies $f(x) \le f(y)$) has a fixed point $p = f(p)$. 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 $P$ 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 $p_0$ such that (without loss of generality) $p_0 \le f(p_0)$, and sets $p_{\alpha+1} = f(p_\alpha)$, 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 $\mathcal{NP}$-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 $\mathcal{NP}$-complete when considered in the class of ordered sets of height $5$ [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 $r:P \rightarrow P$ (idempotent order-preserving mappings). If $P$ has the fixed-point property and $r:P \rightarrow P$ is a retraction, then $r[P]$ also has the fixed-point property. If $p$ is chain complete and $r:P \rightarrow P$ is a comparative retraction (i.e., each point $p$ is comparable to its image $r(p)$), then $p$ has the fixed-point property if and only if $r[P]$ 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 $P=P_0 \supset P_1 \supset \cdots \supset P_n$ of sets such that $P_n$ is a singleton and there are comparative retractions $R_i : P_{i-1} \rightarrow P_{i-1}$ with $r_i[P_{i-1}] = P_i$ ($i = 1,\ldots,n$). 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 $1$ or width $2$ 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" $P_n$ 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 $P$, $Q$, $D$ are finite ordered sets, $P$,$Q$ have no irreducible points and $D$ is dismantlable, then isomorphism of $P^D$ and $Q^D$ implies isomorphism of $P$ and $Q$ (since $P$ is the core of $P^D$ and $Q$ is the core of $Q^D$).

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 $1$; chain-complete width $2$; ordered sets $P$ that have a retraction onto a subset $P \setminus \{a\}$ for some $a \in P$; chain-complete lexicographic sums; and finite ordered sets of interval dimension $2$.

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 $C$ is acyclic, or if its topological realization has the topological fixed-point property, then every simplicial mapping of $C$ fixes a simplex. This, in turn, implies that every graph endomorphism of the comparability graph of $P$ fixes a clique, which implies that every order-preserving self-mapping of $P$ 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 $n$-th iterated clique graph of the comparability graph of $P$ has the fixed-point property.

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

Future investigations will address the fixed-point property for sets of height $2$ or width $3$, 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].

How to Cite This Entry:
Fixed-point property. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Fixed-point_property&oldid=37408
This article was adapted from an original article by B.S.W. SchrÃ¶der (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article