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, Chen and Deng and others. Yang provides a survey.

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. There are various direction-preservation conditions, depending on whether neighboring points are considered points of a hypercube, of a simplex etc. See the page on direction-preserving function for definitions.

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

For functions on discrete sets

We focus on functions $f:X\to \mathbb {R} ^{n}$, where the domain X is a nonempty subset of the Euclidean space $\mathbb {R} ^{n}$. ch(X) denotes the convex hull of X.

Iimura-Murota-Tamura theorem: If X is a finite integrally-convex subset of $\mathbb {Z} ^{n}$, and $f:X\to {\text{ch}}(X)$ is a hypercubic direction-preserving (HDP) function, then f has a fixed-point.

Chen-Deng theorem: If X is a finite subset of $\mathbb {R} ^{n}$, and $f:X\to {\text{ch}}(X)$ is simplicially direction-preserving (SDP), then f has a fixed-point.

Yang's theorems:

• If X is a finite hypercubic subset of $\mathbb {Z} ^{n}$, with minimum point a and maximum point b, $f:X\to \mathbb {R} ^{n}$ is simplicially gross direction preserving (SGDP), and for any x in X: $f_{i}(x_{1},\ldots ,x_{i-1},a_{i},x_{i+1},\ldots ,x_{n})\leq 0$ and $f_{i}(x_{1},\ldots ,x_{i-1},b_{i},x_{i+1},\ldots ,x_{n})\geq 0$, then f has a zero point. This is a discrete analogue of the Poincaré–Miranda theorem.
• If X is a finite integrally-convex subset of $\mathbb {Z} ^{n}$, and $f:X\to {\text{ch}}(X)$ is such that $f(x)-x$ is SGDP, then f has a fixed-point. This is a discrete analogue of the Brouwer fixed-point theorem.
• If X = $\mathbb {Z} ^{n}$, $f:X\to \mathbb {R} ^{n}$ is bounded and $f(x)-x$ is SGDP, then f has a fixed-point (this follows easily from the previous theorem by taking X to be a subset of $\mathbb {Z} ^{n}$ that bounds f).
• If X is a finite integrally-convex subset of $\mathbb {Z} ^{n}$, $F:X\to 2^{X}$ a point-to-set mapping, and for all x in X: $F(x)={\text{ch}}(F(x))\cap \mathbb {Z} ^{n}$ , and there is a function f such that $f(x)\in {\text{ch}}(F(x))$ and $f(x)-x$ is SGDP, then there is a point y in X such that $y\in F(y)$. This is a discrete analogue of the Kakutani fixed-point theorem, and the function f is an analogue of a continuous selection function.

For discontinuous functions on continuous sets

Discrete fixed-point theorems are closely related to fixed-point theorems on discontinuous functions. These, too, use the direction-preservation condition instead of continuity.

Herings-Laan-Talman-Yang fixed-point theorem: Let X be a non-empty polytope in $\mathbb {R} ^{n}$. Let f: X → X be a locally gross direction preserving (LGDP) function: at any point x that is not a fixed point of f, the direction of $f(x)-x$ is grossly preserved in some neighborhood of x, in the sense that for any two points y, z in this neighborhood, its inner product is non-negative, i.e.: $(f(y)-y)\cdot (f(z)-z)\geq 0$. Note that every continuous function is LGDP, but an LGDP function may be discontinuous. An LGDP function may even be neither upper nor lower semi-continuous. Then f has a fixed point in X. Moreover, there is a constructive algorithm for approximating this fixed point.

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.