A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth

DOI10.1090/memo/1272zbMath1491.03004arXiv1303.6471OpenAlexW1512172501MaRDI QIDQ5108706

Jaroslav Nešetřil, Patrice Ossona de Mendez

Publication date: 6 May 2020

Published in: Memoirs of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

first-order logicmodel theoryRadon measuresStone spacegraph limitsmeasurable graphstructural limitsgraph and relational structure

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Stone spaces (Boolean spaces) and related structures (06E15) Graph theory (05C99) Model theory of finite structures (03C13) Applications of model theory (03C98) Integration theory via linear functionals (Radon measures, Daniell integrals, etc.), representing set functions and measures (28C05)

Related Items

Subgraph densities in a surface, Graphons arising from graphs definable over finite fields, Graph limits: An alternative approach to s‐graphons, A duality theoretic view on limits of finite structures, Approximations of Mappings, Relating structure and power: comonadic semantics for computational resources (extended abstract)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• First order convergence of matroids
• Sparsity. Graphs, structures, and algorithms
• Convergent sequences of dense graphs. II. Multiway cuts and statistical physics
• How many \(F\)'s are there in \(G\)?
• Characterisations and examples of graph classes with bounded expansion
• An analytic approach to stability
• École d'été de probabilités de Saint-Flour XIII - 1983
• Limits of dense graph sequences
• Graph limits and hereditary properties
• First-order limits, an analytical perspective
• On forbidden subdivision characterizations of graph classes
• On limits of finite graphs
• Convergent sequences of dense graphs. I: Subgraph frequencies, metric properties and testing
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• Fraternal augmentations, arrangeability and linear Ramsey numbers
• Graphs which contain all small graphs
• Representations for partially exchangeable arrays of random variables
• Borel chromatic numbers
• Recurrence of distributional limits of finite planar graphs
• Limits of structures and the example of tree semi-lattices
• On the scaling limit of finite vertex transitive graphs with large diameter
• Moments of two-variable functions and the uniqueness of graph limits
• Limits of mappings
• 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
• On nowhere dense graphs
• Interpreting nowhere dense graph classes as a classical notion of model theory
• Processes on unimodular random networks
• Tree-depth, subgraph coloring and homomorphism bounds
• Invariant percolation and harmonic Dirichlet functions
• Modeling limits in hereditary classes: reduction and application to trees
• Structural sparsity
• The Entropy of Random-Free Graphons and Properties
• When Trees Grow Low: Shrubs and Fast MSO1
• Graph limits and parameter testing
• Linear time low tree-width partitions and algorithmic consequences
• Where First-Order and Monadic Second-Order Logic Coincide
• Regularity partitions and the topology of graphons
• Hypergraph limits: A regularity approach
• An application of games to the completeness problem for formalized theories
• Homomorphism-Homogeneous Relational Structures
• Threshold Graph Limits and Random Threshold Graphs
• The Grad of a Graph and Classes with Bounded Expansion
• Graph limits and exchangeable random graphs
• Very large graphs
• Trees and amenable equivalence relations
• Countable Ultrahomogeneous Undirected Graphs
• Paley graphs satisfy all first-order adjacency axioms
• Vapnik-Chervonenkis Classes of Definable Sets
• Conversion from Nonstandard to Standard Measure Spaces and Applications in Probability Theory
• Probabilities on finite models
• Cluster analysis of local convergent sequences of structures
• A Model Theory Approach to Structural Limits
• First order properties on nowhere dense structures
• First order limits of sparse graphs: Plane trees and path-width
• Universal Structures with Forbidden Homomorphisms
• EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES
• Graphons, cut norm and distance, couplings and rearrangements
• First-Order Convergence and Roots
• Probabilistic Symmetries and Invariance Principles
• Asymptotic Enumeration of Spanning Trees
• Asymmetric graphs
• Quasi-random graphs