3
$\begingroup$

[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?)

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You should probably add that the group is abelian in the body of the question and not just in the title. $\endgroup$
    – Benjamin Steinberg
    Commented Mar 16, 2015 at 21:06
  • $\begingroup$ ... and that the groups are finite... $\endgroup$
    – YCor
    Commented Mar 16, 2015 at 21:53
  • $\begingroup$ I made the necessary edits! $\endgroup$
    – user6818
    Commented Mar 17, 2015 at 0:24

1 Answer 1

Reset to default
5
$\begingroup$

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.

There are bounds relating the diameter and spectrum, but I have not seen any improvement to these in the abelian case.

Improve this answer
$\endgroup$
16
  • $\begingroup$ 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 )$) $\endgroup$
    – user6818
    Commented Mar 17, 2015 at 0:28
  • $\begingroup$ If you google on "diameter eigenvalue graph" you will find a variety of bounds for graphs in general. These will tend not to be sharp because Cayley graphs for abelian groups with degree at three have low girth, and bounds just mentioned are sharpest when the girth is large. $\endgroup$
    – Chris Godsil
    Commented Mar 17, 2015 at 0:45
  • $\begingroup$ 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. $\endgroup$
    – user6818
    Commented Mar 17, 2015 at 0:52
  • $\begingroup$ The only so-called "proof" that I can see is by just plugging in this big result, sciencedirect.com/science/article/pii/S0095895605000948. I don't seem to see any other first-principles way of seeing it! $\endgroup$
    – user6818
    Commented Mar 17, 2015 at 1:31
  • $\begingroup$ 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? $\endgroup$
    – user6818
    Commented Apr 4, 2015 at 21:56

You must log in to answer this question.

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