Sparsity. Graphs, structures, and algorithms (Q419416): Difference between revisions

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{nowhere dense} if, for every half-integer \(a\), the class \(\mathcal{C} \triangledown a\) is a proper subclass of \(\mathfrak{Graph}\). The authors show, with their vast and versatile erudition, the robustness of this dichotomy and its powerful utility in mathematics and, more widely, in the context of logic (i.e., the finite and/or infinite model theory). This book is organized in three parts, Presentation, Theory, and Applications. After giving a general overview in the first part `Presentation', the authors, in the second part `Theory', devote eleven chapters (Chapters 3 to 13) to delineate and develop various structural results concerned with their dichotomic concept. Several forcible arguments for the robustness of the nowhere dense versus somewhere dense dichotomy are given in Chapter 5. In fact, one may, instead of graph minors, use the concept of topological graph minors or immersions to define variant types of such dichotomy, and all of these variants turn to be identical. More characterizations are given in Chapters 7, 8, 12, and 11. Nowhere dense classes and their significant subclasses, namely, \textit{bounded expansion classes}, which include \textit{excluded minor classes}, are investigated in full details. One of the main tools for these investigations is \textit{tree-depth}. In Chapter 10, the authors give a profound connection of their theory to model theory and deal particularly with relativizations of the homomorphism preservation theorem of first-order logic, which includes a new setting for Benjamin Rossman's celebrated finite homomorphism preservation theorem together with extensions [Journal of the ACM, Vol. 55, No.3, Article 15 (2008)]. In the third part `Applications' (from Chapter 14 to 18), the authors develop a wide range of (both theoretical and algorithmic) applications of the concepts and results introduced in the second part `Theory', which contain theoretical applications to Erdős-Rényi model of random graphs, crossing number, queue and stack layouts, non-repetitive colorings, matching, Burr-Erdős conjecture, and property testing (from Chapter 14 to 16). The part also contains core algorithms corresponding to their theory (Chapter 17) and algorithmic applications to the model checking problem for first-order logic (Chapter 18). This is an excellent and useful book for all researchers in mathematics, computer science, logic, and even in any field in physical science, who seek the tools available for analysis of the properties of discrete structures, and particularly, sparse structures.