The main purpose of this book is to provide help in learning existing techniques in combinatorics. The most effective way of learning such techniques is to solve exercises and problems. This book presents all the material in the form of problems and series of problems (apart from some general comments at the beginning of each chapter). In the second part, a hint is given for each exercise, which contains the main idea necessary for the solution, but allows the reader to practice theechniques by completing the proof. In the third part, a full solution is provided for each problem. This book will be useful to those students who intend to start research in graph theory, combinatorics or their applications, and for those researchers who feel that combinatorial techniques mightelp them with their work in other branches of mathematics, computer science, management science, electrical engineering and so on. For background, only the elements of linear algebra, group theory, probability and calculus are needed.
Author(s): László Lovász
Series: AMS Chelsea Publishing 361
Edition: 2
Publisher: American Mathematical Society
Year: 2007
Language: English
Pages: 642
Cover......Page 1
Title page......Page 4
Dedication......Page 6
Contents......Page 8
Preface to the second edition......Page 10
Preface......Page 12
1.1~1.2......Page 16
§ 1......Page 110
1.3~1.7......Page 17
§ 1. Basic enumeration......Page 162
[Ans]1.4~1.6......Page 163
[Ans]1.7......Page 165
1.8~1.14......Page 18
[Hint]1.8~1.17......Page 111
[Ans]1.8~1.9......Page 166
[Ans]1.10~1.11......Page 169
[Ans]1.12......Page 170
[Ans]1.13~1.14......Page 171
1.15~1.21......Page 19
[Hint]1.18~1.28......Page 112
[Ans]1.15......Page 173
[Ans]1.16......Page 174
[Ans]1.17~1.18......Page 175
[Ans]1.19......Page 176
[Ans]1.20~1.21......Page 177
1.22~1.28......Page 20
[Ans]1.22~1.23......Page 178
[Ans]1.24......Page 179
[Ans]1.25......Page 180
[Ans]1.26......Page 181
[Ans]1.27......Page 182
[Ans]1.28......Page 183
1.29~1.38......Page 21
[Hint]1.29~1.41......Page 113
[Ans]1.29......Page 185
[Ans]1.30......Page 186
[Ans]1.31~1.32......Page 187
[Ans]1.33......Page 188
[Ans]1.34......Page 189
[Ans]1.35~1.36......Page 190
[Ans]1.37~1.38......Page 191
1.39~1.42......Page 22
§ 2......Page 114
[Ans]1.39~1.40......Page 192
[Ans]1.41~1.42......Page 194
[Ans]1.43......Page 197
[Ans]1.44......Page 199
§ 2. The sieve......Page 201
§ 2. The sieve......Page 23
2.1~2.2......Page 24
2.3~2.9......Page 25
[Hint]2.9~2.16......Page 115
[Ans]2.3......Page 202
[Ans]2.4~2.5......Page 203
[Ans]2.6~2.7......Page 204
[Ans]2.8~2.9......Page 205
2.10~2.15......Page 26
[Ans]2.10~2.11......Page 206
[Ans]2.12......Page 207
[Ans]2.13......Page 208
[Ans]2.14......Page 209
[Ans]2.15......Page 210
2.16~2.20......Page 27
[Hint]2.17~2.29......Page 116
[Ans]2.16......Page 211
[Ans]2.17......Page 213
[Ans]2.18......Page 214
[Ans]2.19~2.20......Page 215
2.21~2.28......Page 28
[Ans]2.21......Page 216
[Ans]2.22~2.23......Page 217
[Ans]2.24~2.25......Page 218
[Ans]2.26......Page 219
[Ans]2.27~2.29......Page 220
2.29~2.34......Page 29
§ 3......Page 117
[Ans]2.30......Page 221
[Ans]2.31~2.32......Page 222
[Ans]2.33......Page 223
[Ans]2.34~2.35......Page 224
3.1~3.5......Page 30
[Ans]2.36......Page 225
§ 3. Permutations......Page 226
[Ans]3.2~3.4......Page 227
[Ans]3.5~3.6......Page 228
3.6~3.14......Page 31
[Hint]3.9~3.22......Page 118
[Ans]3.7......Page 229
[Ans]3.8......Page 230
[Ans]3.9......Page 231
[Ans]3.10......Page 232
[Ans]3.11~3.12......Page 233
[Ans]3.13~3.14......Page 234
3.15~3.22......Page 32
[Ans]3.15~3.16......Page 235
[Ans]3.17......Page 236
[Ans]3.18......Page 237
[Ans]3.19~3.21......Page 239
[Ans]3.22......Page 240
3.23~3.28......Page 33
§ 4......Page 119
[Ans]3.23......Page 241
[Ans]3.24~3.25......Page 242
[Ans]3.26~3.27......Page 243
[Ans]3.28......Page 245
§ 4. Two classical enumeration problems in graph theory......Page 34
[Ans]3.29~3.31......Page 246
4.1~4.7......Page 35
§ 4. Two classical enumeration problems in graph theory......Page 247
[Ans]4.2~4.3......Page 248
[Ans]4.4~4.5......Page 249
[Ans]4.6......Page 250
[Ans]4.7......Page 251
4.8~4.12......Page 36
[Ans]4.8......Page 252
[Ans]4.9......Page 253
[Ans]4.10......Page 254
[Ans]4.11~4.12......Page 255
4.13~4.17......Page 37
[Hint]4.7~4.18......Page 120
[Ans]4.13......Page 258
[Ans]4.14......Page 259
[Ans]4.15~4.16......Page 260
[Ans]4.17......Page 261
4.18~4.22......Page 38
[Hint]4.19~4.28......Page 121
[Ans]4.18~4.19......Page 264
[Ans]4.20......Page 265
[Ans]4.21~4.24......Page 267
4.23~4.29......Page 39
[Hint]4.29~4.35......Page 122
[Ans]4.25......Page 268
[Ans]4.26~4.27......Page 270
[Ans]4.28~4.29......Page 271
4.30~4.33......Page 40
[Ans]4.30......Page 276
[Ans]4.31......Page 277
[Ans]4.32~4.33......Page 278
5.1......Page 41
§ 5......Page 123
[Ans]4.34~4.35......Page 281
§ 5. Parity and duality......Page 282
5.2~5.12......Page 42
[Ans]5.2~5.3......Page 283
[Ans]5.4~5.5......Page 284
[Ans]5.6~5.10......Page 285
[Ans]5.11~5.13......Page 286
5.13~5.21......Page 43
[Hint]5.13~5.26......Page 124
[Ans]5.14~5.16......Page 287
[Ans]5.17......Page 288
[Ans]5.18......Page 289
[Ans]5.19~5.20......Page 290
[Ans]5.21~5.22......Page 291
5.22~5.31......Page 44
§ 6......Page 125
[Ans]5.23......Page 292
[Ans]5.24~5.27......Page 293
[Ans]5.28......Page 294
[Ans]5.29~5.31......Page 295
5.32~5.35......Page 45
[Ans]5.32......Page 296
[Ans]5.33......Page 297
[Ans]5.34~5.35......Page 298
§ 6. Connectivity......Page 46
[Ans]5.36~5.37......Page 300
[Ans]5.38......Page 302
6.1~6.8......Page 47
[Hint]6.3~6.19......Page 126
§ 6. Connectivity......Page 304
[Ans]6.3~6.6......Page 305
[Ans]6.7~6.8......Page 306
6.9~6.17......Page 48
[Ans]6.9~6.11......Page 307
[Ans]6.12......Page 308
[Ans]6.13~6.17......Page 309
6.18~6.25......Page 49
[Hint]6.20~6.35......Page 127
[Ans]6.18~6.19......Page 310
[Ans]6.20~6.21......Page 311
[Ans]6.22~6.23......Page 312
[Ans]6.24~6.26......Page 313
6.26~6.32......Page 50
[Ans]6.27~6.29......Page 314
[Ans]6.30~6.32......Page 315
6.33~6.43......Page 51
[Hint]6.36~6.51......Page 128
[Ans]6.33......Page 316
[Ans]6.34~6.37......Page 317
[Ans]6.38~6.39......Page 318
[Ans]6.40~6.42......Page 320
[Ans]6.43~6.45......Page 321
6.44~6.52......Page 52
[Hint]6.52~6.64......Page 129
[Ans]6.46~6.48......Page 322
[Ans]6.49~6.51......Page 323
[Ans]6.52......Page 324
6.53~6.60......Page 53
[Ans]6.53~6.54......Page 325
[Ans]6.55~6.56......Page 326
[Ans]6.57~6.58......Page 327
[Ans]6.59~6.60......Page 328
6.61~6.72......Page 54
[Hint]6.65~6.75......Page 130
[Ans]6.61......Page 330
[Ans]6.62~6.64......Page 331
[Ans]6.65~6.66......Page 332
[Ans]6.67~6.68......Page 333
[Ans]6.69......Page 334
[Ans]6.70~6.72......Page 335
6.73~6.78......Page 55
§ 7......Page 131
[Ans]6.73~6.74......Page 336
[Ans]6.75......Page 337
[Ans]6.76......Page 340
[Ans]6.77......Page 341
§ 7. Factors of graphs......Page 342
7.1~7.5......Page 56
[Ans]7.2......Page 343
[Ans]7.3~7.4......Page 344
[Ans]7.5......Page 345
7.6~7.12......Page 57
[Hint]7.9~7.26......Page 132
[Ans]7.6......Page 346
[Ans]7.7~7.8......Page 347
[Ans]7.9......Page 348
[Ans]7.10~7.11......Page 349
[Ans]7.12~7.13......Page 350
7.13~7.19......Page 58
[Ans]7.14......Page 351
[Ans]7.15~7.16......Page 352
[Ans]7.17......Page 353
[Ans]7.18......Page 354
[Ans]7.19~7.20......Page 355
7.20~7.28......Page 59
[Hint]7.27~7.42......Page 133
[Ans]7.21......Page 356
[Ans]7.22~7.24......Page 357
[Ans]7.25~7.26......Page 359
[Ans]7.27......Page 360
[Ans]7.28......Page 361
7.29~7.33......Page 60
[Ans]7.29~7.30......Page 362
[Ans]7.31......Page 364
[Ans]7.32......Page 365
[Ans]7.33......Page 366
7.34~7.37......Page 61
[Ans]7.34......Page 367
[Ans]7.35......Page 369
[Ans]7.36......Page 370
[Ans]7.37......Page 371
§ 8......Page 134
7.38~7.48......Page 62
[Ans]7.38......Page 372
[Ans]7.39~7.41......Page 373
[Ans]7.42......Page 374
[Ans]7.43~7.45......Page 375
[Ans]7.46......Page 376
§ 8. Independent sets of points......Page 63
[Ans]7.47~7.49......Page 377
[Ans]7.50~7.51......Page 378
[Ans]7.52~7.53......Page 380
8.1~8.8......Page 64
§ 8. Independent sets of points......Page 381
[Ans]8.5......Page 382
[Ans]8.6~8.8......Page 383
8.9~8.21......Page 65
[Hint]8.9~8.27......Page 135
[Ans]8.9~8.10......Page 384
[Ans]8.11~8.13......Page 385
[Ans]8.14~8.15......Page 386
[Ans]8.16~8.19......Page 387
§ 9. Chromatic number......Page 66
[Ans]8.20~8.22......Page 390
[Ans]8.23~8.25......Page 391
[Ans]8.26~8.27......Page 392
9.1~9.9......Page 67
§ 9......Page 136
§ 9. Chromatic number......Page 393
[Ans]9.3~9.6......Page 394
[Ans]9.7......Page 395
[Ans]9.8......Page 396
[Ans]9.9~9.10......Page 397
9.10~9.15......Page 68
[Hint]9.13~9.26......Page 137
[Ans]9.11~9.13......Page 398
[Ans]9.14......Page 399
[Ans]9.15~9.16......Page 400
9.16~9.19......Page 69
[Ans]9.17~9.18......Page 401
[Ans]9.19......Page 402
9.20~9.27......Page 70
[Hint]9.27~9.46......Page 138
[Ans]9.20~9.21......Page 403
[Ans]9.22~9.23......Page 404
[Ans]9.24~9.25......Page 405
[Ans]9.26......Page 406
[Ans]9.27......Page 407
9.28~9.36......Page 71
[Ans]9.28~9.29......Page 408
[Ans]9.30~9.31......Page 409
[Ans]9.32~9.34......Page 410
[Ans]9.35~9.36......Page 411
9.37~9.48......Page 72
§10......Page 139
[Ans]9.37~9.39......Page 412
[Ans]9.40~9.41......Page 413
[Ans]9.42~9.45......Page 414
[Ans]9.46~9.47......Page 415
[Ans]9.48~9.49......Page 417
§10. Extremal problems for graphs......Page 73
[Ans]9.50~9.51......Page 418
[Ans]9.52......Page 419
[Ans]9.53~9.54......Page 420
[Ans]9.55~9.57......Page 422
10.1~10.4......Page 74
[Hint]10.3~10.16......Page 140
§10. Extremal problems for graphs......Page 423
[Ans]10.4......Page 424
10.5~10.15......Page 75
[Ans]10.5......Page 426
[Ans]10.6~10.7......Page 429
[Ans]10.8~10.11......Page 430
[Ans]10.12~10.13......Page 431
[Ans]10.14~10.15......Page 433
10.16~10.24......Page 76
[Hint]10.17~10.28......Page 141
[Ans]10.16......Page 434
[Ans]10.17~10.18......Page 435
[Ans]10.19~10.20......Page 436
[Ans]10.21~10.22......Page 437
[Ans]10.23......Page 438
[Ans]10.24~10.25......Page 439
10.25~10.34......Page 77
[Hint]10.29~10.41......Page 142
[Ans]10.26~10.28......Page 440
[Ans]10.29......Page 441
[Ans]10.30......Page 442
[Ans]10.31~10.32......Page 443
[Ans]10.33~10.34......Page 444
10.35~10.41......Page 78
[Ans]10.35~10.36......Page 445
[Ans]10.37......Page 446
[Ans]10.38......Page 447
[Ans]10.39......Page 448
[Ans]10.40......Page 449
[Ans]10.41......Page 450
§11. Spectra of graphs and random walks......Page 79
§11......Page 143
[Ans]10.42~10.43......Page 451
[Ans]10.44......Page 452
11.1~11.3......Page 80
§11. Spectra of graphs......Page 453
[Ans]11.2......Page 454
[Ans]11.3~11.4......Page 455
11.4~11.12......Page 81
[Hint]11.7~11.21......Page 144
[Ans]11.5......Page 456
[Ans]11.6~11.7......Page 457
[Ans]11.8......Page 458
[Ans]11.9~11.10......Page 459
[Ans]11.11~11.12......Page 460
11.13~11.19......Page 82
[Ans]11.13~11.14......Page 461
[Ans]11.15~11.16......Page 462
[Ans]11.17......Page 463
[Ans]11.18~11.19......Page 464
11.20~11.28......Page 83
[Hint]11.22~11.35......Page 145
[Ans]11.20~11.21......Page 465
[Ans]11.22~11.23......Page 468
[Ans]11.24~11.25......Page 469
[Ans]11.26~11.27......Page 470
[Ans]11.28......Page 471
11.29~11.34......Page 84
[Ans]11.29......Page 472
[Ans]11.30~11.31......Page 473
[Ans]11.32......Page 474
[Ans]11.33......Page 475
[Ans]11.34~11.35......Page 477
11.35~11.44......Page 85
[Hint]11.36~11.45......Page 146
[Ans]11.36......Page 478
[Ans]11.37~11.38......Page 479
[Ans]11.39~11.40......Page 481
[Ans]11.41~11.42......Page 482
[Ans]11.43......Page 483
[Ans]11.44......Page 484
11.45~11.51......Page 86
[Hint]11.46~11.59......Page 147
[Ans]11.45......Page 485
[Ans]11.46~11.48......Page 486
[Ans]11.49~11.51......Page 487
11.52~11.56......Page 87
[Ans]11.52......Page 488
[Ans]11.53......Page 489
[Ans]11.54......Page 490
[Ans]11.55~11.56......Page 491
§12. Automorphisms of graphs......Page 88
[Ans]11.57......Page 492
[Ans]11.58......Page 493
§12. Automorphisms of graphs......Page 494
12.1~12.10......Page 89
§12......Page 148
[Ans]12.2......Page 495
[Ans]12.3~12.5......Page 496
[Ans]12.6......Page 497
[Ans]12.7......Page 498
[Ans]12.8~12.9......Page 500
[Ans]12.10~12.11......Page 501
12.11~12.20......Page 90
§13......Page 149
[Ans]12.12~12.13......Page 502
[Ans]12.14~12.15......Page 504
[Ans]12.16......Page 505
[Ans]12.17......Page 506
[Ans]12.18......Page 507
[Ans]12.19......Page 508
[Ans]12.20......Page 509
§13. Hypergraphs......Page 91
[Ans]12.21......Page 510
[Ans]12.22~12.24......Page 511
[Ans]12.25......Page 512
13.1~13.8......Page 92
[Hint]13.2~13.13......Page 150
§13. Hypergraphs......Page 513
[Ans]13.3~13.4......Page 514
[Ans]13.5~13.6......Page 515
[Ans]13.7~13.8......Page 516
13.9~13.14......Page 93
[Hint]13.14~13.26......Page 151
[Ans]13.9......Page 517
[Ans]13.10......Page 518
[Ans]13.11~13.12......Page 520
[Ans]13.13~13.14......Page 521
13.15~13.23......Page 94
[Ans]13.15......Page 522
[Ans]13.16~13.17......Page 523
[Ans]13.18~13.19......Page 525
[Ans]13.20......Page 526
[Ans]13.21......Page 527
[Ans]13.22......Page 528
[Ans]13.23~13.24......Page 529
13.24~13.30......Page 95
[Hint]13.27~13.39......Page 152
[Ans]13.25~13.26......Page 530
[Ans]13.27~13.28......Page 531
[Ans]13.29......Page 532
[Ans]13.30~13.31......Page 533
13.31~13.37......Page 96
[Ans]13.32......Page 535
[Ans]13.33~13.35......Page 536
[Ans]13.36......Page 538
[Ans]13.37......Page 539
13.38~13.47......Page 97
[Hint]13.40~13.52......Page 153
[Ans]13.38~13.40......Page 540
[Ans]13.41~13.42......Page 541
[Ans]13.43~13.44......Page 542
[Ans]13.45......Page 543
[Ans]13.46......Page 544
[Ans]13.47......Page 545
[Ans]13.48~13.49......Page 546
13.48~13.55......Page 98
§14......Page 154
[Ans]13.50......Page 547
[Ans]13.51......Page 548
[Ans]13.52......Page 549
[Ans]13.53~13.54......Page 550
[Ans]13.55~13.56......Page 551
14.1~14.2......Page 99
§14. Ramsey Theory......Page 553
[Ans]14.2......Page 554
14.3~14.10......Page 100
[Hint]14.10~14.12......Page 155
[Ans]14.3......Page 556
[Ans]14.4......Page 557
[Ans]14.5......Page 558
[Ans]14.6......Page 559
[Ans]14.7......Page 560
[Ans]14.8~14.10......Page 561
14.11~14.16......Page 101
[Hint]14.13~14.25......Page 156
[Ans]14.11~14.12......Page 562
[Ans]14.13~14.14......Page 563
[Ans]14.15~14.16......Page 565
14.17~14.21......Page 102
[Ans]14.17......Page 566
[Ans]14.18......Page 567
[Ans]14.19~14.20......Page 568
[Ans]14.21......Page 569
14.22~14.28......Page 103
§15......Page 157
[Ans]14.22......Page 570
[Ans]14.23......Page 571
[Ans]14.24......Page 572
[Ans]14.25~14.26......Page 573
[Ans]14.27......Page 574
[Ans]14.28......Page 576
§15. Reconstruction......Page 104
[Ans]14.29~14.30......Page 577
[Ans]14.31......Page 579
15.1~15.5......Page 105
[Hint]15.2~15.10......Page 158
§15. Reconstruction......Page 582
[Ans]15.2......Page 584
[Ans]15.3......Page 586
[Ans]15.4~15.5......Page 587
15.6~15.11......Page 106
[Hint]15.11~15.21......Page 159
[Ans]15.6......Page 588
[Ans]15.7......Page 590
[Ans]15.8......Page 591
[Ans]15.9......Page 592
[Ans]15.10~15.11......Page 593
15.12~15.16......Page 107
[Ans]15.12......Page 595
[Ans]15.13......Page 596
[Ans]15.14~15.15......Page 597
[Ans]15.16......Page 598
15.17~15.22......Page 108
[Hint]15.22......Page 160
[Ans]15.17......Page 599
[Ans]15.18~15.19......Page 601
[Ans]15.20......Page 602
[Ans]15.21~15.22......Page 603
Dictionary of the combinatorial phrases and concepts used......Page 606
Notation......Page 622
Index of the abbreviations of textbooks and monographs......Page 626
Subject index......Page 628
Author index......Page 632
Errata......Page 638
Back Cover......Page 642
