Babai's problem
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.[1]
Babai's problem
Let [math]\displaystyle{ G }[/math] be a finite group, let [math]\displaystyle{ \operatorname{Irr}(G) }[/math] be the set of all irreducible characters of [math]\displaystyle{ G }[/math], let [math]\displaystyle{ \Gamma=\operatorname{Cay}(G,S) }[/math] be the Cayley graph (or directed Cayley graph) corresponding to a generating subset [math]\displaystyle{ S }[/math] of [math]\displaystyle{ G\setminus \{1\} }[/math], and let [math]\displaystyle{ \nu }[/math] be a positive integer. Is the set
- [math]\displaystyle{ M_\nu^S=\left\{\sum_{s\in S} \chi(s)\;|\; \chi\in \operatorname{Irr}(G),\; \chi(1)=\nu \right\} }[/math]
an invariant of the graph [math]\displaystyle{ \Gamma }[/math]? In other words, does [math]\displaystyle{ \operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,S') }[/math] imply that [math]\displaystyle{ M_\nu^S=M_\nu^{S'} }[/math]?
BI-group
A finite group [math]\displaystyle{ G }[/math] is called a BI-group (Babai Invariant group)[2] if [math]\displaystyle{ \operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,T) }[/math] for some inverse closed subsets [math]\displaystyle{ S }[/math] and [math]\displaystyle{ T }[/math] of [math]\displaystyle{ G\setminus \{1\} }[/math] implies that [math]\displaystyle{ M_\nu^S=M_\nu^T }[/math] for all positive integers [math]\displaystyle{ \nu }[/math].
Open problem
Which finite groups are BI-groups?[3]
See also
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. 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.
Original source: https://en.wikipedia.org/wiki/Babai's problem.
Read more |