The theory of Kasteleyn orientations is a powerful tool for solving optimization
problems for graphs embeddable on a fixed surface. It also can be used to
compute in polynomial time the partition function of some graphical models
(Markov random fields) - most famously, the Ising model on a 2-D grid. The
theory has some remarkable features:

- It is based on counting determinants and other technics of enumeration.

- It was invented by physisists and it is still heavily used in statistical
physics.

- There is an exponential lower bound for its complexity.

The theory of Kasteleyn orientations is also full of attractive puzzles. In my
talk I will explain basic features of the theory and try to get to more recent
results.

Martin Loebl
Department of Applied Mathematics (KAM)
Faculty of Mathematics and Physics
Charles University, Prague