Forum Problem Lists Definitions FAQ

19.50 (2018)

Solved

A finite graph is said to be integral if all eigenvalues of its adjacency matrix are integers.
$\qquad$ a) Let $G$ be a finite group generated by a normal subset $R$ consisting of involutions. Is it true that the Cayley graph $Cay(G, R)$ is integral?
$\qquad$ b) Let $A_n$ be the alternating group of degree $n$, let $S = \{(123), (124), \dots, (12n)\}$ and $R = S \cup S^{-1}$. Is it true that the Cayley graph $Cay(A_n, R)$ is integral?

Contributor: D. V. Lytkina

Progress

a) Yes, it is true (D. O. Revin, Letter of 21 April 2018; see also the reference for part (b) below; A. Abdollahi, Letter of 3 May 2018). Both proofs suggested are based on character theory; here is the second one. It suffices to show that the eigenvalues of $Cay(G, R)$ are rational, since the eigenvalues of a simple graph are algebraic integers. It is known that every eigenvalue of $Cay(G, R)$ has the form $\theta_\chi = \frac{1}{\chi(1)} \sum_{r \in R} \chi(r)$ for some complex irreducible character $\chi$ of $G$ (implicit on pages 175–177 in P. Diaconis, M. Shahshahani, Z. Wahrscheinlichkeitstheorie Verw. Gebiete, 57 (1981), 159–179, see also Theorem 9 in M. R. Murty, J. Ramanujan Math. Soc., 18, no. 1 (2003) 1–20). Since the value of any complex character on an involution is an integer, it follows that $\theta_\chi$ is rational.

b) Yes, it is true (W. Guo, D. V. Lytkina, V. D. Mazurov, D. O. Revin, Algebra Logic, 58, no. 4 (2019), 297–305).

Comments

All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic. If you want to submit a proof (or a partial proof), please use the dedicated proof submission form rather than posting it in the comments.
Order by newest first or oldest first.

No comments yet. Be the first to comment.

Proof claims

Proof claims are the responsibility of the submitter. Appearance here does not mean the claim has been checked for mathematical correctness. Moderators only screen for spam, abuse, and obviously low-effort submissions.

No proof claims yet.