The lattice graph's Pfaffian orientations, planar and toroidal

More Info
expand_more

Abstract

In 1961 Kasteleyn solved the dimer problem. With the use of Pfaffans he managed to find a formula to enumerate the number of perfect matchings on a lattice graph. In this thesis we take another look at the methods Kasteleyn used. Besides that, we proof that for an m × n lattice graph on the torus, where m and n are even, there does not exist a Pfaffan orientation. Instead, we prove that for an m × 2 and 2 × n lattice graph on the torus, where m and n are even, there does exist a Pfaffan orientation. For the m × n lattice graph on the torus, where m is even and n odd we present an orientation together with an algorithm with which we can simplify cycles. With this algorithm we prove that our orientation is Pfaffan. We will now describe the Pfaffan orientation. All horizontal edges are aimed to the right, all vertical edges switch between all going down for the first column, then up for the second column and so on. The edges that are on the border all have orientation opposite of the ongoing orientation.

Files

Scriptie_4_.pdf
(pdf | 0.525 Mb)
License info not available