Structural sparsity
Borel structureindependence propertylow tree-depth decompositionmodel checkingmodellingnowhere dense classrandom-free limitrelational structuresshallow minorsparsitystabilitystructural limitVC-dimension
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)
This is an extensive survey in a compact format of the notion of structural sparsity. This notion appears in various disguises in different areas, such as graph theory, information theory, model theory and algorithmic complexity. The survey systematically considers different topics in which structural sparsity appears in one or more of its disguises. Key theorems are listed in connection with each topic. Many of these theorems show that, in an appropriate context, structural sparsity can be characterized in more than one way, and the different characterizations can have quite different flavours. The topics and notions discussed include nowhere density, Vapnik-Chervonenkis dimension, stability, regular partitions, structural limits (and graphons), class speed, entropy, logarithmic densities, shallow (topological) minors, bounded expansion, tree depth, quasi-wideness, and algorithmic consequences of the mentioned concepts.
- 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
- Separability properties of monadically dependent graph classes
- 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)
