Timeline for Where does $2\sqrt{d-1}$ come from in Ramanujan graphs?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2017 at 19:31 | vote | accept | Xiaoyu He | ||
| Mar 15, 2017 at 15:34 | comment | added | Igor Rivin | @DavidSpeyer Yes, you are absolutely correct - that was a midnight thought which was not quite thought out. | |
| Mar 15, 2017 at 12:13 | comment | added | David E Speyer | That gives you $2^{1/4} \sqrt{k} \approx 1.19 \sqrt{k}$. There are roughly $5 k^3$ walks of length $6$ (assuming no $4$ or $6$ cycles), giving $5^{1/6} \sqrt{k} \approx 1.30 \sqrt{k}$. To see the $\sqrt{2}$ you need to look at walks of length $2r$ and send $r \to \infty$. | |
| Mar 15, 2017 at 4:26 | comment | added | Igor Rivin | @XiaoyuHe Extend the argument slightly: suppose your graph has not short cycles, in particular, no 4-cycles. Then, the only paths of length 4 returning to the base point $a$ are $a-b-c-b-a$ and $a-b-a-c-a.$ There are roughly $2k^2$, so the sum of the fourth powers of the eigenvalues is $ 2 k^2 n.$ I think this already gives you the $2.$ | |
| Mar 15, 2017 at 2:41 | comment | added | Xiaoyu He | Thanks, this is most of what I was looking for. Is there any intuition for the constant $2$ in front though? | |
| Mar 15, 2017 at 2:21 | history | answered | Igor Rivin | CC BY-SA 3.0 |