Existence of modeling limits for sequences of sparse structures

DOI10.1017/JSL.2018.32zbMATH Open1444.03126arXiv1608.00146OpenAlexW2962785184WikidataQ128298217 ScholiaQ128298217MaRDI QIDQ5222519FDOQ5222519

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)

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.

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

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

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)

Cites Work

• Limits of dense graph sequences
• Recurrence of distributional limits of finite planar graphs
• Large networks and graph limits
• Representations for partially exchangeable arrays of random variables
• Moments of two-variable functions and the uniqueness of graph limits
• Counting graph homomorphisms
• 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
• The Oxford handbook of probability and philosophy
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Sparsity. Graphs, structures, and algorithms
• Title not available (Why is that?)
• Ultraproducts of measure preserving actions and graph combinatorics
• Limits of mappings
• Structural limits and approximations of mappings
• First order convergence of matroids
• A model theory approach to structural limits.
• On limits of finite graphs
• Graph limits and parameter testing
• Regularity partitions and the topology of graphons
• On nowhere dense graphs
• First order properties on nowhere dense structures
• Vapnik-Chervonenkis Classes of Definable Sets
• Harvey Friedman's research on the foundations of mathematics
• Structural sparsity
• Title not available (Why is that?)
• First-order limits, an analytical perspective
• Modeling limits in hereditary classes: reduction and application to trees
• First order limits of sparse graphs: plane trees and path-width
• Title not available (Why is that?)

Cited In (8)

• The cut metric for probability distributions
• Local-global convergence, an analytic and structural approach
• Title not available (Why is that?)
• 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)