An undecidability result on limits of sparse graphs (Q426892)

Summary: Given a set \(\mathcal{B}\) of finite rooted graphs and a radius \(r\) as an input, we prove that it is undecidable to determine whether there exists a sequence \((G_i)\) of finite bounded degree graphs such that the rooted \(r\)-radius neighbourhood of a random node of \(G_i\) is isomorphic to a rooted graph in \(\mathcal{B}\) with probability tending to 1. Our proof implies a similar result for the case where the sequence \((G_i)\) is replaced by a unimodular random graph.