33

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?

Scott Morrison
  • 7,540
Vaughan Jones
  • 528
  • 5
  • 6

1 Answers1

38

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.

Glorfindel
  • 2,743
Jonas Meyer
  • 7,279
  • 23
    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. – Jonas Meyer May 09 '10 at 09:05
  • 65
    Wait, did you just tell Vaughan Jones about his own paper? MO has jumped the shark. – Ben Webster May 09 '10 at 14:26
  • 55
    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 – Vaughan Jones May 09 '10 at 15:52
  • 3
    @Ben: I had to look up the idiom. I am definitely old enough but did not watch Happy Days regularly. Note there is also "nuked the fridge." http://en.wikipedia.org/wiki/Jumping_the_shark – Will Jagy May 09 '10 at 16:45
  • 5
    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. – Jonas Meyer May 09 '10 at 17:34
  • 7
    @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. – Ben Webster May 09 '10 at 18:15
  • The link to sciencedirect.com is broken, but the article can be found at doi:10.1016/0024-3795(89)90449-7. – The Amplitwist May 15 '23 at 05:20