# A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, but for other choices of $S$ with the same cardinality, $\Gamma$ could have $5$ or $6$ distinct eigenvalues. How can I find different $S$ of the same cardinality such that the resulting Cayley graphs have different numbers of distinct eigenvalues?

If there are any hints or references I'd appreciate it if you give them. If there is any proof that one cannot find such $S$, please mention it.

• Are you talking about adjacency eigenvalues? May 7, 2016 at 23:12

For Abelian group $G$, the eigenvalues of the Cayley graph $Cay(G,S)$ can be computed by the group characters and the set $S$. Actually, if $\rho$ be a character of the group $G$, $\rho(S)=\Sigma_{s\in S}\rho(s)$ is an eigenvalue of the Cayley graph $Cay(G,S)$. As the characters of the group $Z_2^n$ can be computed easily, you must choose the set $S$ carefully such a way that the total number of eigenvalues is equal to your predefined number. Also, you should care about the biggest and smallest eigenvalues, since the connected graph is bipartite if and only if these two latter values are equal negatively. Therefore, you must study the effect of characters on special subsets $S$ of the group $Z_2^n$.

For computing the characters of $Z_2^n$, one of the best resource is "CHARACTERS OF FINITE ABELIAN GROUPS" which is written by Prof. Keith Conrad.

For $n=4:$

If $|S|=4$, I think there is just one bipartite graph with eigenvalues $\{[ -4, 1 ], [ -2, 4 ], [ 0, 6 ], [ 2, 4 ], [ 4, 1 ]\}$,

If $|S|=5$, also there is just one bipartite graph with eigenvalues $\{[ -5, 1 ], [ -3, 1 ], [ -1, 6 ], [ 1, 6 ], [ 3, 1 ], [ 5, 1 ]\}$,

If $|S|=6$, again there is just one bipartite graph with eigenvalues $\{[ -6, 1 ], [ -2, 3 ], [ 0, 8 ], [ 2, 3 ], [ 6, 1 ]\}$.

If $|S|=7$, there is just one bipartite graph with eigenvalues $\{[ -7, 1 ], [ -1, 7 ], [ 1, 7 ], [ 7, 1 ]\}$,

If $|S|=8$, there is one bipartite graph with eigenvalues $\{[ -8, 1 ], [ 0, 14 ], [ 8, 1 ]\}$.

By this computation (if I did anything correct), it seems that such graphs are so rare.

• Thanks for your help. But I know character table of that.(It's hadamard matrix of +-1) My question is for what $S$ it has 4 and for what $S$ it has 5 or 6 distinct eigenvalues? May 7, 2016 at 11:47
• I have some numerical computation which I will add. May 7, 2016 at 12:00