main-content

Über dieses Buch

This is the first book devoted to the systematic study of sparse graphs and sparse finite structures. Although the notion of sparsity appears in various contexts and is a typical example of a hard to define notion, the authors devised an unifying classification of general classes of structures. This approach is very robust and it has many remarkable properties. For example the classification is expressible in many different ways involving most extremal combinatorial invariants.

This study of sparse structures found applications in such diverse areas as algorithmic graph theory, complexity of algorithms, property testing, descriptive complexity and mathematical logic (homomorphism preservation,fixed parameter tractability and constraint satisfaction problems). It should be stressed that despite of its generality this approach leads to linear (and nearly linear) algorithms.

Jaroslav Nešetřil is a professor at Charles University, Prague; Patrice Ossona de Mendez is a CNRS researcher et EHESS, Paris.

This book is related to the material presented by the first author at ICM 2010.

Inhaltsverzeichnis

Chapter 1. Introduction

Abstract
Combinatorics is a long story. But we believe that we live in the unique point of scientific history when combinatorics is becoming an essential part of mathematics and when the rich techniques developed in isolated and specific contexts are put to service in solving problems which are of general mathematical and scientific interest.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 2. A Few Problems

Abstract
Meshes are a standard support for finding approximate solutions to partial differential equations (PDE) as well as of integral equations. Computational techniques working with a Divide-and-Conquer scheme need an initial mesh to be recursively broken into pieces of comparable size by cutting along small set of points (called a vertex separator).
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 3. Prolegomena

Abstract
In this chapter we introduce the relevant concepts and techniques, and prove some basic results which will be used later on.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 4. Measuring Sparsity

Abstract
In the introduction we described the big picture of our theory. Here we begin with a more formal treatment. We define shallow minors, topological minors, and immersions as the basic local changes in graph classes. We show that edge densities in the iteration of these local changes are related and that they are also related to other parameters such as chromatic number and generalized coloring numbers.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 5. Classes and Their Classification

Abstract
This chapter starts on an abstract level, by dealing with classes and their properties. As such it belongs to model theory (and general theory of categories). However our approach is very concrete and we deal with classes of graphs although many of the concepts and results carry over a more general setting. This will be made explicit in Sect. 5.8.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 6. Bounded Height Trees and Tree-Depth

Abstract
After treating graph classes and class resolutions we return to the basics: the structure of finite trees as the true measure of our things.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 7. Decomposition

Abstract
The local properties of structures are frequently studied by means of decompositions: the large structure is cut into (hopefully simpler)pieces whose properties are then studied together with the interconnections between pieces. Several decomposition schemes can be considered. For example, one can stress the regularity of the interconnections of the pieces as in modular decomposition of graphs (a recursive partition into modules such that, for each module, the neighborhoods outside the module of the vertices within the module are all equal [206, 266, 330]). As another example, one can consider a family of overlapping simple pieces covering the structure, in the spirit of the coherency between charts in topological atlases, such as the gluing axiom of sheaves [320] or the arrow construction for the category of labeled rooted forest and the category of labeled Feynman graphs [290].
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 8. Independence

Abstract
We know that the dichotomy nowhere dense vs. somewhere dense can be expressed by means of decompositions, maximal cliques, and coloring numbers. We now give in a way a dual characterization by independence(or stability).
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 9. First-Order Constraint Satisfaction Problems, Limits and Homomorphism Dualities

Abstract
An important part of the classical model theory studies properties of abstract mathematical structures (finite or not) expressible in first-order logic [257]. In the setting of finite model theory, which developed more recently, one studies first-order logic (and its various extensions) just on finite structures [141, 303]. Both theories share many similarities but also display important and profound differences. This will be illustrated in this chapter by means of several examples. We start with a generalization of the coloring problem.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 10. Preservation Theorems

Abstract
We start with the following observation: If a formula $$\Theta$$expresses a H-coloring problem (i.e.$$\textbf{G}\models \Theta$$if and only if$$G \rightarrow H$$the negated formula $$\rightharpoondown \Theta$$is preserved by homomorphisms:
$$\textbf{G}\models \rightharpoondown \Phi \;and\; G\rightarrow {G}\prime \quad \Rightarrow \quad {G}\prime \models \rightharpoondown \Phi$$
(1.10)
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 11. Restricted Homomorphism Dualities

Abstract
In the case where the input structures are restricted to some class C, some more “restricted” homomorphism dualities may appear.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 12. Counting

Abstract
In the previous chapters of this book we investigated the problem of the existence of particular structures or operations with them, such as the existence of special partitions, the value of special parameters (for example $$\nabla_{r}(G)$$ or the existence of special subsets.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 13. Back to Classes

Abstract
In this chapter we summarize the results on sparsity of classes with all their characterizations. The multiplicity of the equivalent characterizations that can be given for the nowhere dense–somewhere dense dichotomy is mainly a consequence of several related aspects:
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 14. Classes with Bounded Expansion – Examples

Abstract
Bounded expansion classes are the focus of this chapter and one of the leitmotivs of the whole book. In this chapter, we shall give many examples of classes with bounded expansion. The examples which we cover are schematically depicted on Fig. 14.1. These classes cover most classes considered in structural graph theory and the relevant parts of logic and discrete geometry. This will be explained for several of these classes in a greater detail in this chapter.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 15. Some Applications

Abstract
A matching of a graph G is a set of pairwise non-intersecting edges. An induced matching of a graph G is a matching of G which is an induced subgraph of G, that is a matching with the property that no endpoint of an edge in the matching is adjacent to an endpoint of another edge in the matching.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 16. Property Testing, Hyperfiniteness and Separators

Abstract
Since the introduction by Alhazen and Avicenna of the experimental method and of the combination of observations, experiments and rational arguments in the early eleventh century, the scientific method gained in significance and became, after the works of Bacon, Descartes, Boyle and Newton, the standard methodology to come close to the Truth.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 17. Core Algorithms

Abstract
An essential part of this book deals with estimates of complexity of algorithms. The aim of this chapter is to describe core algorithms, like the computation of a p-tree-depth decomposition. We shall describe this particular algorithm in a sufficiently precise way to allow an actual implementation of the described algorithms. In order to base our complexity results, we specify our computational model in this chapter.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 18. Algorithmic Applications

Abstract
As a particular interpretation, this problem contains the decision problem for first-order logic (that is, the problem of algorithmically deciding whether a first-order formula is universally valid). A negative answer to the Entscheidungsproblem was given by Church and Turing, who proved that it is impossible to decide algorithmically whether statements in arithmetic are true or false.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 19. Further Directions

Abstract
Like every active area of mathematics our book leaves some intriguing and challenging problems open. They relate for example to better computations and improvements of provided bounds. In a way most of our results on logarithmic density are just the first order approximations which certainly can be improved on many places.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Chapter 20. Solutions and Hints for some of the Exercises

Abstract
3.1 For $$A \subseteq V(G)$$ let f(A) be the number of edges between A and $$V(G)/A$$. Let A be such that f(A) is maximal. No vertex $$\nu \in A$$ has more neighbors in A than in V(G)\A as we would have f$$(A-\nu) > A$$.
Jaroslav Nešetřil, Patrice Ossona de Mendez

Backmatter

Weitere Informationen