Babai's problem

Babai's problem is a problem in algebraic graph theory first proposed in 1979 by László Babai.{{Citation |last1=Babai |first1=László |authorlink=László Babai|title=Spectra of Cayley graphs |journal=Journal of Combinatorial Theory, Series B |date=October 1979 |volume=27 |issue=2 |pages=180–189 |doi=10.1016/0095-8956(79)90079-0|doi-access= }}

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_\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 $\operatorname{Cay}(G,S)\cong \operatorname{Cay}(G,S')$ imply that $M_\nu^S=M_\nu^{S'}$ ?

BI-group

A finite group $G$ is called a BI-group (Babai Invariant group){{cite journal |last1=Abdollahi |first1=Alireza |last2=Zallaghi |first2=Maysam |title=Non-Abelian finite groups whose character sums are invariant but are not Cayley isomorphism |journal=Journal of Algebra and Its Applications |date=10 February 2019 |volume=18 |issue=1 |pages=1950013 |doi=10.1142/S0219498819500130|arxiv=1710.04446 }} 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_\nu^S=M_\nu^T$ for all positive integers $\nu$ .

Open problem

Which finite groups are BI-groups?{{cite journal |last1=Abdollahi |first1=Alireza |last2=Zallaghi |first2=Maysam |title=Character Sums for Cayley Graphs |journal=Communications in Algebra |date=24 August 2015 |volume=43 |issue=12 |pages=5159–5167 |doi=10.1080/00927872.2014.967398}}

References

Category:Algebraic graph theory

Category:Unsolved problems in graph theory

Babai's problem

Babai's problem

BI-group

Open problem

See also

References