Number theoretic spectral properties of random graphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T06:34:10Z http://mathoverflow.net/feeds/question/5994 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/5994/number-theoretic-spectral-properties-of-random-graphs Number theoretic spectral properties of random graphs Noah Snyder 2009-11-18T19:13:22Z 2010-04-13T04:17:30Z <p>If G is a graph then its adjacency matrix has a distinguished Peron-Frobenius eigenvalue x. Consider the field Q(x). I'd like a result that says that if G is a "random graph" then the Galois group of Q(x) is "large" with high probability. (Well, what I really want is just that the Galois group is non-abelian, but I'm guessing that for a typical graph it will be the full symmetric group.)</p> <p>Here's another version of this question. Take a graph with a marked point and start adding a really long tail coming into that point. This gives a sequence of graphs G_n. If G is sufficiently complicated (i.e. you're not building the A or D type Dynkin diagrams as the G_n) is Gal(Q(x_n)/Q) symmetric for large enough n?</p> <p>The reason behind these questions is that fusion graphs of fusion categories always have cyclotomic Peron-Frobenius eigenvalue. So results along these lines would say things like "random graphs aren't fusion graphs" or "fusion graphs don't come in infinite families." So the particular details of these questions aren't what's important, really any results on the number theory of the Peron-Frobenius eigenvalue of graphs would be of interest.</p> http://mathoverflow.net/questions/5994/number-theoretic-spectral-properties-of-random-graphs/6053#6053 Answer by JSE for Number theoretic spectral properties of random graphs JSE 2009-11-19T02:32:00Z 2009-11-19T02:32:00Z <p>I don't know the answer to your question offhand, but I think that the characteristic polynomials P_n[T] of your graphs G_n are going to satsify a simple linear recurrence, maybe</p> <p>P_n = -TP_{n-1} - P_{n-2}</p> <p>or something of that kind. Under what circumstances a linear recurrence of this kind can have infinitely many terms with Galois group smaller than symmetric seems a natural question.</p> http://mathoverflow.net/questions/5994/number-theoretic-spectral-properties-of-random-graphs/6058#6058 Answer by David Speyer for Number theoretic spectral properties of random graphs David Speyer 2009-11-19T03:34:26Z 2009-11-19T03:34:26Z <p>Scott asked a <a href="http://mathoverflow.net/questions/1822/how-can-i-prove-that-a-sequence-of-squares-of-graph-norms-is-never-cyclotomic" rel="nofollow">similar question</a>.</p> http://mathoverflow.net/questions/5994/number-theoretic-spectral-properties-of-random-graphs/7102#7102 Answer by Lavender Honey for Number theoretic spectral properties of random graphs Lavender Honey 2009-11-29T02:42:43Z 2010-04-13T04:17:30Z <p>Just in case anyone else is still thinking about this question...</p> <p>The answer is the following. Either:</p> <ol> <li><p>The eigenvalues of $G_n$ are all of the form $\zeta + \zeta^{-1}$ for roots of unity $\zeta$, and the graphs $G_n$ are subgraphs of the Dynkin diagrams $A_n$ or $D_n$.</p></li> <li><p>For sufficiently large $n$, the largest eigenvalue $\lambda$ is greater than two, and $\mathbf{Q}(\lambda^2)$ is not abelian.</p></li> </ol> <p>The proof is effective, but a little long to post here. The main ingredients are some basic facts about Weil height, some ideas due to Cassels, and an amplification step using Chebyshev polynomials.</p> <hr> <p>The <a href="http://arxiv.org/abs/1004.0665" rel="nofollow">paper</a> is now on the ArXiv. See the last section for the proof of this result, and the second to last section for a more effective but logically weaker result.</p>