# 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.

Exercise: Fill in the details of the proof. If you want to see the solution, click here [needs subscription].