Sparsity. Graphs, structures, and algorithms
type: Item
instance of: scholarly article
title: Sparsity. Graphs, structures, and algorithms
zbMATH Open document ID: 1268.05002
DOI: 10.1007/978-3-642-27875-4
author: J. Nešetřil
author: P. Ossona de Mendez
published in: Algorithms and Combinatorics
publication date: 2012-05-18T00:00:00Z
review text: What is a natural definition of `sparsity' as mathematical structure? This book gives us a very persuasive answer for this quite difficult and highly abstract question: ``The notion of sparsity of course depends on the particular field of study (sparse matrix, sparse graph, sparse set). However, a bit surprisingly, many of these concepts and problems fit into a grand picture which we introduce. We aim for generality yet we shall illustrate most of the topics on a very simple model: undirected graphs.'' ``What is a sparse graph? This is a fuzzy notion which has to be understood in the context. A sparse graph is not defined by itself, it is sparse relative to other graphs. Sparsity is a robust notion which does not change by a small change, like the notion of a heap of hay which does not change by a adding or removing a few straws. Hence this notion should not apply to a single graph, but rather to a class of graphs.'' ``The sparse versus dense dichotomy takes in this book the form of a classification of arbitrary (infinite) classes of finite graphs (or finite structures) into somewhere dense and nowhere dense classes.'' A graph \(H\) is said to be a \textit{shallow minor} of a graph \(G\) at \textit{depth} \(d\) if \(H\) is a graph minor of \(G\) such that each vertex \(x\) of \(H\) is corresponding to a subgraph \(G_x\) of \(G\) which has radius at most \(d\), and that, for each edge \(uv\) of \(H\), there exists an edge of \(G\) joining a vertex of \(G_u\) and a vertex of \(G_v\). (Although this definition is extended to the range of the half-integral values \(d\), those details are omitted here.) A graph class \(\mathcal{C}\) is called \textit{somewhere dense} if there exists a finite half-integer \(a\) such that the graph class \(\mathcal{C} \triangledown a\) of the all `depth \(a\)'-shallow minors of the graphs of \(\mathcal{C}\) turns out to be the class \(\mathfrak{Graph}\) of all finite graphs. By contrast, a graph class \(\mathcal{C}\) is called \textit{nowh…
reviewed by: Tadashi Sakuma
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05C42
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 05C83
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 03C13
zbMATH DE Number: 6036475
zbMATH Keywords: density
zbMATH Keywords: sparsity
zbMATH Keywords: tree-depth
zbMATH Keywords: graph minor
zbMATH Keywords: homomorphism
zbMATH Keywords: model theory
zbMATH Keywords: first-order logic
Wikidata QID: Q55868072
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1007/978-3-642-27875-4
OpenAlex ID: W4253175698
Recommended article: Spectral Sparsification of Graphs
Recommended article: Sparse matrix decompositions and graph characterizations
Recommended article: A general framework for graph sparsification
Recommended article: A General Framework for Graph Sparsification
Recommended article: Q5090497
Recommended article: Structural Properties of Sparse Graphs
Recommended article: Sparse graphs: Metrics and random models
Recommended article: Spanners in sparse graphs
Recommended article: Spanners in Sparse Graphs
description: scientific article; zbMATH DE number 6036475