On the theory of Pfaffian orientations. I: Perfect matchings and permanents (Q1277143)

Associate a variable \(x_e\) with each edge of a graph \(G\). For each perfect matching \(P\) of a graph \(G\), let \(x(P)\) denote the product of the variables corresponding to the edges of \(P\). Let \({\mathcal P}(G,x)\) denote the polynomial which equals the sum of \(x(P)\) over all perfect matchings \(P\) of \(G\). Let \(G\) be a graph of order \(2n\) and let \(D\) denote an orientation of \(G\). Let \(A(D)\) be the skew-symmetric matrix whose rows and columns are indexed by the vertices of \(G\), and whose \(u,v\) entry is \(x_{uv}\) when \((u,v)\) is an arc of \(D\), or \(-x_{uv}\) when \((v,u)\) is an arc of \(D\), or 0 when \(u\) and \(v\) are not adjacent in \(G\). The authors prove that if \(G\) is a graph embeddable on an orientable surface of genus \(g\), then \({\mathcal P}(G,x)\) may be expressed as a linear combination of \(4^g\) Pfaffians of matrices \(A(D)\), where each \(D\) is an orientation of \(G\).