Book:John M. Harris/Combinatorics and Graph Theory/Second Edition

John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff: Combinatorics and Graph Theory (2nd Edition)

Published $\text {2008}$, Springer

ISBN 978-0387797106

Subject Matter

• Graph Theory

Contents

Preface to the Second Edition

Preface to the First Edition

1 Graph Theory

1.1 Introductory Concepts

1.1.1 Graphs and Their Relatives

1.1.2 The Basics

1.1.3 Special Types of Graphs

1.2 Distance in Graphs

1.2.1 Definitions and a Few Properties

1.2.2 Graphs and Matrices

1.2.3 Graph Models and Distance

1.3 Trees

1.3.1 Definitions and Examples

1.3.2 Properties of Trees

1.3.3 Spanning Trees

1.3.4 Counting Trees

1.4 Trails, Circuits, Paths, and Cycles

1.4.1 The Bridges of Königsberg

1.4.2 Eulerian Trails and Circuits

1.4.3 Hamiltonian Paths and Cycles

1.4.4 Three Open Problems

1.5 Planarity

1.5.1 Definitions and Examples

1.5.2 Euler's Formula and Beyond

1.5.3 Regular Polyhedra

1.5.4 Kuratowski's Theorem

1.6 Colorings

1.6.1 Definitions

1.6.2 Bounds on Chromatic Number

1.6.3 The Four Color Problem

1.6.4 Chromatic Polynomials

1.7 Matchings

1.7.1 Definitions

1.7.2 Hall's Theorem and SDRs

1.7.3 The König–Egerváry Theorem

1.7.4 Perfect Matchings

1.8 Ramsey Theory

1.8.1 Classical Ramsey Numbers

1.8.2 Exact Ramsey Numbers and Bounds

1.8.3 Graph Ramsey Theory

1.9 References

2 Combinatorics

2.1 Some Essential Problems

2.2 Binomial Coefficients

2.3 Multinomial Coefficients

2.4 The Pigeonhole Principle

2.5 The Principle of Inclusion and Exclusion

2.6 Generating Functions

2.6.1 Double Decks

2.6.2 Counting with Repetition

2.6.3 Changing Money

2.6.4 Fibonacci Numbers

2.6.5 Recurrence Relations

2.6.6 Catalan Numbers

2.7 Pólya's Theory of Counting

2.7.1 Permutation Groups

2.7.2 Burnside's Lemma

2.7.3 The Cycle Index

2.7.4 Pólya's Enumeration Formula

2.7.5 de Bruijn's Generalization

2.8 More Numbers

2.8.1 Partitions

2.8.2 Stirling Cycle Numbers

2.8.3 Stirling Set Numbers

2.8.4 Bell Numbers

2.8.5 Eulerian Numbers

2.9 Stable Marriage

2.9.1 The Gale–Shapley Algorithm

2.9.2 Variations on Stable Marriage

2.10 Combinatorial Geometry

2.10.1 Sylvester's Problem

2.10.2 Convex Polygons

2.11 References

3 Infinite Combinatorics and Graphs

3.1 Pigeons and Trees

3.2 Ramsey Revisited

3.3 ZFC

3.3.1 Language and Logical Axioms

3.3.2 Proper Axioms

3.3.3 Axiom of Choice

3.4 The Return of der König

3.5 Ordinals, Cardinals, and Many Pigeons

3.5.1 Cardinality

3.5.2 Ordinals and Cardinals

3.5.3 Pigeons Finished Off

3.6 Incompleteness and Cardinals

3.6.1 Gödel's Theorems for PA and ZFC

3.6.2 Inaccessible Cardinals

3.6.3 A Small Collage of Large Cardinals

3.7 Weakly Compact Cardinals

3.8 Infinite Marriage Problems

3.8.1 Hall and Hall

3.8.2 Countably Many Men

3.8.3 Uncountably Many Men

3.8.4 Espousable Cardinals

3.8.5 Perfect Matchings

3.9 Finite Combinatorics with Infinite Consequences

3.10 $k$-critical Linear Orderings

3.11 Points of Departure

3.12 References

References

Index