An Undecidability Result on Limits of Sparse Graphs

Abstract

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.