5
$\begingroup$

Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to count perfect matchings of the 2-by-$n$ grid?)

I suspect that the answer is "no", since the method seems to implicitly involve the whole matching polynomial (instead of restricting to perfect matchings), and I don't think that the matching polynomials of these graphs are particularly tractable (though I could be wrong about that, especially in the case of the 2-by-$n$ grid).

See Erin E. Emerson Peter Mark Kayll's paper "Another short proof of the Joni-Rota-Godsil integral formula for counting bipartite matchings" available at http://www.oalib.com/paper/2935566#.U34Gzi-2zCo , and references contained therein. Or see the abstract at http://www.oalib.com/paper/2935566#.U34I1y8RLSd .

Improve this question
$\endgroup$
2
  • $\begingroup$ The matching polynomial together with the integral gives the number of perfect matchings in the bipartite complement. Is that what you want? Your question doesn't mention the complement. $\endgroup$
    – Brendan McKay
    Commented May 22, 2014 at 15:02
  • $\begingroup$ You're right, Brendan; thanks for pointing that out. And now I'm even more dubious about the method working for the class of examples I'm interested in, since the complements of these graphs have so many edges. $\endgroup$
    – James Propp
    Commented May 22, 2014 at 15:51

0

Reset to default

You must log in to answer this question.