A Course in Combinatorics

Combinatorics, a subject dealing with ways of arranging and distributing objects, involves ideas from geometry, algebra, and analysis. The breadth of the theory is matched by that of its applications, which include topics as diverse as codes, circuit design and algorithm complexity. It has thus become an essential tool in many scientific fields. In this second edition the authors have made the text as comprehensive as possible, dealing in a unified manner with such topics as graph theory, extremal problems, designs, colorings, and codes. The depth and breadth of the coverage make the book a unique guide to the whole of the subject. It is ideal for courses on combinatorical mathematics at the advanced undergraduate or beginning graduate level, and working mathematicians and scientists will also find it a valuable introduction and reference.

Table of Contents

1 Graphs

2 Trees

3 Colorings of graphs and Ramsey’s theorem

4 Turan’s theorem and extremal graphs

5 Systems of distinct representatives

6 Dilworth’s theorem and extremal set theory

7 Flows in networks

8 De Bruijn sequences

9 Two (0,1,*) problems: addressing for graphs and a hash-coding scheme

10 The principle of inclusion and exclusion; inversion formulae

11 Permanents

12 The Van der Waerden conjecture

13 Elementary counting; Stirling numbers

14 Recursions and generating functions

15 Partitions

16 (0, 1 )-Matrices

17 Latin squares

18 Hadamard matrices, Reed- Muller codes

19 Designs

20 Codes and designs

21 Strongly regular graphs and partial geometries

22 Orthogonal Latin squares

23 Projective and combinatorial geometries

24 Gaussian numbers and q-analogues

25 Lattices and Mobius inversion

26 Combinatorial designs and projective geometries

27 Diffierence sets and automorphisms

28 Diffierence sets and the group ring

29 Codes and symmetric designs

30 Association schemes

31 (More) algebraic techniques in graph theory

32 Graph connectivity

33 Planarity and coloring

34 Whitney duality

35 Embeddings of graphs on surfaces

36 Electrical networks and squared squares

37 P6lya theory of counting

38 Baranyai’s theorem

Appendix 1 Hints and comments on problems

Appendix 2 Formal power series

About the Authors

Jacobus Hendricus van Lint was a Dutch mathematician, professor at the Eindhoven University of Technology, of which he was rector magnificus from 1991 till 1996. He gained his Ph.D. from Utrecht University in 1957 under the supervision of Fred van der Blij.

Richard Michael Wilson is a mathematician and a professor emeritus at the California Institute of Technology. Wilson and his PhD supervisor Dijen K. Ray-Chaudhuri, solved Kirkman’s schoolgirl problem in 1968. Wilson is known for his work in combinatorial mathematics, as well as on historical flutes.