Combinatorics and Graph Theory

✍ Scribed by Harris, John M

• Publisher: Springer Science+Business Media
• Year: 2008
• Tongue: English
• Leaves: 391
• Series: Undergraduate Texts in Mathematics
• Edition: 2
• Category: Library

✦ Synopsis

This book evolved from several courses in combinatorics and graph theory given at Appalachian State University and UCLA. Chapter 1 focuses on finite graph theory, including trees, planarity, coloring, matchings, and Ramsey theory. Chapter 2 studies combinatorics, including the principle of inclusion and exclusion, generating functions, recurrence relations, Pólya theory, the stable marriage problem, and several important classes of numbers. Chapter 3 presents infinite pigeonhole principles, König's lemma, and Ramsey's theorem, and discusses their connections to axiomatic set theory. The text is written in an enthusiastic and lively style. 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. The text is primarily directed toward upper-division undergraduate students, but lower-division undergraduates with a penchant for proof and graduate students seeking an introduction to these subjects will also find much of interest.

✦ Table of Contents

Preface to the Second Edition......Page 5
Preface to the First Edition......Page 7
Contents......Page 10
1 Graph Theory......Page 13
1.1 Introductory Concepts......Page 14
1.2 Distance in Graphs......Page 29
1.3 Trees......Page 42
1.4 Trails, Circuits, Paths, and Cycles......Page 63
1.5 Planarity......Page 85
1.6 Colorings......Page 97
1.7 Matchings......Page 113
1.8 Ramsey Theory......Page 128
1.9 References......Page 138
2 Combinatorics......Page 140
2.1 Some Essential Problems......Page 141
2.2 Binomial Coefficients......Page 148
2.3 Multinomial Coefficients......Page 155
2.4 The Pigeonhole Principle......Page 161
2.5 The Principle of Inclusion and Exclusion......Page 167
2.6 Generating Functions......Page 175
2.7 Polya's Theory of Counting......Page 201
2.8 More Numbers......Page 228
2.9 Stable Marriage......Page 259
2.10 Combinatorial Geometry......Page 275
2.11 References......Page 288
3 Infinite Combinatorics and Graphs......Page 292
3.1 Pigeons and Trees......Page 293
3.2 Ramsey Revisited......Page 296
3.3 ZFC......Page 301
3.4 The Return of der Konig......Page 312
3.5 Ordinals, Cardinals, and Many Pigeons......Page 315
3.6 Incompleteness and Cardinals......Page 329
3.7 Weakly Compact Cardinals......Page 335
3.8 Infinite Marriage Problems......Page 338
3.9 Finite Combinatorics with Infinite Consequences......Page 355
3.10 k-critical Linear Orderings......Page 358
3.11 Points of Departure......Page 359
3.12 References......Page 363
References......Page 365
Index......Page 379

✦ Subjects

Science;Mathematics;Reference;Nonfiction