Combinatorics Seminar 2018

Speaker: Martin Loebl, Charles University

Date: Mon, Sep 10, 2018

Time: 10:00 - 11:00

Venue: Zhongyuan 212

Title: The Kasteleyn method


I will explain chronologically some basic results of this fascinating subject of mathematics, physics and computer science:

  1. The number $p(G)$ of the perfect matchings of a planar bipartite graph $G$ is a determinant. [Kasteleyn 1961]

  2. If a bipartite graph $G$ has genus $g$ then $p(G)$ is a linear combination of $4^g$ determinants. [conjectured by Kasteleyn in 60's, proved by Galluccio, Loebl 1999; independently by Tesler 2000; Cimasoni, Reshetikhin 2006 interpreted the formula as the Arf-invariant formula]

  3. The number $p(G)$, $G$ bipartite, is also a hyperdeterminant of a 3D matrix。 [Loebl, Rytir, the theory of geometric representations of binary linear codes 2016]

  4. The generating function of the perfect matchings of a bipartite graph can be expressed as a formal (infinite) product by a generalisation of a theorem of Bass. [Loebl, 2018]

  5. The previous two results hold analogously (in dimension 4) for the generating function of codewords of each binary linear code. [Loebl 2018; this substantially generalises the same result for the cycle space of a planar graph by Feynman and Sherman from the beginning of 60's]

Slides: View slides