The Use of Retractions in the Fixed Point Theory for Ordered Sets
Document Type
Book Chapter
Publication Date
6-10-2016
Department
Mathematics
School
Mathematics and Natural Sciences
Abstract
This chapter gives an overview how retractions are used to prove fixed point results in ordered sets. The primary focus is on comparative retractions, that is, retractions r so that, for each x, the image r(x) is comparable to the preimage x. We start with infinite ordered sets and the classical Abian-Brown Theorem, which establishes that, for every order-preserving self map f of a chain-complete ordered set, if there is an x ≤ f (x), then f has a fixed point. Subsequently, using comparative retractions, we prove that the unit ball in Lp has the (order-theoretical) fixed point property, that is, every order-preserving self map has a fixed point. On a finite ordered set, a comparative retraction is the composition of comparative retractions that each remove a single point. Such a point is called irreducible and the fixed point property is not affected by the presence or absence of irreducible points. An ordered set that can be reduced, by successive removal of irreducible points, to a singleton is called dismantlable by irreducibles. We exhibit the relation between ordered sets that are dismantlable by irreducibles and the application of constraint propagation methods to find fixed point free order-preserving self maps. Closely related to irreducible points are points that are removed by a, not necessarily comparative, retraction that removes a single point. These points are called retractable points. There is a fixed point theorem for retractable points that generalizes the one for irreducible points. However, connectedly collapsible ordered sets, a natural class of ordered sets that is defined based on this theorem, are computationally more challenging than ordered sets that are dismantlable by irreducibles. Whereas the definition of dismantlability can be directly verified in polynomial time, direct verification of the definition of connected collapsibility is worst-case exponential. For graphs, the natural analogue of the fixed point property for ordered sets is the fixed clique property. Although there is no analogue of the Abian-Brown Theorem for the fixed clique property, there are analogues of the fixed point theorems for irreducible and for retractable vertices. For simplicial complexes, the natural analogue of the fixed point property for ordered sets is the fixed simplex property. Although there is an analogue of the fixed point theorem for irreducible vertices, there is no full analogue of the corresponding theorem for retractable vertices. We conclude with the connection between the fixed point property for ordered sets and the iteration of the clique graph operator on the comparability graph. Specifically, it is shown that, for ordered sets that are dismantlable by irreducibles, iteration of the clique graph operator on the comparability graph leads to a graph with one vertex. It is also shown that, if iteration of the clique graph operator on the comparability graph leads to a graph with one vertex, then the ordered set has the fixed point property.
Publication Title
Fixed Point Theory and Graph Theory: Foundations and Integrative Approaches
First Page
365
Last Page
417
Recommended Citation
Schröder, B.
(2016). The Use of Retractions in the Fixed Point Theory for Ordered Sets. Fixed Point Theory and Graph Theory: Foundations and Integrative Approaches, 365-417.
Available at: https://aquila.usm.edu/fac_pubs/19536
COinS