Interpreting nowhere dense graph classes as a classical notion of model theory
From MaRDI portal
Abstract: A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe that this tameness notion from algorithmic graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property.
Recommendations
Cites work
- Classification theory and the number of non-isomorphic models.
- Domination problems in nowhere-dense classes of graphs
- Finite Model Theory on Tame Classes of Structures
- First order properties on nowhere dense structures
- Homomorphism preservation on quasi-wide classes
- scientific article; zbMATH DE number 1007358 (Why is no real title available?)
- scientific article; zbMATH DE number 2203240 (Why is no real title available?)
- Learnability and definability in trees and similar structures
- On nowhere dense graphs
- On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
- Sparsity. Graphs, structures, and algorithms
- Stable graphs
- Superstable graphs
- Vapnik-Chervonenkis Classes of Definable Sets
Cited in
(45)- FO model checking on geometric graphs
- Towards a characterization of universal categories
- (Lack of) model structures on the category of graphs
- Regular partitions of gentle graphs
- Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
- Strict superstablity and decidability of certain generic graphs
- On nowhere dense graphs
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Bounds on half graph orders in powers of sparse graphs
- On ultralimits of sparse graph classes
- On (uniform) hierarchical decompositions of finite structures and model-theoretic geometry
- Progressive algorithms for domination and independence
- Algorithmic properties of sparse digraphs
- A unified approach to structural limits and limits of graphs with bounded tree-depth
- FO model checking of geometric graphs
- On the number of types in sparse graphs
- Characterizations of monadic NIP
- Existence of modeling limits for sequences of sparse structures
- Local-global convergence, an analytic and structural approach
- Tameness in least fixed-point logic and McColm's conjecture
- Erdös-Hajnal properties for powers of sparse graphs
- Bounds on half graph orders in powers of sparse graphs
- Discrepancy and sparsity
- Counting subgraphs in somewhere dense graphs
- Stable graphs of bounded twin-width
- Model checking on interpretations of classes of bounded local cliquewidth
- Existential characterizations of monadic NIP
- Strong odd colorings in graph classes of bounded expansion
- Graph theory. Abstracts from the workshop held January 5--10, 2025
- Decomposition horizons and a characterization of stable hereditary classes of graphs
- A survey of degree-boundedness
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- On first-order transductions of classes of graphs
- Algebraically universal categories of relational structures
- Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
- Monadic NIP in monotone classes of relational structures (extended abstract)
- Shallow vertex minors, stability, and dependence
- Twin-width. IV: Ordered graphs and matrices
- First-order transductions of graphs (invited talk)
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Extension preservation on dense graph classes
- On the VC dimension of first-order logic with counting and weight aggregation
- Advances in algorithmic meta theorems (invited paper)
- Vapnik-Chervonenkis dimension and density on Johnson and Hamming graphs
- First-order limits, an analytical perspective
This page was built for publication: Interpreting nowhere dense graph classes as a classical notion of model theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2441640)
