Complexity: Knots, Colourings and Countings (London Mathematical Society Lecture Note Series #186) Book

1	The complexity of enumeration	1
1.1	Basics of complexity	1
1.2	Counting problems	3
1.3	# P-complete problems	6
1.4	Decision easy, counting hard	10
1.5	The Permanent	11
1.6	Hard enumeration problems not thought to be # P-complete	14
1.7	Self-avoiding walks	16
1.8	Toda's theorems	17
2	Knots and links	20
2.2	Tait colourings	23
2.3	Classifying knots	25
2.4	Braids and the braid group	29
2.5	The braid index and the Seifert graph of a link	31
2.6	Enzyme action	35
2.7	The number of knots and links	37
2.8	The topology of polymers	37
3	Colourings, flows and polynomials	42
3.1	The chromatic polynomial	42
3.2	The Whitney-Tutte polynomials	44
3.3	Tutte Grothendieck invariants	46
3.4	Reliability theory	48
3.5	Flows over an Abelian group	49
3.6	Ice models	50
3.7	A catalogue of invariants	51
4	Statistical physics	54
4.1	Percolation processes	54
4.2	The Ising model	58
4.3	Combinatorial interpretations	60
4.4	The Ashkin-Teller-Potts model	62
4.5	The random cluster model	64
4.6	Percolation in the random cluster model	67
5	Link polynomials and the Tait conjectures	71
5.1	The Alexander polynomial	71
5.2	The Jones polynomial and Kauffman bracket	75
5.3	The Homfly polynomial	82
5.4	The Kauffman 2-variable polynomial	84
5.5	The Tait conjectures	87
5.6	Thistlethwaite's nontriviality criterion	90
5.7	Link invariants and statistical mechanics	92
6	Complexity questions	95
6.1	Computations in knot theory	95
6.2	The complexity of the Tutte plane	96
6.3	The complexity of knot polynomials	100
6.4	The complexity of the Ising model	104
6.5	Reliability and other computations	107
7	The complexity of uniqueness and parity	110
7.1	Unique solutions	110
7.2	Unambiguous machines and one-way functions	113
7.3	The Valiant-Vazirani theorem	114
7.4	Hard counting problems not parsimonious with SAT	117
7.5	The curiosity of parity	118
7.6	Toda's theorem on parity	122
8	Approximation and randomisation	124
8.1	Metropolis methods	124
8.2	Approximating to within a ratio	126
8.3	Generating solutions at random	129
8.4	Rapidly mixing Markov chains	130
8.5	Computing the volume of a convex body	132
8.6	Approximations and the Ising model	135
	References	143