A Walk Through Combinatorics: An Introduction to Enumeration And Graph Theory

by Bona, Miklos

• ISBN13: 9789812568854
• ISBN10: 9812568859
• eBook ISBN(s): 9789814365475
• Edition: 2nd
• Format: Hardcover
• Copyright: 2006-10-31
• Publisher: World Scientific Pub Co Inc
• More Book Details
• Purchase Benefits

Summary

This is a textbook for an introductory combinatorics course that can take up one or two semesters. An extensive list of problems, ranging from routine exercises to research questions, is included. In each section, there are also exercises that contain material not explicitly discussed in the preceding text, so as to provide instructors with extra choices if they want to shift the emphasis of their course. Just as with the first edition, the new edition walks the reader through the classic parts of combinatorial enumeration and graph theory, while also discussing some recent progress in the area: on the one hand, providing material that will help students learn the basic techniques, and on the other hand, showing that some questions at the forefront of research are comprehensible and accessible for the talented and hard-working undergraduate. The basic topics discussed are: the twelvefold way, cycles in permutations, the formula of inclusion and exclusion, the notion of graphs and trees, matchings and Eulerian and Hamiltonian cycles. The selected advanced topics are: Ramsey theory, pattern avoidance, the probabilistic method, partially ordered sets, and algorithms and complexity. As the goal of the book is to encourage students to learn more combinatorics, every effort has been made to provide them with a not only useful, but also enjoyable and engaging reading.

Table of Contents

Foreword	p. vii
Preface	p. ix
Acknowledgments	p. xi
Basic Methods
Seven Is More Than Six. The Pigeon-Hole Principle	p. 1
The Basic Pigeon-Hole Principle	p. 1
The Generalized Pigeon-Hole Principle	p. 3
Exercises	p. 9
Supplementary Exercises	p. 11
Solutions to Exercises	p. 12
One Step at a Time. The Method of Mathematical Induction	p. 19
Weak Induction	p. 19
Strong Induction	p. 24
Exercises	p. 26
Supplementary Exercises	p. 28
Solutions to Exercises	p. 29
Enumerative Combinatorics
There Are A Lot Of Them. Elementary Counting Problems	p. 37
Permutations	p. 37
Strings over a Finite Alphabet	p. 40
Choice Problems	p. 43
Exercises	p. 47
Supplementary Exercises	p. 51
Solutions to Exercises	p. 53
No Matter How You Slice It. The Binomial Theorem and Related Identities	p. 65
The Binomial Theorem	p. 65
The Multinomial Theorem	p. 70
When the Exponent Is Not a Positive Integer	p. 72
Exercises	p. 74
Supplementary Exercises	p. 77
Solutions to Exercises	p. 80
Divide and Conquer. Partitions	p. 89
Compositions	p. 89
Set Partitions	p. 91
Integer Partitions	p. 94
Exercises	p. 101
Supplementary Exercises	p. 102
Solutions to Exercises	p. 103
Not So Vicious Cycles. Cycles in Permutations	p. 109
Cycles in Permutations	p. 110
Permutations with Restricted Cycle Structure	p. 115
Exercises	p. 120
Supplementary Exercises	p. 122
Solutions to Exercises	p. 124
You Shall Not Overcount. The Sieve	p. 131
Enumerating The Elements of Intersecting Sets	p. 131
Applications of the Sieve Formula	p. 134
Exercises	p. 138
Supplementary Exercises	p. 139
Solutions to Exercises	p. 139
A Function Is Worth Many Numbers. Generating Functions	p. 145
Ordinary Generating Functions	p. 145
Recurrence Relations and Generating Functions	p. 145
Products of Generating Functions	p. 152
Compositions of Generating Functions	p. 157
Exponential Generating Functions	p. 160
Recurrence Relations and Exponential Generating Functions	p. 160
Products of Exponential Generating Functions	p. 162
Compositions of Exponential Generating Functions	p. 164
Exercises	p. 167
Supplementary Exercises	p. 169
Solutions to Exercises	p. 172
Graph Theory
Dots and Lines. The Origins of Graph Theory	p. 183
The Notion of Graphs. Eulerian Walks	p. 183
Hamiltonian Cycles	p. 188
Directed Graphs	p. 190
The Notion of Isomorphisms	p. 193
Exercises	p. 196
Supplementary Exercises	p. 199
Solutions to Exercises	p. 201
Staying Connected. Trees	p. 209
Minimally Connected Graphs	p. 209
Minimum-weight Spanning Trees. Kruskal's Greedy Algorithm	p. 216
Graphs and Matrices	p. 220
Adjacency Matrices of Graphs	p. 220
The Number of Spanning Trees of a Graph	p. 223
Exercises	p. 228
Supplementary Exercises	p. 230
Solutions to Exercises	p. 232
Finding A Good Match. Coloring and Matching	p. 241
Introduction	p. 241
Bipartite Graphs	p. 243
Matchings in Bipartite Graphs	p. 248
More Than Two Colors	p. 254
Matchings in Graphs That Are Not Bipartite	p. 256
Exercises	p. 259
Supplementary Exercises	p. 261
Solutions to Exercises	p. 262
Do Not Cross. Planar Graphs	p. 269
Euler's Theorem for Planar Graphs	p. 269
Polyhedra	p. 272
Coloring Maps	p. 279
Exercises	p. 281
Supplementary Exercises	p. 282
Solutions to Exercises	p. 283
Horizons
Does It Clique? Ramsey Theory	p. 287
Ramsey Theory for Finite Graphs	p. 287
Generalizations of the Ramsey Theorem	p. 292
Ramsey Theory in Geometry	p. 295
Exercises	p. 298
Supplementary Exercises	p. 299
Solutions to Exercises	p. 301
So Hard To Avoid. Subsequence Conditions on Permutations	p. 307
Pattern Avoidance	p. 307
Stack Sortable Permutations	p. 319
Exercises	p. 330
Supplementary Exercises	p. 331
Solutions to Exercises	p. 333
Who Knows What It Looks Like, But It Exists. The Probabilistic Method	p. 345
The Notion of Probability	p. 345
Non-constructive Proofs	p. 348
Independent Events	p. 351
The Notion of Independence and Bayes' Theorem	p. 351
More Than Two Events	p. 355
Expected Values	p. 356
Linearity of Expectation	p. 357
Existence Proofs Using Expectation	p. 360
Conditional Expectation	p. 361
Exercises	p. 363
Supplementary Exercises	p. 365
Solutions to Exercises	p. 368
At Least Some Order. Partial Orders and Lattices	p. 375
The Notion of Partially Ordered Sets	p. 375
The Mobius Function of a Poset	p. 380
Lattices	p. 388
Exercises	p. 395
Supplementary Exercises	p. 397
Solutions to Exercises	p. 399
The Sooner The Better. Combinatorial Algorithms	p. 407
In Lieu of Definitions	p. 407
The Halting Problem	p. 408
Sorting Algorithms	p. 409
BubbleSort	p. 409
MergeSort	p. 412
Comparing the Growth of Functions	p. 416
Algorithms on Graphs	p. 417
Minimum-cost Spanning Trees, Revisited	p. 417
Finding the Shortest Path	p. 421
Exercises	p. 426
Supplementary Exercises	p. 428
Solutions to Exercises	p. 428
Does Many Mean More Than One? Computational Complexity	p. 433
Turing Machines	p. 433
Complexity Classes	p. 436
The Class P	p. 436
The Class NP	p. 438
NP-complete Problems	p. 445
Other Complexity Classes	p. 450
Exercises	p. 453
Supplementary Exercises	p. 454
Solutions to Exercises	p. 455
Bibliography	p. 461
Index	p. 465
Table of Contents provided by Ingram. All Rights Reserved.