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?
$\begingroup$
$\endgroup$
3
-
10$\begingroup$ What is the norm of a graph? $\endgroup$– Qiaochu YuanMay 9, 2010 at 4:56
-
8$\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 GeraschenkoMay 9, 2010 at 5:35
-
$\begingroup$ Reposting a link mentioned in the previous comment so that it appears in the "Linked" questions list: How can I prove that a sequence of squares of graph norms is never cyclotomic? $\endgroup$– The AmplitwistMay 15, 2023 at 5:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
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.
answered May 9, 2010 at 6:06
-
23$\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$ May 9, 2010 at 9:05
-
65$\begingroup$ Wait, did you just tell Vaughan Jones about his own paper? MO has jumped the shark. $\endgroup$– Ben Webster ♦May 9, 2010 at 14:26
-
55$\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$ May 9, 2010 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$ May 9, 2010 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, 2010 at 18:15