You are here

Applied Combinatorics

Fred S. Roberts and Barry Tesman
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2009
Number of Pages: 
860
Format: 
Hardcover
Edition: 
2
Price: 
99.95
ISBN: 
9781420099829
Category: 
Textbook
BLL Rating: 

The Basic Library List Committee strongly recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Allen Stenger
, on
12/31/2009
]

This is an overwhelmingly complete introductory textbook in combinatorics. It not only covers nearly every topic in the subject, but gives several realistic applications for each topic.

The present book takes a very broad view of combinatorics. It spends about 500 pages on counting problems, which is what most people think of as combinatorics. It also has about 200 pages on existence problems (whether there exist arrangements with certain properties; for example block design problems) and about 150 pages on optimization (such as shortest route problems and the stable marriage problem). These latter two sections deal with techniques that use combinatorial ideas, although usually without explicitly counting things. These sections tend to be very algorithmic, although they typically do not deal with running times and other details as algorithm books do.

Paul Halmos once explained that “Calculus books are bad because there is no such subject as calculus; it is not a subject because it is many subjects.” Is combinatorics a subject, and are combinatorics books bad? I think combinatorics has expanded to the point any reasonably comprehensive text would be horribly fragmented, and that is a problem with the present book. I like this book much better as a reference than as a textbook. The authors state that it is possible to cover the whole book in one year. I believe this, but at the end of the year I think it’s unlikely that the students would retain very much of the hundreds of ideas presented here.

Rummaging through MAA Reviews suggests that all modern introductory texts in combinatorics are at least 450 pages, and most run to 600 or more. The present book has 860 pages and much more breadth than its competitors. I don’t have a good solution for this “combinatorial explosion”. One idea, that would actually work pretty well, is to go back to older, shorter, classic texts such as Ryser’s 1963 Combinatorial Mathematics or Riordan’s 1958 An Introduction to Combinatorial Analysis. These cover most of the important ideas and techniques of combinatorics, but without the myriad variations found in more modern books. Another idea, more promising but more scary, is to build a course based on problems that have a heavy combinatorial flavor, such as those found in Aigner & Ziegler’s Proofs from the BOOK or Iosevich’s A View From the Top. In all of these choices the present book would be valuable as a source of applications and for enrichment reading.


Allen Stenger is a math hobbyist, library propagandist, and retired computer programmer. He volunteers in his spare time at MathNerds.com, a math help site that fosters inquiry learning. His mathematical interests are number theory and classical analysis.

What Is Combinatorics?

The Three Problems of Combinatorics

The History and Applications of Combinatorics

THE BASIC TOOLS OF COMBINATORICS

Basic Counting Rules

The Product Rule

The Sum Rule

Permutations

Complexity of Computation

r-Permutations

Subsets

r-Combinations

Probability

Sampling with Replacement

Occupancy Problems

Multinomial Coefficients

Complete Digest by Enzymes

Permutations with Classes of Indistinguishable Objects Revisited

The Binomial Expansion

Power in Simple Games

Generating Permutations and Combinations

Inversion Distance between Permutations and the Study of Mutations

Good Algorithms

Pigeonhole Principle and Its Generalizations

Introduction to Graph Theory

Fundamental Concepts

Connectedness

Graph Coloring and Its Applications

Chromatic Polynomials

Trees

Applications of Rooted Trees to Searching, Sorting, and Phylogeny Reconstruction

Representing a Graph in the Computer

Ramsey Numbers Revisited

Relations

Relations

Order Relations and Their Variants

Linear Extensions of Partial Orders

Lattices and Boolean Algebras

THE COUNTING PROBLEM

Generating Functions and Their Applications

Examples of Generating Functions

Operating on Generating Functions

Applications to Counting

The Binomial Theorem

Exponential Generating Functions and Generating Functions for Permutations

Probability Generating Functions

The Coleman and Banzhaf Power Indices

Recurrence Relations

Some Examples

The Method of Characteristic Roots

Solving Recurrences Using Generating Functions

Some Recurrences Involving Convolutions

The Principle of Inclusion and Exclusion

The Principle and Some of Its Applications

The Number of Objects Having Exactly m Properties

The Pólya Theory of Counting

Equivalence Relations

Permutation Groups

Burnside’s Lemma

Distinct Colorings

The Cycle Index

Pólya’s Theorem

THE EXISTENCE PROBLEM

Combinatorial Designs

Block Designs

Latin Squares

Finite Fields and Complete Orthogonal Families of Latin Squares

Balanced Incomplete Block Designs

Finite Projective Planes

Coding Theory

Information Transmission

Encoding and Decoding

Error-Correcting Codes

Linear Codes

The Use of Block Designs to Find Error-Correcting Codes

Existence Problems in Graph Theory

Depth-First Search: A Test for Connectedness

The One-Way Street Problem

Eulerian Chains and Paths

Applications of Eulerian Chains and Paths

Hamiltonian Chains and Paths

Applications of Hamiltonian Chains and Paths

COMBINATORIAL OPTIMIZATION

Matching and Covering

Some Matching Problems

Some Existence Results: Bipartite Matching and Systems of Distinct Representatives

The Existence of Perfect Matchings for Arbitrary Graphs

Maximum Matchings and Minimum Coverings

Finding a Maximum Matching

Matching as Many Elements of X as Possible

Maximum-Weight Matching

Stable Matchings

Optimization Problems for Graphs and Networks

Minimum Spanning Trees

The Shortest Route Problem

Network Flows

Minimum-Cost Flow Problems

Appendix: Answers to Selected Exercises

Author Index

Subject Index

References appear at the end of each chapter.