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.

Improve this question
$\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
    Commented Feb 7, 2019 at 11:26
  • $\begingroup$ Yes, my mistake. I will clarify in the title. $\endgroup$
    – Alex Meiburg
    Commented Feb 7, 2019 at 11:34

1 Answer 1

Reset to default
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$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ yep, I can confirm it's a good example :-) $\endgroup$
    – Dima Pasechnik
    Commented 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$
    – Alex Meiburg
    Commented 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$
    – LeechLattice
    Commented Feb 7, 2019 at 12:37

You must log in to answer this question.

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