9
$\begingroup$

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

Improve this question
$\endgroup$
3

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ There should always be such a recurrence which you can compute by expansion by minors; I expect that you should then be able to write down the generating function for the characteristic polynomials and then see what happens from there. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 22, 2009 at 15:26
  • $\begingroup$ Indeed, this is where the paper of Asaeda-Yasuda begins: they show that the characteristic polynomials (divided by (x-2)^2) satisfy q_k(x) = (x^2 − 4x + 2)q_{k−1}(x) − q_{k−2}(x) It's then another 19 pages of hard 19th century number theory to the result! $\endgroup$
    – Kim Morrison
    Commented Oct 22, 2009 at 16:33
2
$\begingroup$

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?

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .