Retracts: graphs and ordered sets from the metric point of view. (English) Zbl 0597.54028

Combinatorics and ordered sets, Proc. AMS-IMS-SIAM Joint Summer Res. Conf., Arcata/Calif. 1985, Contemp. Math. 57, 175-226 (1986).
[For the entire collection see Zbl 0588.00011.]
The authors present a theory of generalized metric spaces motivated by analogies between metric spaces, graphs, and posets which occur mainly in fixed point theory, universality (embedding in powers or products), and some descriptive theory. Its inspiration is credited to the thesis of A. Quilliot [Thèse de doctorat d’État, Univ. Paris VI (1983)] which set forth a similar complex of analogies, a number of them new. While the present paper gives some more new results, the main point is the common generalization.
The graphs considered here are reflexive; this amounts to saying that morphisms may always collapse edges. A symmetric (i.e. undirected reflexive graph is considered as a metric space in which the distance between vertices x,y is 0 if \(x=y\), 1/2 if \(x\neq y\) but there is an edge joining x and y, and 1 otherwise. However, there is another relevant metric with values in \(N\cup \{\infty \}\), distance being minimal length of a joining path. For directed graphs also there are a condensed and an expanded metric; the condensed one is 0 if \(x=y\), 1/2 if \(x\neq y\) but there are edges xy and yx, a if there is only xy, \(\bar a\) if only yx, 1 if there is no edge, and the expanded one unfolds this like the undirected case. Posets are in effect treated as directed graphs, with the expanded metric; transitivity implies some simplification. This distance, the ”fence distance”, was introduced and exploited by Quilliot (op. cit.).
The basic abstraction from these examples is a metric space with distance in a Heyting involutive semigroup V: a complete lattice with semigroup operation \(+\) for which 0 is an identity, \(+\) is isotone, the involution - is isotone and anti-isomorphic for \(+\), and \((\Lambda p_{\alpha})+(\Lambda q_{\beta})=\Lambda (p_{\alpha}+q_{\beta})\). At this level, much can be done. V itself is an injective V-metric space (morphisms being non-expansive, embeddings rigid), every V-metric space is embeddable in a power of V and has an injective envelope. The further results require more concepts, but they include and extend recent results on fixed points of non-expansive mappings of hyperconvex spaces (beginning with the fixed point theorem for a bounded hyperconvex space of R. Sine and P. M. Soardi). The authors point out more analogies which they cannot yet treat as instances of single central ideas; notably, precompactness of a metric space corresponds to partial well-orderedness of a poset.
Reviewer: J.R.Isbell


54E35 Metric spaces, metrizability
54F05 Linearly ordered topological spaces, generalized ordered spaces, and partially ordered spaces
06F30 Ordered topological structures
06A06 Partial orders, general
05C20 Directed graphs (digraphs), tournaments


Zbl 0588.00011