<p>You might find <a href="http://www.math.psu.edu/morton/pfaffiancircuits.pdf">this paper</a> 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.</p>

CC BY-SA 2.5
2010-12-31T19:33:00.733Z
That's awesome! Thanks and happy new year!
Dai Le
CC BY-SA 2.5
2011-01-01T01:50:46.707Z
Whoo...thats great! Totally in tune with what I wanted. Many many thanks (and yes a happy new year)
Akash Kumar
CC BY-SA 2.5
2010-12-31T16:44:32.747Z
2010-12-31T16:44:32.747Z
Jason Morton
<p>This should really have been a comment, but for the lack of space I am posting this as an answer.</p>

<p>Thanks for the answers and comments everyone. Recently, I came across another survey by Robin Thomas. You can find it here <a href="http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf" rel="nofollow">http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf</a>. </p>

<p>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. </p>

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

CC BY-SA 2.5
2010-12-30T01:29:43.277Z
2010-12-30T01:29:43.277Z
Akash Kumar
<p>(This is an interesting question for me because I'm also reading about the Pfaffian.) </p>

<p>I suggest the following references:</p>

<p><ul>
<li>Chapter 8 of the awesome book <a href="http://rads.stackoverflow.com/amzn/click/0821847597">Matching Theory</a> by Lovasz and Plummer.</li>
<li>The paper <a href="http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf">Division-Free Algorithms for the Determinant and the Pfaﬃan: Algebraic and Combinatorial Approaches</a> by Rote. This paper relates the Pfaffian with the combinatorial object called <em>alternating closed walk sequence</em> (aka. alternating clow sequence), which gives us a dynamic (division-free) algorithm for computing the Pfaffian.</li>
<li>The paper <a href="http://deepblue.lib.umich.edu/bitstream/2027.42/28397/1/0000172.pdf">Nonintersecting paths, pfaﬃans, and plane partitions</a> 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.,</p>

<blockquote>
  <p>If $A$ is a skew-symmetric matrix, then $\mathsf{pf}(A)^2 = \mathsf{det}(A)$.</li>
  </ul></p>
</blockquote>

CC BY-SA 3.0
2014-04-07T18:09:44.363Z
@Dai, this looks very interesting. Which of these three references mentions Berkowitz's algorithm (Pfaffian version)?
Michael Soltys
CC BY-SA 2.5
2010-12-25T23:11:57.907Z
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!
Akash Kumar
CC BY-SA 2.5
2010-12-26T00:58:30.227Z
@arnab and @Akash I'm glad my suggestion helps! Merry Christmas and happy new year to you two!
Dai Le
CC BY-SA 2.5
2010-12-25T20:15:09.237Z
2010-12-25T21:17:29.703Z
2010-12-25T21:17:29.703Z
Dai Le
<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2010-12-25T21:30:14.947Z
This is known as the "dimer problem." An overview is in section 7.14 of Baxter's "Exactly Solved Models" and also in http://www.math.brown.edu/~rkenyon/papers/de2.pdf Number of dimers can be expressed as Ising model partition function, a worked out example of Ising partition function through Pfaffian is given in http://www.cs.cmu.edu/~jch1/research/presentation/globersonjaakkola.ppt
Yaroslav Bulatov
CC BY-SA 2.5
2010-12-25T23:13:05.177Z
thanks for the comment yaroslav. the cmu example looks helpful
Akash Kumar
CC BY-SA 2.5
2010-12-27T15:30:51.620Z
You may be interested in the brief history of pfaffians from http://www.combinatorics.org/Volume_3/PDF/v3i2r5.pdf
Radu GRIGore
CC BY-SA 2.5
2010-12-30T01:23:16.840Z
Thanks for the comment Radu. I came across another survey by Robin Thomas. You can find it here http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf
Akash Kumar
<reference-request><co.combinatorics><counting-complexity>
Regarding Pfaffian Methods in Counting and Combinatorics
Akash Kumar
# Regarding Pfaffian Methods in Counting and Combinatorics

(Asked by: username_0 on 2010-12-25)

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.

**Tags:** reference-request, co.combinatorics, counting-complexity
> **Comments:**
> **username_1**: This is known as the "dimer problem." An overview is in section 7.14 of Baxter's "Exactly Solved Models" and also in http://www.math.brown.edu/~rkenyon/papers/de2.pdf Number of dimers can be expressed as Ising model partition function, a worked out example of Ising partition function through Pfaffian is given in http://www.cs.cmu.edu/~jch1/research/presentation/globersonjaakkola.ppt  
> **username_0**: thanks for the comment yaroslav. the cmu example looks helpful  
> **username_2**: You may be interested in the brief history of pfaffians from http://www.combinatorics.org/Volume_3/PDF/v3i2r5.pdf  
> **username_0**: Thanks for the comment Radu. I came across another survey by Robin Thomas. You can find it here http://people.math.gatech.edu/~thomas/PAP/pfafsurv.pdf  

---

## 3 answers

### Answer by username_4 on 2010-12-25. Score: 17 | Accepted answer

(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](http://rads.stackoverflow.com/amzn/click/0821847597) by Lovasz and Plummer.
* The paper [Division-Free Algorithms for the Determinant and the Pfaﬃan: Algebraic and Combinatorial Approaches](http://page.mi.fu-berlin.de/rote/Papers/pdf/Division-free+algorithms.pdf) 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, pfaﬃans, and plane partitions](http://deepblue.lib.umich.edu/bitstream/2027.42/28397/1/0000172.pdf) 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)$.

> **Comments:**
> **username_0**: 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!  
> **username_4**: @arnab and @Akash I'm glad my suggestion helps! Merry Christmas and happy new year to you two!  
> **username_5**: @Dai, this looks very interesting. Which of these three references mentions Berkowitz's algorithm (Pfaffian version)?  

---

### Answer by username_3 on 2010-12-31. Score: 12

You might find [this paper](http://www.math.psu.edu/morton/pfaffiancircuits.pdf) 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.

> **Comments:**
> **username_4**: That's awesome! Thanks and happy new year!  
> **username_0**: Whoo...thats great! Totally in tune with what I wanted. Many many thanks (and yes a happy new year)  

---

### Answer by username_0 on 2010-12-30. Score: 6

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.


---

