Graph sphericity

The sphericity $sph(G)$ of a graph $G(V,E)$ is the smallest dimension $d$ such that there exists a mapping $f:V\rightarrow R^d$ such that $0<||f(u)-f(v)||< 1$ if and only if $\{u,v\}\in E$ . The following theorem is due to Frankl and Maehara and is a nice application of random projections. Here, $n=|V|$ .

Theorem [Frankl-Maehara 1988]: Let $G$ be a graph with minimum adjacency eigenvalue $\lambda_{min}\geq -c$ where $c \geq 2$ and suppose $n>\Big(12(2c-1)^2 \log{(n)} \Big)^2$ . Then, $sph(G)<12(2c-1)^2\log{(n)}$ .

Proof Sketch: Shift the adjacency matrix $A$ by $cI$ and factor it as $MM^T$ since $A+cI$ is positive semidefinite (all its eigenvalues are non-negative). Apply the Johnson-Lindenstrauss lemma on the set of points defined by the rows of $M$ . Conclude.