The Babai Conjecture on Graph Isomorphism

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

A finite simple graph is $G=(V,E)$, where $E$ is a set of unordered pairs of distinct vertices. Two graphs $G,H$ are isomorphic if there is a bijection $\phi:V(G)\to V(H)$ with \[ \{u,v\}\in E(G)\ \Longleftrightarrow\ \{\phi(u),\phi(v)\}\in E(H). \] Use an adjacency-matrix encoding. A quasipolynomial bound is $\exp((\log N)^{O(1)})$, where $N$ is the total number of input vertices; the exponent is an absolute constant, independent of the graphs.

Statement recorded in the supplied source.

Is there a deterministic algorithm deciding whether any two finite graphs are isomorphic in worst-case time \[ \exp\left(C(\log(N+2))^c\right) \] for absolute constants $C,c>0$? This recorded quasipolynomial target is achieved by Babai's algorithm; it does not ask for a polynomial-time bound. [S2]

Short English statement

Can isomorphism of arbitrary finite graphs be decided in quasipolynomial time? Babai's cited algorithm attains this historical target.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1156 (ALG-016). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 László Babai, Graph Isomorphism in Quasipolynomial Time, Proceedings of STOC 2016, 684--697, abstract and introduction; arXiv:1512.03547. https://arxiv.org/abs/1512.03547.