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
    Commented 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$

You must log in to answer this question.

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