Monotone maps, sphericity and bounded second eigenvalue (Q2573647): Difference between revisions

Embedding of a metric space is monotone if it preserves the order relation between the distances of points in the space. The authors consider the minimal dimension which permits a monotone embedding of a finite metric spaces with \(n\) points into an Euclidean space. It is shown that the minimal dimension of the host space is between \(n/2-1\) and \(n\) for monotone embeddings into \(l_{\infty}\) and between \(n/2\) and \(n\) for embeddings into \(l_2\). Next, they turn to spherical embeddings of graphs, which only respect the distinction between ``short'' and ``long'' distances, given the threshold value. They give the lower bound on sphericity of regular graphs in terms of the second largest eigenvalue of the adjacency matrix, which yields that \(\delta n\)-regular graphs, \(0<\delta\leq\frac 1 2\), with the second eigenvalue at most \(\lambda_2\) have linear sphericity. Finally, they prove that for \(\delta=\frac 12\), such graphs are nearly complete bipartite graphs, while for \(\delta < \frac 12\), only finitely many graphs exist.