Nešetřil–Ossona de Mendez limit-modeling conjecture for nowhere-dense classes

Let C{\cal C} be a nowhere-dense class of graphs. A sequence of graphs from C{\cal C} is first order convergent if the limiting frequency of every first-order property exists. A limit modeling is a modeling representing the limiting first-order probabilities of the sequence. Nešetřil–Ossona de Mendez conjecture. Every first order convergent sequence of graphs from C{\cal C} has a limit modeling. This conjecture addresses the existence of analytic representations for first-order limits of sparse graphs; the source presents it as a central open problem for nowhere-dense classes.

Sources & referencesView supporting material

Primary source

Jakub Gajarsky, Petr Hlineny, Tomas Kaiser, Daniel Kral, Martin Kupec, Jan Obdrzalek, Sebastian Ordyniak and Vojtech Tuma, “First order limits of sparse graphs: Plane trees and path-width”, arXiv:1504.08122 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.