How would you call it?

In preparation for the special program on spectral graph theory at the Simons Institute, which starts in a week, I have been reading on the topics of the theory that I don’t know much about: the spectrum of random graphs, properties of highly expanding graphs, spectral sparsification, and so on.

I have been writing some notes for myself, and here is something that bothers me: How do you call the second largest, in absolute value, eigenvalue of the adjacency matrix of a graph, without resorting to the sentence I just wrote? And how do you denote it?

I have noticed that the typical answer to the first question is “second eigenvalue,” but this is a problem when it creates confusion with the actual second largest eigenvalue of the adjacency matrix, which could be a very different quantity. The answer to the second question seems to be either a noncommittal “{\lambda}” or a rather problematic “{\lambda_2}.”

For my own use, I have started to used the notation {\lambda_{2abs}}, which can certainly use some improvement, but I am still at a loss concerning terminology.

Perhaps one should start from where this number is coming from, and it seems that its important property is that, if the graph is {d} regular and has {n} vertices, and has adjacency matrix A, this number is the spectral norm of {A - \frac dn J} (where {J} is the matrix with ones everywhere), so that it measures the distance of {A} from the “perfect {d}-regular expander” in a norm that is useful to reason about cuts and also tractable to compute.

So, since it is the spectral norm of a modification of the adjacency matrix, how about calling it {<}adjective{>} spectral norm? I would vote for shifted spectral norm because I would think of subtracting {\frac dn J} as a sort of shift.

Please, do better in the comments!

11 thoughts on “How would you call it?

  1. How about “second singular value”? If you’re only talking about undirected graphs, then all the eigenvalues are real, so the only distinction you’re after is the sign, and this phrase captures that.

  2. One could also use “reduced spectral norm” – it is the spectral norm of the action of the adjacency matrix restricted to mean zero vectors.

  3. In my own notes, but with a different normalization (the Markov operator instead of the adjacency matrix), I called this the “equidistribution radius” (thinking of spectral radius and the link with rate of convergence of random walks), and used \rho_{\Gamma} for the notation. This was about expanders, so it was important to have a notaiton where the graph appears, as it would naturally vary in a sequence.

  4. I vote for:

    a) Only working with the Laplacian.

    b) Writing its eigenvalues as $0 = \lambda_0 \leq lambda_1 \leq \cdots$ or $0 = \lambda_1 \leq lambda_2 \leq \cdots$ (your choice).

    c) Calling the second of these the “spectral gap” and denoting it $\lambda$.

    d) Not worrying too much about $\lambda_i$’s which exceed 1. If you must, replace the graph with its lazy version.

  5. @Ryan, that’s good when you are thinking about sparsest cut and the mixing time of random walks up to constant, but if you want to think about highly expanding graphs it is a more natural normalization to have eigenvalues small in absolute value (adjacency matrix or random walk matrix) than to be close to d or to 1 (laplacian, normalized laplacian), and if you are interested in Ramanujan graphs you can’t make a bipartite Ramanujan graph into a non-bipartite Ramanujan graph just by making it lazy.

    And, as you know, I am really the wrong audience for point (d)

  6. How about the “largest nontrivial eigenvalue” or the “nontrivial spectral norm”? with these maybe there’s a higher chance that someone would guess the meaning even without seeing the definition. for the same reason I would stick with lamda_2 but just define it somewhere appropriately. its perfectly fine to order the eigenvalues by absolute value.

    another option is the ” spectral/analytical non expansion” (is there a nicer word for the complement of expansion/conductance?) since it measures the spectral/analytical proxy for the (complement of) combinatorial expansion.

  7. Another version, inspired by compressed sensing notation and with a view towards other generalizations, is to call it “ell_2/ell_2 (non) expansion”

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s