Existence of modeling limits for sequences of sparse structures

DOI10.1017/JSL.2018.32MaRDI QIDQ5222519zbMATH OpenOpenAlexWikidataFDO

Authors J. Nešetřil, P. Ossona de Mendez

Publication date 6 April 2020

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.00146

zbMATH Keywords

modelingfirst-order propertiesstructural limitconvergence of graphslimit statisticstotally Borel graph

Mathematics Subject Classification ID

Other model constructions (03C30) Classification theory, stability, and related concepts in model theory (03C45) Models with special properties (saturated, rigid, etc.) (03C50) Graph theory (05C99) Applications of model theory (03C98) Other connections with logic and set theory (28E15)

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, and it was conjectured that this is the case if the graphs in the sequence are sufficiently sparse. Precisely, two conjectures were proposed: * 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. * A monotone class of graphs $mathcalC$ has the property that every FO-convergent sequence of graphs from $mathcalC$ has a modeling limit if and only if $mathcalC$ is nowhere dense, that is if and only if for each integer $p$ there is $N(p)$ such that no graph in $mathcalC$ contains the $p$th subdivision of a complete graph on $N(p)$ vertices as a subgraph.

Recommendations

• Modeling limits in hereditary classes: reduction and application to trees
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Sparse combinatorial structures: classification and applications
• From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
• On ultralimits of sparse graph classes

Cites work

• scientific article; zbMATH DE number 3819693 (Why is no real title available?)
• scientific article; zbMATH DE number 3941494 (Why is no real title available?)
• scientific article; zbMATH DE number 3111916 (Why is no real title available?)
• A model theory approach to structural limits.
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Counting graph homomorphisms
• First order convergence of matroids
• First order limits of sparse graphs: plane trees and path-width
• First order properties on nowhere dense structures
• First-order limits, an analytical perspective
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Graph limits and parameter testing
• Harvey Friedman's research on the foundations of mathematics
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Large networks and graph limits
• Limits of dense graph sequences
• Limits of mappings
• Modeling limits in hereditary classes: reduction and application to trees
• Moments of two-variable functions and the uniqueness of graph limits
• On limits of finite graphs
• On nowhere dense graphs
• Recurrence of distributional limits of finite planar graphs
• Regularity partitions and the topology of graphons
• Representations for partially exchangeable arrays of random variables
• Sparsity. Graphs, structures, and algorithms
• Structural limits and approximations of mappings
• Structural sparsity
• The Oxford handbook of probability and philosophy
• Ultraproducts of measure preserving actions and graph combinatorics
• Vapnik-Chervonenkis Classes of Definable Sets

Cited in

(8)

• The cut metric for probability distributions
• Local-global convergence, an analytic and structural approach
• scientific article; zbMATH DE number 7471705 (Why is no real title available?)
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Modeling limits in hereditary classes: reduction and application to trees
• Approximations of mappings
• On rational limits of Shelah-Spencer graphs
• First order limits of sparse graphs: plane trees and path-width

This page was built for publication: Existence of modeling limits for sequences of sparse structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5222519)