Preface	6
	Contents	7
	Chapter 1 Basic concepts	9
	1.1 Sets, functions, structures	9
	1.2 Algorithms and Complexity	11
	1.3 Generating functions	14
	1.4 Principle of inclusion and exclusion	15
	Chapter 2 Introduction to GraphTheory	20
	2.1 Basic notions of graph theory	20
	2.2 Cycles and Euler’s theorem	25
	2.3 Cycle space and cut space	27
	2.4 Flows in directed graphs	32
	2.5 Connectivity	34
	2.6 Factors, matchings, and dimers	36
	2.7 Graph colorings	43
	2.8 Random graphs and Ramsey theory	44
	2.9 Regularity lemma	46
	2.10 Planar graphs	47
	2.11 Tree-width and excluded minors	54
	Chapter 3 Trees and electricalnetworks	57
	3.1 Minimum spanning tree and greedy algorithm	57
	3.2 Tree isomorphism	58
	3.3 Tree enumeration	61
	3.4 Electrical networks	63
	3.5 Random walks	68
	Chapter 4 Matroids	71
	4.1 Examples of matroids	73
	4.2 Greedy algorithm	75
	4.3 Circuits	76
	4.4 Basic operations	77
	4.5 Duality	77
	4.6 Representable matroids	79
	4.7 Matroid intersection	80
	4.8 Matroid union and min-max theorems	80
	Chapter 5 Geometric representationsof graphs	82
	5.1 Topological spaces	82
	5.2 Planar curves: Gauß codes	87
	5.3 Planar curves: rotation	92
	5.4 Convex embeddings	93
	5.5 Coin representations	96
	5.6 Counting fatgraphs: matrix integrals	98
	Chapter 6 Game of dualities	106
	6.1 Edwards-Anderson Ising model	106
	6.2 Max-Cut for planar graphs	108
	6.3 Van der Waerden’s theorem	110
	6.4 MacWilliams’ theorem	111
	6.5 Phase transition of 2D Ising	113
	6.6 Critical temperature of the honeycomb lattice	115
	6.7 Transfer matrix method	118
	6.8 The Yang-Baxter equation	121
	Chapter 7 The zeta function andgraph polynomials	123
	7.1 The Zeta function of a graph	123
	7.2 Chromatic, Tutte and flow polynomials	128
	7.3 Potts, dichromate and ice	132
	7.4 Graph polynomials for embedded graphs	135
	7.5 Some generalizations	138
	7.6 Tutte polynomial of a matroid	142
	Chapter 8 Knots	144
	8.1 Reidemeister moves	145
	8.2 Skein relation	146
	8.3 The knot complement	147
	8.4 The Alexander-Conway polynomial	149
	8.5 Braids and the braid group	151
	8.6 Knot invariants and vertex models	152
	8.7 Alexander-Conway as a vertex model	153
	8.8 The Kauffman derivation of the Jones polynominal	153
	8.9 Jones polynomial as vertex model	156
	8.10 Vassiliev invariants and weight systems	156
	Chapter 9 2D Ising and dimer models	159
	9.1 Pfaffians, dimers, permanents	159
	9.2 Products over aperiodic closed walks	164
	Bibliography	174
	List of Figures	181
	Index	183