4
$\begingroup$

The eigenvalues associated to a graph's adjacency matrix are necessarily algebraic integers, because the adjacency matrix itself is entirely integer. I'm curious as to whether it's possible to have all irrational eigenvalues $\lambda$ simultaneously obey $\lambda > 1$. This is not possible for all eigenvalues, as the trace is zero, so there must be negative eigenvalues. There are many graphs whose integer eigenvalues are all negative, so intuitively we might feel that if we put enough negative integers in the spectrum, then we could a significant positive set of algebraic integers all conjugate to each other. The "obstruction" is that these would then need to have a norm that's a significantly large integer, and it's difficult to find these.

A natural starting place to look, perhaps, would be for a graph that has $x^2-5x+5$ as one of the factors of its characteristic polynomial.

I'm sorry if many of these statements are somewhat elementary, I'm just trying to provide the little ideas I have on the question. I couldn't find anything elsewhere online.

$\endgroup$
2
  • $\begingroup$ A graph with all eigenvalues integral will satisfy this vacuously. I presume you want to assume at least one eigenvalue is irrational? $\endgroup$
    – Wojowu
    Feb 7, 2019 at 11:26
  • $\begingroup$ Yes, my mistake. I will clarify in the title. $\endgroup$ Feb 7, 2019 at 11:34

1 Answer 1

8
$\begingroup$

Yes, the graph with adjacency matrix

 0     0     1     0     1     1     1     1
 0     0     0     1     0     0     0     1
 1     0     0     0     1     1     1     1
 0     1     0     0     0     0     0     0
 1     0     1     0     0     1     1     1
 1     0     1     0     1     0     1     1
 1     0     1     0     1     1     0     0
 1     1     1     0     1     1     0     0 

and graph6 string

GQil^W

is such a graph, as the characteristic polynomial is $x(x+2)(x+1)^4(x^2-6x+6)$, and the two roots of $(x^2-6x+6)$ are both larger than $1$.

$\endgroup$
3
  • $\begingroup$ yep, I can confirm it's a good example :-) $\endgroup$ Feb 7, 2019 at 12:00
  • $\begingroup$ Lovely, thank you! Did you have a system to find or construct this graph? Some sort of modified companion matrix or something? $\endgroup$ Feb 7, 2019 at 12:30
  • 3
    $\begingroup$ @AlexMeiburg The graphs are generated by geng. For precomputed graphs, one can also use the House of Graphs collection. $\endgroup$ Feb 7, 2019 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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