Nešetřil–Ossona de Mendez limit-modeling conjecture for nowhere-dense classes
Nešetřil–Ossona de Mendez limit-modeling conjecture for nowhere-dense classes
Let be a nowhere-dense class of graphs. A sequence of graphs from 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 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.