21
$\begingroup$

Let $n \in \mathbb N$ and $\{\sigma,\tau\} \subset {\rm Sym}(n)$ be a generating set.

Question: What is the maximal possible girth (if one varies $\sigma, \tau$) of the associated Cayley graph?

I am interested in asymptotic bounds. In [A. Gamburd, S. Hoory, M. Shahshahani, A. Shalev, B. Virág, On the girth of random Cayley graphs. Random Structures Algorithms 35 (2009), no. 1, 100–117.] it was proved that a random pair will produce girth $\Omega( (n \log(n))^{1/2})$ with probability tending to $1$. However, I am not aware of concrete generators that realize this girth.

A natural guess for a lower bound on the maximal possible girth (and maybe even the typical girth) would be $\Omega(n \log(n))$. It is also clear that $O(n \log(n))$ is an upper bound for the maximal possible girth.

To the best of my knowledge, it is not known if ${\rm Sym}(n)$ does satisfy a law of length $O(n)$. Hence, any superlinear lower bound on the maximal possible girth would have an immediate application.

$\endgroup$
12
  • 3
    $\begingroup$ @ShahroozJanbaz this has bounded girth! Indeed, $[\sigma,\tau]^3=1$, which is a cycle of length 12. $\endgroup$
    – YCor
    May 29, 2017 at 10:46
  • 2
    $\begingroup$ Side note: the girth is meant to be the smallest length of a nontrivial element in the kernel of the canonical map from the free group on $(\sigma,\tau)$ to Sym(n). (In particular, for it to match with the Cayley graph girth, one needs to use a pair of edges if one generator were of order 2, to force the girth to be 2). $\endgroup$
    – YCor
    May 29, 2017 at 10:51
  • 2
    $\begingroup$ @ShahroozJanbaz the graph is $2|A|$-regular, i.e. 4-regular. You're forgetting inverses. $\endgroup$
    – YCor
    May 29, 2017 at 10:51
  • 1
    $\begingroup$ @MikaeldelaSalle: The order can be as large as $\exp((n\log(n))^{1/2})$. Take a disjoint union of prime cycles $(p_1)...(p_k)$ such that $p_1+\cdots+p_k \sim n$. Then this works for the first primes up to roughly $(n\log(n))^{1/2}$ and then $p_1\cdot \cdots \cdot p_k$ (the order of the permutation) is roughly $\exp((n\log(n))^{1/2})$. This was first observed by Landau. $\endgroup$ Jun 2, 2017 at 12:08
  • 2
    $\begingroup$ Unfortunately there seems to be a gap in the paper Andreas Thom cites, see arxiv.org/pdf/1706.09972.pdf by Sean Eberhard (which gives a lower bound of $n^{1/3}$) $\endgroup$ Sep 27, 2018 at 17:09

1 Answer 1

5
+200
$\begingroup$

I don't know how to answer your question, but I'll suggest a possible approach, i.e. a source of examples that potentially have large girth.

As I'm sure you're aware, Margulis constructed graphs of large girth which were Cayley graphs of $SL_2(\mathbb{Z}/p)$. The point is that reducing a free subgroup $SL_2(\mathbb{Z}) (\mod p)$, one could show that words in the generators must have a certain length before they could be trivial by computing the operator norm of products of matrices. These graphs achieve the optimal growth of girth of $O(\log(n))$, where $n$ is the number of vertices. His approach works for families of simple groups of Lie type, by reducing linear representations $(\mod p)$.

By analogy, one could hope to achieve Cayley graphs for the symmetric or alterating groups by considering non-linear actions of free groups on varieties, and reducing $(\mod p)$ to get families of finite actions. Recently Bourgain, Gamburd, and Sarnak have investigated such actions for the Markoff equation:

$$ x^2+y^2+z^2=xyz.$$

The automorphism $\theta: (x,y,z)\mapsto (y,z, yz-x)$ (found by exchanging the two solutions of the quadratic formula in the variable $z$ and permuting) together with permutations generates a virtually free group of automorphisms (in fact, it has a finite-index 2-generators subgroup). These act transitively on the fundamental solution $(3,3,3)$, giving the Markoff triples.

Subsequently it was shown by Meiri and Puder that the action on the solutions to the Markoff equation $(\mod p)$ is usually symmetric or alternating (the number of solutions is $O(p^2)$, so one gets generators for $Sym(O(p^2))$). Thus, one may ask for the girth of the Cayley graph associated to this action. It seems tricky to implement Margulis' method here, because it is not as easy to identify when a polynomial automorphism is trivial $(\mod p)$, unlike the linear case. Also, the growth of the action on the Markoff numbers is superexponential instead of exponential. One may show that on a ball of radius $c\log\log p$, the fundamental solution $(3,3,3)$ is not sent to itself. In particular, the orbit of $(3,3,3) (\mod p)$ under the element $\theta$ has size at least $\log\log p$. This is far off from optimal of course. But there is a bit of evidence that one can do much better: in this paper, it is shown that $\theta$ has a cycle of size $O(\log p)$. Moreover, Bourgain-Gamburd-Sarnak remark that experiments indicate that the Cayley graphs form an expander family, although they don't explicitly conjecture this or discuss the girth.

A heuristic that the girth should be at least $O(\log(p))$: taking the involution generators for the automorphism group $(x,y,z)\mapsto (x,y,xy-z), (x,xz-y,z), (yz-x,y,z)$, one sees that their compositions have degrees which grow at most exponentially (in fact, at most the Fibonacci sequence) with $n$ compositions. Since a non-trivial polynomial in $\mathbb{F}_p[x,y,z]$ must be non-vanishing if the degree of each variable is $<p$, we see that these polynomials will be non-identity if $n < c\log p$. Hence, one would expect that the girth is at least $O(\log p)$. The problem with this approach is that one should actually work over the ring of functions on the variety $\{ (x,y,z)\in \mathbb{F}_p^3 | x^2+y^2+z^2=xyz\}$, so one must make sure that the polynomials are not trivial in this ring. This is still far off from the "Girth of random graphs" result that you cite.

$\endgroup$
1
  • $\begingroup$ Nice idea, I will think about it. $\endgroup$ Jun 5, 2017 at 20:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.