Structural sparsity

DOI10.1070/RM9688MaRDI QIDQ2815673zbMATH OpenOpenAlexFDO

Authors J. Nešetřil, P. Ossona de Mendez

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

Borel structureindependence propertylow tree-depth decompositionmodel checkingmodellingnowhere dense classrandom-free limitrelational structuresshallow minorsparsitystabilitystructural limitVC-dimension

Mathematics Subject Classification ID

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

Recommendations

• Sparsity. Graphs, structures, and algorithms
• Characterisations of nowhere dense graphs (invited talk)
• Structural Properties of Sparse Graphs
• Sparse combinatorial structures: classification and applications
• Extremal problems for sparse graphs

Cited in

(31)

• Towards a characterization of universal categories
• Generalized arboricity of graphs with large girth
• Obstructions for bounded shrub-depth and rank-depth
• Regular partitions of gentle graphs
• Classes of graphs with low complexity: the case of classes with bounded linear rankwidth
• On nowhere dense graphs
• Quantified conjunctive queries on partially ordered sets
• Extremal problems for sparse graphs
• Sparse combinatorial structures: classification and applications
• From sparse graphs to nowhere dense structures: decompositions, independence, dualities and limits
• Structural Properties of Sparse Graphs
• Sublinear time estimation of degree distribution moments: the arboricity connection
• Nonrepetitive colorings of line arrangements
• Diameter, eccentricities and distance oracle computations on H-minor free graphs and graphs of bounded (distance) Vapnik-Chervonenkis dimension
• Harary polynomials
• A unified approach to structural limits and limits of graphs with bounded tree-depth
• Existence of modeling limits for sequences of sparse structures
• Local-global convergence, an analytic and structural approach
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Discrepancy and sparsity
• Isomorphism for tournaments of small twin width
• Decomposition horizons and a characterization of stable hereditary classes of graphs
• Decomposition horizons: from graph sparsity to model-theoretic dividing lines (extended abstract)
• Advances in algorithmic meta theorems (invited paper)
• Strong modeling limits of graphs with bounded tree-width
• In praise of homomorphisms
• Sparse versus simple structure loadings
• Invariant measures via inverse limits of finite structures
• On low tree-depth decompositions
• Uniqueness and minimal obstructions for tree-depth
• Mapping planar graphs into the Coxeter graph

This page was built for publication: Structural sparsity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815673)