Combinatorics and Graph Theory

Description

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. Preface to the Second Edition Preface to the First Edition Contents Graph Theory Introductory Concepts Graphs and Their Relatives The Basics Special Types of Graphs Distance in Graphs Definitions and a Few Properties Graphs and Matrices Graph Models and Distance Trees Definitions and Examples Properties of Trees Spanning Trees Counting Trees Trails, Circuits, Paths, and Cycles The Bridges of Königsberg Eulerian Trails and Circuits Hamiltonian Paths and Cycles Three Open Problems Planarity Definitions and Examples Euler's Formula and Beyond Regular Polyhedra Kuratowski's Theorem Colorings Definitions Bounds on Chromatic Number The Four Color Problem Chromatic Polynomials Matchings Definitions Hall's Theorem and SDRs The König--Egerváry Theorem Perfect Matchings Ramsey Theory Classical Ramsey Numbers Exact Ramsey Numbers and Bounds Graph Ramsey Theory References Combinatorics Some Essential Problems Binomial Coefficients Multinomial Coefficients The Pigeonhole Principle The Principle of Inclusion and Exclusion Generating Functions Double Decks Counting with Repetition Changing Money Fibonacci Numbers Recurrence Relations Catalan Numbers Pólya's Theory of Counting Permutation Groups Burnside's Lemma The Cycle Index Pólya's Enumeration Formula de Bruijn's Generalization More Numbers Partitions Stirling Cycle Numbers Stirling Set Numbers Bell Numbers Eulerian Numbers Stable Marriage The Gale--Shapley Algorithm Variations on Stable Marriage Combinatorial Geometry Sylvester's Problem Convex Polygons References Infinite Combinatorics and Graphs Pigeons and Trees Ramsey Revisited ZFC Language and Logical Axioms Proper Axioms Axiom of Choice The Return of der König Ordinals, Cardinals, and Many Pigeons Cardinality Ordinals and Cardinals Pigeons Finished Off Incompleteness and Cardinals Gödel's Theorems for PA and ZFC Inaccessible Cardinals A Small Collage of Large Cardinals Weakly Compact Cardinals Infinite Marriage Problems Hall and Hall Countably Many Men Uncountably Many Men Espousable Cardinals Perfect Matchings Finite Combinatorics with Infinite Consequences k-critical Linear Orderings Points of Departure References References Index