Babai's problem

Template:Unsolved 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 $\mathrm{Irr}(G)$ be the set of all irreducible characters of $G$, let $\mathrm{\Gamma }=\mathrm{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=\{\sum _{s\in S}\chi (s)|\chi \in \mathrm{Irr}(G),\chi (1)=\nu \}$

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

BI-group

A finite group $G$ is called a BI-group (Babai Invariant group) if $\mathrm{Cay}(G,S)\cong \mathrm{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