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.

Hellenica World - Scientific Library

Retrieved from "http://en.wikipedia.org/"

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