3
$\begingroup$

For a generating set $S$ of a group $G$ denote by $\mathrm{Cay}(G,S)$ the corresponding Cayley graph.

For a finite graph $A$ denote by $\beta(A)$ its bandwidth.

Question: Has the "group bandwidth"

$$\beta(G):=\min_{S\subset G}\beta(\mathrm{Cay}(G,S))$$

of finite groups been studied?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ The bandwidth is clearly minimized on a minimal generating set, i.e. a generating set which after removing any element is no longer a generating set. For $\mathbb F_p^n$, such a generating set is a basis, and in particular is unique up to automorphisms. In particular, for $p=2$, the relevant Cayley graph is a hypercube, so the bandwidth was determined by one of the results mentioned on the Wikipedia page you link, i.e. Harper, L. (1966). "Optimal numberings and isoperimetric problems on graphs".doi.org/10.1016%2FS0021-9800%2866%2980059-5 $\endgroup$
    – Will Sawin
    Oct 30, 2022 at 23:29

1 Answer 1

Reset to default
4
$\begingroup$

There is a well-known conjecture of Babai: suppose that $G$ is a finite, non-abelian, simple group. Suppose that $S$ is any generating set for $G$. Then the diameter of the resulting Cayley graph is at most $C \cdot \log(|G|)^c$ where $C$ and $c$ are constants that do not depend on anything.

This conjecture is very difficult, but has been resolved in some cases. See the article Growth in groups: ideas and perspectives by Helfgott in the Bulletin of the AMS.

When the conjecture is true, then we get a lower bound on the bandwidth: when you lay the group out on the integers the distance between the largest and the smallest element is exactly $|G| - 1$. On the other hand, it only takes poly-log many edges to connect them in the Cayley graph. Thus some edge has layout length at least $|G| /(C \cdot \log(|G|)^c)$.

On the other hand, if $G$ is cyclic then the bandwidth of $G$ is one or two as $|G|$ is even or odd.

Improve this answer
$\endgroup$

Your Answer

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

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