Authors: David Hartman, Tomáš Hons and Jaroslav Nešetřil

The field of graph convergence studies asymptotic properties of large graphs with the goal to define a well-behaved notion of a limit structure for a convergent sequence of graphs. The two most prominent types of convergence are defined for sequences of dense and sparse graphs. These were recently unified by Nešetřil and Ossona de Mendez into a common framework called first-order convergence using the expressive power of first-order logic. Moreover, the flexibility of this framework has since led to studies of convergence for other structures, such as matroids and mappings.

An important problem in the field is which objects can actually be approximated by finite structures, that is, to arise as a limit. This seems to be a very difficult problem (cf. Aldous-Lyons conjecture). We thus restrict ourselves to a simplified problem to approximate vertices of the limit object, which we call rooted inverse problem. This can be viewed as an attempt to trace the origin of limit’s vertices to the finite structures.

The rooted inverse problem was first defined by Nešetřil and Ossona de Mendez and answered negatively in general by Christofides and Král’. However, they also proved that almost all vertices of the limit can be approximated. Later, we proved that this includes algebraic vertices. Here we show that all vertices of the limit can be approximated given that the limit is sparse enough. We conjecture that all the vertices can be approximated if the limit is NIP.