Timeline for When are (Abelian) Cayley graphs also expanders?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 10, 2015 at 14:03 | comment | added | Sebi Cioaba | Anthony's comment gives a good intuition. In my paper, I showed that Abelian Cayley graphs have many closed walks of a given length. Since the trace of the corresponding power of the adjacency matrix equals both the number of closed walks and the sum of the powers of the eigenvalues, this means that some eigenvalues of the graph have to be large. To find a lower bound for the number of closed walks of a given length, you can express it as the number of solutions (ordered tuples) of an equation in the generators. The group being Abelian helps to lower bound this number of solutions. | |
| Mar 9, 2015 at 18:30 | vote | accept | user6818 | ||
| Mar 9, 2015 at 18:29 | comment | added | user6818 | Thanks! I am currently hard-pressed to see how the Abelian group structure says anything about the second highest eigenvalue of the adjacency matrix. I guess reading the Alon-Roichman will provide some insights - but is there something immediate/short/intuitive that you can explain! | |
| Mar 9, 2015 at 12:17 | comment | added | Sebi Cioaba | Alon and Roichman "Random Cayley graphs and expanders" math.tau.ac.il/~nogaa/PDFS/exp1.pdf showed that when the degree is logarithmic in the size of the graph, one gets an expander almost always. | |
| Mar 8, 2015 at 19:30 | comment | added | user6818 | @SebiCioba Is there something about the degree of the Cayley graph becoming logarithmic in the size of the graph if you try to lower the second eigenvalue? (see page 39 of the attached reference in the question) | |
| Mar 8, 2015 at 12:37 | history | edited | Sebi Cioaba | CC BY-SA 3.0 |
added 173 characters in body
|
| Mar 8, 2015 at 11:49 | history | answered | Sebi Cioaba | CC BY-SA 3.0 |