Timeline for When are (Abelian) Cayley graphs also expanders?
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 12 at 21:55 | answer | added | Mike Krebs | timeline score: 2 | |
| Mar 9, 2015 at 18:30 | vote | accept | user6818 | ||
| Mar 8, 2015 at 22:55 | comment | added | user6818 | Also you can see my comment to Sebi Cioba's answer. | |
| Mar 8, 2015 at 20:16 | comment | added | Anthony Quas | Here's a proof. Suppose there are $d$ generators. Then you are interested in counting the number of distinct group elements you can make by composing $n$ generators. I will give an upper bound on the size of the $n$-ball by only taking account of coincidences that occur by rearrangement; but not any other coincidences. Hence we're asking how many ways are there to pick $n$ items with replacement but without order from $d$. It's a well known combinatorial fact ("stars and bars") that there are $\binom{n+d-1}{d-1}\sim n^{d-1}/(d-1)!$ ways to do this. | |
| Mar 8, 2015 at 19:23 | comment | added | user6818 | @AnthonyQuas Can you give a proof (or a reference) to this exact statement about Cayley graphs having a polynomial neighbourhood size? | |
| Mar 8, 2015 at 11:49 | answer | added | Sebi Cioaba | timeline score: 10 | |
| Mar 8, 2015 at 2:23 | comment | added | Anthony Quas | Abelian Cayley graphs have polynomial neighbourhood size, and so cannot be expanders. To be an expander, you have to be able to get from any vertex to any other by following a short path. The difficulty with Abelian groups is that many different paths take you to the same place (following $g$ then $h$ is the same as following $h$ then $g$). To have expansion, you need most of the $N^l$ paths of length $l$ to take you to different places (so the number of places you can get to grows exponentially). In an Abelian gp, you can only get to $l^N$ places, roughly. | |
| Mar 8, 2015 at 1:18 | history | edited | user6818 | CC BY-SA 3.0 |
added 10 characters in body
|
| Mar 8, 2015 at 1:01 | history | edited | user6818 | CC BY-SA 3.0 |
edited title
|
| Mar 8, 2015 at 0:13 | history | asked | user6818 | CC BY-SA 3.0 |