Monotone Maps, Sphericity and Bounded Second Eigenvalue

Details Monotone Maps, Sphericity and Bounded Second Eigenvalue Monotone Maps, Sphericity and Bounded Second Eigenvalue

2004-01-22

arxiv.org/abs/math/0401293v1

Mathematics

Combinatorics

Scientific paper

We consider {\em monotone} embeddings of a finite metric space into low dimensional normed space. That is, embeddings that respect the order among the distances in the original space. Our main interest is in embeddings into Euclidean spaces. We observe that any metric on $n$ points can be embedded into $l_2^n$, while, (in a sense to be made precise later), for almost every $n$-point metric space, every monotone map must be into a space of dimension $\Omega(n)$. It becomes natural, then, to seek explicit constructions of metric spaces that cannot be monotonically embedded into spaces of sublinear dimension. To this end, we employ known results on {\em sphericity} of graphs, which suggest one example of such a metric space - that defined by a complete bipartitegraph. We prove that an $\delta n$-regular graph of order $n$, with bounded diameter has sphericity $\Omega(n/(\lambda_2+1))$, where $\lambda_2$ is the second largest eigenvalue of the adjacency matrix of the graph, and $0 < \delta \leq \half$ is constant. We also show that while random graphs have linear sphericity, there are {\em quasi-random} graphs of logarithmic sphericity. For the above bound to be linear, $\lambda_2$ must be constant. We show that if the second eigenvalue of an $n/2$-regular graph is bounded by a constant, then the graph is close to being complete bipartite. Namely, its adjacency matrix differs from that of a complete bipartite graph in only $o(n^2)$ entries. Furthermore, for any $0 < \delta < \half$, and $\lambda_2$, there are only finitely many $\delta n$-regular graphs with second eigenvalue at most $\lambda_2$.

Affiliated with

Also associated with

No associations

Rating

Monotone Maps, Sphericity and Bounded Second Eigenvalue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Monotone Maps, Sphericity and Bounded Second Eigenvalue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Monotone Maps, Sphericity and Bounded Second Eigenvalue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-385172