2
$\begingroup$

This question is in reference to this other question,

Can someone point out references (or explain!) which give techniques of being able to prove for any Cayley graph this property of having a girth logarithmic in size of the group?

The only example like this that I can see is this argument in theorem 3.4 in this paper, http://math1.math.huji.ac.il/~alexlub/PAPERS/ramanujan%20graphs/ramanujanGraphs.pdf but this looks like an extremely specialized calculation and its not clear to me if anything here can be done in other situations. I would like to to know if there are any generic insights known!

I am guessing that there will be a difference in the techniques depending on which of the 3 scenarios in the linked MO question is one trying to address. Given a non-Abelian group proving that (1) there exists a set of generators with this property will possibly entail a totally different proof than proving that (2) any arbitrarily picked large enough symmetric generating set or (3) a symmetric generating set picked uniformly at random has this logarithmic girth property.

Also if someone can point out methods about finding one such symmetric generating set with this property in cases where any of the three scenarios is true!

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

For the Cayley graph of $SL_2(\mathbb{F}_p)$ with respect to $(1,2,0,1)$, its transpose, and their inverses (so a 4-regular graph), there is a short and elegant proof of Margulis that the girth is logarithmic; see http://link.springer.com/article/10.1007/BF02579283#page-1

The proof was reproduced in the appendix of my book with G. Davidoff and P. Sarnak. The basic tool is the fact that, in $SL_2(\mathbb{Z})$, the matrix $(1,2,0,1)$ and its transpose generate a free group on 2 generators (which is proved by a standard ping-pong argument).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Let me combine here a few questions here stemming from your comments. Firstly the only implication I know of this kind is that an expander has girth at most logarithmic in the graph size. (1) If one wants to show that a certain graph is not an expander then one has to show that the girth is somehow "very high". But what exactly does one need to show about the girth to guarantee non-expansion? I am not seeing a very precise statement. (2) Isn't that solvability argument an upper bound on the girth? So that can't prove or disprove something being an expander - right? $\endgroup$
    – user6818
    Commented Apr 29, 2015 at 0:10
  • $\begingroup$ (3) And what is the standard ping-pong argument? Could you kindly reference it? $\endgroup$
    – user6818
    Commented Apr 29, 2015 at 0:14
0
$\begingroup$

Let's try again. For $SL(2),$ there is an argument due to Bourgain-Gamburd, which can be found in these notes of Emmanuel Breuillard. (corollary 0.2). Other gith estimates are shown in the well-known paper of Gamburd, Hoory, Shahshahani, Shalev, Virag 

MR2532876
Gamburd, A.(1-UCSC); Hoory, S.(IL-IBM); Shahshahani, M.(IR-TPM-SM); Shalev, A.(IL-HEBR-   IM); Virág, B.(3-TRNT-MS)
On the girth of random Cayley graphs. (English summary) 
Random Structures Algorithms 35 (2009), no. 1, 100–117. )

Both the results and the techniques (to give a girth estimate) are of interest to the OP, and to others, I assume.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You mean this paper? arxiv.org/pdf/1010.4259v3.pdf $\endgroup$
    – user6818
    Commented Apr 27, 2015 at 20:45
  • $\begingroup$ Probably not, as the word "girth" does not appear in that paper... $\endgroup$
    – Alain Valette
    Commented Apr 27, 2015 at 21:02
  • $\begingroup$ The link is broken. It seems to want to point to an article entitled "Expansion in finite simple groups of Lie type" but MathSciNet shows nothing by that title, by those authors or any others. The paper linked by @user6818, entitled "Strongly dense free subgroups of semisimple algebraic groups", seems to be the only joint paper of those four authors, but does not seem to be relevant. $\endgroup$
    – Nate Eldredge
    Commented Apr 27, 2015 at 21:16
  • $\begingroup$ Oops. See corrected post. $\endgroup$
    – Igor Rivin
    Commented Apr 27, 2015 at 21:18

You must log in to answer this question.

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