It is known that there is a gap between 2 and the next largest norm of a graph. Is there an interval of the real line in which norms of graphs are dense?

  • 9
    $\begingroup$ What is the norm of a graph? $\endgroup$ – Qiaochu Yuan May 9 '10 at 4:56
  • 7
    $\begingroup$ The norm of a graph is the largest eigenvalue of its adjacency matrix. Scott's question mathoverflow.net/questions/1822/… has some motivation for thinking about graph norms. $\endgroup$ – Anton Geraschenko May 9 '10 at 5:35

I found a reference that seems to answer your question:

Shearer, James B. On the distribution of the maximum eigenvalue of graphs, 1989. The theorem in this paper is that the set of largest eigenvalues of adjacency matrices of graphs is dense in the interval $\left[\sqrt{2+\sqrt{5}},\infty\right)$. Here's an online version.

Here's a related paper:

Hoffman, Alan J. On limit points of spectral radii of non-negative symmetric integral matrices, 1972. In this paper limit points less than $\sqrt{2+\sqrt{5}}$ are described. In particular, they form an increasing sequence starting at 2 and converging to $\sqrt{2+\sqrt{5}}$. Here's an online version. The author also posed the problem that led to Shearer's paper.

  • 20
    $\begingroup$ These results and more are mentioned in Proposition 1.1.5 of Coxeter Graphs and Towers of Algebras by Goodman, de la Harpe, and Jones, 1989. $\endgroup$ – Jonas Meyer May 9 '10 at 9:05
  • 63
    $\begingroup$ Wait, did you just tell Vaughan Jones about his own paper? MO has jumped the shark. $\endgroup$ – Ben Webster May 9 '10 at 14:26
  • 52
    $\begingroup$ Perhaps I should end up with a negative score because of this... However I assure you that one does not have to be gaga to have forgotten what was in a book one wrote with 2 coauthors over 20 years ago. Looking at it it seems that the Shearer result was not yet published when our book was finished-it does not seem to be mentioned in the appendix I which is the only place I looked in the book when looking for the answer to the question. Apologies, especially to Pierre if he reads this, Vaughan Jones $\endgroup$ – Vaughan Jones May 9 '10 at 15:52
  • 5
    $\begingroup$ The set of limit points was vaguely reminiscent of the set of possible Jones indices, which is why I looked. I found the proposition using the listing of $(2+5^{1/2})^{1/2}$ in the index. I then hesitated to mention it, not wanting the comment to be seen as criticism--but I had to. We haven't met, but I imagined it would be worth a laugh. No need to apologize. $\endgroup$ – Jonas Meyer May 9 '10 at 17:34
  • 7
    $\begingroup$ @Everybody- No worries. It's a good thing that this tidbit is sitting somewhere on the internet, waiting to be found by google (try googling some combination of title key words, you'll see this page is quite high). I, at least, am of the opinion that anything that gets more good content on the site is a good thing. It's also good to see you here, Vaughan. $\endgroup$ – Ben Webster May 9 '10 at 18:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.