Author(s): Andrew Goodall
Series: lecture notes
Edition: version 2017-04-10
Year: 2017
Language: English
Commentary: Downloaded from https://iuuk.mff.cuni.cz/~andrew/VKKI.pdf . Combines three other sets of notes by the author.
1 The chromatic polynomial 1
1.1 Graph-theoretic preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 The chromatic polynomial and proper colourings . . . . . . . . . . . . . . . 2
1.3 Deletion and contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Subgraph expansions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Some other deletion–contraction invariants. . . . . . . . . . . . . . . . . . . 15
2 Flows and tensions 17
2.1 Orientations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Circuits and cocircuits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3 The incidence matrix of an oriented graph . . . . . . . . . . . . . . . . . . 21
2.4 A-flows and A-tensions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.5 Tensions and colourings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.6 Duality of bases for A-tensions and A-flows . . . . . . . . . . . . . . . . . . 28
2.7 Examples of nowhere-zero flows . . . . . . . . . . . . . . . . . . . . . . . . 29
2.8 The flow polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3 The Tutte polynomial 35
3.1 Deletion-contraction recurrence . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2 Sugraph expansion of the Tutte polynomial . . . . . . . . . . . . . . . . . . 42
3.3 Coefficients. Spanning tree expansion. . . . . . . . . . . . . . . . . . . . . 45
3.4 The Tutte polynomial of a planar graph . . . . . . . . . . . . . . . . . . . 48
3.5 The spanning tree partition of subgraphs. . . . . . . . . . . . . . . . . . . . 50
3.6 The beta invariant. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.7 Computational complexity . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
3.8 The Laplacian and the number of spanning trees . . . . . . . . . . . . . . . 56
3.9 Hamming weight enumerator for tensions and flows . . . . . . . . . . . . . 57
3.10 Bicycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.11 Z 3 -tension-flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4 The Tutte polynomial in statistical physics 64
4.1 Colourings and flows in the ice model . . . . . . . . . . . . . . . . . . . . . 64
4.2 The Potts model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.3 The Fortuin-Kasteleyn random cluster model . . . . . . . . . . . . . . . . . 69
5 Graph homomorphisms 71
5.1 Graph invariants and graph homomorphism profiles . . . . . . . . . . . . . 72
5.2 Homomorphism profiles determining graph invariants . . . . . . . . . . . . 74
5.3 Spectrum and degree sequence by left profiles . . . . . . . . . . . . . . . . 76
6 From graphs to matroids 77
6.1 Cuts, circuits and cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
6.2 Orthogonality of cycles and cutsets . . . . . . . . . . . . . . . . . . . . . . 81
6.3 Graph duality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.4 Matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.5 Dual matroids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.6 Deletion and contraction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7 Connections to knot theory 91
7.1 The medial of a plane graph . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.2 Eulerian tours of digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.3 2-in 2-out digraphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
7.4 Interlace polynomial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
7.5 The Kauffman bracket of a link . . . . . . . . . . . . . . . . . . . . . . . . 109
