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.


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

I suggest the following references:

  • 2
    $\begingroup$ Really, thanks a lot Dai. Those are really good references. I will go through them very soon. Thanks again. And yes, enjoy this Christmas and have a very happy new year! $\endgroup$ – Akash Kumar Dec 25 '10 at 23:11
  • $\begingroup$ @arnab and @Akash I'm glad my suggestion helps! Merry Christmas and happy new year to you two! $\endgroup$ – Dai Le Dec 26 '10 at 0:58
  • $\begingroup$ @Dai, this looks very interesting. Which of these three references mentions Berkowitz's algorithm (Pfaffian version)? $\endgroup$ – Michael Soltys Apr 7 '14 at 18:09

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.

  • $\begingroup$ That's awesome! Thanks and happy new year! $\endgroup$ – Dai Le Dec 31 '10 at 19:33
  • $\begingroup$ Whoo...thats great! Totally in tune with what I wanted. Many many thanks (and yes a happy new year) $\endgroup$ – Akash Kumar Jan 1 '11 at 1:50

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.


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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.