On tight spans for directed distances (Q1928578): Difference between revisions

A metric space \((V,d)\) is an \textsl{extension} of a metric space \((X,\mu)\) if \(V \supset X\) and \(d|_{X}=\mu\); furthermore, \((V,d)\) is called a \textsl{tight} extension of \((X,\mu)\) if there is no other extension \((V,d')\) of \((X,\mu)\) with \(d'\leq d\). In [Comment. Math. Helv. 39, 65--76 (1964; Zbl 0151.30205)], \textit{J. R. Isbell} introduced the \textsl{injective hull} of \((X,\mu)\) which is also called the \textsl{tight span} of \((X,\mu)\) after the article [Adv. Math. 53, 321--402 (1984; Zbl 0562.54041)] where \textit{A. W. M. Dress} rediscovered this construction. The tight span of \((X,\mu)\) contains every tight extension of \((X,\mu)\) as a subspace and is realized by the set of minimal elements of the polyhedron in \((\mathbb{R}^{X},l_{\infty})\): \[ \mathcal{P}_{\mu}:=\{ f : X \to {\mathbb R},\: f(x)+f(y) \geq \mu(x,y), \: \forall \:x,y \in X\}. \] In this paper, the authors consider the situation when \(d\) is only a \textsl{directed metric}, i.e. a function \(d : X \times X \to [0,+\infty[\) satisfying \(d(x,x)=0\) for all \(x\) in \(X\) and the triangle inequalities \(d(x,y)+d(y,z)\geq d(x,z)\) for all \(x,y,z\) in \(X\); \((X,d)\) is then called a \textsl{directed metric space}. The notion of \textsl{directed tight extension} is naturally defined and the authors prove the existence of a tight span in this new setting (a \textsl{directed tight span}). They also introduce the notion of \textsl{cyclically tight extensions} for which they also prove the existence of a tight span (a \textsl{directed cyclically tight span}); both of these tight spans are realized as the set of minimal elements of an unbounded polyhedron. Next, the authors develop the link between \textsl{tight span} and \textsl{tropical polytope} (this last notion has been introduced by \textit{M. Develin} and \textit{B. Sturmfels} in [Doc. Math., J. DMV 9, 1--27, erratum 205--206 (2004; Zbl 1054.52004)]) and obtain in particular a characterization of directed \textsl{tree} metrics; some of their results have been obtained independently by \textit{S. Herrmann} and \textit{V. Moulton} [Discrete Math. 312, No. 16, 2506--2521 (2012; Zbl 1301.54042)] by defining tight spans in terms of point configurations. In the last section, the authors give applications to the study of directed multicommodity flow (\textsl{multiflow}) problems in combinatorial optimization.