Combinatorics and graph theory

There are certain rules that one must abide by in order to create a successful sequel. -- Randy Meeks, from the trailer to Scream 2 While we may not follow the precise rules that Mr. Meeks had in mind for s- cessful sequels, we have made a number of changes to the text in this second edition. In the new edition, we continue to introduce new topics with concrete - amples, we provide complete proofs of almost every result, and we preserve the book'sfriendlystyle andlivelypresentation,interspersingthetextwith occasional jokes and quotations. The rst two chapters, on graph theory and combinatorics, remain largely independent, and may be covered in either order. Chapter 3, on in nite combinatorics and graphs, may also be studied independently, although many readers will want to investigate trees, matchings, and Ramsey theory for nite sets before exploring these topics for in nite sets in the third chapter. Like the rst edition, this text is aimed at upper-division undergraduate students in mathematics, though others will nd much of interest as well. It assumes only familiarity with basic proof techniques, and some experience with matrices and in nite series. The second edition offersmany additionaltopics for use in the classroom or for independentstudy. Chapter 1 includesa new sectioncoveringdistance andrelated notions in graphs, following an expanded introductory section. This new section also introduces the adjacency matrix of a graph, and describes its connection to important features of the graph.

Reviews 1

Choice Review

Harris (Furman Univ.), Hirst (Appalachian State Univ., Boone, NC), and Mossinghoff (Univ. of California, Los Angeles) offer in their first two chapters some of the topics typical of a one-semester undergraduate course in discrete mathematics: graph theory, generating functions, Polya counting, and matching theory. Although many such courses have a computer science orientation, this book is aimed squarely at mathematics majors, especially chapter 3 on infinite combinatorics. Here the reader revisits Ramsey theory and then meets the formal foundations of set theory, ordinals, cardinals, G"odel's theorem, and such exotica as large cardinals. Many mathematics majors simply never take a whole course in logic or in set theory, so even the brief exposure they might pick up here might serve them well when they go on to study topology and algebra. Although other books, notably the sketchier book by George Polya, Robert E. Tarjan, and Donald R. Woods, Notes on Introductory Combinatorics (CH, Jun'84), cover similar material, the clean, outward-looking treatment here justifies this new publication. Recommended. Undergraduates. D. V. Feldman; University of New Hampshire

Preface to the Second Edition	p. vii
Preface to the First Edition	p. ix
1 Graph Theory	p. 1
1.1 Introductory Concepts	p. 2
1.1.1 Graphs and Their Relatives	p. 2
1.1.2 The Basics	p. 5
1.1.3 Special Types of Graphs	p. 10
1.2 Distance in Graphs	p. 17
1.2.1 Definitions and a Few Properties	p. 18
1.2.2 Graphs and Matrices	p. 21
1.2.3 Graph Models and Distance	p. 26
1.3 Trees	p. 30
1.3.1 Definitions and Examples	p. 31
1.3.2 Properties of Trees	p. 34
1.3.3 Spanning Trees	p. 38
1.3.4 Counting Trees	p. 43
1.4 Trails, Circuits, Paths, and Cycles	p. 51
1.4.1 The Bridges of Konigsberg	p. 52
1.4.2 Eulerian Trails and Circuits	p. 55
1.4.3 Hamiltonian Paths and Cycles	p. 60
1.4.4 Three Open Problems	p. 67
1.5 Planarity	p. 73
1.5.1 Definitions and Examples	p. 74
1.5.2 Euler's Formula and Beyond	p. 78
1.5.3 Regular Polyhedra	p. 80
1.5.4 Kuratowski's Theorem	p. 83
1.6 Colorings	p. 85
1.6.1 Definitions	p. 86
1.6.2 Bounds on Chromatic Number	p. 88
1.6.3 The Four Color Problem	p. 93
1.6.4 Chromatic Polynomials	p. 97
1.7 Matchings	p. 101
1.7.1 Definitions	p. 102
1.7.2 Hall's Theorem and SDRs	p. 104
1.7.3 The Konig-Egervary Theorem	p. 109
1.7.4 Perfect Matchings	p. 111
1.8 Ramsey Theory	p. 116
1.8.1 Classical Ramsey Numbers	p. 116
1.8.2 Exact Ramsey Numbers and Bounds	p. 118
1.8.3 Graph Ramsey Theory	p. 124
1.9 References	p. 126
2 Combinatorics	p. 129
2.1 Some Essential Problems	p. 130
2.2 Binomial Coefficients	p. 137
2.3 Multinomial Coefficients	p. 144
2.4 The Pigeonhole Principle	p. 150
2.5 The Principle of Inclusion and Exclusion	p. 156
2.6 Generating Functions	p. 164
2.6.1 Double Decks	p. 166
2.6.2 Counting with Repetition	p. 168
2.6.3 Changing Money	p. 171
2.6.4 Fibonacci Numbers	p. 177
2.6.5 Recurrence Relations	p. 181
2.6.6 Catalan Numbers	p. 185
2.7 Polya's Theory of Counting	p. 190
2.7.1 Permutation Groups	p. 191
2.7.2 Burnside's Lemma	p. 196
2.7.3 The Cycle Index	p. 200
2.7.4 Polya's Enumeration Formula	p. 202
2.7.5 de Bruijn's Generalization	p. 209
2.8 More Numbers	p. 217
2.8.1 Partitions	p. 218
2.8.2 Stirling Cycle Numbers	p. 227
2.8.3 Stirling Set Numbers	p. 231
2.8.4 Bell Numbers	p. 237
2.8.5 Eulerian Numbers	p. 242
2.9 Stable Marriage	p. 248
2.9.1 The Gale-Shapley Algorithm	p. 250
2.9.2 Variations on Stable Marriage	p. 250
2.10 Combinatorial Geometry	p. 264
2.10.1 Sylvester's Problem	p. 265
2.10.2 Convex Polygons	p. 270
2.11 References	p. 277
3 Infinite Combinatorics and Graphs	p. 281
3.1 Pigeons and Trees	p. 282
3.2 Ramsey Revisited	p. 285
3.3 ZFC	p. 290
3.3.1 Language and Logical Axioms	p. 290
3.3.2 Proper Axioms	p. 292
3.3.3 Axiom of Choice	p. 297
3.4 The Return of der Konig	p. 301
3.5 Ordinals, Cardinals, and Many Pigeons	p. 304
3.5.1 Cardinality	p. 304
3.5.2 Ordinals and Cardinals	p. 308
3.5.3 Pigeons Finished Off	p. 312
3.6 Incompleteness and Cardinals	p. 318
3.6.1 Godel's Theorems for PA and ZFC	p. 318
3.6.2 Inaccessible Cardinals	p. 320
3.6.3 A Small Collage of Large Cardinals	p. 322
3.7 Weakly Compact Cardinals	p. 324
3.8 Infinite Marriage Problems	p. 327
3.8.1 Hall and Hall	p. 328
3.8.2 Countably Many Men	p. 330
3.8.3 Uncountably Many Men	p. 336
3.8.4 Espousable Cardinals	p. 340
3.8.5 Perfect Matchings	p. 343
3.9 Finite Combinatorics with Infinite Consequences	p. 344
3.10 k-critical Linear Orderings	p. 347
3.11 Points of Departure	p. 348
3.12 References	p. 352
References	p. 355
Index	p. 369

Available:*

On Order

Summary

Summary

Reviews 1

Choice Review

Table of Contents