The Johnson-Lindenstrauss lemma and the sphericity of some graphs

A simple short proof of the Johnson-Lindenstrauss lemma is given to show that if G is a graph on n vertices and with smallest eigenvalue i then its sphericity sph(G) is less than cA2 log n.

Abstract

A simple short proof of the Johnson-Lindenstrauss lemma (concerning nearly isometric embeddings of finite point sets in lower-dimensional spaces) is given. This result is applied to show that if G is a graph on n vertices and with smallest eigenvalue i then its sphericity sph(G) is less than cA2 log n. It is also proved that if G or its complement is a forest then sph(G) < c log n holds. Q 19%8 Academic Press, Inc.