Return to Answer

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

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.

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 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, the bandwidth of a cyclic group is one or two as the order is even or odd.

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

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

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 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, the bandwidth of a cyclic group is one or two as the order is even or odd.