Babai's problem explained

Babai's problem is a problem in algebraic graph theory first proposed in 1979 by László Babai.

Babai's problem

Let

G be a finite group, let \operatorname{Irr}(G) be the set of all irreducible characters of G , let \Gamma = \operatorname{Cay}(G,S) be the Cayley graph (or directed Cayley graph) corresponding to a generating subset S of G\setminus \{ 1 \} , and let \nu be a positive integer. Is the set M ^{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 \operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,S') imply that M ^{S'} _{\nu} ?

BI-group

A finite group

G is called a BI-group (Babai Invariant group)^[1] if \operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,T) for some inverse closed subsets S and T of G\setminus \{ 1 \} implies that M ^{T} _{\nu} for all positive integers \nu .

Open problem

Which finite groups are BI-groups?^[2]

See also

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

Notes and References

1. Abdollahi . Alireza . Zallaghi . Maysam . Non-Abelian finite groups whose character sums are invariant but are not Cayley isomorphism . . 10 February 2019 . 18 . 1 . 1950013 . 10.1142/S0219498819500130. 1710.04446 .
2. Abdollahi . Alireza . Zallaghi . Maysam . Character Sums for Cayley Graphs . . 24 August 2015 . 43 . 12 . 5159–5167 . 10.1080/00927872.2014.967398.