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

Advertisements