Structural sparsity

DOI10.1070/RM9688zbMath1367.03065OpenAlexW4253717429MaRDI QIDQ2815673

Patrice Ossona de Mendez, Jaroslav Nešetřil

Publication date: 30 June 2016

Published in: Russian Mathematical Surveys (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1070/rm9688

zbMATH Keywords

stabilitymodellingVC-dimensionmodel checkingrelational structuresindependence propertysparsitylow tree-depth decompositionBorel structureshallow minorstructural limitnowhere dense classrandom-free limit

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99) Model theory of finite structures (03C13) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Applications of model theory (03C98) Descriptive complexity and finite models (68Q19)

Related Items (18)

In praise of homomorphisms ⋮ Diameter, Eccentricities and Distance Oracle Computations on H-Minor Free Graphs and Graphs of Bounded (Distance) Vapnik–Chervonenkis Dimension ⋮ Harary polynomials ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Towards a characterization of universal categories ⋮ Invariant measures via inverse limits of finite structures ⋮ A Unified Approach to Structural Limits and Limits of Graphs with Bounded Tree-Depth ⋮ Uniqueness and minimal obstructions for tree-depth ⋮ Mapping planar graphs into the Coxeter graph ⋮ Regular partitions of gentle graphs ⋮ Classes of graphs with low complexity: the case of classes with bounded linear rankwidth ⋮ Generalized arboricity of graphs with large girth ⋮ Nonrepetitive colorings of line arrangements ⋮ Partitioning \(H\)-minor free graphs into three subgraphs with no large components ⋮ Obstructions for bounded shrub-depth and rank-depth ⋮ Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection ⋮ EXISTENCE OF MODELING LIMITS FOR SEQUENCES OF SPARSE STRUCTURES ⋮ Local-global convergence, an analytic and structural approach

This page was built for publication: Structural sparsity