How can I prove that a sequence of squares of graph norms is never cyclotomic? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-21T11:31:40Z http://mathoverflow.net/feeds/question/1822 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/1822/how-can-i-prove-that-a-sequence-of-squares-of-graph-norms-is-never-cyclotomic How can I prove that a sequence of squares of graph norms is never cyclotomic? Scott Morrison 2009-10-22T05:19:34Z 2009-10-22T15:24:53Z <p>The <em>norm</em> of a graph is the largest eigenvalue of the adjacency matrix. I'll write ||<code>G</code>|| for the norm of <code>G</code>.</p> <p>Now, fix some graph <code>G</code> with a chosen vertex <code>*</code>, and consider the family of graphs <code>G_k</code> obtained by adding a chain of <code>k</code> edges to <code>*</code>.</p> <p>For many such examples, the sequence <code>{ </code>||<code>G_k</code>||<code>^2}_k</code> appears to be never cyclotomic; I'd like some ideas as to how I might try to prove such statements for particular graphs <code>G</code>.</p> <p>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 <a href="http://arxiv.org/abs/0711.4144" rel="nofollow">Asaeda-Yasuda</a> in which they did this for the graph</p> <pre> o-o-o / *-o-o-o \ o-o-o </pre> <p>(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!</p> <p>Finally -- the application here is to subfactors; <a href="http://arxiv.org/abs/math.QA/0203060" rel="nofollow">Etingof-Nikshych-Ostrik</a> 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 <code>{G_k}</code>.</p> http://mathoverflow.net/questions/1822/how-can-i-prove-that-a-sequence-of-squares-of-graph-norms-is-never-cyclotomic/1843#1843 Answer by Harrison Brown for How can I prove that a sequence of squares of graph norms is never cyclotomic? Harrison Brown 2009-10-22T08:19:19Z 2009-10-22T08:19:19Z <p>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?</p> <p>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?</p> http://mathoverflow.net/questions/1822/how-can-i-prove-that-a-sequence-of-squares-of-graph-norms-is-never-cyclotomic/1885#1885 Answer by David Speyer for How can I prove that a sequence of squares of graph norms is never cyclotomic? David Speyer 2009-10-22T15:24:53Z 2009-10-22T15:24:53Z <p>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.</p> <p>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.</p>