Timeline for How generic are Cayley graphs of non-Abelian groups with logarithmic girth?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 28, 2015 at 17:24 | comment | added | Asaf | The Bourgain-Gamburd method can indeed give you some spectral-gap (not necessarily the real one, but some bound), but it depends on many many constants which appears in different stages as input (say some constants which appear inside the BGS lemma). You can look at some of the computations done by Kowalski here - people.math.ethz.ch/~kowalski/expander-graphs.pdf You can try explicitly to compute it for say $SL_{2}(F_{p})$ and find out that you get spectral gap which is far below $3/16$. | |
| Apr 27, 2015 at 20:44 | comment | added | user6818 | ^Not getting you. Are these estimates independent of the choice of the generating set? | |
| Apr 27, 2015 at 20:18 | comment | added | Alain Valette | @Anirbit: If $G$ is abelian non-cyclic, than the girth is at most 4 because $[a,b]=aba^{-1}b^{-1}=1$ for every $a,b\in G$. If $G$ is metabelian, i.e. solvable of degree 2, then the girth is at most 16 because $[[a,b],[c,d]]=1$ for every $a,b,c,d\in G$. Etc... | |
| Apr 27, 2015 at 18:26 | comment | added | user6818 | Or can this quansirandomness property be converted into a method to find an appropriate symmetric generating set? | |
| Apr 27, 2015 at 18:25 | comment | added | user6818 | Yes. But has anyone been able to show any spectral-gaps from quasirandomness? (apart from saying that it is non-zero) | |
| Apr 27, 2015 at 18:12 | comment | added | Asaf | @Anirbit , the quasirandomness is used only in the final part of the Bourgain-Gamburd argument, I haven't said it is the only one (actually the main one, growth lemma which was proven by Helfgott from arithmetic combinatorics is used in the middle part). See the other posts in this course by Tao. And the problem that B-G solved was a conjecture by Lubotzky (and Weiss) about thin-groups being expanders (not formulated in this language obviously), hence proving any kind of spectral gap. Obviously when good arithmetical reasoning enters (Ramanujan) you can get much better bounds than those. | |
| Apr 27, 2015 at 17:58 | comment | added | Student | @Asaf Looking at that Terence Tao's article it seems that they cannot guarantee any good spectral gap from the property of quasirandomness. Is that right? | |
| Apr 26, 2015 at 21:41 | comment | added | Student | ^Can you give a reference to this? It seems very hard to find examples of such girth calculation for Cayley graphs! | |
| Apr 26, 2015 at 21:39 | comment | added | Alain Valette | @user6818: If $G$ is solvable of solvability degree $n$, then the girth of any Cayley graph is at most $4^n$ (= the length of an $n$-iterated commutator in the generators of a free group). So you may forget about solvable groups. | |
| Apr 26, 2015 at 21:35 | comment | added | Alain Valette | math1.math.huji.ac.il/~alexlub/PAPERS/ramanujan%20graphs/… | |
| Apr 26, 2015 at 21:34 | comment | added | Student | Then let me check again! | |
| Apr 26, 2015 at 21:34 | comment | added | Alain Valette | @Anirbit: Theorem 3.4 in LPS is exactly the logarithmic girth!!! | |
| Apr 26, 2015 at 21:27 | comment | added | Student | Yes. I know that. But its not clear to me that this LPS paper actually proves this logarithmic girth property. They take a totally eigenvalue approach to get their sharp numbers. I am looking for techniques to prove high girth. Let me put up a separate question about it. | |
| Apr 26, 2015 at 21:25 | comment | added | Alain Valette | @Anirbit: The Ramanujan graphs based on $SL_2(\mathbb{F}_p)$ have logarithmic girth, see the 1988 by A. Lubotzky, R. Phillips and P. Sarnak in Combinatorica. | |
| Apr 26, 2015 at 6:48 | comment | added | Student | Is there any reference for the proof of this property for SL_2(F_p) ? Any reference for techniques about proving lower bounds or calculating the girth of non-Abelian Cayley graphs? | |
| Apr 25, 2015 at 20:40 | comment | added | Asaf | Every expander graph have logarithmic diameter (which follows from say the expander mixing lemma). There is indeed relation to representation theory which was termed by Gowers as quasi-randomness, see the following post by Tao - terrytao.wordpress.com/2011/12/16/… | |
| Apr 25, 2015 at 20:00 | history | edited | user6818 | CC BY-SA 3.0 |
added 184 characters in body
|
| Apr 25, 2015 at 19:33 | history | edited | user6818 | CC BY-SA 3.0 |
edited title
|
| Apr 25, 2015 at 19:04 | history | asked | user6818 | CC BY-SA 3.0 |