Sparsity: Graphs, Structures, and Algorithms (Algorithms and Combinatorics, 28)

✍ Scribed by Jaroslav Nesetril, Patrice Ossona de Mendez

• Publisher: Springer
• Year: 2012
• Tongue: English
• Leaves: 472
• Category: Library

✦ Synopsis

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.

✦ Table of Contents

Preface
Contents
List of Symbols
Presentation
1 Introduction
2 A Few Problems
2.1 Breaking a Mesh
2.2 Forging Alliances
2.3 Are Symmetries Frequent?
2.4 Large Matchings on a Torus
2.5 Homomorphism Dualities
The Theory
3 Prolegomena
3.1 Graphs
3.2 Average Degree and Minimum Degree
3.3 Graph Degeneracy and Orientations
3.4 Girth
3.5 Minors
3.6 Width, Separators and Expanders
3.7 Homomorphisms
3.8 Relational Structures and First-Order Logic
3.8.1 Relational Structures
3.8.2 First-Order Logic
3.8.3 Derived Graphs
3.8.4 Ehrenfeucht-Fraïssé Games
3.8.5 Interpretation
3.9 Ramsey Theory
3.10 Graph Parameters
3.11 Computational complexity
Exercises
4 Measuring Sparsity
4.1 Basic Definitions
4.2 Shallow Minors
4.3 Shallow Topological Minors
4.4 Grads and Top-Grads
4.5 Polynomial Equivalence of Grads and Top-Grads
4.6 Relation with Chromatic Number
4.7 Stability of Grads by Lexicographic Product
4.8 Shallow Immersions
4.9 Generalized Coloring Numbers
Exercises
5 Classes and Their Classification
5.1 Operations on Classes and Resolutions
5.1.1 Class Suprema and Class Limits
5.1.2 Class Operations
5.1.3 Class Resolutions
5.1.4 Topological Parameters
5.2 Logarithmic Density and Concentration
5.3 Classification of Classes by Clique Minors
5.4 Classification by Density—Trichotomy of Classes
5.5 Classes with Bounded Expansion
5.6 Classes with Locally Bounded Expansion
5.7 A Historical Note on Connection to Model Theory
5.8 Classes of Relational Structures
Exercises
6 Bounded Height Trees and Tree-Depth
6.1 Definitions and Basic Properties
6.2 Tree-Depth, Minors and Paths
6.3 Compact Elimination Trees and Weak-Coloring
6.4 Tree-Depth, Tree-Width and Vertex Separators
6.5 Centered Colorings
6.6 Cycle Rank
6.7 Games and a Min-Max Formula for Tree-Depth
6.8 Reductions and Finiteness
6.9 Ehrenfeucht-Fraïssé Games
6.10 Well Quasi-orders
6.11 The Homomorphism Quasi-order
Exercises
7 Decomposition
7.1 Motivation, Low Tree-Width and Low Tree-Depth
7.2 Low Tree-Depth Coloring and p-Centered Colorings
7.3 Transitive Fraternal Augmentation
7.4 Fraternal Augmentations of Graphs
7.5 The Weak-Coloring Approach
Exercises
8 Independence
8.1 How Wide is a Class?
8.2 Wide Classes
8.3 Finding d-Independent Sets in Graphs
8.3.1 Finding 1-Independent Sets in Graphs
8.3.2 Finding a 2-Independent Set in a 1-Independent Set
8.3.3 Finding a (2r+1)-independent Set in a 2r-independent Set
8.3.4 Finding a (2r+2)-Independent Set in a (2r+1)-Independent Set
8.4 Quasi-Wide Classes
8.5 Almost Wide Classes
8.6 A Nice (Asymmetric) Application
Exercises
9 First-Order CSP, Limits and Homomorphism Dualities
9.1 Introduction
9.2 Homomorphism Dualities and the Functor U
9.2.1 Finite Dualities
9.2.2 Tree Dualities and the Functor U
9.3 Metrics on the Homomorphism Order
9.3.1 Partially Ordered Sets
9.3.2 The Homomorphism Order of -Structures
9.3.3 Connectivity and Multiplicativity
9.3.4 Left and Right Distances for the Homomorphism Order
9.3.5 Density
9.3.5.1 Density and Ambivalence of the Homomorphism Order
9.4 Left Limits and Countable Structures
9.4.1 Left Limits
9.5 Right Limits and Full Limits
9.5.1 The Right Distance
9.5.2 Full Distance
9.5.3 Full Dualities
Exercises
10 Preservation Theorems
10.1 Introduction
10.2 Primitive Positive Theories and Left Limits
10.3 Theories and Countable Structures
10.4 Primitive Positive Theories Again
10.5 Quotient Metric Spaces
10.6 The Topological Preservation Theorem
10.7 Homomorphism Preservation Theorems
10.8 Homomorphism Preservation Theoremsfor Finite Structures
Exercises
11 Restricted Homomorphism Dualities
11.1 Introduction
11.2 Classes with All Restricted Dualities
11.3 Characterization of Classes with All Restricted Dualities by Distances
11.4 Characterization of Classes with All Restricted Dualities by Local Homomorphisms
11.5 Restricted Dualities in Bounded Expansion Classes
11.6 Characterization of Classes with All Restricted Dualities by Reorientations
11.7 Characterization of Classes with All Restricted Dualities by Subdivisions
11.8 First-Order Definable H-Colorings
11.9 Consequences and Related Problems
11.9.1 On Hadwiger Conjecture
11.9.2 On Bounded Expansion Classes
11.9.3 On Distance Colorings – Powers and Exact Powers
Exercises
12 Counting
12.1 Introduction
12.2 Generalized Sunflowers
12.2.1 Generalized Sunflowers
12.3 Counting Patterns of Bounded Height in a Colored Forest
12.3.1 Patterns
12.3.2 Blowing Patterns
12.3.3 Warm Up: Counting Patterns of Height 1
12.3.4 Counting Patterns of Height h
12.4 Counting in Graphs with Bounded Tree Depth
12.5 Counting Subgraphs in Graphs
12.6 Counting Subgraphs in Graphs in a Class
Exercises
13 Back to Classes
13.1 Resolutions
13.2 Parameters
13.3 Nowhere Dense Classes
13.4 Bounded Expansion Classes
13.5 Bounded Tree-Depth Classes
13.6 Remarks on Structures
Applications
14 Classes with Bounded Expansion – Examples
14.1 Random Graphs (Erdos-Rényi Model)
14.2 Crossing Number
14.3 Queue and Stack Layouts
14.4 Queue Number
14.5 Stack Number
14.6 Non-repetitive Colorings
Exercises
15 Some Applications
15.1 Finding Matching and Paths
15.1.1 Introduction
15.1.2 Finding a Big Subgraph with Low Degrees
15.1.3 Finding Matchings
15.1.4 Finding Paths
15.1.5 A Particular Application: Strong Star Chromatic Number
15.2 Burr–Erdos Conjecture
15.3 The Game Chromatic Number
15.4 Fiedler Value of Classes with Sublinear Separators
16 Property Testing, Hyperfiniteness and Separators
16.1 Property Testing
16.1.1 The Dense Model
16.1.2 The Bounded Degree Model
16.2 Weakly Hyperfinite Classes
16.3 Vertex Separators
16.4 Sub-exponential -expansion
Exercises
17 Core Algorithms
17.1 Data Structures and Algorithmic Aspects
17.2 p-Tree-Depth Coloring
17.2.1 Fraternal Augmentation
17.2.2 Computing the Forest
17.3 Computing and Approximating Tree-Depth
17.4 Counting Homomorphisms to Graphs with Bounded Tree-Depth
17.5 First-Order Cores of Graphs with Bounded Tree-Depth
Exercises
18 Algorithmic Applications
18.1 Introduction
18.2 Truncated Distances
18.3 The Subgraph Isomorphism Problem and Boolean Queries
18.4 The Distance-d Dominating Set Problem
18.5 General First-Order Model Checking
18.6 Counting Versions of Model Checking
18.6.1 Enumerating Isomorphs
18.6.2 Counting Versions
18.6.3 Counting the Number of Solutions of a Boolean Query
Exercises
19 Further Directions
20 Solutions and Hints for some of the Exercises
References
Index