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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: