Preface

Summary

These lecture notes axe based on a series of lectures which I gave at the Advanced Research Institute of Discrete Applied Mathematics (ARIDAM VI) in June 1991.

The lectures were addressed to an audience of discrete mathematicians and computer scientists. I have tried to make the material understandable to both groups; the result is that there are introductions to topics such as the complexity of enumeration, knots, the Whitney/Tutte polynomials and various models of statistical physics.

The main thrust throughout is towards algorithms, applications and the interrelationship among seemingly diverse problem areas. In many cases I have only given sketches of the main ideas rather than full proofs. However, I have tried to give detailed references. I have assumed some familiarity with the basic concepts of computational complexity and combinatorics, but I have aimed to define anything nonstandard when it is first encountered. My notation in both cases corresponds to standard usage, such as Garey and Johnson (1979) and Bollobás (1979).

Since the lectures I have rewritten the notes to incorporate some of the new developments but the basic material is the essence of what was presented. Much of the work was done when I held a John von Neumann Professorship at the University of Bonn. I am very grateful for the opportunity this offered, and to my friends at the Forschungsinstitut für Diskrete Mathematik, where the facilities and atmosphere make it such a stimulating place to visit.