The sphericity of a graph is the smallest dimension such that there exists a mapping such that if and only if . The following theorem is due to Frankl and Maehara and is a nice application of random projections. Here, .
Theorem [Frankl-Maehara 1988]: Let be a graph with minimum adjacency eigenvalue where and suppose . Then, .
Proof Sketch: Shift the adjacency matrix by and factor it as since is positive semidefinite (all its eigenvalues are non-negative). Apply the Johnson-Lindenstrauss lemma on the set of points defined by the rows of . Conclude.
Exercise: Fill in the details of the proof. If you want to see the solution, click here [needs subscription].