MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
up vote 19 down vote accepted

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

The answer is the following. Either:

  1. 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$.

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

share|cite|improve this answer
I'd love to see the sketch, FC. Does it apply to arbitrary linear recurrences in Q[T]? – JSE Nov 29 '09 at 15:03
Sweet! I am also looking forward to seeing this argument. – David Speyer Nov 30 '09 at 0:54
(Upvote is for the statement that the proof will appear.) – David Speyer Nov 30 '09 at 0:55

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.

share|cite|improve this answer

Scott asked a similar question.

share|cite|improve this answer
And Speyer gave a better version of my answer! – JSE Nov 19 '09 at 4:02
Really, just more verbose. I don't have any more ideas than you do. – David Speyer Nov 19 '09 at 14:16
Doh, I vaguely remembered that and double checked that I hadn't posted it before, and forgot to check Scott. Silly me. – Noah Snyder Nov 19 '09 at 17:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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