Local canonical labeling of Erdős–Rényi random graphs
share
We study local canonical labeling algorithms on an Erdős–Rényi random graph G(n,p_n). A canonical labeling algorithm assigns a unique label to each vertex of an unlabeled graph such that the labels are invariant under isomorphism. Here we focus on local algorithms, where the label of each vertex depends only on its low-depth neighborhood. Czajka and Pandurangan showed that the degree profile of a vertex (i.e., the sorted list of the degrees of its neighbors) gives a canonical labeling with high probability when n p_n = ω( log^4(n) / loglog n ) (and p_n≤ 1/2); subsequently, Mossel and Ross showed that the same holds when n p_n = ω( log^2(n) ). Our first result shows that their analysis essentially cannot be improved: we prove that when n p_n = o( log^2(n) / (loglog n)^3 ), with high probability there exist distinct vertices with isomorphic 2-neighborhoods. Our main result is a positive counterpart to this, showing that 3-neighborhoods give a canonical labeling when n p_n ≥ (1+δ) log n (and p_n ≤ 1/2); this improves a recent result of Ding, Ma, Wu, and Xu, completing the picture above the connectivity threshold. We also discuss implications for random graph isomorphism and shotgun assembly of random graphs.
READ FULL TEXT