The book first describes connections between some basic problems and technics of combinatorics and statistical physics. The discrete mathematics and physics terminology are related to each other. Using the established connections, some exciting activities in one field are shown from a perspective of the other field. The purpose of the book is to emphasize these interactions as a strong and successful tool. In fact, this attitude has been a strong trend in both research communities recently. It also naturally leads to many open problems, some of which seem to be basic. Hopefully, this book will help making these exciting problems attractive to advanced students and researchers.
Author(s): Martin Loebl
Year: 2009
Language: English
Pages: 198
Cover......Page 1
Discrete Mathematics in Statistical Physics. Introductory Lectures......Page 4
Copyright - ISBN: 9783528032197......Page 5
Preface......Page 8
Contents......Page 10
1.1 Sets, functions, structures ......Page 12
1.2 Algorithms and Complexity ......Page 15
1.3 Generating functions ......Page 17
1.4 Principle of inclusion and exclusion ......Page 18
2.1 Basic notions of graph theory ......Page 24
2.4 Building of a 2-connected graph ......Page 29
2.3 Cycle space and cut space ......Page 31
2.7 A cut of capacity 13 ......Page 36
2.8 Splitting a vertex v ......Page 38
2.6 Factors, matchings, and dimers ......Page 40
2.7 Graph colorings ......Page 47
2.8 Random graphs and Ramsey theory ......Page 49
2.9 Regularity lemma ......Page 50
2.10 Planar graphs ......Page 51
2.16 G is a minor of H ......Page 58
3.1 Minimum spanning tree and greedy algorithm ......Page 62
3.2 Tree isomorphism ......Page 63
3.3 Tree enumeration ......Page 66
3.4 Electrical networks ......Page 68
3.5 Random walks ......Page 73
4 Matroids ......Page 76
4.1 Examples of matroids ......Page 78
4.2 Greedy algorithm ......Page 80
4.3 Circuits ......Page 81
4.5 Duality ......Page 82
4.6 Representable matroids ......Page 84
4.8 Matroid union and min-max theorems ......Page 85
5.1 Topological spaces ......Page 88
5.2 A fatgraph ......Page 93
5.3 Planar curves: rotation ......Page 98
5.8 Rotation: an example ......Page 99
5.5 Coin representations ......Page 102
5.6 Counting fatgraphs: matrix integrals ......Page 104
6.1 Edwards-Anderson Ising model ......Page 112
6.2 Max-Cut for planar graphs ......Page 114
6.3 Van der Waerden’s theorem ......Page 116
6.4 MacWilliams’ theorem ......Page 117
6.5 Phase transition of 2D Ising ......Page 119
6.2 Weights in the hexagonal lattice ......Page 121
6.4 Dual weights ......Page 124
6.8 The Yang-Baxter equation ......Page 127
7.1 The Zeta function of a graph ......Page 130
7.2 Chromatic, Tutte and flow polynomials ......Page 135
7.3 Potts, dichromate and ice ......Page 139
7.4 Ice and ASM ......Page 142
7.5 Some generalizations ......Page 146
7.6 Tutte polynomial of a matroid ......Page 149
8.1 Unknot, unknot, right-handed trefoil, figure eight knot ......Page 152
8.3 Three types of Reidemeister moves for unoriented knots ......Page 153
8.4 Three types of Reidemeister moves for oriented knots ......Page 154
8.5 Three configurations of the skein relation ......Page 155
8.4 The Alexander-Conway polynomial ......Page 157
8.8 A braid and its closure ......Page 159
8.9 R-matrix correspondence ......Page 160
8.8 The Kauffman derivation of the Jones polynomial ......Page 161
8.10 Vassiliev invariants and weight systems ......Page 164
9.1 Pfaffians, dimers, permanents ......Page 168
9.2 Products over aperiodic closed walks ......Page 173
Bibliography......Page 184
List of Figures ......Page 192
2.1 Basic pictures of graph theory ......Page 25
2.2 Examples of trees ......Page 26
2.3 Cycles and 2-connectivity ......Page 28
2.5 More concepts of graph theory ......Page 30
2.6 An example of a twist ......Page 33
2.9 An exchange ......Page 41
2.10 Edmonds-Gallai decomposition ......Page 44
2.11 Bi-transposition ......Page 45
2.12 Greedy may need |V|/2 colors......Page 48
2.13 The same side? ......Page 52
2.14 A planar graph and its dual ......Page 54
2.15 A flip ......Page 55
2.17 A graph of tree width 3 ......Page 59
3.1 Planted tree and its code ......Page 64
3.2 Decoding ......Page 65
3.3 A vertebrate and the corresponding mapping ......Page 67
3.4 Resistors connected in series and in parallel; by symmetry (all resistors are assumed to be the same) V (a) = V (c) and V (d) = V (f) so a is identified with c and d is identified with f ......Page 69
3.5 A_1 = S/A, B_1 = S/B,C_1 = S/C, S = AB + BC + CA......Page 70
4.1 Fano matroid F_7......Page 79
5.1 Adding a handle, a twisted handle and a crosscap ......Page 91
5.4 A fat graph and its medial graph ......Page 94
5.6 The signs of the crossings of C ......Page 95
5.7 w = 134261253456, A = {1, 2, 6} ......Page 96
5.9 A coin representation of the cube ......Page 103
5.10 A half-fatedge ......Page 107
5.12 tr(M^n) and its graphic interpretation as a star fat diagram......Page 108
5.14 A fatgraph interpreted from < tr(M^3)^4 tr(M^2)^3 >......Page 109
6.1 Each vertex is replaced by a path of triangles ......Page 115
6.3 The honeycomb lattice and the associated triangular lattices formed by the geometric duality and by the star- triangle transformation ......Page 122
6.5 A strip of plaquettes ......Page 125
7.1 The Petersen graph ......Page 138
7.3 Ice and 3-face-colorings ......Page 141
7.5 Rotation polynomial weights ......Page 143
7.6 Angles at a corner ......Page 144
7.7 Admissible orientations, allowed arrow coverings, and transition weights ......Page 145
8.7 Relations in the Wirtinger presentation ......Page 156
8.10 Undirected sign ......Page 162
8.12 Figure 8 knot with double points and its chord diagram ......Page 165
8.13 4T relation ......Page 166
9.1 Classes I- III ......Page 176
Index ......Page 194
