+612 9045 4394
$7.95 Delivery per order to Australia and New Zealand
100% Australian owned
Over a hundred thousand in-stock titles ready to ship
Complexity : Knots, Colourings and Countings - Dominic Welsh


Knots, Colourings and Countings

Paperback Published: 11th October 1993
ISBN: 9780521457408
Number Of Pages: 172

Share This Book:


RRP $85.95
Ships in 10 to 15 business days

Earn 151 Qantas Points
on this Book

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.

Industry Reviews

"...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

The complexity of enumerationp. 1
Basics of complexityp. 1
Counting problemsp. 3
# P-complete problemsp. 6
Decision easy, counting hardp. 10
The Permanentp. 11
Hard enumeration problems not thought to be #P-completep. 14
Self-avoiding walksp. 16
Toda's theoremsp. 17
Additional notesp. 19
Knots and linksp. 20
Introductionp. 20
Tait colouringsp. 23
Classifying knotsp. 25
Braids and the braid groupp. 29
The braid index and the Seifert graph of a linkp. 31
Enzyme actionp. 35
The number of knots and linksp. 37
The topology of polymersp. 37
Additional notesp. 40
Colourings, flows and polynomialsp. 42
The chromatic polynomialp. 42
The Whitney-Tutte polynomialsp. 44
Tutte Grothendieck invariantsp. 46
Reliability theoryp. 48
Flows over an Abelian groupp. 49
Ice modelsp. 50
A catalogue of invariantsp. 51
Additional notesp. 53
Statistical physicsp. 54
Percolation processesp. 54
The Ising modelp. 58
Combinatorial interpretationsp. 60
The Ashkin-Teller-Potts modelp. 62
The random cluster modelp. 64
Percolation in the random cluster modelp. 67
Additional notesp. 70
Link polynomials and the Tait conjecturesp. 71
The Alexander polynomialp. 71
The Jones polynomial and Kauffman bracketp. 75
The Homfly polynomialp. 82
The Kauffman 2-variable polynomialp. 84
The Tait conjecturesp. 87
Thistlethwaite's nontriviality criterionp. 90
Link invariants and statistical mechanicsp. 92
Additional notesp. 94
Complexity questionsp. 95
Computations in knot theoryp. 95
The complexity of the Tutte planep. 96
The complexity of knot polynomialsp. 100
The complexity of the Ising modelp. 104
Reliability and other computationsp. 107
Additional notesp. 109
The complexity of uniqueness and parityp. 110
Unique solutionsp. 110
Unambiguous machines and one-way functionsp. 113
The Valiant-Vazirani theoremp. 114
Hard counting problems not parsimonious with SATp. 117
The curiosity of parityp. 118
Toda's theorem on parityp. 122
Additional notesp. 123
Approximation and randomisationp. 124
Metropolis methodsp. 124
Approximating to within a ratiop. 126
Generating solutions at randomp. 129
Rapidly mixing Markov chainsp. 130
Computing the volume of a convex bodyp. 132
Approximations and the Ising modelp. 135
Some open questionsp. 137
Additional notesp. 141
Referencesp. 143
Table of Contents provided by Syndetics. All Rights Reserved.

ISBN: 9780521457408
ISBN-10: 0521457408
Series: London Mathematical Society Lecture Notes
Audience: Professional
Format: Paperback
Language: English
Number Of Pages: 172
Published: 11th October 1993
Country of Publication: GB
Dimensions (cm): 22.86 x 15.34  x 1.14
Weight (kg): 0.29

Earn 151 Qantas Points
on this Book