Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

2012 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

Sparsity

Graphs, Structures, and Algorithms

verfasst von: Jaroslav Nešetřil, Patrice Ossona de Mendez

Verlag: Springer Berlin Heidelberg

Buchreihe : Algorithms and Combinatorics

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Ü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

Frontmatter

Presentation

Frontmatter
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

The Theory

Frontmatter
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

Applications

Frontmatter
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
Metadaten
Titel
Sparsity
verfasst von
Jaroslav Nešetřil
Patrice Ossona de Mendez
Copyright-Jahr
2012
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-27875-4
Print ISBN
978-3-642-27874-7
DOI
https://doi.org/10.1007/978-3-642-27875-4