Discrete fixed-point theorem

In discrete mathematics, a discrete fixed-point theorem is a fixed-point theorem for functions defined on finite sets, typically subsets of the integer grid $\mathbb {Z} ^{n}$.

Discrete fixed-point theorems were developed by Iimura, Murota and Tamura, Yang, Chen and Deng and others.

Basic concepts

Continuous fixed-point theorems often require a continuous function. Since continuity is not meaningful for functions on discrete sets, it is replaced by conditions such as a direction-preserving function. Such conditions imply that the function does not change too drastically when moving between neighboring points of the integer grid.

Continuous fixed-point theorems often require a convex set. The analogue of this property for discrete sets is an integrally-convex set.

Theorems

Given a set X in $\mathbb {Z} ^{n}$, we denote by ch(X) its convex hull, which is a subset of $\mathbb {R} ^{n}$.

• Let X be a finite integrally-convex set contained in $\mathbb {Z} ^{n}$. Let f be a hypercubic direction-preserving function from X to ch(X). Then f has a fixed-point in X.
• Let X be a finite set contained in $\mathbb {R} ^{n}$. Let f be a simplicially direction-preserving function X to ch(X). Then f has a fixed-point in X.

See also

• Sperner's lemma - a fixed-point-like lemma on vertices of a triangulation.
• Knaster–Tarski theorem and Bourbaki–Witt theorem - two fixed-point theorems on partially-ordered sets.