A Course in Combinatorics

Cover......Page 1
Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface to the first edition......Page 13
Preface to the 2nd edition......Page 15
1 Graphs......Page 17
References.......Page 26
2 Trees......Page 28
References.......Page 38
3 Colorings of graphs and Ramsey’s theorem......Page 40
Notes.......Page 50
References.......Page 51
4 Turán’s theorem and extremal graphs......Page 53
References.......Page 57
5 Systems of distinct representatives......Page 59
Notes.......Page 67
References.......Page 68
6 Dilworth’s theorem and extremal set theory......Page 69
References.......Page 75
7 Flows in networks......Page 77
References.......Page 85
8 De Bruijn sequences......Page 87
Notes.......Page 91
References.......Page 92
9 Two (0,1,*) problems: addressing for graphs and a hash-coding scheme......Page 93
References.......Page 104
10 The principle of inclusion and exclusion; inversion formulae......Page 105
Notes.......Page 112
References.......Page 113
11 Permanents......Page 114
References.......Page 124
12 The Van der Waerden conjecture......Page 126
References.......Page 134
13 Elementary counting; Stirling numbers......Page 135
Notes.......Page 144
14 Recursions and generating functions......Page 145
Notes.......Page 166
References.......Page 167
15 Partitions......Page 168
Notes.......Page 182
References.......Page 183
16 (0,1)-Matrices......Page 185
References.......Page 197
17 Latin squares......Page 198
References.......Page 213
18 Hadamard matrices, Reed–Muller codes......Page 215
Notes.......Page 229
References.......Page 230
19 Designs......Page 231
Notes.......Page 255
References.......Page 257
20 Codes and designs......Page 260
Notes.......Page 275
References.......Page 276
21 Strongly regular graphs and partial geometries......Page 277
Notes.......Page 295
References.......Page 296
22 Orthogonal Latin squares......Page 299
Notes.......Page 316
References.......Page 317
23 Projective and combinatorial geometries......Page 319
Notes.......Page 339
References.......Page 340
24 Gaussian numbers and q-analogues......Page 341
References.......Page 348
25 Lattices and Möbius inversion......Page 349
References.......Page 365
26 Combinatorial designs and projective geometries......Page 367
Notes.......Page 383
References.......Page 384
27 Diffierence sets and automorphisms......Page 385
Notes.......Page 397
References.......Page 398
28 Diffierence sets and the group ring......Page 399
Notes.......Page 410
References.......Page 411
29 Codes and symmetric designs......Page 412
References.......Page 420
30 Association schemes......Page 421
Notes.......Page 446
References.......Page 447
31 (More) algebraic techniques in graph theory......Page 448
Notes.......Page 465
References.......Page 466
32 Graph connectivity......Page 467
References.......Page 474
33 Planarity and coloring......Page 475
Notes.......Page 486
References.......Page 487
34 Whitney duality......Page 488
References.......Page 506
35 Embeddings of graphs on surfaces......Page 507
References.......Page 521
36 Electrical networks and squared squares......Page 523
References.......Page 536
37 Pólya theory of counting......Page 538
References.......Page 551
38 Baranyai’s theorem......Page 552
Notes.......Page 556
References.......Page 557
Appendix 1 Hints and comments on problems......Page 558
Appendix 2 Formal power series......Page 594
Name Index......Page 600
Subject Index......Page 606