Number theoretic spectral properties of random graphs - MathOverflow

Number theoretic spectral properties of random graphs

2009-11-18T19:13:22Z

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.)

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?

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.

Answer by JSE for Number theoretic spectral properties of random graphs

2009-11-19T02:32:00Z

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_n = -TP_{n-1} - P_{n-2}

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.

Answer by David Speyer for Number theoretic spectral properties of random graphs

2009-11-19T03:34:26Z

Scott asked a similar question.

Answer by Lavender Honey for Number theoretic spectral properties of random graphs

2009-11-29T02:42:43Z

Just in case anyone else is still thinking about this question...

The answer is the following. Either:

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$.
For sufficiently large $n$, the largest eigenvalue $\lambda$ is greater than two, and $\mathbf{Q}(\lambda^2)$ is not abelian.

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.

The paper 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.