Graph colouring and the probabilistic method

Cover......Page 1
Series: Algorithms and Combinatorics 23......Page 2
Graph Colouring and the Probabilistic Method......Page 4
Copyright......Page 5
Preface......Page 6
Contents......Page 10
Part I. Preliminaries......Page 16
1.1 The Basic Definitions......Page 18
1.2 Some Classical Results......Page 20
1.3 Fundamental Open Problems......Page 22
1.4 A Point of View......Page 24
1.5 A Useful Technical Lemma......Page 25
1.6 Constrained Colourings and the List Chromatic Number......Page 26
1.7 Intelligent Greedy Colouring......Page 27
Exercises......Page 28
2.1 Finite Probability Spaces......Page 30
2.2 Random Variables and Their Expectations......Page 32
2.3 One Last Definition......Page 34
2.4 The Method of Deferred Decisions......Page 35
Exercises......Page 36
Part II. Basic Probabilistic Tools......Page 40
3. The First Moment Method......Page 42
3.1 2-Colouring Hypergraphs......Page 43
3.2 Triangle-Free Graphs with High Chromatic Number......Page 44
3.3 Bounding the List Chromatic Number as a Functione of the Colouring Number......Page 46
3.3.1 An Open Problem......Page 48
3.4 The Cochromatic Number......Page 49
Exercises......Page 51
4. The Lovasz Local Lemma......Page 54
4.1 Constrained Colourings and the List Chromatic Number......Page 56
Exercises......Page 57
5. The Chernoff Bound......Page 58
5.1 Hajos's Conjecture......Page 59
Exercises......Page 61
Part III. Vertex Partitions......Page 62
6. Hadwiger's Conjecture......Page 64
6.2 Step 2: Finding a Split Minor......Page 65
6.3 Step 3: Finding the Minor......Page 67
Exercises......Page 68
7. A First Glimpse of Total Colouring......Page 70
8. The Strong Chromatic Number......Page 76
Exercises......Page 80
9.1 The Idea......Page 82
9.2 Some Details......Page 85
9.3 The Main Proof......Page 89
Exercises......Page 90
Part IV. A Naive Colouring Procedure......Page 92
10.1 Talagrand's Inequality......Page 94
10.2 Colouring Triangle-Free Graphs......Page 98
10.3 Colouring Sparse Graphs......Page 101
10.4 Strong Edge Colourings......Page 102
Exercises......Page 104
11.1 Azuma's Inequality......Page 106
11.2 A Strengthening of Brooks' Theorem......Page 109
11.3 The Probabilistic Analysis......Page 113
11.4 Constructing the Decomposition......Page 115
Exercises......Page 118
Part V. An Iterative Approach......Page 120
12.1 Introduction......Page 122
12.2.1 The Heart of The Procedure......Page 124
12.2.2 The Finishing Blow......Page 126
12.3 The Main Steps of the Proof......Page 127
12.4 Most of the Details......Page 130
12.5 The Concentration Details......Page 135
Exercises......Page 138
13. Triangle-Free Graphs......Page 140
13.1.1 A Modified Procedure......Page 141
13.1.2 Fluctuating Probabilities......Page 143
13.1.3 A Technical Fiddle......Page 145
13.2.1 Dealing with Large Probabilities......Page 146
13.2.3 The Final Step......Page 147
13.2.4 The Parameters......Page 148
13.3 Expectation and Concentration......Page 151
Exercises......Page 153
14. The List Colouring Conjecture......Page 154
14.1.2 The Local Structure......Page 155
14.1.3 Rates of Change......Page 156
14.1.4 The Preprocessing Step......Page 157
14.2 Choosing Reserve_e......Page 159
14.3 The Expected Value Details......Page 160
14.4 The Concentration Details......Page 164
14.5 The Wrapup......Page 166
14.6 Linear Hypergraphs......Page 167
Exercises......Page 168
Part VI. A Structural Decomposition......Page 170
15.2 The Decomposition......Page 172
15.3 Partitioning the Dense Sets......Page 175
15.4.1 Generalizing Brooks' Theorem......Page 180
15.4.2 Blowing Up a Vertex......Page 181
Exercises......Page 182
16. w,x and D......Page 184
16.1 The Modified Colouring Procedure......Page 186
16.2 An Extension of Talagrand's Inequality......Page 187
16.3 Strongly Non-Adjacent Vertices......Page 188
16.4 Many Repeated Colours......Page 190
16.5 The Proof of Theorem 16.5......Page 194
16.6 Proving the Harder Theorems......Page 196
16.7 Two Proofs......Page 197
Exercises......Page 199
17.1 Introduction......Page 200
17.2 The Procedure......Page 202
17.3 The Analysis of the Procedure......Page 203
17.4 The Final Phase......Page 206
18.1 Introduction......Page 210
18.2.1 Ornery Sets......Page 213
18.2.2 The Output of Phase I......Page 215
18.2.3 A Proof Sketch......Page 216
18.3 Phase II: Colouring the Dense Sets......Page 221
18.3.1 Y_i is Non-Empty......Page 222
18.3.2 Our Distribution is Nearly Uniform......Page 223
18.3.3 Completing the Proof......Page 224
18.4 Phase III: The Temporary Colours......Page 225
18.4.1 Step 1: The Kernels of the Ornery Sets......Page 226
18.4.2 Step 2: The Remaining Temporary Colours......Page 230
18.5 Phase IV - Finishing the Sparse Vertices......Page 231
18.6 The Ornery Set Lemmas......Page 232
Part VII. Sharpening our Tools......Page 234
19. Generalizations of the Local Lemma......Page 236
19.1 Non-Uniform Hypergraph Colouring......Page 237
19.2 More Frugal Colouring......Page 239
19.2.1 Acyclic Edge Colouring......Page 240
19.3 Proofs......Page 241
19.4 The Lopsided Local Lemma......Page 243
Exercises......Page 244
20.1 The Original Inequality......Page 246
20.2 More Versions......Page 249
Exercises......Page 251
Part VIII. Colour Assignment via Fractional Colouring......Page 252
21.1 Fractional Colouring......Page 254
21.2 Finding Large Stable Sets in Triangle-Free Graphs......Page 257
21.3 Fractionally,......Page 259
Exercises......Page 261
22.1 Hard-Core Distributions......Page 262
22.2 Hard-Core Distributions from Fractional Colourings......Page 264
22.3 The Mating Map......Page 267
22.4 An Independence Result......Page 269
22.5 More Independence Results......Page 275
23.1 Assigning the Colours......Page 280
23.1.1 Hard-Core Distributions and Approximate Independence......Page 281
23.2 The Chromatic Index......Page 282
23.3 The List Chromatic Index......Page 285
23.3.1 Analyzing an Iteration......Page 287
23.3.2 Analyzing a Different Procedure......Page 289
23.3.3 One More Tool......Page 292
23.4 Comparing the Procedures......Page 294
23.4.1 Proving Lemma 23.9......Page 297
Part IX. Algorithmic Aspects......Page 300
24.1 The Basic Ideas......Page 302
24.2 An Algorithm......Page 303
24.3 Generalized Tic-Tac-Toe......Page 304
24.4 Proof of Lemma 24.3......Page 306
25. Algorithmic Aspects of the Local Lemma......Page 310
25.1.1 The Basics......Page 311
25.1.2 Further Details......Page 314
25.2 A Different Approach......Page 315
25.3 Applicability of the Technique......Page 316
25.3.1 Further Extensions......Page 318
25.4 Extending the Approach......Page 319
25.4.1 3-Uniform Hypergraphs......Page 320
25.4.2 k-Uniform Hypergraphs with k>=4......Page 323
25.4.3 The General Technique......Page 325
Exercises......Page 327
References......Page 330
Index......Page 338