In discrete mathematics, a discrete fixed-point is a fixed-point for functions defined on finite sets, typically subsets of the integer grid .
Discrete fixed-point theorems were developed by Iimura, [1] Murota and Tamura, [2] Chen and Deng [3] and others. Yang [4] provides a survey.
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 (HGDP), of a simplex (SGDP) 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 .
A fixed point of a discrete function f is defined exactly as for continuous functions: it is a point x for which f(x)=x.
We focus on functions , where the domain X is a nonempty subset of the Euclidean space . ch(X) denotes the convex hull of X.
Iimura-Murota-Tamura theorem: [2] If X is a finite integrally-convex subset of , and is a hypercubic direction-preserving (HDP) function, then f has a fixed-point.
Chen-Deng theorem: [3] If X is a finite subset of , and is simplicially direction-preserving(SDP), then f has a fixed-point.
Yang's theorems: [4]
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: [6]
Let X be a non-empty convex compact subset of . 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 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.: . Then f has a fixed point in X.
The theorem is originally stated for polytopes, but Philippe Bich extends it to convex compact sets. [7] : Thm.3.7 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. Moreover, there is a constructive algorithm for approximating this fixed point.
Discrete fixed-point theorems have been used to prove the existence of a Nash equilibrium in a discrete game, and the existence of a Walrasian equilibrium in a discrete market. [8]
Brouwer's fixed-point theorem is a fixed-point theorem in topology, named after L. E. J. (Bertus) Brouwer. It states that for any continuous function mapping a nonempty compact convex set to itself, there is a point such that . The simplest forms of Brouwer's theorem are for continuous functions from a closed interval in the real numbers to itself or from a closed disk to itself. A more general form than the latter is for continuous functions from a nonempty convex compact subset of Euclidean space to itself.
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space. The idea is that a compact space has no "punctures" or "missing endpoints", i.e., it includes all limiting values of points. For example, the open interval (0,1) would not be compact because it excludes the limiting values of 0 and 1, whereas the closed interval [0,1] would be compact. Similarly, the space of rational numbers is not compact, because it has infinitely many "punctures" corresponding to the irrational numbers, and the space of real numbers is not compact either, because it excludes the two limiting values and . However, the extended real number linewould be compact, since it contains both infinities. There are many ways to make this heuristic notion precise. These ways usually agree in a metric space, but may not be equivalent in other topological spaces.
In the mathematical field of algebraic topology, the fundamental group of a topological space is the group of the equivalence classes under homotopy of the loops contained in the space. It records information about the basic shape, or holes, of the topological space. The fundamental group is the first and simplest homotopy group. The fundamental group is a homotopy invariant—topological spaces that are homotopy equivalent have isomorphic fundamental groups. The fundamental group of a topological space is denoted by .
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seeming, topology called the box topology, which can also be given to a product space and which agrees with the product topology when the product is over only finitely many spaces. However, the product topology is "correct" in that it makes the product space a categorical product of its factors, whereas the box topology is too fine; in that sense the product topology is the natural topology on the Cartesian product.
In mathematics, a topological space is, roughly speaking, a geometrical space in which closeness is defined but cannot necessarily be measured by a numeric distance. More specifically, a topological space is a set whose elements are called points, along with an additional structure called a topology, which can be defined as a set of neighbourhoods for each point that satisfy some axioms formalizing the concept of closeness. There are several equivalent definitions of a topology, the most commonly used of which is the definition through open sets, which is easier than the others to manipulate.
In mathematics, a (real) interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. An interval can contain neither endpoint, either endpoint, or both endpoints.
In functional analysis and related areas of mathematics, Fréchet spaces, named after Maurice Fréchet, are special topological vector spaces. They are generalizations of Banach spaces. All Banach and Hilbert spaces are Fréchet spaces. Spaces of infinitely differentiable functions are typical examples of Fréchet spaces, many of which are typically not Banach spaces.
This is a glossary of some terms used in Riemannian geometry and metric geometry — it doesn't cover the terminology of differential topology.
In mathematics, the barycentric subdivision is a standard way to subdivide a given simplex into smaller ones. Its extension on simplicial complexes is a canonical method to refine them. Therefore, the barycentric subdivision is an important tool in algebraic topology.
In mathematics, a duality translates concepts, theorems or mathematical structures into other concepts, theorems or structures in a one-to-one fashion, often by means of an involution operation: if the dual of A is B, then the dual of B is A. Such involutions sometimes have fixed points, so that the dual of A is A itself. For example, Desargues' theorem is self-dual in this sense under the standard duality in projective geometry.
In the mathematical area of game theory, a minimax theorem is a theorem providing conditions that guarantee that the max–min inequality is also an equality. The first theorem in this sense is von Neumann's minimax theorem about zero-sum games published in 1928, which was considered the starting point of game theory. Von Neumann is quoted as saying "As far as I can see, there could be no theory of games ... without that theorem ... I thought there was nothing worth publishing until the Minimax Theorem was proved".
In mathematics, infinite-dimensional holomorphy is a branch of functional analysis. It is concerned with generalizations of the concept of holomorphic function to functions defined and taking values in complex Banach spaces, typically of infinite dimension. It is one aspect of nonlinear functional analysis.
In mathematics, triangulation describes the replacement of topological spaces by piecewise linear spaces, i.e. the choice of a homeomorphism in a suitable simplicial complex. Spaces being homeomorphic to a simplicial complex are called triangulable. Triangulation has various uses in different branches of mathematics, for instance in algebraic topology, in complex analysis or in modeling.
In mathematics, subharmonic and superharmonic functions are important classes of functions used extensively in partial differential equations, complex analysis and potential theory.
In topology and other branches of mathematics, a topological space X is locally connected if every point admits a neighbourhood basis consisting of open connected sets.
In commutative algebra, an element b of a commutative ring B is said to be integral over a subring A of B if b is a root of some monic polynomial over A.
This is a glossary of properties and concepts in algebraic topology in mathematics.
In discrete mathematics, a direction-preserving function is a function on a discrete space, such as the integer grid, that (informally) does not change too drastically between two adjacent points. It can be considered a discrete analogue of a continuous function.
An integrally convex set is the discrete geometry analogue of the concept of convex set in geometry.
In functional analysis and related areas of mathematics, a metrizable topological vector space (TVS) is a TVS whose topology is induced by a metric. An LM-space is an inductive limit of a sequence of locally convex metrizable TVS.
