Interpreting nowhere dense graph classes as a classical notion of model theory

DOI10.1016/j.ejc.2013.06.048zbMath1284.05155arXiv1011.4016OpenAlexW2076594341WikidataQ57949108 ScholiaQ57949108MaRDI QIDQ2441640

Hans Adler, Isolde Adler

Publication date: 25 March 2014

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

PAC learning\(r\)-minors

Mathematics Subject Classification ID

Computational learning theory (68Q32) Graph minors (05C83) Classification theory, stability, and related concepts in model theory (03C45) Density (toughness, etc.) (05C42)

Related Items (20)

On ultralimits of sparse graph classes ⋮ Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs ⋮ FO model checking on geometric graphs ⋮ On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry ⋮ Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs ⋮ Unnamed Item ⋮ Towards a characterization of universal categories ⋮ First-order limits, an analytical perspective ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Bounds on half graph orders in powers of sparse graphs ⋮ Regular partitions of gentle graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Characterizations of monadic NIP ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ Local-global convergence, an analytic and structural approach ⋮ Strict superstablity and decidability of certain generic graphs ⋮ Erdös--Hajnal Properties for Powers of Sparse Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Learnability and definability in trees and similar structures
• Homomorphism preservation on quasi-wide classes
• Classification theory and the number of non-isomorphic models.
• On nowhere dense graphs
• Domination Problems in Nowhere-Dense Classes
• Superstable graphs
• Finite Model Theory on Tame Classes of Structures
• Vapnik-Chervonenkis Classes of Definable Sets
• Stable graphs
• First order properties on nowhere dense structures
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities

This page was built for publication: Interpreting nowhere dense graph classes as a classical notion of model theory