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 “” or a rather problematic “.”
For my own use, I have started to used the notation , 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 regular and has vertices, and has adjacency matrix A, this number is the spectral norm of (where is the matrix with ones everywhere), so that it measures the distance of from the “perfect -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 as a sort of shift.
Please, do better in the comments!