On the Theory of Pfaffian Orientations. I. Perfect Matchings and Permanents.

∗Anna Galluccio Istituto di Analisi dei Sistemi ed

Informatica - CNR viale Manzoni 30

00185 Roma

ITALY galluccio@iasi.rm.cnr.it

†Martin Loebl Department of Applied Mathematics Charles University Malostranske n. 25 118 00 Praha 1 CZECH REPUBLIC loebl@kam.ms.mff.cuni.cz

Received May 7, 1998; Accepted October 28, 1998.

Abstract

Kasteleyn stated that the generating function of the perfect matchings of a graph of genus g may be written as a linear combination of 4^{g} Pfaffians. Here we prove this statement. As a consequence we present a combinatorial way to compute the permanent of a square matrix.

Mathematical Reviews Subject Numbers 05B35, 05C15, 05A15

∗Supported by NATO-CNR Fellowship †Supported by DONET, GACR 0194 and GAUK 194

1 Introduction

The theory of Pfaffian orientations of graphs has been introduced by Kasteleyn [7, 6, 5] in early sixties to solve some enumeration problems arising from statistical physics [4, 10]. He proved fundamental results in the planar case and extended his approach to toroidal grids [5, 6, 7]. The case of general toroidal graphs was also considered in an unpublished manuscript by Barahona [1].

In the present paper we extend the method proposed by Kasteleyn and we prove that the generating function of the perfect matchings of a graph of genus g may be obtained as a linear combination of 4^{g} Pfaffians. As a consequence, we provide a new technique to compute permanents of square matrices, which completes the scheme proposed by Pólya in [9].

A graph is a pair G = (V, E) where V is a set of vertices and E is a set of unordered pairs of elements of V, called edges. In this paper we shall consider only graphs with finite number of vertices. If e = xy is an edge then the vertices x, y are called endvertices of e. We associate with each edge e of G a variable x_{e} and we let x = (x_{e} : e ∈ E). For each M ⊂ E, let x(M) denote the product of the variables of the edges of M.

A graph G′ = (V′, E′) is called a subgraph of a graph G = (V, E) if V′ ⊂ V and E′ ⊂ E. A perfect matching of a graph is a set of disjoint edges, whose union equals the set of the vertices.

Let {v_{1}, e_{1}, v_{2}, e_{2}, ..., v_{i}, e_{i}, v_{i+1}, ..., e_{n}, v_{n+1}} be a sequence such that each v_{j} is a vertex of a graph G, each e_{j} is an edge of G and e_{j} = v_{j}v_{j+1}, and v_{i} ≠ v_{j} for i < j except if i = 1 and j = n + 1. If also v_{1} ≠ v_{n+1} then P is called a path of G. If v_{1} = v_{n+1} then P is called a cycle of G. In both cases the length of P equals n. When no confusion arises we shall also denote paths by simply listing their edges, namely P = (e_{1}, e_{2}, …, e_{n}).

A graph G = (V, E) is connected if it has a path between any pair of vertices, and it is 2-connected if the graph G_{v} = (V − {v}, {e ∈ E; v ∉ e}) is connected for each vertex v of G. Each maximal 2-connected subgraph of G is called a 2-connected component of G.

Let AΔB denote the symmetric difference of the sets A and B and let a =^{2} b denote a = b modulo 2.

Let M, N be two perfect matchings of a graph G. Then MΔN consists of vertex disjoint cycles of even length. These cycles are called alternating cycles of M and N.

An orientation of a graph G = (V, E) is a digraph D = (V, A) obtained from G by fixing an orientation of each edge of G, i.e., by ordering the elements of each edge of G. The elements of A are called arcs.

Let C be a cycle of G and let D be an orientation of G. C is said to be clockwise even in D if it has an even number of edges directed in D in agreement with the clockwise traversal. Otherwise C is called clockwise odd.

Definition 1.1 The generating function of the perfect matchings of G is the polynomial P(G, x) which equals the sum of x(P) over all perfect matchings P of G.

Definition 1.2 Let G be a graph and let D be an orientation of G. Let M be a perfect matching of G. For each perfect matching P of G let sgn(D, MΔP) = (−1)^{n} where n is the number of clockwise even alternating cycles of M and P, and let P(D, M) be the sum of sgn(D, MΔP)x(P) over all perfect matchings P of G.

Definition 1.3 Let G = (V, E) be a graph with 2n vertices and D an orientation of G. Denote by A(D) the skew-symmetric matrix with the rows and the columns indexed by V, where a_{vw} = x_{vw} in case (v, w) is an arc of D, a_{vw} = −x_{vw} in case (w, v) is an arc of D, and a_{vw} = 0 otherwise.

The Pfaffian of the skew-symmetric matrix A(D) is defined as

P f(A(D)) = ∑_{P} s^{∗}(P)a_{i_{1}j_{1}} ⋯ a_{i_{n}j_{n}}

where P = {{i_{1}j_{1}}, ⋯, {i_{n}j_{n}}} is a partition of the set {1, …, 2n} into pairs, i_{k} < j_{k} for k = 1, …, n, and s^{∗}(P) equals the sign of the permutation i_{1}j_{1} … i_{n}j_{n} of 12 … (2n).

Each nonzero term of the expansion of the Pfaffian of A(D) equals x(P) or −x(P) where P is a perfect matching of G. If s(D, P) denote the sign of the term x(P), we have that

P f(A(D)) = ∑_{P} s(D, P)x(P).

The following theorem was proved by Kasteleyn [5].

Theorem 1.4 Let G be a graph and D an orientation of G. Let P, M be two perfect matchings of G. Then

s(D, P) = s(D, M)sgn(D, MΔP).

Hence,

P f(A(D)) = ∑_{P} s(D, P)x(P) = s(D, M) ∑_{P} sgn(D, MΔP)x(P) = s(D, M)P(D, M).

The relevance of Pfaffians in our context lies in the fact that, despite their similarity with the permanent, they are polynomial time computable for skew-symmetric matrices (see [2]). In fact, see [7] for a proof.

Theorem 1.5 Let G be a graph and let D be an orientation of G. Then

P f^{2}(A(D)) = det(A(D)).

In [5] Kasteleyn introduced the following notion:

Definition 1.6 A graph G is called Pfaffian if it has a Pfaffian orientation, i.e., an orientation such that all alternating cycles with respect to an arbitrary fixed perfect matching M of G are clockwise odd.

Hence if a graph G has a Pfaffian orientation D then the signs s(D, P) are equal for all perfect matchings P of G and P(G, x)^{2} = P f^{2}(A(D)) = det(A(D)).

An embedding of a graph on a surface is defined in a natural way: the vertices are embedded as points, and each edge is embedded as a continuous non-self-intersecting curve connecting the embeddings of its endvertices. The interiors of the embeddings of the edges are pairwise disjoint and the interiors of the curves embedding edges do not contain points embedding vertices.

A graph is called planar if it may be embedded on the plane. A plane graph is a planar graph together with its planar embedding. The embedding of a plane graph partitions the plane into connected regions called faces. The (unique) unbounded face is called outer face and the bounded faces are called inner faces.

Let G be a plane graph. A subgraph of G consisting of the vertices and the edges embedded on the boundary of a face will also be called a face. If a plane graph is 2-connected then each face is a cycle.

Kasteleyn [5] observed that the planar graphs have a Pfaffian orientation; more specifically, he proved that

Theorem 1.7 Every plane graph has a Pfaffian orientation such that all inner faces are clockwise odd.

Proof. Let G be a plane graph, and let M be its perfect matching. Each alternating cycle of M belongs to a 2-connected component of G.

Observe that G has an orientation so that each inner face of each 2-connected component of G is clockwise odd. Each such face ‘encircles’ no vertex of the corresponding 2-connected component. Let W be a 2-connected component of G. Observe that the orientation we constructed has the property that a cycle C of W is clockwise odd if and only if C encircles an even number of vertices of W. Let C be an alternating cycle of M and let W be a 2-connected component of G which contains C. Then C encircles an even number of vertices of W and hence it is clockwise odd. □

2 Embeddings and Pfaffian orientations

The genus g of a graph G is that of the orientable surface S ⊂ IR^{3} of minimal genus on which G may be embedded. Any orientable surface of genus g has a polygonal representation obtained by cutting the g handles of its space model. In what follows we base our working definition of a surface on this concept.

Definition 2.1 A surface S_{g} of genus g consists of a base B_{0} and 2g bridges B_{j}^{i}, i = 1, ..., g and j = 1, 2, where i) B_{0} is a convex 4g-gon with vertices a_{1}, ..., a_{4g} numbered clockwise;

ii) B_{1}^{i}, i = 1, …, g, is a 4-gon with vertices x_{1}^{i}, x_{2}^{i}, x_{3}^{i}, x_{4}^{i} numbered clockwise. It is glued with B_{0} so that the edge [x_{1}^{i}, x_{2}^{i}] of B_{1}^{i} is identified with the edge [a_{4(i−1)+1}, a_{4(i−1)+2}] of B_{0} and the edge [x_{3}^{i}, x_{4}^{i}] of B_{1}^{i} is identified with the edge [a_{4(i−1)+3}, a_{4(i−1)+4}] of B_{0};

iii) B_{2}^{i}, i = 1, …, g, is a 4-gon with vertices y_{1}^{i}, y_{2}^{i}, y_{3}^{i}, y_{4}^{i} numbered clockwise. It is glued with B_{0} so that the edge [y_{1}^{i}, y_{2}^{i}] of B_{2}^{i} is identified with the edge [a_{4(i−1)+2}, a_{4(i−1)+3}] of B_{0} and the edge [y_{3}^{i}, y_{4}^{i}] of B_{2}^{i} is identified with the edge [a_{4(i−1)+4}, a_{4(i−1)+5(mod4g)}] of B_{0}.

Observe that in Definition 2.1 we denote by [a, b] edges of polygons and not edges of graphs. The usual representation in the space of an orientable surface S of genus g may be then obtained from its polygonal representation S_{g} by the following operation: for each bridge B, glue together the two segments which B shares with the boundary of B_{0}, and delete B.

Definition 2.2 A graph G is called a g-graph if it may be embedded on S_{g} so that all the vertices belong to the base B_{0}, and the embedding of each edge uses at most one bridge. The set of the edges embedded entirely on the base will be denoted by E_{0} and the set of the edges embedded on the bridge B_{j}^{i} will be denoted by E_{j}^{i}, i = 1, …, g, j = 1, 2. If a g-graph G satisfies the following further conditions:

1. the outer face of G_{0} = (V, E_{0}) is a cycle, and it is embedded on the boundary of B_{0},

2. if e ∈ E_{1}^{i} then e is embedded entirely on B_{1}^{i} and one endvertex of e belongs to [x_{1}^{i}, x_{2}^{i}] and the other one belongs to [x_{3}^{i}, x_{4}^{i}]. Similarly, if e ∈ E_{2}^{i} then e is embedded entirely on B_{2}^{i} and one endvertex of e belongs to [y_{1}^{i}, y_{2}^{i}] and the other one belongs to [y_{3}^{i}, y_{4}^{i}].

3. each vertex is incident with at most one edge which does not belong to E_{0},

4. G_{0} has a perfect matching,

then we say that G is a proper g-graph.

Given a proper g-graph G, we denote by C_{0} the cycle which forms the outer face of E_{0}; then, we fix a perfect matching of G_{0} and denote it by M_{0}.

Definition 2.3 Let G be a proper g-graph and let G_{j}^{i} = (V, E_{0} ∪ E_{j}^{i}). If we draw B_{0} ∪ B_{j}^{i} on the plane as follows: B_{0} is unchanged, and the edge [x_{1}^{i}, x_{4}^{i}] ([y_{1}^{i}, y_{4}^{i}] respectively) of B_{j}^{i} is drawn so that it belongs to the external boundary of B_{0} ∪ B_{j}^{i}, we obtain a planar embedding of G_{j}^{i}. This embedding will be called planar projection of E_{j}^{i} outside B_{0}.

Definition 2.4 Let G = (V, E) be a proper g-graph. A Pfaffian orientation D_{0} of G_{0} such that each inner face of each 2-connected component of G_{0} is clockwise odd in D_{0} is called a basic orientation of G_{0}.

Note that a basic orientation always exists for a planar graph by Theorem 1.7.

Definition 2.5 Let G = (V, E) be a proper g-graph and D_{0} a basic orientation of G_{0}. We define the orientation D_{j}^{i} of each G_{j}^{i} as follows: We consider G_{j}^{i} embedded on the plane by the planar projection of E_{j}^{i} outside B_{0} (see Definition 2.3), and complete the basic orientation D_{0} of G_{0} to an orientation of G_{j}^{i} so that each inner face of each 2-connected component of G_{j}^{i} is clockwise odd. The orientation −D_{j}^{i} is defined by reversing the orientation D_{j}^{i} of G_{j}^{i}.

Observe that after fixing a basic orientation D_{0}, the orientation D_{j}^{i} is uniquely determined for each i, j.

Definition 2.6 Let G be a proper g-graph, g ≥ 1. An orientation D of G which equals the basic orientation D_{0} on G_{0} and which equals D_{j}^{i} or −D_{j}^{i} on E_{j}^{i} is called relevant. We define its type r(D) ∈ {+1, −1}^{2g} as follows: For i = 0, …, g − 1 and j = 1, 2, r(D)_{2i+j} equals +1 or −1 according to the sign of D_{j}^{i+1} in D.

Definition 2.7 Let G be a proper g-graph and let A be a subset of its edges. The type of A is a vector t(A) ∈ {0, 1}^{2g} defined as follows: For i = 0, ..., g − 1 and j = 1, 2, we let t(A)_{2i+j} equals the number of edges of A which belong to E_{j}^{i+1}, modulo 2.

Let CR(A) =^{2} ∑_{i=0}^{g−1} t(A)_{2i+1} · t(A)_{2i+2} denote the number of crossings of the embeddings of the edges of A, after making planar projections of E_{j}^{i} for all i, j.

Let BR(A) denote the subset of edges of A which do not belong to E_{0}. For each e ∈ BR(A), let d(e) = 2i + j if e ∈ E_{j}^{i+1}.

We complete the section with a lemma.

Lemma 2.8 Let G be a proper g-graph. Let C_{1}, ..., C_{k} be vertex-disjoint cycles of G and let C denote their union. Then

CR(C) =^{2} ∑_{i=1}^{k} CR(C_{i}).

Proof. Let us embed the cycles C_{1}, ..., C_{k} using the planar projections of E_{j}^{i} outside B_{0} by Definition 2.7. Then CR(C) equals the total number of crossings of C (modulo 2). Now, each cycle C_{l}, l = 1, ..., k is represented as a closed curve in the plane and each pair of cycles C_{i} and C_{j}, i ≠ j, intersects an even number of times. Hence the sum (modulo 2) of the number of crossings between pairs of cycles C_{i} and C_{j}, i ≠ j, is 0 and does not affect CR(C). Each of the remaining crossings is a crossing of some C_{l}, l = 1, ..., k, with itself and the lemma follows. □

3 Perfect matchings

Through this section, the graph G will be a proper g-graph embedded on a fixed surface S_{g}. We also fix a perfect matching M_{0} of G_{0}.

The aim of this section is to prove that, for any perfect matching P, the sgn(D, M_{0} ΔP) depends only on the vectors t(M_{0}ΔP) and r(D).

Given an orientation D of G and an even length cycle C of G, we denote by l_{D}(C) the number of arcs of C directed in agreement with any of the two possible ways of traversing C, modulo 2. For short, any alternating cycle with respect to M_{0} will be simply called an alternating cycle. In order to prove our statement, we consider first the case that M_{0}ΔP consists of exactly one alternating cycle.

Theorem 3.1 Let G be a proper g-graph and let D be a relevant orientation of G. If C is an alternating cycle of G, then

l_{D}(C) =^{2} |BR(C)| − 1 − CR(C) + \frac{1}{2} ∑_{e∈BR(C)}(r(D)_{d(e)} + 1).

Proof. We assume without loss of generality that G = C ∪ C_{0} ∪ M_{0}, where C_{0} is the outer face of G_{0} and M_{0} is the fixed perfect matching of G_{0}. Let D_{0} be the basic orientation of G_{0}. Claim 1. If C intersects at most one of E_{1}^{i}, E_{2}^{i}, for each i = 1, ..., g, then

l_{D}(C) =^{2} |BR(C)| − 1 + \frac{1}{2} ∑_{e∈BR(C)}(r(D)_{d(e)} + 1).

A cycle C satisfying the properties of Claim 1 may be embedded without crossings using the planar projection of each E_{j}^{i} outside B_{0}. Hence l_{D}(C) = 1 if and only if |{e ∈ BR(C) : r(D)_{d(e)} = −1}| =^{2} 0. End of Claim 1.

The proof is by induction on |BR(C)|. The case |BR(C)| = 0 is proved by Claim 1. By induction we assume that

l_{W} (C′) =^{2} |BR(C′)| − 1 − CR(C′) + \frac{1}{2} ∑_{e∈BR(C′)}(r(W)_{d(e)} + 1)

for any alternating cycle C′ of a proper g-graph H, with relevant orientation W, such that |BR(C′)| < |BR(C)|.

We distinguish two cases.

Case 1. There exists a bridge B = B_{j}^{i} containing more than one edge of C. Let e = u_{1}u_{2} and f = v_{1}v_{2} be two edges of C ∩ E_{j}^{i} which see each other on B, i.e., there is no other edge of C drawn between them on B. Without loss of generality, let e be nearer to the edge [a_{2(i−1)+j}, a_{2(i−1)+j+3}] of B = B_{j}^{i} than f and let u_{1}, v_{1} and u_{2}, v_{2} belong to the edge [a_{2(i−1)+j}, a_{2(i−1)+j+1}] and [a_{2(i−1)+j+2}, a_{2(i−1)+j+3}], respectively. Since e, f do not belong to E_{0}, they are not edges of M_{0} ⊂ E_{0}.

Let R_{i} be the subpath of C_{0} from u_{i} to v_{i}, i = 1, 2, and let R be the cycle of G consisting of (R_{1}, f, R_{2}, e). By the choice of e, f, the cycle R is the boundary of a face of the planar projection of G_{j}^{i} = (V, E_{0} ∪ E_{j}^{i}) outside B_{0}. Observe that l_{W} (R) = 1 for each relevant orientation W of G, since R contains two edges embedded outside B_{0}.

Let us introduce a new edge h (not belonging to G), between the endvertices of e, f such that one of two cycles H̄_{1}, H̄_{2} formed by h and C and containing h is alternating. Without loss of generality, let h have u_{1} as an endvertex. Hence we have that h = u_{1}v_{1} or h = u_{1}v_{2}.

We may assume without loss of generality that H̄_{2} is alternating. Hence H̄_{1} contains both e, f. Note that H̄_{1} consists of an even number of edges. We denote by h_{1}, h_{2} the two arcs with the same endvertices as h, directed oppositely. Let D′ = D ∪ {h_{1}, h_{2}}. Let H_{i} be the subdigraph of D′ which is the orientation of H̄_{i} using h_{i}, i = 1, 2. Observe that l_{D}(C) = l_{D′}(H_{1}) + l_{D′}(H_{2}).

Subcase 1.1: h_{1} = u_{1}v_{1}.

We adjust the boundary of B_{0} by replacing {R_{1}} with h_{1}, h_{2}. Observe that CR(C) =^{2} CR(H_{1}) + CR(H_{2}): attention should be drawn to the question of how crossings of C with itself are manifested as crossings of H_{1} or H_{2}, when all E_{j}^{i} are projected outside of B_{0} (see Definition 2.3). If two edges of C cross and they are not separated in C by the endvertices of h_{1}, then that crossing counts as a crossing with in H_{1} or H_{2}. We must therefore consider the parity of the number of crossings of C where the crossed edges are separated in C by the endvertices of h_{1}. These crossings are counted as crossings of H_{1} with H_{2}. If the number of such crossings of C is odd, then there must be an additional crossing of H_{1} with H_{2}, since the total number of crossings of H_{1} with H_{2} must be even. Since h_{1} and h_{2} do not cross, this additional crossing must occur at an endvertex of h_{1}. It is easy to see that in the present case there is no such crossing, and so, there are an even number of crossings of C where the crossed edges are separated in C by the ends of h. The required congruence therefore follows in this case. We construct now two digraphs D_{1}, D_{2} as follows:

- D_{1} is obtained from D−{e, f} by adding new vertices u′_{1}, v′_{1} of degree 2, incident with new arcs e′, f′, h′_{1}. The arcs e′, f′, h′_{1} are obtained from e, f, h_{1} by replacing u_{1} by u′_{1} and v_{1} by v′_{1}. We adjust the boundary of B_{0} by replacing {R_{2}} with {e′, f′, h′_{1}}. Finally we add h′_{1} to M_{0}. Let H′_{1} be the cycle of D_{1} obtained from H_{1} by replacing e, f, h_{1} by e′, f′, h′_{1}. Then l_{D_{1}}(H′_{1}) = l_{D′}(H_{1}) and CR(H′_{1}) =^{2} CR(H_{1});

- D_{2} is obtained from D−{e, f} by adding arc h_{2}. We remind that h_{2} is embedded on the adjusted B_{0} parallel to R_{1}. Let H′_{2} = H_{2}. Then l_{D_{2}}(H′_{2}) = l_{D′}(H_{2}) and CR(H′_{2}) =^{2} CR(H_{2}).

We remind that l_{D}(R) = 1. Hence, exactly one of h_{i} is oriented so that both cycles it makes with R are clockwise odd. Let it be h_{2}. Then D_{2} is a relevant orientation and D_{1} becomes relevant after reversing the orientation of h′_{1}: this digraph, obtained from D_{1} by reversing the orientation of h′_{1}, we denote by D_{1}^{∗}, and its subdigraph corresponding to H′_{1} we denote by H_{1}^{∗}. Then, l_{D_{1}^{∗}}(H_{1}^{∗}) =^{2} l_{D_{1}}(H′_{1}) + 1.

Note that both D_{2} and D_{1}^{∗} are relevant orientations of proper g-graphs, H′_{2} is an alternating cycle of D_{2}, H_{1}^{∗} is an alternating cycle of D_{1}^{∗} and CR(H_{1}^{∗}) < CR(C) and CR(H′_{2}) < CR(C). Hence, by the induction assumption, we have that:

l_{D}(C) =^{2} l_{D′}(H_{1}) + l_{D′}(H_{2}) =^{2} l_{D_{1}}(H′_{1}) + l_{D_{2}}(H′_{2}) =^{2} l_{D_{1}^{∗}}(H_{1}^{∗}) + 1 + l_{D_{2}}(H′_{2}) =^{2}

|BR(H_{1}^{∗})| − 1 − CR(H_{1}^{∗}) + \frac{1}{2} ∑_{p∈BR(H_{1}^{∗})}(r(D_{1}^{∗})_{d(p)} + 1)+

|BR(H′_{2})| − 1 − CR(H′_{2}) + \frac{1}{2} ∑_{p∈BR(H′_{2})}(r(D_{2})_{d(p)} + 1) + 1.

Now, the theorem follows by observing that |BR(C)| =^{2} |BR(C − {e, f})| =^{2} |BR(H_{1}^{∗})| + |BR(H′_{2})| − 2, CR(C) =^{2} CR(H_{1}^{∗}) + CR(H′_{2}) and r(D_{1}^{∗})_{d(p)}, r(D_{2})_{d(p)} and r(D)_{d(p)} coincide for any p ∈ BR(C) − {e, f}. Hence,

l_{D}(C) =^{2} |BR(C)| − 1 − CR(C) + \frac{1}{2} ∑_{p∈BR(C)}(r(D)_{d(p)} + 1).

(End of Subcase 1.1)

Subcase 1.2: h_{1} = u_{1}v_{2}.

Let h_{1} and h_{2} be embedded on the bridge B. Observe that CR(C) =^{2} CR(H_{1}) + CR(H_{2}) + 1: attention again should be drawn to the question of how crossings of C with itself are manifested as crossings of H_{1} or H_{2}, when all E_{j}^{i} are projected outside of B_{0} (see Definition 2.3). To see this clearly, we introduce some notation. Let A be a subset of arcs of H_{1} and B a subset of arcs of H_{2}. We denote by CR(A × B) the number of crossings between arcs of A and B, mod 2. We also denote by cr(i, j) the number of crossings of arcs of H_{i} ∩ C with h_{j}. Hence, we have:

CR(H_{1}) =^{2} CR(H_{1} ∩ C) + cr(1, 1),
CR(H_{2}) =^{2} CR(H_{2} ∩ C) + cr(2, 2),
CR(C) =^{2} CR(H_{1} ∩ C) + CR(H_{2} ∩ C) + CR((H_{1} ∩ C) × (H_{2} ∩ C)),
CR(H_{1} × H_{2}) =^{2} 0,

and

∑_{i,j=1}^{2} cr(i, j) =^{2} 0

since each arc which crosses h_{1} crosses also h_{2}.

Hence it remains to show that

CR(H_{1} × H_{2}) =^{2} CR((H_{1} ∩ C) × (H_{2} ∩ C)) + cr(1, 2) + cr(2, 1) + 1 :

this follows since in this case one additional crossing between H_{1} and H_{2} must occur at an endvertex of h. The required congruence follows.

We construct two digraphs D_{1}, D_{2} as follows:

- D_{1} is obtained from D − {e, f} by adding a new arc h′_{1} between v_{1} and the endvertex u_{2} of e. If l_{D′}(fh_{1}e) = 1 then we let h′_{1} = (v_{1}, u_{2}). If l_{D′}(fh_{1}e) = 0 then we let h′_{1} = (u_{2}, v_{1}).

We consider h′_{1} embedded on the bridge B. Let H′_{1} be obtained from H_{1} by replacing {f, h_{1}, e} by h′_{1}. We have l_{D′}(H_{1}) = l_{D_{1}}(H′_{1}) and CR(H_{1}) = CR(H′_{1}).

- D_{2} is obtained from D −{e, f} by adding the arc h_{2}. We consider h_{2} embedded on the bridge B. We let H_{2} = H′_{2}. Thus again we have l_{D′}(H_{2}) = l_{D_{2}}(H′_{2}) and CR(H_{2}) = CR(H′_{2}).

We remind that l_{D}(R) = 1 and thus exactly one of h_{i} is oriented so that both cycles it makes with R are clockwise odd. Let it be h_{2}. Let R_{3} be the subpath of C_{0} from v_{1} to v_{2} such that (e, R_{1}, R_{3}, R_{2}) is a cycle. We have l_{D_{1}}(h′_{1}, R_{3}, R_{2}) =^{2} l_{D′}(e, h_{1}, f, R_{3}, R_{2}) =^{2} l_{D′}(f, R_{3}) + l_{D′}(e, h_{1}, R_{2}).

We show now that both D_{1} and D_{2} are relevant orientations with r(D_{1}) = r(D_{2}) = r(D). We only need to show that h′_{1} and h_{2} are correctly oriented in D_{1} and D_{2}. This follows easily for D_{2}, since both cycles h_{2} makes with R are clockwise odd.

For D_{1} we distinguish two cases. First, let r(D)_{2(i−1)+j} = 1. In this case we have l_{D′}(f, R_{3}) = 1 and l_{D′}(e, h_{2}, R_{2}) = 1. Hence l_{D′}(e, h_{1}, R_{2}) = 0. It follows that l_{D_{1}}(h′_{1}, R_{3}, R_{2}) = 1 and D_{1} is relevant with r(D_{1}) = r(D). Secondly, let r(D)_{2(i−1)+j} = −1. In this case we have l_{D′}(f, R_{3}) = 0 and l_{D′}(e, h_{2}, R_{2}) = 1. Hence l_{D′}(e, h_{1}, R_{2}) = 0. It follows that l_{D_{1}}(h′_{1}, R_{3}, R_{2}) = 0 and D_{1} is relevant with r(D_{1}) = r(D).

Hence, D_{i} is a relevant orientation of a proper g-graph, H′_{i} is an alternating cycle of D_{i} and |BR(H′_{i})| < |BR(C)|, for i = 1, 2, and, by the induction hypothesis, we have that:

l_{D}(C) =^{2} l_{D′}(H_{1}) + l_{D′}(H_{2}) =^{2} l_{D_{1}}(H′_{1}) + l_{D_{2}}(H′_{2}) =^{2}

|BR(H′_{1})| − 1 − CR(H′_{1}) + \frac{1}{2} ∑_{p∈BR(H′_{1})}(r(D_{1})_{d(p)} + 1) + \frac{1}{2}(r(D_{1})_{d(h_{1})} + 1)+

|BR(H′_{2})| − 1 − CR(H′_{2}) + \frac{1}{2} ∑_{p∈BR(H′_{2})}(r(D_{2})_{d(p)} + 1) + \frac{1}{2}(r(D_{2})_{d(h_{2})} + 1).

The theorem follows by observing that |BR(C)| =^{2} |BR(C −{e, f})| =^{2} |BR(H′_{1})|+ |BR(H′_{2})| − 2, CR(C) + 1 =^{2} CR(H′_{1}) + CR(H′_{2}) and r(D_{1}) = r(D_{2}) = r(D).

(End of Subcase 1.2) End of Case 1

Case 2. There exists i such that C contains exactly one edge from both E_{1}^{i} and E_{2}^{i}. Let e ∈ E_{1}^{i} and f ∈ E_{2}^{i} and let C_{1} and C_{2} be two paths such that C = (C_{1}, e, C_{2}, f). The endvertices of e, f belong to C_{0}. Let us assume that along the boundary of B_{0} from a_{4(i−1)+1} to a_{4i+1}, the endvertices of e, f appear in the order v_{1}, u_{1}, v_{2}, u_{2} where e = u_{1}u_{2} and f = v_{1}v_{2}.

Let R_{1}, R_{2} be the two disjoint subpaths of the segment of C_{0} between a_{4(i−1)+1} and a_{4i+1}, which cover the endvertices of e, f. Note that R_{1}, R_{2} contain no other vertex of G incident with an edge out of E_{0}, by the choice of i. Let R denote the cycle (R_{1}, e, R_{2}, f) and let R_{3} denote the segment of C_{0} between u_{1} and v_{2}.

Let us introduce a new edge h (not belonging to G), between endvertices of e, f such that one of two cycles Ī_{1}, Ī_{2} formed by h and C and containing h is alternating.

Without loss of generality let h have u_{1} as an endvertex. Hence we have that h = u_{1}v_{1} or h = u_{1}v_{2}. We may also assume without loss of generality that Ī_{2} is alternating. Hence Ī_{1} contains both e, f. Note that Ī_{1} consists of an even number of edges.

We denote by h_{1}, h_{2} the two arcs with the same endvertices as h, directed oppositely. Let D′ = D ∪ {h_{1}, h_{2}}. Let I_{i} be the subdigraph of D′ which is the orientation of Ī_{i} using h_{i}, i = 1, 2. Observe that l_{D}(C) = l_{D′}(I_{1}) + l_{D′}(I_{2}).

Again we distinguish two subcases.

Subcase 2.1: h_{1} = u_{1}v_{1}.

In this case h forms a cycle with R_{1}.

As in Subcase 1.1, we extend B_{0} along R_{1} and consider h_{1}, h_{2} as embedded on the extended B_{0}.

Observe that CR(C) =^{2} CR(I_{1}) + CR(I_{2}): attention should be drawn to the question of how crossings of C with itself are manifested as crossings of I_{1} or I_{2}, when all E_{j}^{i} are projected outside of B_{0} (see Definition 2.3). In this case, the arguments are identical to those used in the proof of Subcase 1.1, and we omit them.

We construct two digraphs D_{1}, D_{2} as follows:

- D_{1} is obtained from D−{e, f} by adding new vertices u′_{1}, v′_{1} of degree 2, incident with new arcs e′, f′, h′_{1}. The arcs e′f′, h′_{1} are obtained from e, f, h_{1} by replacing u_{1} by u′_{1} and v_{1} by v′_{1}. We extend B_{0} along R_{2} and we embed the path (e′, f′, h′_{1}) on the extended B_{0}. Finally we add h′_{1} to M_{0}. Let I′_{1} be the cycle of D_{1} obtained from I_{1} by replacing e, f, g_{1} by e′, f′, g′_{1}. We have l_{D′}(I_{1}) = l_{D_{1}}(I′_{1}) and CR(I_{1}) − 1 =^{2} CR(I′_{1}).

- D_{2} is obtained from D −{e, f} by adding the arc h_{2}. We consider h_{2} embedded on the extended B_{0} along R_{1}. We let I′_{2} = I_{2}. Hence, l_{D′}(I_{2}) = l_{D_{2}}(I′_{2}) and CR(I_{2}) =^{2} CR(I′_{2}).

Hence, for i = 1, 2, D_{i} is an orientation of a proper g-graph and I′_{i} is an alternating cycle of D_{i}. Moreover |BR(I′_{i})| < |BR(C)|.

Let us assume without loss of generality that h_{2} is directed so that the cycle l_{D′}(R_{1}, h_{2}) = 1. Hence D_{2} is a relevant orientation with r(D_{2}) = r(D).

We show now that D_{1} is a relevant orientation with r(D) = r(D_{1}) if and only if r(D)_{d(e)} = r(D)_{d(f)}. We first prove that if r(D)_{d(e)} = r(D)_{d(f)} = 1 then D_{1} is a relevant orientation.

In this case it suffices to show that l_{D_{1}}(R_{2}, f′, h′_{1}, e′) =^{2} 1. We have l_{D_{1}}(h′_{1}, f′, R_{3}) =^{2} l_{D′}(h_{1}, f, R_{3}) =^{2} l_{D′}(h_{2}, f, R_{3})+1 =^{2} l_{D_{2}}(h_{2}, f, R_{3})+1 =^{2} 0, since r(D_{2})_{d(f)} = r(D)d(f) = 1, and thus, l_{D_{2}}(h_{2}, f, R_{3}) = 1.

Moreover l_{D_{1}}(R_{2}, R_{3}, e′) = l_{D′}(R_{2}, R_{3}, e) = 1, since r(D)_{d(e)} = 1 and D is a relevant orientation. Replacing f′h′_{1} for R_{3} gives what we claimed.

Similarly, we can prove that if r(D)_{d(e)} = r(D)_{d(f)} = −1 then again l_{D_{1}}(R_{2}, f′, h′_{1}, e′) = 1, and so, D_{1} is a relevant orientation.

On the other hand, if r(D)_{d(e)} ≠ r(D)_{d(f)} then D_{1} is obtained from a relevant orientation by reversing one arc, and so, it is not relevant.

Summarizing, if r(D)_{d(e)} = r(D)_{d(f)} then D_{1} is a relevant orientation with r(D) = r(D_{1}), and if r(D)_{d(e)} ≠ r(D)_{d(f)} then D_{1} becomes relevant after reversing the orientation of h′_{1}: this digraph, obtained from D_{1} by reversing the orientation of h′_{1}, we denote by D_{1}^{∗}, and its subdigraph corresponding to H′_{1} we denote by H_{1}^{∗}. Then l_{D_{1}^{∗}}(I′_{1}) =^{2} l_{D_{1}}(I′_{1}) + 1.

Using the induction assumption of 3.1 for D^{∗}, I_{1}^{∗}, D_{1}, I′_{1} and D_{2}, I′_{2} we get:

l_{D}(C) =^{2} l_{D′}(I_{1}) + l_{D′}(I_{2}) =^{2} l_{D_{1}}(I′_{1}) + l_{D_{2}}(I′_{2}) =^{2}

|BR(C)|−4−CR(C)+1+ \frac{1}{2} ∑_{p∈BR(C)−\{e,f\}}(r(D)_{d(p)}+1)+ \frac{1}{2}(r(D)_{d(e)}−1+r(D)_{d(f)}−1) =^{2}

|BR(C)| − 1 − CR(C) + \frac{1}{2} ∑_{p∈BR(C)}(r(D)_{d(p)} + 1).

(End of Subcase 2.1)

Subcase 2.2: h = u_{1}v_{2}.

In this case h forms a cycle with R_{3}. We extend B_{0} along R_{3} and consider h_{1}, h_{2} embedded on the extended B_{0}.

Observe that CR(C) =^{2} CR(I_{1})+CR(I_{2}):attention should be drawn to the question of how crossings of C with itself are manifested as crossings of I_{1} or I_{2}, when all E_{j}^{i} are projected outside of B_{0} (see Definition 2.3). In this case, the arguments are identical to those used in the proof of Subcase 1.1 and Subcase 2.1, and we omit them.

We construct two digraphs D_{1}, D_{2} as follows:

- D_{1} is obtained from D−{e, f} by adding new vertices u′_{1}, v′_{2} of degree 2, incident with new arcs e′, f′, h′_{1}. The arcs e′, f′, h′_{1} are obtained from e, f, h_{1} by replacing u_{1} by u′_{1} and v_{2} by v′_{2}. We extend B_{0} along R_{1}R_{3}R_{2} and we embed e′, f′, h′_{1} on the extended B_{0}. Finally we add h′_{1} to M_{0}. Let I′_{1} be the cycle of D_{1} obtained from I_{1} by replacing e, f, h_{1} by e′, f′, h′_{1}. We have that l_{D′}(I_{1}) =^{2} l_{D_{1}}(I′_{1}) and CR(I′_{1}) =^{2} CR(I_{1}) − 1.

- D_{2} is obtained from D − {e, f, } by adding arc h_{2}. We again extend B_{0} along R_{3} and consider h_{2} embedded on the extended B_{0}. We let I′_{2} = I_{2}. Hence, l_{D′}(I_{2}) =^{2} l_{D_{2}}(I′_{2}) and CR(I′_{2}) =^{2} CR(I_{2}).

Hence for i = 1, 2, D_{i} is an orientation of a proper g-graph and I′_{i} is an alternating cycle of D_{i}. Moreover |BR(I′_{i})| < |BR(C)|.

Let us assume without loss of generality that h_{2} is directed so that l(R_{3}, h_{2}) = 1. Hence D_{2} is a relevant orientation with r(D_{2}) = r(D).

As in Subcase 2.1, we shall show that D_{1} is a relevant orientation if and only if r(D)_{d(e)} = r(D)_{d(f)}: It again suffices to consider the case that r(D)_{d(e)} = r(D)_{d(f)} = 1. In this case it suffices to show that l_{D_{1}}(R_{2}, R_{3}, R_{1}, f′, h′_{1}, e′) = 1. In fact, we have l_{D_{2}}(R_{1}, f, h_{2}) = 1 since r(D_{d(f)}) = 1 and D_{2} is a relevant orientation. Hence l_{D_{1}}(R_{1}, f′, h′_{1}) = 0. Moreover l_{D_{1}}(R_{2}, R_{3}, e′) =^{2} l_{D}(R_{2}, R_{3}, e) = 1 since r(D)_{d(e)} = 1. Hence l_{D_{1}}(R_{2}, R_{3}, R_{1}, f′, h′_{1}, e′) = 1.

Summarizing, if r(D)_{d(e)} = r(D)_{d(f)} then D_{1} is a relevant orientation with r(D) = r(D_{1}), and if r(D)_{d(e)} ≠ r(D)_{d(f)} then D_{1} becomes relevant after reversing the orientation of h′_{1}.

The proof then proceeds analogously as in Subcase 2.1. (End of Subcase 2.2)

End of Case 2

It is not difficult to see that the two cases complete the proof. □

Next we show that a statement analogous to that of Theorem 3.1 holds for the set of the alternating cycles of M_{0}ΔP as well.

Theorem 3.2 Let G be a proper g-graph and let D be a relevant orientation of G. Let P be a perfect matching of G. Then

sgn(D, M_{0}ΔP) = (−1)^{q},

where

q =^{2} |BR(M_{0}ΔP)| − CR(M_{0}ΔP) + \frac{1}{2} ∑_{e∈BR(M_{0}ΔP)}(r(D)_{d(e)} + 1).

Proof. Let C_{1}, ..., C_{k} be the alternating cycles of M_{0}ΔP. We have that sgn(D, M_{0}ΔP) = (−1)^{q}, where q =^{2} l(C_{1}) + ... + l(C_{k}) − k.

Using Theorem 3.1 for C_{1}, ..., C_{k}, it remains to show that:

CR(M_{0}ΔP) =^{2} ∑_{j=1}^{k} CR(C_{j}),

but this holds by Lemma 2.8 and the theorem follows. □

Corollary 3.3 Let G be a proper 1-graph and D a relevant orientation of G. Let C be a set of disjoint alternating cycles of M_{0}. Then:

1. If r(D) = (1, 1) then sgn(D, C) = 1 if and only if t(C) ∈ {(0, 0), (0, 1), (1, 0)}.

2. If r(D) = (1, −1) then sgn(D, C) = 1 if and only if t(C) ∈ {(0, 0), (1, 1), (1, 0)}.

3. If r(D) = (−1, 1) then sgn(D, C) = 1 if and only if t(C) ∈ {(0, 0), (0, 1), (1, 1)}.

4. If r(D) = (−1, −1) then sgn(D, C) = 1 if and only if t(C) = (0, 0).

Definition 3.4 Let G be a proper g-graph and D a relevant orientation of G. Let r(D) = (r_{1}, ..., r_{2g}). We let c(r(D)) equal to the product of c_{i}, i = 0, ..., g − 1, where c_{i} = c(r_{2i+1}, r_{2i+2}) and c(1, 1) = c(1, −1) = c(−1, 1) = 1/2 and c(−1, −1) = −1/2.

Observe that c(r(D)) = (−1)^{n}2^{−g}, where n = |{i; r_{2i+1} = r_{2i+2} = −1}|.

Corollary 3.5 Let G be a proper 1-graph. Let D_{1}, D_{2}, D_{3}, D_{4} be the relevant orientations of G. Then

P(G, x) = ∑_{i=1}^{4} c(r(D_{i}))P(D_{i}, M_{0}).

A result analogous to Corollary 3.5 holds for all proper g-graphs, g > 1. In order to deduce it we start with another corollary of Theorem 3.2.

Corollary 3.6 Let G be a proper g-graph and D a relevant orientation of G. Let P be a perfect matching of G. Then sgn(D, M_{0}ΔP) is a function of r(D) and t(M_{0}ΔP) only. Let us denote this function by σ(r(D), t(M_{0}ΔP)).

Lemma 3.7 Let r = (r_{1}, …, r_{2g}) and t = (t_{1}, …, t_{2g}) be 2g-dimensional vectors. Let r(j) = (r_{2j+1}, r_{2j+2}) and t(j) = (t_{2j+1}, t_{2j+2}), j = 0, …, g − 1. Then

σ(r, t) = ∏_{j=0}^{g−1} σ(r(j), t(j)).

Proof. By Corollary 3.6, we have that sgn(D, C) = sgn(D′, C′) if and only if r(D) = r(D′) and t(C) = t(C′). This implies that we can restrict ourselves to consider the following case: G = C_{0} ∪ M_{0} ∪ C is a proper g-graph, D is a relevant orientation of G such that r(D) = r and C consists of a set of vertex-disjoint cycles C_{1}, …, C_{k} satisfying the following properties:

1. each C_{i} is alternating with respect to the perfect matching M_{0},

2. for each i, j |E_{j}^{i}| ≤ 1,

3. for each i there is at most one j such that |C_{j} ∩ (E_{1}^{i} ∪ E_{2}^{i})| ≥ 1,

4. for each C_{j} there is exactly one i such that C_{j} intersects E_{1}^{i} ∪ E_{2}^{i},

5. t(C) = t.

Hence,

σ(r, t) = sgn(D, C) = ∏_{i=1}^{k} sgn(D, C_{i}) = ∏_{i=1}^{k} sgn(D_{i}, C_{i})

where D_{i} is the restriction of D to C_{0} ∪ C_{i}. Observe that, by Corollary 3.3, σ(z_{1}, z_{2}) = 1 if z_{2} = (0, 0). Hence, using Corollary 3.6, we have that ∏_{i=1}^{k} sgn(D_{i}, C_{i}) = ∏_{j=0}^{g−1} σ(r^{j}, t^{j}) as claimed.

□

Theorem 3.8 Let G be a proper g-graph. Then

P(G, x) = L_{g}(G, x) = ∑_{i=1}^{4^{g}} c(r(D_{i}))P(D_{i}, M_{0})

where D_{i}, i = 1, …, 4^{g}, are the relevant orientations of G.

Proof. Let P be a perfect matching of G. In each term P(D_{i}, M_{0}), the coefficient of x(P) is sgn(D_{i}, M_{0}ΔP). By Corollary 3.6, sgn(D_{i}, M_{0}ΔP) = σ(r(D_{i}), t(M_{0}ΔP)).

Let

K_{g}(t(M_{0}ΔP)) = ∑_{i=1}^{4^{g}} c(r(D_{i}))σ(r(D_{i}), t(M_{0}ΔP))

denote the coefficient of x(P) in L_{g}(G, x).

To prove the theorem it suffices to prove the following claim:

Claim. K_{g}(t(M_{0}ΔP)) = 1 for each t(M_{0}ΔP). The proof of the claim is by induction on g. The basis of the induction when g = 1 is proved in Corollary 3.5.

To prove the inductive step we introduce the following notation: if z is a 2gdimensional vector then we let z = (z(0), …, z(g − 1)) where z(i) = (z_{2i+1}, z_{2i+2}).

We call two relevant orientations D and D′ of G equivalent if (r(D)(1), …, r(D)(g− 1)) = (r(D′)(1), …, r(D′)(g − 1)). Clearly, the equivalence classes consist of 4 elements; let R_{1}, …, R_{4^{g−1}} be the equivalence classes of the relevant orientations of G and let R_{j} = {D_{1}^{j}, D_{2}^{j}, D_{3}^{j}, D_{4}^{j}}, j = 1, …, 4^{g−1}.

Finally let r(D_{i}^{j})(k) = r_{i}^{j}(k), k = 0, …, g − 1 and let t = t(M_{0}ΔP). We have that

K_{g}(t) = ∑_{j=1}^{4^{g−1}} ∑_{i=1}^{4} c(r(D_{i}^{j}))σ(r(D_{i}^{j}), t).

Now, by Lemma 3.7, this equals

∑_{j=1}^{4^{g−1}} ∑_{i=1}^{4} c(r_{i}^{j}(0))c(r_{i}^{j}(1), …, r_{i}^{j}(g − 1)) ∏_{k=0}^{g−1} σ(r_{i}^{j}(k), t(k)).

By the definition of the equivalence classes, r_{1}^{j}(k) = r_{2}^{j}(k) = r_{3}^{j}(k) = r_{4}^{j}(k) for k ≥ 1 and j = 1, …, 4^{g−1}. Hence, we let r_{i}^{j}(k) = r^{j}(k) and write the above summation as:

∑_{j=1}^{4^{g−1}} c(r^{j}(1), …, r^{j}(g − 1)) ∏_{k=1}^{g−1} σ(r^{j}(k), t(k)) ∑_{i=1}^{4} c(r_{i}^{j}(0))σ(r_{i}^{j}(0), t(0))

.

The internal sum equals to 1 for each j = 1, …, 4^{g−1} by the basis step of the induction, and hence, using Lemma 3.7 in the external sum, we can write the above summation as

∑_{j=1}^{4^{g−1}} c(r^{j}(1), …, r^{j}(g − 1))σ((r^{j}(1), …, r^{j}(g − 1)), (t(1), …, t(g − 1))) =

K_{g−1}(t(1), …, t(g − 1)) = 1,

by the inductive hypothesis for g − 1. End of Claim.

□

As a consequence of Theorem 1.4 and Theorem 3.8, we have:

Corollary 3.9 Let G be a proper g-graph. Then s(D_{i}, M_{0}) = s(D_{j}, M_{0}) for each i, j ∈ {1, …, 4^{g}} and

P(G, x) = L_{g}(G, x) = s(D_{1}, M_{0}) ∑_{i=1}^{4^{g}} c(r(D_{i}))P f(A(D_{i}))

where D_{i}, i = 1, …, 4^{g}, are the relevant orientations of G.

Theorem 3.10 Let G be a graph embeddable on an orientable surface of genus g. Then 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.

Proof. As observed in the previous section, any orientable surface S of genus g may be obtained from its polygonal representation S_{g} as follows: for each bridge B, glue together the two segments in which B intersects the boundary of B_{0}, and delete B.

If a graph G is embedded on an orientable surface S of genus g, then without loss of generality no vertex belongs to the boundary of B_{0}. In this way we get an embedding of G on S_{g} such that all vertices of G belong to B_{0} but the embeddings of some edges may use several bridges.

We construct a graph G′ by replacing each edge e = uv which uses k bridges, k ≥ 1, by a path P_{e} = (u, e_{1}, v_{1}, …, v_{2k}, e_{2k+1}, v). The new vertices v_{1}, ..., v_{2k} are embedded on the embedding of e so that each new edge uses at most one bridge. Moreover, we let x′_{e_{1}} = x_{e} and x′_{e_{i}} = 1 for each i > 1. We do a similar construction when G_{0} has no perfect matching. In fact, take any perfect matching M of G and replace any edge e = uv ∈ M embedded on a bridge by a path u, e_{1}, y, e_{2}, z, e_{3}, v and let x′_{e_{1}} = x_{e} and x′_{e_{2}} = x′_{e_{3}} = 1. Then leave the only edge e_{2} to be embedded on the bridge B.

Finally, we add edges so that the outer face of the planar part is a cycle and we let x′_{e} = 0 for each such edge e.

It is easy to see that G′ is a proper g-graph and that P(G′, x′) = P(G, x).

Now, by Theorem 3.8, P(G′, x′) may be written as a linear combination of 4^{g} terms P f(A(D′)), where each D′ is a relevant orientation of G′.

It remains to show that for each relevant orientation D′ of G′ there is an orientation D of G such that P f(A(D′)) = P f(A(D)) or P f(A(D′)) = −P f(A(D)).

We construct D from D′ in two steps:

1. delete the edges e of G′ − G with x′_{e} = 0,

2. for each edge e of G which was changed into a path P_{e} of odd length in the construction of G′, orient e in the direction in which an odd number of edges of P_{e} is directed in D′: this is uniquely determined since P_{e} has an odd length.

If P is a perfect matching of G then there is a unique perfect matching P′ of G′ such that x(P) = x′(P′).

Observe that sgn(D, P ΔQ) = sgn(D′, P′ΔQ′) for each pair of perfect matchings P, Q of G. The claim now follows from Theorem 1.4.

This finishes the proof of the theorem. □

4 Pfaffian Graphs, Exact Matching, and Permanents

The results of the previous section have interesting algorithmic implications.

Theorem 4.1 Let g and k be fixed positive integers. Let G be the class of graphs of genus g whose edges are partitioned into at most k classes and the variables x_{e} have the same value in each class. Then P(G, x) may be determined in polynomial time for G ∈ G.

Proof. It follows from Theorems 3.8 and 3.10 that P(G, x) may be expressed as a linear combination of a finite number of Pfaffians.

We show now that if the set of the edges of graph G is partitioned into a bounded number of classes and the variables x_{e} are equal in each class, then P(D, M) and P f(A(D)) may be determined efficiently. Let M = {{i_{1}j_{1}}, …, {i_{n}j_{n}}}, i_{k} < j_{k}, be a perfect matching of G. Let x′ be defined as follows: x′_{e} = x_{e} if e ∉ M and x′_{f} = x_{f}z if f ∈ M, where z is a new variable. Let A′ be the matrix obtained from A(D) by replacing each x_{e} by x′_{e}. Then det(A′) may be viewed as a polynomial det(A′)(x, z) in the variables x and z and its coefficients can be determined efficiently.

By Theorem 1.5, P f(A′)(x, z) = ±\sqrt{det(A′)(x, z)}. Hence we can determine efficiently a polynomial Q(x, z) such that P f(A′)(x, z) = ±Q(x, z)). Note that P(D, M) = ±Q(x, 1).

There is exactly one monomial in Q(x, z) containing z^{n} and its coefficient is +1 or −1. Let Q′(x, z) be the unique polynomial such that Q′(x, z) = Q(x, z) or Q′(x, z) = −Q(x, z) and the coefficient of Q′(x, z) of the term containing z^{n} equals +1. We have P(D, M) = +Q′(x, 1). Moreover, P f(A(D)) = s(D, M)P(D, M) and s(D, M) = s^{∗}(M)t^{∗}(M) where t^{∗}(M) equals the product of the signs of the elements a_{i_{k}j_{k}} of the matrix A(D) such that i_{k}j_{k} ∈ M. Hence P(D, M) and P f(A(D)) may be determined efficiently. □

As a consequence, if we are in the hypothesis stated by the theorem, the following problems may be solved efficiently.

1. Recognition of Pfaffian graphs: given a graph G ∈ G, decide whether G admits a Pfaffian orientation.

It was proved by Vazirani and Yannakakis (see the proof of Theorem 3.1 in [13]) that, given a graph G, it is possible to construct efficiently an orientation D of G such that G is Pfaffian if and only if D is its Pfaffian orientation. Hence P f(A(D)) equals to the number of the perfect matchings of G if and only if G is Pfaffian, and it means that we can decide efficiently whether a graph is Pfaffian once we can compute efficiently its number of perfect matchings.

2. Exact Matching Problem: given a graph G ∈ G with some edges coloured red, and a number h, decide whether G has a perfect matching with exactly h red edges.

It suffices to assign an x variable to red edges and a y variable to the remaining edges and compute P(G; x, y). If the coefficient of the monomial x^{h}y^{t−h}, where t is the cardinality of a perfect matching of G, is nonzero then the answer to the problem is yes, otherwise no such a matching exists.

3. Computing permanents of square matrices.

In 1913, Pólya [9] suggested computing the permanent of a matrix A by changing the signs of some entries of A so that the determinant of the resulting matrix equals the permanent of A. Let us call a (0, 1)-matrix A convertible if such a change is possible.

Szegö [11] pointed out in the same year that not all matrices are convertible. This may be explained nowadays using a complexity argument. There is an effi-

cient algorithm to compute the determinant, while Valiant proved that the problem of computing the permanent of a (0, 1)-matrix is #P -complete [12].

The computational problem of recognition of convertible matrices has been proved recently to admit a polynomial algorithm by McCuaig, Robertson, Seymour and Thomas [8]. An earlier paper of Galluccio and Loebl [3] contains a related algorithmic result, as well as a history of the problem.

The problem of recognizing convertible matrices is equivalent to the problem of recognizing bipartite Pfaffian graphs, and to the Even Cycle Problem: given a directed graph, decide whether it contains a directed cycle of even length.

Let A be a square matrix. Denote by G(A) the bipartite graph whose two bipartition classes are indexed by the rows and the columns of A, and for each edge ij, a_{ij} = x_{ij}. Then per(A) = P(G(A), x).

Hence, Theorem 3.10 provides a new combinatorial way to compute permanents of square matrices: per(A) may be written as a linear combination of 4^{g} terms of form P f(A(D)), where D is an orientation of G(A) and g is the genus of G(A).

Since G(A) is a bipartite graph, the non-zero entries of A(D) belong to two blocks A_{1}, A_{2}, where A_{1} is obtained from A by changing the sign of some entries and A_{2} = −A_{1}. Moreover |P f(A(D)| = |det(A_{1})| = |det(A_{2})| by Theorem 1.5.

This means that the method of Pólya may be completed as follows:

Corollary 4.2 Let A be a square matrix. Then per(A) may be expressed as a linear combination of terms of the form det(A^{i}), i = 1, ..., 4^{g}, where each A^{i} is obtained from A by changing the sign of some entries.

Acknowledgements. The authors are grateful to Chris Godsil, Robin Thomas and Dominic Welsh for fruitful discussions, and to the referee for the comments which highly improved the quality of the paper.

References

[1] F. Barahona. Balancing signed toroidal graphs in polynomial time. Preprint University of Chile, 1983. Unpublished manuscript.

[2] A. Cayley. Sur les determinants gauches. Crelle’s J., 38:93–96, 1847.

[3] A. Galluccio and M. Loebl. Even cycles and H-homeomorphisms. Technical Report 424, IASI-CNR, 1995. Submitted for publication.

[4] M. Kac and J.C. Ward. A combinatorial solution of the two-dimensional Ising model. Physical Review, 88, 1952.

[5] P. W. Kasteleyn. The statistics of dimers on a lattice. Physica, 27:1209–1225, 1961.

[6] P. W. Kasteleyn. Dimer statistics and phase transitions. Jour. Math. Physics, 4:287–293, 1963.

[7] P.W. Kasteleyn. Graph theory and crystal physics. In Graph theory and theoretical physics, New York, 1967. Academic Press.

[8] W. McCuaig, N. Robertson, P. D. Seymour, and R. Thomas. Permanents, pfaffian orientations, and even directed circuits. 1996. Preprint.

[9] G. Pólya. Aufgabe 424. Arch. Math. Phys., 20:271, 1913.

[10] R.B. Potts and J.C. Ward. The combinatorial method and the two-dimensional Ising model. Progress of Theoretical Physics, 13, 1955.

[11] G. Szegö. Lozung zu 424. Arch. Math. Phys., 21:291–292, 1913.

[12] L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8:189–201, 1979.

[13] V. V. Vazirani and M. Yannakakis. Pfaffian orientations, 0-1 permanents and even cycles in directed graphs. Discr. Appl. Math., 25:179–190, 1989.