Fixed-point property

for partially ordered sets

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].

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