Book:John M. Harris/Combinatorics and Graph Theory/Second Edition
Jump to navigation
Jump to search
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
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
- 1.1 Introductory Concepts
- 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