Misplaced Pages

Babai's problem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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 {\displaystyle G} be a finite group, let Irr ⁡ ( G ) {\displaystyle \operatorname {Irr} (G)} be the set of all irreducible characters of G {\displaystyle G} , let Γ = Cay ⁡ ( G , S ) {\displaystyle \Gamma =\operatorname {Cay} (G,S)} be the Cayley graph (or directed Cayley graph) corresponding to a generating subset S {\displaystyle S} of G ∖ { 1 } {\displaystyle G\setminus \{1\}} , and let ν {\displaystyle \nu } be a positive integer. Is the set

M ν S = { ∑ s ∈ S χ ( s ) | χ ∈ Irr ⁡ ( G ) , χ ( 1 ) = ν } {\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 Γ {\displaystyle \Gamma } ? In other words, does Cay ⁡ ( G , S ) ≅ Cay ⁡ ( G , S ′ ) {\displaystyle \operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,S')} imply that M ν S = M ν S ′ {\displaystyle M_{\nu }^{S}=M_{\nu }^{S'}} ?

BI-group

A finite group G {\displaystyle G} is called a BI-group (Babai Invariant group) if Cay ⁡ ( G , S ) ≅ Cay ⁡ ( G , T ) {\displaystyle \operatorname {Cay} (G,S)\cong \operatorname {Cay} (G,T)} for some inverse closed subsets S {\displaystyle S} and T {\displaystyle T} of G ∖ { 1 } {\displaystyle G\setminus \{1\}} implies that M ν S = M ν T {\displaystyle M_{\nu }^{S}=M_{\nu }^{T}} for all positive integers ν {\displaystyle \nu } .

Open problem

Which finite groups are BI-groups?

See also

References

  1. 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
  2. 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 (1): 1950013. arXiv:1710.04446. doi:10.1142/S0219498819500130.
  3. 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.
Categories: