1. EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES
- Author
-
Jaroslav Nešetřil, Patrice Ossona de Mendez, Department of Applied Mathematics (KAM) (KAM), Univerzita Karlova v Praze, Centre d'Analyse et de Mathématique sociales (CAMS), and École des hautes études en sciences sociales (EHESS)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Sequence ,Logic ,010102 general mathematics ,0102 computer and information sciences ,Characterization (mathematics) ,01 natural sciences ,Combinatorics ,Philosophy ,Definable set ,Monotone polygon ,Integer ,010201 computation theory & mathematics ,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO] ,Standard probability space ,Limit (mathematics) ,Ball (mathematics) ,0101 mathematics ,ComputingMilieux_MISCELLANEOUS ,Mathematics - Abstract
A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequence of graphs do not always admit a modeling limit, but it was conjectured that FO-convergent sequences of sufficiently sparse graphs have a modeling limits. Precisely, two conjectures were proposed:1.If a FO-convergent sequence of graphs is residual, that is if for every integer d the maximum relative size of a ball of radius d in the graphs of the sequence tends to zero, then the sequence has a modeling limit.2.A monotone class of graphs ${\cal C}$ has the property that every FO-convergent sequence of graphs from ${\cal C}$ has a modeling limit if and only if ${\cal C}$ is nowhere dense, that is if and only if for each integer p there is $N\left( p \right)$ such that no graph in ${\cal C}$ contains the pth subdivision of a complete graph on $N\left( p \right)$ vertices as a subgraph.In this article we prove both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense–somewhere dense dichotomy.
- Published
- 2019