+612 9045 4394
 
CHECKOUT
Complexity : Knots, Colourings and Countings - Dominic Welsh

Complexity

Knots, Colourings and Countings

Paperback

Published: 11th October 1993
RRP $85.95
$75.25
12%
OFF
if ordered within
This title is not in stock at the Booktopia Warehouse and needs to be ordered from our supplier.
Click here to read more about delivery expectations.

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.

"...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 Note Series
Audience: Professional
Format: Paperback
Language: English
Number Of Pages: 172
Published: 11th October 1993
Publisher: CAMBRIDGE UNIV PR
Country of Publication: GB
Dimensions (cm): 22.86 x 15.88  x 0.64
Weight (kg): 0.25