[Assume all groups are finite]

One knows the general statement that the sum of the values of the character function on the generating set is an eigenvalue of a Cayley graph.

• But the above doesn't seem to automatically tell me anything about the ordering among the eigenvalues. Is there an expression or a method of calculating which will directly tell me something about the second largest adjacency eigenvalue of a Cayley graph? (At least when its Abelian?)

• Is there way to relate the second largest eigenvalue of a Cayley graph to the length of closed paths and/or the diameter of the Cayley graph or of the volume of of $n-$balls around the vertices? (Again any known simplification for the Abelian case?)

• You should probably add that the group is abelian in the body of the question and not just in the title. – Benjamin Steinberg Mar 16 '15 at 21:06
• ... and that the groups are finite... – YCor Mar 16 '15 at 21:53
• I made the necessary edits! – user6818 Mar 17 '15 at 0:24

Let $M$ be a $d\times m$ matrix over $GF(2)$ and let $X(M)$ be the graph on the binary vectors of length $d$, where two vectors are adjacent in their difference is a column of $M$. (This is a Cayley graph with valency $m$ on $2^d$ vertices.) The row space of $M$ is a binary code and $m-2k$ is an eigenvalue of $X(M)$ if and only if there is a code word of weight $k$ in this code. So to determine the second-largest eigenvalue of the Cayley graph, we must determine the minimum weight of the code. This is known to be an NP-hard problem.
• Thanks for the help! The only connection I know between the second-largest adjacency eigenvalue ($\lambda_2$) and the diameter ($D$) is the Alon-Bopanna error term $\lambda_2 \geq 2 \sqrt{d-1}(1 - \frac{c}{D^2})$ Can this is specialized to the Cayley graph case by saying something like that the $D \leq log (\vert G \vert)$ ? (I am guessing the second inequality is true because every group has a generating set of size $O(log \vert G \vert )$) – user6818 Mar 17 '15 at 0:28
• I see a statement at places like that the only way a d-regular Abelian Cayley graph can lower its second adjacency eigenvalue by even $\epsilon d$ is by shooting up its degree to $log(\vert G \vert)$. I don't seem to have any intuition about this. Almost nothing I know about Cayley graphs has a "log" about it or even specific to Abelians. – user6818 Mar 17 '15 at 0:52
• Can you kindly elaborate more on your answer? (1) Are you considering some $2^d$ sized Cayley graph of the group $GL_d(\mathbb{F}_2)$ over some generating set of $m$ elements? What is this generating set you have in mind? (2) What is this $k$ in your $m-2k$? From where are you getting this number $m-2k$? (3) Can you kindly give a reference to this known NP-hard question that you refer to about finding the minimum weight of code? – user6818 Apr 4 '15 at 21:56