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
References
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 Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
