Complexity Knots, Colourings and Countings [Paperback]

These notes are based on a series of lectures given at the Advanced Research Institute of Discrete Applied Mathematics, Rutgers University.Based on lectures at the Advanced Research Institute of Discrete Applied Mathematics in June 1991, these notes link algorithmic problems arising in knot theory, statistical physics and classical combinatorics for researchers in discrete mathematics, computer science and statistical physics.Based on lectures at the Advanced Research Institute of Discrete Applied Mathematics in June 1991, these notes link algorithmic problems arising in knot theory, statistical physics and classical combinatorics for researchers in discrete mathematics, computer science and statistical physics.The aim of these notes is to link algorithmic problems arising in knot theory with statistical physics and classical combinatorics. Apart from the theory of computational complexity needed to deal with enumeration problems, introductions are given to several of the topics, such as combinatorial knot theory, randomized approximation models, percolation, and random cluster models.1. The complexity of enumeration; 2. Knots and links; 3. Colourings, flows and polynomials; 4. Statistical physics; 5. Link polynomials; 6. Complexity questions; 7. The complexity of uniqueness and parity; 8. Approximation and randomisation; References. ...suitable for advanced graduate students and researchers in complexity theory...The list of references is long and good, and the index is useful. Computing Reviews ...an urbane presentation...of the seemingly disparate threads that will some day be the new math...the author has attained a degree of clarity and readability that few mathematicians today are capable of. Gian-Carlo Rota ...certain to be a valuable reference... Lorenzo Traldi, Mathematical Reviews A clear and up-to-date survey of what's known--and what's still unknown. American Mathematical Monthly