The lattice graph's Pfaffian orientations, planar and toroidal
D.E. Fredriksz (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Dion Gijswijt – Mentor (TU Delft - Discrete Mathematics and Optimization)
Wolter Groenevelt – Graduation committee member (TU Delft - Analysis)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
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.