Babai's problem

Unsolved problem in mathematics

Which finite groups are BI-groups?

More unsolved problems in mathematics

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 {Irr} (G)$ be the set of all irreducible characters of $G$, let $\Gamma =\operatorname {Cay} (G,S)$ be the Cayley graph (or directed Cayley graph) corresponding to a generating subset $S$ of $G\setminus \{1\}$, and let $\nu$ be a positive integer. Is the set

$M_{\nu }^{S}=\left\{\sum _{s\in S}\chi (s)\;|\;\chi \in \operatorname {Irr} (G),\;\chi (1)=\nu \right\}$

an invariant of the graph $\Gamma$? In other words, does $\operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,S')$ imply that $M_{\nu }^{S}=M_{\nu }^{S'}$?

BI-group

A finite group $G$ is called a BI-group (Babai Invariant group) if $\operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,T)$ for some inverse closed subsets $S$ and $T$ of $G\setminus \{1\}$ 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