Английская Википедия:Babai's problem
Шаблон:Unsolved Babai's problem is a problem in algebraic graph theory first proposed in 1979 by László Babai.[1]
Babai's problem
Let <math>G</math> be a finite group, let <math>\operatorname{Irr}(G)</math> be the set of all irreducible characters of <math>G</math>, let <math>\Gamma=\operatorname{Cay}(G,S)</math> be the Cayley graph (or directed Cayley graph) corresponding to a generating subset <math>S</math> of <math>G\setminus \{1\}</math>, and let <math>\nu</math> be a positive integer. Is the set
- <math>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>\Gamma</math>? In other words, does <math>\operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,S')</math> imply that <math>M_\nu^S=M_\nu^{S'}</math>?
BI-group
A finite group <math>G</math> is called a BI-group (Babai Invariant group)[2] if <math>\operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,T)</math> for some inverse closed subsets <math>S</math> and <math>T</math> of <math>G\setminus \{1\}</math> implies that <math>M_\nu^S=M_\nu^T</math> for all positive integers <math>\nu</math>.
Open problem
Which finite groups are BI-groups?[3]
See also
References