How can I prove that a sequence of squares of graph norms is never cyclotomic? - MathOverflow

How can I prove that a sequence of squares of graph norms is never cyclotomic?

2009-10-22T05:19:34Z

The norm of a graph is the largest eigenvalue of the adjacency matrix. I'll write ||G|| for the norm of G.

Now, fix some graph G with a chosen vertex *, and consider the family of graphs G_k obtained by adding a chain of k edges to *.

For many such examples, the sequence { ||G_k||^2}_k appears to be never cyclotomic; I'd like some ideas as to how I might try to prove such statements for particular graphs G.

I know how to show individual algebraic integers aren't cyclotomic -- modulo any prime not dividing the discriminant, the minimal polynomial of a cyclotomic integer must factor into factors with uniform degree. This approach seems very hard to make work for a family of numbers, although I'm aware of the work of Asaeda-Yasuda in which they did this for the graph

        o-o-o
       /
*-o-o-o
       \
        o-o-o

(with the exception of k=4, where the norm-square is in fact cyclotomic). If anyone has ideas about how one should attack such a question, or examples of similar problems, please let me know!

Finally -- the application here is to subfactors; Etingof-Nikshych-Ostrik proved that the index of a subfactor must be a cyclotomic integer, and the index is just the norm square of the principal graph. When we look for possible new examples of subfactors, we tend to get results constraining the principal graph to lie in such a sequence {G_k}.

Answer by Harrison Brown for How can I prove that a sequence of squares of graph norms is never cyclotomic?

2009-10-22T08:19:19Z

I have a hunch that this may be more approachable for trees than for general graphs. I seem to recall the construction T_k showing up in the study of graceful labelings -- one can prove (IIRC) that for any fixed tree T, T_k eventually has a graceful labeling. Not directly applicable to what you want, but interesting nonetheless, perhaps?

In addition, there's the fact that almost all trees on the same number of vertices are cospectral; is it true that for a random graph ||G||^2 is not cyclotomic? Is it true if G is a random tree?

Answer by David Speyer for How can I prove that a sequence of squares of graph norms is never cyclotomic?

2009-10-22T15:24:53Z

This is a vague thought: is there some simple recurrence for the characteristic polynomials of the charctertistic polynomials of the corresponding matrices. For example, if you look at the A_n chains, the polynomials are the Chebyshev polynomials, whose roots are cyclotomic, and which obey a simple resursion.

Even if you had a recursion, I do not know how to show that the roots are not cyclotomic, but the problem feels more tractable.