Combinatorics and Graph Theory

by Harris, John M.; Hirst, Jeffry L.; Mossinghoff, Michael J.

• ISBN13: 9780387797106
• ISBN10: 0387797106
• Edition: 2nd
• Format: Hardcover
• Copyright: 2008-09-01
• Publisher: Springer Verlag

Summary

"This book covers a wide variety of topics in combinatorics and graph theory. It includes results and problems that cross subdisciplines, emphasizing relationships between different areas of mathematics. In addition, recent results appear in the text, illustrating the fact that mathematics is a living discipline."--BOOK JACKET.

Table of Contents

Preface to the Second Edition	p. vii
Preface to the First Edition	p. ix
Graph Theory	p. 1
Introductory Concepts	p. 2
Graphs and Their Relatives	p. 2
The Basics	p. 5
Special Types of Graphs	p. 10
Distance in Graphs	p. 17
Definitions and a Few Properties	p. 18
Graphs and Matrices	p. 21
Graph Models and Distance	p. 26
Trees	p. 30
Definitions and Examples	p. 31
Properties of Trees	p. 34
Spanning Trees	p. 38
Counting Trees	p. 43
Trails, Circuits, Paths, and Cycles	p. 51
The Bridges of Konigsberg	p. 52
Eulerian Trails and Circuits	p. 55
Hamiltonian Paths and Cycles	p. 60
Three Open Problems	p. 67
Planarity	p. 73
Definitions and Examples	p. 74
Euler's Formula and Beyond	p. 78
Regular Polyhedra	p. 80
Kuratowski's Theorem	p. 83
Colorings	p. 85
Definitions	p. 86
Bounds on Chromatic Number	p. 88
The Four Color Problem	p. 93
Chromatic Polynomials	p. 97
Matchings	p. 101
Definitions	p. 102
Hall's Theorem and SDRs	p. 104
The Konig-Egervary Theorem	p. 109
Perfect Matchings	p. 111
Ramsey Theory	p. 116
Classical Ramsey Numbers	p. 116
Exact Ramsey Numbers and Bounds	p. 118
Graph Ramsey Theory	p. 124
References	p. 126
Combinatorics	p. 129
Some Essential Problems	p. 130
Binomial Coefficients	p. 137
Multinomial Coefficients	p. 144
The Pigeonhole Principle	p. 150
The Principle of Inclusion and Exclusion	p. 156
Generating Functions	p. 164
Double Decks	p. 166
Counting with Repetition	p. 168
Changing Money	p. 171
Fibonacci Numbers	p. 177
Recurrence Relations	p. 181
Catalan Numbers	p. 185
Polya's Theory of Counting	p. 190
Permutation Groups	p. 191
Burnside's Lemma	p. 196
The Cycle Index	p. 200
Polya's Enumeration Formula	p. 202
de Bruijn's Generalization	p. 209
More Numbers	p. 217
Partitions	p. 218
Stirling Cycle Numbers	p. 227
Stirling Set Numbers	p. 231
Bell Numbers	p. 237
Eulerian Numbers	p. 242
Stable Marriage	p. 248
The Gale-Shapley Algorithm	p. 250
Variations on Stable Marriage	p. 250
Combinatorial Geometry	p. 264
Sylvester's Problem	p. 265
Convex Polygons	p. 270
References	p. 277
Infinite Combinatorics and Graphs	p. 281
Pigeons and Trees	p. 282
Ramsey Revisited	p. 285
ZFC	p. 290
Language and Logical Axioms	p. 290
Proper Axioms	p. 292
Axiom of Choice	p. 297
The Return of der Konig	p. 301
Ordinals, Cardinals, and Many Pigeons	p. 304
Cardinality	p. 304
Ordinals and Cardinals	p. 308
Pigeons Finished Off	p. 312
Incompleteness and Cardinals	p. 318
Godel's Theorems for PA and ZFC	p. 318
Inaccessible Cardinals	p. 320
A Small Collage of Large Cardinals	p. 322
Weakly Compact Cardinals	p. 324
Infinite Marriage Problems	p. 327
Hall and Hall	p. 328
Countably Many Men	p. 330
Uncountably Many Men	p. 336
Espousable Cardinals	p. 340
Perfect Matchings	p. 343
Finite Combinatorics with Infinite Consequences	p. 344
k-critical Linear Orderings	p. 347
Points of Departure	p. 348
References	p. 352
References	p. 355
Index	p. 369
Table of Contents provided by Ingram. All Rights Reserved.