Injective convex polyhedra (Q331374)

Given \(x \in {\mathbb R}^n\), let \(\| x \|_{\infty} = \max |x_i|\), \(\| x \|_1 = \sum^n_{i=1} |x_i|\), and let \(S \subset {\mathbb R}^n\), endowed with the metric \(d_{\infty}\) defined by \(\| x \|_{\infty}\), be an injective object in the category of metric spaces and distance non-increasing maps. This \((S, d_{\infty})\) is called \textit{injective}. The main results of the paper are devoted to characterization of injective convex polyhedra and injective convex polyhedral cones in terms of their facets and tangent cones (Theorems 1, 2) and Theorem 8. {Let \(P \subset {\mathbb R}^n\) be a convex polyhedron with non-empty interior. Then the following two conditions are equivalent: (i) \(P\) is injective; (ii) \(T_p P\) is injective for every \(p \in \partial P\).} Here \(T_p P\) is the tangent cone to \(P\) at \(p \in \partial P\). The author applies these results to the linear programming in the case of at most two variables per inequality (TVLI). Let \(I_n := \{1,2,\ldots n\}\), \(I_m := \{1,2,\ldots m\}\). Theorem 3. {Consider \(f,g: I_m \to I_n\) and for \(i \in I_m\), \(a_i, b_i, c_i \in {\mathbb R}\) so that \[ P = \bigcap_{i \in I_m} \{x \in {\mathbb R}^n: a_i x_{f(i)} + b_i x_{g(i)} \geq c_i \} \] satisfies \(\mathrm{int}(P) \neq \emptyset\), and \(P \neq {\mathbb R}^n\). Then, \(P\) is injective.} A characterization of injective linear subspaces of \({\mathbb R}^n\) is obtained as well: Theorem 6. Let \(\emptyset \neq X \subset {\mathbb R}^n\) be a linear subspace, \(\dim X=k\). Then, the following conditions are equivalent: (i) \(X \) is injective; (ii) There is a subset \(J \subset I_n\), with \(|J| = k\) such that for any \(i \in I_n \setminus J\) there exist real numbers \(\{\alpha (i,j) \}_{j \in J}\) such that \(\sum_{j \in J} |\alpha (i,j)| \leq 1\) and such that \[ X = \{x\in {\mathbb R}^n: \text{ for all } i \in I_n \setminus J,\, x_i = \sum_{j \in J} \alpha (i,j) x_j \}. \] In particular, Theorem 7. Let \(\nu \in {\mathbb R}^n \setminus \{0\}\). The hyperplane \(X=\{x\in {\mathbb R}^n: x \cdot \nu = 0 \} \subset {\mathbb R}^n\) is injective if and only if \(\| \nu \|_1 \leq 2 \|\nu \|_{\infty}\). Here \(x \cdot \nu\) is the standard scalar product. Reviewer's remark: It seems to the reviewer that on the page 593, line 8, one should read ``satisfying \(r_y + r_z \geq d_{\infty} (y,z)\) for every \(y,z \in Y\)'', not ``\(r_y + r_z \geq d_{\infty} (x,z)\)'' since there are no ``\(x\)'' in these considerations.