Babai's Problem

Babai's problem is a problem in algebraic graph theory first proposed in 1979 by László Babai.

Babai's problem

Let $G$ be a finite group, let $\operatorname(G)$ be the set of all irreducible characters of $G$, let $\Gamma=\operatorname(G,S)$ be the Cayley graph (or directed Cayley graph) corresponding to a generating subset $S$ of $G\setminus \$, and let $\nu$ be a positive integer. Is the set
: $M_\nu^S=\left\$
an ''invariant'' of the graph $\Gamma$? In other words, does $\operatorname(G,S)\cong \operatorname(G,S')$ imply that $M_\nu^S=M_\nu^$?

BI-group

A finite group $G$ is called a BI-group (Babai Invariant group) if $\operatorname(G,S)\cong \operatorname(G,T)$ for some inverse closed subsets $S$ and $T$ of $G\setminus \$ implies that $M_\nu^S=M_\nu^T$ for all positive integers $\nu$.

Open problem

Which finite groups are BI-groups?

See also

* List of unsolved problems in mathematics
* List of problems solved since 1995

References

{{Reflist

Algebraic graph theory
Unsolved problems in graph theory