4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Are you talking about adjacency eigenvalues? $\endgroup$ May 7, 2016 at 23:12

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Vahid
    May 7, 2016 at 11:47
  • $\begingroup$ I have some numerical computation which I will add. $\endgroup$
    – Shahrooz
    May 7, 2016 at 12:00

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.