Discrete mathematics in statistical physics : introductory lectures

Preface......Page 6
Contents......Page 7
1.1 Sets, functions, structures......Page 10
1.2 Algorithms and Complexity......Page 13
1.3 Generating functions......Page 15
1.4 Principle of inclusion and exclusion......Page 16
2.1 Basic notions of graph theory......Page 22
2.2 Cycles and Euler’s theorem......Page 27
2.3 Cycle space and cut space......Page 29
2.4 Flows in directed graphs......Page 34
2.5 Connectivity......Page 36
2.6 Factors, matchings, and dimers......Page 38
2.7 Graph colorings......Page 45
2.8 Random graphs and Ramsey theory......Page 47
2.9 Regularity lemma......Page 48
2.10 Planar graphs......Page 49
2.11 Tree-width and excluded minors......Page 56
3.1 Minimum spanning tree and greedy algorithm......Page 60
3.2 Tree isomorphism......Page 61
3.3 Tree enumeration......Page 64
3.4 Electrical networks......Page 66
3.5 Random walks......Page 71
4 Matroids......Page 74
4.1 Examples of matroids......Page 76
4.2 Greedy algorithm......Page 78
4.3 Circuits......Page 79
4.5 Duality......Page 80
4.6 Representable matroids......Page 82
4.8 Matroid union and min-max theorems......Page 83
5.1 Topological spaces......Page 86
5.2 Planar curves: Gauß codes......Page 91
5.3 Planar curves: rotation......Page 96
5.4 Convex embeddings......Page 97
5.5 Coin representations......Page 100
5.6 Counting fatgraphs: matrix integrals......Page 102
6.1 Edwards-Anderson Ising model......Page 110
6.2 Max-Cut for planar graphs......Page 112
6.3 Van der Waerden’s theorem......Page 114
6.4 MacWilliams’ theorem......Page 115
6.5 Phase transition of 2D Ising......Page 117
6.6 Critical temperature of the honeycomb lattice......Page 119
6.7 Transfer matrix method......Page 122
6.8 The Yang-Baxter equation......Page 125
7.1 The Zeta function of a graph......Page 128
7.2 Chromatic, Tutte and flow polynomials......Page 133
7.3 Potts, dichromate and ice......Page 137
7.4 Graph polynomials for embedded graphs......Page 140
7.5 Some generalizations......Page 144
7.6 Tutte polynomial of a matroid......Page 147
8 Knots......Page 150
8.1 Reidemeister moves......Page 151
8.2 Skein relation......Page 152
8.3 The knot complement......Page 153
8.4 The Alexander-Conway polynomial......Page 155
8.5 Braids and the braid group......Page 157
8.6 Knot invariants and vertex models......Page 158
8.8 The Kauffman derivation of the Jones polynomial......Page 159
8.10 Vassiliev invariants and weight systems......Page 162
9.1 Pfaffians, dimers, permanents......Page 166
9.2 Products over aperiodic closed walks......Page 171
Bibliography......Page 182
List of Figures......Page 190
Index......Page 192