1
$\begingroup$

Given a non-Abelian group $G$ I want to choose a symmetric generating set $S \subset G$ such that $Cay(G,S)$ has girth logarithmic in the size of the set. I want to know,

  • For which $G$ can the existence of such a $S$ be guaranteed?
  • For which $G$ will any arbitrary choice of a large enough set $S$ guarantee this property?
  • For which $G$ will a $S$ of large enough size picked uniformly at random be likely to ensure this property?

Some searching through literature tells me that $SL_2(\mathbb{F}_p)$ satisfies all the above properties. Any reference for proofs of this particular example would also be helpful. Though my question is more like looking for generic patterns.

I can't make this intuition precise but my gut feeling is that all these properties are true if the dimension of the smallest irrep of $G$ is of the order of some root of the size of the group. (like for $SL_2(\mathbb{F}_p)$ the smallest irrep is of dimension order of cube-root of the size of the group)

One might also be reminded of things like, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v11i1r62/pdf http://www.eatcs.org/beatcs/index.php/beatcs/article/view/209

Improve this question
$\endgroup$
16
  • 1
    $\begingroup$ 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/… $\endgroup$
    – Asaf
    Commented Apr 25, 2015 at 20:40
  • $\begingroup$ 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? $\endgroup$
    – Student
    Commented Apr 26, 2015 at 6:48
  • $\begingroup$ @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. $\endgroup$
    – Alain Valette
    Commented Apr 26, 2015 at 21:25
  • 1
    $\begingroup$ 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. $\endgroup$
    – Student
    Commented Apr 26, 2015 at 21:27
  • 1
    $\begingroup$ @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... $\endgroup$
    – Alain Valette
    Commented Apr 27, 2015 at 20:18

0

Reset to default

You must log in to answer this question.