Regarding Pfaffian Methods in Counting and Combinatorics

Question

Recently, I was going over an introduction to Holographic Algorithms. I came across some combinatorial objects called Pfaffians. I do not really know much about those at the moment and came across some surprising uses they can be put to.

For instance, I came to know that they can be used to efficiently count the number of perfect matchings in planar graphs. Also, they can be used to count the number of possible tilings of a chessboard using 2*1 tiles. The tiling connection seemed very curious to me and I tried searching for more relevant materials on the web but in most places I merely found just one statement or two about the connection and nothing else.

I just meant to ask if someone could suggest some reference to relevant literature as that would be really great and I am looking forward to study some related materials.

Answer 1

(This is an interesting question for me because I'm also reading about the Pfaffian.)

I suggest the following references:

• Chapter 8 of the awesome book Matching Theory by Lovasz and Plummer.
• The paper Division-Free Algorithms for the Determinant and the Pfaffian: Algebraic and Combinatorial Approaches by Rote. This paper relates the Pfaffian with the combinatorial object called alternating closed walk sequence (aka. alternating clow sequence), which gives us a dynamic (division-free) algorithm for computing the Pfaffian.
• The paper Nonintersecting paths, pfaffians, and plane partitions by Stembridge, which shows how to use the Pfaffian to enumerate configurations in combinatorics. The paper also gives combinatorial proofs of basic identities, e.g.,

  If $A$ is a skew-symmetric matrix, then $\mathsf{pf}(A)^2 = \mathsf{det}(A)$.

Answer 2

You might find this paper on Pfaffian circuits and the references therein interesting; I've meant it to be a self-contained introduction to holographic algorithms as well as exploring what can be done with Pfaffians.

Answer 3

This should really have been a comment, but for the lack of space I am posting this as an answer.

Thanks for the answers and comments everyone. Recently, I came across another survey by Robin Thomas. You can find it here http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf.

Other than this, I would also add one statement about the tiling connection (which was pointed out to me by Prof Dana Randall). If you take the dual lattice, then 2x1 domino tiles are just edges. Therefore, a perfect tiling is precisely a perfect matching in the dual. Then, the theory of Pfaffians can be used to count perfect matchings in planar graphs.

This means that you can just primarily focus on counting perfect matchings in the graph - the rest just follows trivially.

Answer 4

There is also work done by Charles Little, Fischer, McCuaig, Robertson, Seymour and Thomas, Loebl, Galluccio, Tesler, Miranda, Lucchesi, de Carvalho, and Murty (the ones that come to my mind right now.)