A Course in Combinatorics

Citation

van Lint, J. H., & Wilson, R. M. (2001). A Course in Combinatorics (2nd ed.). Cambridge University Press.

Chapter Summary

The second edition has 38 short chapters, preceded by the prefaces to both editions and followed by a bibliography and an index; the print edition runs to about 600 pages. Cambridge describes it as a book on ways of arranging and distributing objects that involves ideas from geometry, algebra and analysis, dealing in a unified manner with graph theory, extremal problems, designs, colorings and codes, and suited to advanced undergraduate or beginning graduate courses. The chapters are titled by topic, and the groupings below follow the order of the table of contents.

Chapters 1–4: Graphs; Trees; Colorings of graphs and Ramsey's theorem; Turán's theorem and extremal graphs

The book opens with basic graph theory and trees, and moves directly to colorings, Ramsey's theorem and the extremal problem of Turán's theorem.

Chapters 5–9: Systems of distinct representatives; Dilworth's theorem and extremal set theory; Flows in networks; De Bruijn sequences; Two (0, 1, ⋆) problems: addressing for graphs and a hash-coding scheme

These chapters cover systems of distinct representatives, Dilworth's theorem and extremal set theory, flows in networks, de Bruijn sequences, and a pair of problems on addressing for graphs and a hash-coding scheme.

Chapters 10–12: The principle of inclusion and exclusion, inversion formulae; Permanents; The Van der Waerden conjecture

The enumeration thread begins with inclusion and exclusion, then turns to permanents and the Van der Waerden conjecture about them.

Chapters 13–15: Elementary counting, Stirling numbers; Recursions and generating functions; Partitions

Counting techniques continue with Stirling numbers, recursions, generating functions and partitions.

Chapters 16–18: (0, 1)-Matrices; Latin squares; Hadamard matrices, Reed–Muller codes

The next block turns to matrices of zeros and ones, Latin squares, and Hadamard matrices, ending in Reed–Muller codes.

Chapters 19–23: Designs; Codes and designs; Strongly regular graphs and partial geometries; Orthogonal Latin squares; Projective and combinatorial geometries

Here the book brings together the structures at its center: designs and their relation to codes, strongly regular graphs and partial geometries, orthogonal Latin squares, and projective and combinatorial geometries.

Chapters 24–26: Gaussian numbers and q-analogues; Lattices and Möbius inversion; Combinatorial designs and projective geometries

This group covers q-analogues, lattices with Möbius inversion, and a return to combinatorial designs and projective geometries.

Chapters 27–31: Difference sets and automorphisms; Difference sets and the group ring; Codes and symmetric designs; Association schemes; (More) algebraic techniques in graph theory

The algebraic block treats difference sets, the group ring, symmetric designs and codes, association schemes and further algebraic methods in graph theory.

Chapters 32–36: Graph connectivity; Planarity and coloring; Whitney Duality; Embeddings of graphs on surfaces; Electrical networks and squared squares

The final graph-theory group deals with connectivity, planarity and coloring, duality, embeddings on surfaces, and electrical networks with the problem of squared squares.

Chapters 37–38: Pólya theory of counting; Baranyai's theorem

The book ends with Pólya's counting theory and Baranyai's theorem.

Key Concepts

Chapters 1–18: Graphs, extremal problems, enumeration

• Ramsey theory and extremal graphs: Ramsey's theorem and Turán's theorem (Chapters 3–4).
• Inclusion and exclusion, permanents: Chapters 10–12.
• Generating functions and partitions: Chapters 13–15.
• Latin squares and Hadamard matrices: Chapters 17–18.

Chapters 19–38: Designs, codes, geometries and further graph theory

• Designs, codes and association schemes: Chapters 19–20, 29 and 30.
• Strongly regular graphs, difference sets and the group ring: Chapters 21, 27 and 28.
• Planarity, duality and graph embeddings: Chapters 33–35.
• Pólya counting and Baranyai's theorem: Chapters 37–38.

Critical Analysis

Strengths

• Breadth in short chapters. Thirty-eight compact chapters give a wide map of the subject, which Cambridge presents as a unified treatment of graph theory, extremal problems, designs, colorings and codes. Dieter Jungnickel, reviewing for Zentralblatt MATH, expected it to become a standard choice among combinatorics texts.
• Elegant proofs and good problems. The Mathematical Gazette calls it a source of elegant proofs and tantalizing examples, and another review quoted by Cambridge notes plenty of interesting problems, concrete examples and useful notes and references.
• Useful at two levels. A review credited to the EMS and quoted by Cambridge recommends it to any student of combinatorics and says that, because of its breadth, it has many new things to tell researchers too.
• Algebraic and geometric ideas together. The table of contents puts codes, designs, finite geometries, the group ring and association schemes in one book, so students see the same structures from several sides.

Limitations

• Demanding. The Mathematical Gazette review says that no one will find the book easy and calls it unashamedly mathematical. The authors' stated audience is advanced undergraduates or beginners in graduate study.
• Not a single narrative. The chapters follow topics rather than a continuous argument, so there is no one thread to follow from Chapter 1 to Chapter 38; readers should expect to choose a route.
• Uneven prerequisites. Early chapters need little beyond a discrete mathematics course, while the algebraic chapters (the group ring, association schemes) draw on abstract algebra that the reader must already have.

Where It Fits in the Course

This is the advanced combinatorics book in a list otherwise made of first courses. Susanna Epp's Discrete Mathematics with Applications, Kenneth Rosen's Discrete Mathematics and Its Applications and Oscar Levin's open textbook teach logic, proof, counting and graphs for readers meeting such mathematics for the first time. Lovász, Pelikán and Vesztergombi's Discrete Mathematics: Elementary and Beyond is a short problem-driven introduction that comes naturally before this one. Graham, Knuth and Patashnik's Concrete Mathematics overlaps on generating functions and recurrences but is oriented toward the analysis of algorithms, whereas van Lint and Wilson lean toward designs, codes and finite geometry.

How to Use This Book

The book suits advanced undergraduates and graduate students who have completed a discrete mathematics course and a first course in linear algebra; some abstract algebra helps for the later chapters.

• Core path: Chapters 1–4 for graphs and extremal problems, Chapters 10–15 for counting, and Chapters 19 and 20 for designs and codes make a self-contained first course.
• Algebraic path: Chapters 21, 23 and 27–30 on strongly regular graphs, geometries, difference sets and association schemes reward readers who know some abstract algebra.
• Graph-theory path: Chapters 32–36 form a second graph-theory course on connectivity, planarity and surfaces.
• Practice: because the chapters are short and independent, assign one chapter per week or read them out of order; work the problems and follow the notes and references the reviewers praise.