This course — taught in Spring 2009 with Martin Loebl — is an introduction to several tools used in discrete enumeration and to some counting techniques, with applications both in graph theory and statistical physics.
It was a lecture at the Department of Applied Mathematics (KAM) of Charles University.

Lecture 1(PDF)

Two dualities of cycle spaces and cut spaces of a graph (linear algebra and geometric). Graphs on surfaces, fat graphs.

Lecture 2(PDF)

Ising problem, cuts and even sets. Max-cut in planar graphs. Enumeration dualities: theorems of van der Waerden and MacWilliams.

Lecture 3

The lecture was replaced by a seminar.

Lecture 4(PDF)

The permanent. Link to perfect matchings. Application of Brègman's theorem and the van der Waerden bound to bound the number of perfect matchings in some classes of graphs (results by Alon & Friedland, and by Alon, Rödl & Rucinsky).

Lecture 5(PDF)

Introduction to the entropy. Basic properties and applications. Radhakrishnan's proof of Brègman's theorem (using entropy).

Lecture 6

Introduction to the transfer matrix method.

Lecture 7(PDF)

Schnyder woods and 3-orientations of plane triangulations: existence, algorithm.

Lecture 8(PDF)

Fullerene molecules: existence of an exponential number of perfect matchings (Kékulé structures).

Lecture 9(PDF)

Planar bridgeless cubic graphs have an exponential number of perfect matchings, proof for cyclically 4-edge-connected planar bridgeless cubic graphs.