Canonical labelling of sparse random graphs

On an n-vertex input graph, a canonical labelling algorithm computes a bijection from the set of vertices of the graph to {1,..,n} such that, for any other isomorphic graph, their labelled versions (according to the bijection) are identical. Once two graphs are canonically labelled, determining whether they are isomorphic can be done in linear time. The existence of polynomial-time algorithms for testing isomorphism of two given graphs and for producing a canonical labelling remains open. Babai's breakthrough quasi-polynomial algorithm for testing graph isomorphism was subsequently extended to a canonical labelling algorithm of the same time complexity
Nevertheless, for typical graphs (or, in other words, with high probability for binomial random graphs G(n,p) with p=1/2) it is known that there exists a linear time canonisation algorithm, due to Babai, Erdős, and Selkow (1980). Since then, several results have established efficient canonical labelling algorithms for random graphs across various ranges of edge probability p=p(n). Recently, we filled the last remaining gap and proved that there exists a polynomial-time algorithm that labels canonically the random graph G(n,p) with high probability, whatever the edge probability function p(n). The core of the algorithm is, so called, colour refinement procedure, which distinguishes graphs if and only if they are distinguishable in 2-variable first order logic with counting
The talk is based on joint work with Oleg Verbitsky