Graph comparison meets Alexandrov (Q6101509)

Graph comparison is a certain type of condition on a metric space encoded by a finite graph. Suppose that \(\Gamma\) is a graph with vertices \(v_1,\ldots ,v_n\). The authors write \(v_i \sim v_j\) (or \(v_i\not\sim v_j\)) if \(v_i\) is adjacent (or nonadjacent) to \(v_j\). A metric space \(X\) meets the \(\Gamma\)-comparison if for every \(n\) points in \(X\) labeled by vertices of \(\Gamma\) there is a model configuration \(\tilde{v}_1, \ldots, \tilde{v}_n\) in some Hilbert space \(\mathbb{H}\) such that: \begin{align*} v_i \sim v_j&\implies | v_i \sim v_j|_{\mathbb{H}}\leq | v_i-v_j|_{X},\\ v_i \not\sim v_j&\implies | v_i \sim v_j|_{\mathbb{H}}\geq | v_i-v_j|_{X}, \end{align*} where \(| \cdot -\cdot |_X\) is the metric in \(X\). By \(T_3\) the authors denote \(K_{1,3}\) and by \(C_4\) a four-cycle. The following theorem is proved: Theorem. Let \(\Gamma\) be an arbitrary finite graph. Then either \(\Gamma\)-comparison holds in every metric space or \(\Gamma\)-comparison implies \(C_4\)- or \(T_3\)-comparison. As a consequence of the above theorem the following is proved: Corollary. Let \(\Gamma\) be a finite connected graph. Suppose that \(\Gamma\)-comparison is trivial. Then \(\Gamma\) can be constructed from a path \(P_\ell\) of length \(\ell\geq 0\) and two complete graphs \(K_{m_1}\) and \(K_{m_2}\) by attaching \(k_1\) vertices to the left end of \(P_\ell\) and \(k_2\) vertices of \(K_{m_2}\) to the right end of \(P_\ell\).