In algebraic graph theory, Babai's problem was proposed in 1979 by László Babai.[1]

Babai's problem

Let G be a finite group, let \( {\displaystyle \operatorname {Irr} (G)} \) be the set of all irreducible characters of G, let \( {\displaystyle \Gamma =\operatorname {Cay} (G,S)} \) be the Cayley graph (or directed Cayley graph) corresponding to a generating subset S of \( {\displaystyle G\setminus \{1\}} \), and let \( \nu \) be a positive integer. Is the set

\( {\displaystyle 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 \( {\displaystyle \operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,S')} \) imply that \( {\displaystyle M_{\nu }^{S}=M_{\nu }^{S'}} \) ?

BI-group (Babai Invariant group)

A finite group G is called a BI-group (Babai Invariant group)[2] if \( {\displaystyle \operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,T)} \) for some inverse closed subsets S and T of \( {\displaystyle G\setminus \{1\}} \), then M\( {\displaystyle M_{\nu }^{S}=M_{\nu }^{T}} \) for all positive integers \( \nu \) .
Open problem

Which finite groups are BI-groups?[3]
See also

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


Babai, László (October 1979), "Spectra of Cayley graphs", Journal of Combinatorial Theory, Series B, 27 (2): 180–189, doi:10.1016/0095-8956(79)90079-0
Abdollahi, Alireza; Zallaghi, Maysam (10 February 2019). "Non-Abelian finite groups whose character sums are invariant but are not Cayley isomorphism". Journal of Algebra and Its Applications. 18 (01): 1950013. arXiv:1710.04446. doi:10.1142/S0219498819500130.
Abdollahi, Alireza; Zallaghi, Maysam (24 August 2015). "Character Sums for Cayley Graphs". Communications in Algebra. 43 (12): 5159–5167. doi:10.1080/00927872.2014.967398.

Undergraduate Texts in Mathematics

Graduate Texts in Mathematics

Graduate Studies in Mathematics

Mathematics Encyclopedia



Hellenica World - Scientific Library

Retrieved from ""
All text is available under the terms of the GNU Free Documentation License