# Bandwidth of finite groups

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?

• 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 Oct 30, 2022 at 23:29

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.
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.