An exploration of the permanent-determinant method

Greg Kuperberg UC Davis

              greg@math.ucdavis.edu

Abstract

The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, are methods to enumerate perfect matchings of plane graphs that were discovered by P. W. Kasteleyn. We present several new techniques and arguments related to the permanent-determinant with consequences in enumerative combinatorics. Here are some of the results that follow from these techniques:

1. If a bipartite graph on the sphere with 4n vertices is invariant under the antipodal map, the number of matchings is the square of the number of matchings of the quotient graph.

2. The number of matchings of the edge graph of a graph with vertices of degree at most 3 is a power of 2.

3. The three Carlitz matrices whose determinants count a × b × c plane partitions all have the same cokernel.

4. Two symmetry classes of plane partitions can be enumerated with almost no calculation.

Submitted: October 16, 1998; Accepted: November 9, 1998 [Also available as math.CO/9810091]

The permanent-determinant method and its generalization, the Hafnian-Pfaffian method, is a method to enumerate perfect matchings of plane graphs that was discovered by P. W. Kasteleyn [18]. Given a bipartite plane graph Z, the method produces a matrix whose determinant is the number of perfect matchings of Z. Given a non-bipartite plane graph Z, it produces a Pfaffian with the same property. The method can be used to enumerate symmetry classes of plane partitions [21, 22] and domino tilings of an Aztec diamond [45] and is related to some recent factorizations of the number of matchings of plane graphs with symmetry [5, 15]. It is related to the Gessel-Viennot lattice path method [12], which has also been used to enumerate plane partitions [2,38]. The method could lead to a fully unified enumeration of all ten symmetry classes of plane partitions. It may also lead to a proof of the conjectured q-enumeration of totally symmetric plane partitions.

In this paper, we will discuss some basic properties of the permanent-determinant method and some simple arguments that use it. Here are some original results that follow from the analysis:

1. If a bipartite graph on the sphere with 4n vertices is invariant under the antipodal map, the number of matchings is the square of the number of matchings of the quotient graph.

2. The number of matchings of the edge graph of a graph with vertices of degree at most 3 is a power of 2.

3. The three Carlitz matrices whose determinants count a × b × c plane partitions all have the same cokernel.

4. Two symmetry classes of plane partitions can be enumerated with almost no calculation. (This result was independently found by Ciucu [5]).

The paper is largely written in the style of an expository, emphasizing techniques for using the permanent-determinant method rather than specific theorems that can be proved with the techniques. Here is a summary for the reader interested in comparing with previously known results: Sections I, II, and III are a review of wellknown linear algebra and results of Kasteleyn, except for III A and III B, which are new. Sections IV, V, and VI are mostly new. Parts of Section IV were discovered independently by Regge and Rasetti, Jockusch, Ciucu, and Tesler. Obviously the Gessel-Viennot method, the Ising model, and tensor calculus themselves are due to others. Section VII consists entirely of new and independently discovered results about plane partitions. Finally Section VIII is strictly a historical survey.

A Acknowledgements

The author would like to thank Mihai Ciucu and especially Jim Propp for engaging discussions and meticulous proofreading. The author also had interesting discussions about the present work with John Stembridge and Glenn Tesler.

The figures for this paper were drafted with PSTricks [44].

I Graphs and determinants

A sign-ordering of a finite set is a linear ordering chosen up to an even permutation. Given two disjoint sets A and B, a bijection f : A → B induces a sign-ordering of A ∪ B as follows. Order the elements of A arbitrarily, and then list

a_{1}, f(a_{1}), a_{2}, f(a_{2}), ….

More generally, an oriented matching of a finite set A, meaning a partition of A into ordered pairs, induces a sign-ordering of A by the same construction. A sign-ordering of A ∪ B is also equivalent to a linear ordering of A and a linear ordering of B, chosen up to simultaneous odd or even permutations, by choosing f to be order-preserving.

Let Z be a weighted bipartite graph with black and white vertices, where the weights of the edges lie in some field 𝔽. (Usually 𝔽 will will be ℝ or ℂ.) The graph Z has a weighted, bipartite adjacency matrix, M(Z), whose rows are indexed by the black vertices of Z and whose columns are indexed by the white vertices. The matrix entry M(Z)_{v,w} is the total weight of all edges from v to w. If the vertices of Z are sign-ordered, then det(M(Z)) is well-defined (and taken to be 0 unless M(Z) is square). By abuse of notation, we define

det(Z) = det(M(Z)).

The sign of det(Z) is determined by choosing linear orderings of the rows and columns compatible with the sign-ordering of Z. If the vertices are not sign-ordered, the absolute determinant | det(Z)| is still well-defined.

Just as matrices are a notation for linear transformations, a weighted bipartite graph Z can also denote a linear transformation

L(Z) : 𝔽[B] → 𝔽[W].

Here B is the set of black vertices, W is the set of white vertices, and 𝔽[X] denotes the set of formal linear combinations of elements of X with coefficients in 𝔽. The map L(Z) is the one whose matrix is M(Z). Note that Z is not uniquely determined by L(Z): if Z has multiple edges, the linear transformation only depends on the sum of the weights of these edges. If Z has an edge with weight 0, the edge is synonymous with an absent edge. Row and column operations on M(Z) can be viewed as operations on Z itself modulo these ambiguities.

These observations also hold for weighted, oriented non-bipartite graphs. Given such a graph Z, the antisymmetric adjacency matrix A(Z) has a row and column for every vertex of Z. The matrix entry A(Z)_{v,w} is the total weight of all edges from v to w minus the total weight of edges from w to v. This matrix has a Pfaffian Pf(A(Z)) whose sign is well-defined if the vertices of Z are sign-ordered. We also define

Pf(Z) = Pf(A(Z)).

Recall that the Pfaffian Pf(M) of an antisymmetric matrix M is a sum over matchings in the set of rows of M. The sign of the Pfaffian depends on a sign-ordering of the rows of M. In these respects, the Pfaffian generalizes the determinant. The Pfaffian also satisfies the relation

det(M) = Pf(M)^{2}.  (1)

This relation has a bijective proof: If M is antisymmetric, the terms in the determinant indexed by permutations with odd-length cycles vanish or cancel in pairs. The remaining terms are bijective with pairs of matchings of the rows of M, and the signs agree. This argument, and the permanent-determinant method generally, blur the distinction between bijective and algebraic proofs in enumerative combinatorics.

In particular,

det(Z) = Pf(Z)

when Z is bipartite if all edges are oriented from black to white. (If this seems inconsistent with equation (1), recall that the implicit matrix on the right, A(Z), has two copies of the one on the left, M(Z).) If Z has indeterminate weights, the polynomial det(Z) or Pf(Z) has one term for each perfect matching m of Z. The term may be written

t(m) = (−1)^{m}ω(m),

where (−1)^{m} is the sign of m relative to the sign-ordering of vertices of Z, and ω(m) is the product of the weights of edges of m. Thus det(Z) or Pf(Z) for an arbitrary graph Z is a basic object in enumerative combinatorics.

II The permanent-determinant method

Let Z be a connected, bipartite planegraph. By planarity we mean that Z is embedded in an (oriented) sphere. The faces of Z are disks; together with the edges and vertices they form a cell structure, or CW complex, on the sphere. Since the sphere is oriented, each face is oriented. The edges of Z have a preferred orientation, namely the one in which all edges point from black to white. The Kasteleyn curvature (curvature for short) of Z at a face F is defined as

c(F) = (−1)^{|F |/2+1} \frac{∏_{e∈F_{+}} ω(e)}{∏_{e∈F_{−}} ω(e)},

where |F | is the number of edges in F, F_{+} is the set of edges whose orientation agrees with the orientation of F, and F_{−} is the set of edges whose orientation disagrees with that of F. (Each face inherits its orientation from that of the sphere.) A face F is flat if c(F) is 1. See Figure 1.

\begin{matrix}F_{−} \\ F_{+} \\ F_{−} \\ F_{+} \\ F_{−} \\ F_{+} \\ F \end{matrix}

Figure 1: Computing Kasteleyn curvature.

Theorem 1 (Kasteleyn). If Z is unweighted, a flat weighting exists.

The theorem depends on the following lemma.

Lemma 2. If Z has an even number of vertices, and in particular if black and white vertices are equinumerous, then there are an even number of faces with 4k sides.

Proof. Let n_{V}, n_{E}, and n_{F} be the number of vertices, edges, and faces of Z, respectively. The Euler characteristic equation of the sphere is

χ = n_{F} − n_{E} + n_{V} = 2.

The term n_{V} is even. Divide the contribution to n_{E} from each edge, namely −1, evenly between the two incident faces. Then the contribution to n_{F} − n_{E} of a face with 4k sides is an odd integer, while the contribution of a face with 4k + 2 sides is an even integer. Therefore there are an even number of the former.

Proof of theorem. Consider the cohomological chain complex of the cell structure given by Z with coefficients in the multiplicative group 𝔽^{∗}. (Since it may be confusing to consider homological algebra with multiplicative coefficients, we will sometimes denote a “sum” of 𝔽^{∗}-cochains as a ∔ b.) Consider the same orientations of the edges and faces of Z as above. With these orientations, we can view a function from n-cells to 𝔽^{∗} as an n-cochain. In particular, a weighting ω of Z is equivalent to a 1-cochain. Let ω_{k}, the Kasteleyn cochain, be a 2-cochain which assigns (−1)^{|F |/2+1} to each face f. The coboundary δω of ω is related to the curvature by

c(F) = ω_{k} ∔ δω.

Thus, a flat weighting exists if and only if ω_{k} is a coboundary. By the lemma, ω_{k} has an even number of faces with weight −1 and the rest have weight 1. Thus, ω_{k} represents the trivial second cohomology class of the sphere. Therefore it is a coboundary.

Following the terminology of the proof, the curvature of any weighting is a coboundary, because it is the sum (in the sense of “∔”) of two coboundaries, ω_{k} and the coboundary of the weighting. Thus the product of all curvatures of all faces is 1.

Theorem 3 (Kasteleyn). If Z is flat, the number of perfect matchings is ± det(Z), because t(m) has the same sign for all m.

A complete proof is given in Reference 21, but the result also follows from a more general result.

By a loop we mean a collection of edges of Z whose union is a simple closed curve. If the loop ℓ is the difference between two matchings m_{1} and m_{2}, then all edges of ℓ point in the same direction if we reverse the edges of ℓ ∩ m_{2}. Of the two regions of the sphere separated by ℓ, the positive one is the one whose orientation agrees with ℓ.

Theorem 4. If m_{1} and m_{2} are two matchings of Z that differ by one loop ℓ, the ratio of their terms t(m_{1})/t(m_{2}) in the expansion of det(Z) equals the product of the curvatures of the faces on the positive side of ℓ.

Proof. The loop ℓ has an even number of sides and also must enclose an even number vertices on the positive side S_{+}. If we remove the vertices and edges on the negative side S_{−}, we obtain a new graph Z′ such that the loop ℓ bounds a face F that replaces S_{−}. Since the total curvature of all faces of Z′ is 1, the curvature of F is the reciprocal of the total curvature of all other faces. Finally,

c(F) = (−1)^{|F |/2+1} \frac{∏_{e∈F_{+}} ω(e)}{∏_{e∈F_{−}} ω(e)}

= (−1)^{m_{1}}(−1)^{m_{2}} \frac{∏_{e∈ℓ∩m_{2}} ω(e)}{∏_{e∈ℓ∩m_{1}} ω(e)}

= \frac{t(m_{2})}{t(m_{1})}.

The signs agree because m_{1} and m_{2} differ by an even cycle, which is an odd permutation if and only if F has 4k sides.

\begin{matrix}F_{1} \\ F_{2} \\ F_{3} \\ F_{4} \\ ℓ \end{matrix}

Figure 2: A loop enclosing four faces.

Figure 2 illustrates the proof of Theorem 4. The loop encloses four faces. Edges in bold appear in at least one of two terms m_{1} and m_{2} that differ by ℓ. The theorem in this case says that

\frac{t(m_{2})}{t(m_{1})} = c(F_{1})c(F_{2})c(F_{3})c(F_{4}).

In light of Theorem 4, if Z is an unweighted graph, a curvature function and a reference matching m are enough to define det(Z), because we can choose a weighting and a sign-ordering with the desired curvature and such that t(m) = 1. The matrix M(Z) will then have the following ambiguity. In general, if ω_{1} and ω_{2} are two weightings with the same curvature, then ω_{1} ∔ ω_{2}^{−1} is a 1-cocycle. Since the first homology of the sphere is trivial, the ratio is a 1-coboundary, i.e., ω_{1} and ω_{2} differ by a 0-cochain. The corresponding matrices M(Z_{ω_{1}}) and M(Z_{ω_{2}}) then differ by multiplication by diagonal matrices on the left and the right.

III The Hafnian-Pfaffian method

Kasteleyn’s method for non-bipartite plane graphs expresses the number of perfect matchings as a Pfaffian. For simplicity, we consider unweighted, oriented graphs. The analysis has a natural generalization to weighted graphs in which the orientation is completely separate from the weighting. The curvature of an orientation at a face is 1 if an odd number of edges point clockwise around the face and −1 otherwise. The orientation is flat if the curvature is 1 everywhere. A routine generalization of Theorem 3 shows that if Z has a flat orientation, Pf(Z) is the number of matchings [18].

A graph Z, whether planar or not, is Pfaffian if it admits an orientation such that all terms in Pf(Z) have the same sign [24].

If Z is bipartite, orienting Z is equivalent to giving each edge a 1 if it points to black to white and −1 otherwise. The weighting is flat if and only if the orientation is flat.

Theorem 5 (Kasteleyn). If Z is an unoriented plane graph, a flat orientation exists.

In particular, planar graphs are Pfaffian.

Proof. The proof follows that of Theorem 1. Fix an orientation o, and again consider the mod 2 Euler characteristic of the sphere. Ignoring the vertices, we transfer the Euler characteristic of each edge to the incident face whose orientation agrees with that of the edge. The net Euler characteristic of a face is then 0 if it is flat and 1 if it is not, therefore there must be an even number of non-flat faces. Let k be the curvature of o.

The Euler characteristic calculation shows that k is a coboundary of a 1-cochain c with coefficients in the multiplicative group {±1}. Let o′ = c ∔ o be the “sum” of c and o, defined by the rule that o′ and o agree on those edges where c is 1 and disagree where c is −1. Then o′ is flat.

In the same vein, suppose that Z and Z′ are the same graph with two different flat orientations. By homology considerations, the “difference” of the two orientations (1 where they agree, −1 where they disagree) is a 1-coboundary. Thus they differ by the coboundary of a 0-cochain c, which is a function from the vertices to {±1}. Let D be the diagonal matrix whose entries are the values of c. Then A(Z), A(Z′), and D satisfy the relation

A(Z) = DA(Z′)D^{T} .

Note that c and D are unique up to sign.

III A Spin structures

We conclude with some comments about flat orientations of a graph Z on a surface of genus g. Kasteleyn [18] proved that the number of matchings of such a graph is given by a sum of 4^{g} Pfaffians defined using inequivalent flat orientations of Z. (See also Tesler [40].) There is an interesting relationship between these flat orientations and spin structures. A spin structure on a surface is determined by a vector field with even-index singularities. We can make such a vector field using an orientation and a matching m. At each vertex, make the vectors point to the vertex. Then replace each edge by a continuous family of edges such that in the middle of the edge, the vector field is 90 degrees clockwise relative to the orientation of the edge Figure 3 shows this operation applied to the four edges of a square.

Figure 3: Vectors describing a spin structure.

Because the orientation is flat, the vector field extends to the faces with even-index singularities, but the singularities at the vertices are odd. Contract the odd-index singularities in pairs along edges of the matching; the resulting vector field induces a spin structure. For a fixed orientation, inequivalent matchings yield distinct spin structures. Here two matchings are equivalent if they are homologous. For a fixed matching, two inequivalent orientations yield distinct spin structures.

III B Projective-plane graphs

An expression for the number of matchings of a non-planar graph may in general require many Pfaffians. But there is an interesting near-planar case when a single Pfaffian suffices.

A graph is a projective-plane graph if it is embedded in the projective plane. A graph embedded in a surface is locally bipartite if all faces are disks and have an even number of sides. It is globally bipartite if it is bipartite. If Z is locally but not globally bipartite, then it has a non-contractible loop, but all non-contractible loops have odd length while all contractible loops have even length.

Theorem 6. If Z is a connected, projective-plane graph which is locally but not globally bipartite, then it is Pfaffian.

Proof. Assume that Z has an even number of vertices.

The curvature of an orientation of Z is well-defined even though the projective plane is non-orientable: Since each face has an even number of sides, the curvature is 1 if an odd number of edges point in both directions and −1 otherwise. If the curvature of an arbitrary orientation o is a coboundary, meaning that an even number of faces have curvature −1, then there is a flat orientation by the homology argument of Theorem 5.

To prove that the curvature of o must be a coboundary, we cut along a noncontractible loop ℓ, which must have odd length, to obtain an oriented plane graph Z′. Every face of Z becomes a face of Z′, and in addition Z′ has an outside face with 2|ℓ| sides. A face in Z′ has the same curvature as in Z assuming that it is a face of both graphs. The graph Z′ has an odd number of vertices, because it has |ℓ| more vertices than Z does. By the argument of Theorem 5, Z′ has an odd number of faces with curvature −1. Moreover, the outside face is one of them, because each of the edges of ℓ appears twice, both times pointing either clockwise or counterclockwise. Therefore Z must have an even number of faces with curvature −1.

Finally, we show that a flat orientation of Z is in fact Pfaffian. Let m_{1} and m_{2} be two matchings that differ by a single loop. Since the loop has even length, it is contractible. By the usual argument, the ratio t(m_{1})/t(m_{2}) of the corresponding terms in the expansion of Pf(A(Z)) equals the product of the curvatures of the faces that the loop bounds. Since Z is flat, this product is 1.

IV Symmetry

IV A Generalities

Let V be a vector space over ℂ, the complex numbers. If a linear transformation L : V → V commutes with the action of a reductive group G, then det(L) factors according to the direct sum decomposition of V into irreducible representations of G. At the abstract level, for each distinct irreducible representation R, we can make a vector space V_{R} such that V_{R} ⊗ R is an isotypic summand of V, and there exist isotypic blocks

L_{R} : V_{R} → V_{R}

such that

L = ⨁_{R}(L_{R} ⊗ I_{R}),

where I_{R} is the identity on R. Then

det(L) = ∏_{R} det(L_{R})^{dim R}.  (2)

More concretely, if M is a matrix and a group G has a matrix representation ρ such that

ρ(g)M = Mρ(g),

then after a change of basis, M decomposes into blocks, with dim R identical blocks of some size for each irreducible representation R of G, so its determinant factors.

Suppose that L is an endomorphism of some integral lattice X in V (concretely, if M is an integer matrix) and R is some rational representation. After choosing a rational basis {r_{i}} for R, we can realize copies V_{r_{i}} of V_{R} as rational subspaces of V. The lattice L preserves each V_{r_{i}} and acts acts on it as L_{R}. Then X ∩ V_{r_{i}} is a lattice in V_{r_{i}}, and L is an endomorphism of this lattice as well. The conclusion is that each det(L_{R}) must be an integer because L_{R} is an endomorphism of a lattice. Indeed, this argument works for any number field (such as the Gaussian rationals) and its ring of integers (such as the Gaussian integers) if R is not a rational representation, which tells us that equation 2 is in general a factorization into algebraic integers if L is integral. The determinant det(L_{R}) is, a priori, in the same field as the representation R. A refinement of the argument shows that it is in the same field as the character of R, which may lie in a smaller field than R itself.

The general principle of factorization of determinants applies to enumeration of matchings in graphs with symmetry via the Hafnian-Pfaffian method. As discussed in Sections I and III, an oriented graph Z yields an antisymmetric map

A(Z) : ℂ[Z] → ℂ[Z].

Figure 4: A Pfaffian orientation with broken symmetry.

Any symmetry of the oriented graph intertwines this map, and the factorization principle applies. However there are three complications. First, the orientation may have less symmetry than the graph itself (Figure 4). Second, the principle of factorization gives information about the determinant and not the Pfaffian. (If a summand R of an orthogonal representation V is orthogonal and L is an antisymmetric endomorphism of V, then the factor det(L_{R}) is the square of Pf(L_{R}). But if R is symplectic or complex, then det(L_{R}) need not be a square. In these cases the factorization principle is less informative.) Third, the number of matchings might only factor into algebraic integers, which is less informative than a factorization into ordinary integers.

Let Z be a connected plane graph, and suppose that a group G acts on the sphere and preserves Z and the orientation of the sphere. Then G acts by permutation matrices on V = ℂ[Z], the vector space generated by vertices of Z. Although G commutes with the adjacency matrix of Z, it does not in general commute with the antisymmetric adjacency matrix A(Z) if Z is oriented, because G might not preserve the orientation of Z. However, if Z has a flat orientation o and g ∈ G, then go differs from o by a coboundary in the sense of Sections II and III. This means that there is a signed permutation matrix g̃ which does commute with A(Z). These signed permutation matrices together form a linear representation of some group G̃ which extends G. At first glance it may appear as if the fiber of this extension is as big as {±1}^{|Z|}. But because Z is connected, among diagonal signed matrices only the identity and its negative commute with A(Z); only constant 0-cochains leave alone the orientation of every edge of Z. Therefore G̃ is a central extension of G by the twoelement group G_{0} = {±1}. The subgroup G_{0} either acts trivially on V or negates it. Thus, in decomposing V into irreducible representations, we need only consider those where G_{0} acts trivially (by definition the even representations) or only those where G_{0} acts by negation (by definition the odd representations), depending on whether the action on V is even or odd.

If G has odd order, the central extension must split. In this case, by averaging, Z has a flat orientation invariant under G [41]. If G a cyclic group of rotations of order 2n, then the central extension might not split, but it is not very interesting as an extension; if Z is bipartite, one can find a flat weighting using 4nth roots of unity which is invariant under G [15]. But in the most complicated case, when Z has icosahedral symmetry, the central extension G̃ (when it is non-trivial) is the binary icosahedral group Ã_{5}, which is quite interesting. This central extension seems related to the connection between flat orientations and spin structures mentioned in Section III, because the symmetry group of a spun sphere is an analogous central extension of SO(3). Irrespective of G, the representation theory of G̃ reveals a factorization of the number of matchings of Z.

If Z is bipartite, then there are two important changes to the story. First, after including signs, one can make orientation-reversing symmetries commute with A(Z) as well, because in the bipartite case they take flat orientations to flat orientations. If Z is not bipartite, the best signed versions of orientation-reversing symmetries instead anticommute with A(Z). Anticommutation is less informative than commutation, but they still sometimes provide information together with the following fact from linear algebra: If A and B anticommute and B is invertible, then

tr(A^{n}) = tr(−A^{n}) = 0

for n odd, because

−A^{n} = B^{−1}A^{n}B.

Second, if Z is bipartite, then color-reversing symmetries yield no direct information via representation theory. In this case, it is better to apply representation theory to the bipartite adjacency matrix M(Z). This matrix represents a linear map

L : ℂ[B] → ℂ[W],

where B is the set of black vertices and W is the set of white vertices, rather than a linear endomorphism of a single space. The color-preserving symmetries act on both V = ℂ[B] and U = ℂ[W] and M(Z) intertwines these actions. Hence for each irreducible R there is an isotypic block

L_{R} : V_{R} → U_{R}.

Hence for each R we must choose volume elements on V_{R} and U_{R} so that det L_{R} is well-defined. Nevertheless, equation 2 still holds if it is properly interpreted.

IV B Cyclic symmetry

Suppose that G is generated by a single rotation g of order n, and let ω be an nth root of unity when n is odd or G fixes a vertex (the split case), or an odd 2nth root of unity when n is even and G does not fix a vertex (the non-split case). Then the vertex space ℂ[Z] has an isotypic summand ℂ[Z]_{ω}. A suitable set of vectors of the form

v + ωgv + … + ω^{n}g^{n}v,

where v is a vertex of Z, form a basis of ℂ[Z]_{ω} (assuming certain sign conventions in the non-split case). In this case the isotypic blocks of A(Z) are all represented by weighted plane graphs whose Kasteleyn curvature can be easily derived from that of Z [15].

If Z is bipartite, then a reflection symmetry produces a similar factorization, and again the resulting matrices are represented by plane graphs [5].

The other possibility for a color-preserving cyclic symmetry is a glide-reflection. In particular, Z may be invariant under the antipodal map on the sphere. In this case, the blocks of M(Z) cannot be represented by plane graphs. Instead, they produce projective-plane graphs. So the number of matchings factors, but the permanentdeterminant method does not identify either factor as an unweighted enumeration.

IV C Color-reversing symmetry

If Z is bipartite, then a color-reversing symmetry does not a priori lead to an interesting factorization of the number of matchings of Z. For example, if the symmetry is an involution, then if we use it to establish a bijection between black and white vertices, we learn only that M(Z) is symmetric, which says little about its determinant. However, color-reversing symmetries do have two interesting and related consequences.

First, if Z has color-reversing and color-preserving symmetries, the color-reversing symmetries sometimes imply that the numerical factors of det(Z) from the colorpreserving symmetries lie in smaller-than-expected number-field rings. For example, if Z has a color-reversing 90-degree rotational symmetry g, then the symmetry g^{2} yields

det(Z) = det(Z_{i}) det(Z_{−i}),

where Z_{±i} is the quotient graph Z/g^{2} with curvature ±i at the faces fixed by g^{2}. (Recall that Z is on the sphere, so there are two fixed faces.) Then the remaining symmetry tells us that Z_{i} and Z_{−i} have a curvature-preserving isomorphism, which means that their determinants are equal up to a unit in the Gaussian integers. At the same time, their determinants are complex conjugates. Thus, det(Z_{i}) is, up to a unit, in the form a or (1 + i)a for some rational integer a. The conclusion is that det(Z) is either a square or twice a square [15]. Similarly, if Z has a color-reversing 60-degree symmetry,

det(Z) = ab^{2}

for some integers a and b coming from enumerations in quotient graphs.

Second, if Z has a color-reversing involution g which does not fix any edges, then the antisymmetric adjacency matrix A(Z/g) of the quotient graph Z/g can be interpreted as the bipartite adjacency matrix of Z with some weighting. Since the determinant is the square of the Pfaffian,

det(Z) = Pf(Z/g).

If Z/g is flat (which implies that Z/g has an even number of vertices), then Z with its induced weighting may or may not be flat, depending on g. Assuming Z is connected, g may be the antipodal involution in the sphere or it may be rotation by 180 degrees. In the first case, Z is flat, while Z/g is projective-plane graph which is locally but not globally bipartite. In the second case, Z is not flat, but has curvature −1 at the two faces fixed by rotation. The first case is a new theorem:

Theorem 7. If Z is a bipartite graph on the sphere with 4n vertices which is invariant under the antipodal involution g, and if g exchanges colors of vertices of Z, then the number of matchings of Z is the square of the number of matchings of Z/g.

For example, the surface of a Rubik’s cube satisfies these conditions (Figure 5).

Figure 5: The Rubik’s cube graph.

Exercise. Prove Theorem 7 with an explicit bijection.

This exercise is a special case of the bijective argument that

det(M) = Pf(M)^{2}

for any antisymmetric matrix M.

IV D Icosahedral symmetry

The results of this section were discovered independently by Rasetti and Regge [32].

The easiest realization of the binary icosahedral group Ã_{5} is as the subgroup of the unit quaternions a + bi⃗ + cj⃗ + dk⃗ for which (a, b, c, d) is one of the points

\frac{1}{2}(τ, 1, \frac{1}{τ}, 0) (1, 0, 0, 0) \frac{1}{2}(1, 1, 1, 1)

or the points obtained from these by changing signs or even permutations of coordinates. Here τ is the golden ratio. Note that two elements of Ã_{5} are conjugate if and only if they have the same real part a.

1 2 3 4 5 6 4 2 3

Figure 6: Extended E_{8}, a graph of representations of Ã_{5}.

This realization also describes a two-dimensional representation π of Ã_{5}. The character of π is twice the real parts of the elements of Ã_{5}. By the McKay correspondence, the irreducible representations of Ã_{5} together form an E_{8} graph, where the trivial representation is the extending vertex, and two representations R and R′ are joined by an edge if R ⊗ π contains R′ as a summand. This diagram is given in Figure 6 together with the dimensions of the representations. The trivial representation is circled. A black vertex is an even representation in the sense of Section IV A, while a white vertex is an odd representation. This graph can be used to compute the character table of Ã_{5}, which is given in Table 1. In this table,

\overline{τ} = −\frac{1}{τ}

is the Galois conjugate of τ. The table indicates various properties of the representations. The conjugacy class c_{0} contains only 1, so its row is the trace of the identity or the dimension of each representation. The conjugacy class c_{8} contains only −1, so its row indicates which representations are even and which are odd. The representation R_{1} equals the defining representation π. Apparently, five of the characters are rational, while the other four lie in the golden field ℚ(τ). Less superficially, the character table can be used to find the direct sum decomposition of an arbitrary representation from its character, or to decompose an equivariant map into its isotypic blocks.

Suppose that a graph Z has icosahedral symmetry. If a rotation by 180 degrees fixes a vertex of Z, then the action of Ã_{5} on ℂ[Z] is even, but if such a rotation fixes an edge or a face, then the action is odd (exercise). In the second case, the factorization principle says that det(A(Z)) is in the form a^{2}\overline{a}^{2}b^{4}c^{6}, where b and c are integers and a and \overline{a} are conjugate elements in ℤ(τ), because the available representations have

\begin{matrix}χ & R_{0} & R_{1} & R_{2} & R_{3} & R_{4} & R_{5} & R_{6} & R_{7} & R_{8} \\ c_{0} & 1 & 2 & 3 & 4 & 5 & 6 & 4 & 2 & 3 \\ c_{1} & 1 & τ & τ & 1 & 0 & −1 & −1 & \overline{τ} & \overline{τ} \\ c_{2} & 1 & 1 & 0 & −1 & −1 & 0 & 1 & 1 & 0 \\ c_{3} & 1 & −\overline{τ} & \overline{τ} & −1 & 0 & 1 & −1 & −τ & τ \\ c_{4} & 1 & 0 & −1 & 0 & 1 & 0 & 0 & 0 & −1 \\ c_{5} & 1 & \overline{τ} & \overline{τ} & 1 & 0 & −1 & −1 & τ & τ \\ c_{6} & 1 & −1 & 0 & 1 & −1 & 0 & 1 & −1 & 0 \\ c_{7} & 1 & −τ & τ & −1 & 0 & 1 & −1 & −\overline{τ} & \overline{τ} \\ c_{8} & 1 & −2 & 3 & −4 & 5 & −6 & 4 & −2 & 3 \end{matrix}

Table 1: Character table of Ã_{5}

dimensions 2,2,4, and 6. Thus the number of matchings factors as a^{1}\overline{a}^{1}b^{2}c^{3}. In the first case, ℂ[Z] decomposes entirely into orthogonal representations, which implies that

Pf(Z) = a^{1}b^{3}\overline{b}^{3}c^{4}d^{5}

using the dimensions of the representations and the number fields in which they lie. Here are four interesting examples. In the first three, the author explicitly computed the factorization from symmetry by computing the trace of gM(Z)^{n} for different g and n.

Figure 7: The edge graph of a dodecahedron.

1. If Z is an icosahedron, then ℂ[Z] consists of two copies of the 6-dimensional representation R_{6}, which means that A(Z) is, after a change of basis, six copies of a 2 × 2 matrix M. Moreover, A(Z) anticommutes with antipodal inversion,

Figure 8: The C_{60} graph with two kinds of edges.

so M must have vanishing trace. The matrix M^{2}, and therefore A(Z) must be a multiple of the identity. In fact,

A(Z)^{2} = 5I.

Thus there are 5^{3} = 125 matchings.

2. If Z is a dodecahedron, then

Pf(Z) = 36 = 1^{3}6^{2}.

The space ℂ[Z] has two 6-dimensional summands, which contribute the factors of 1, and two 4-dimensional summands, which contribute the factors of 6.

3. If Z is the edge graph of a dodecahedron or icosahedron (Figure 7), then

Pf(Z) = (4 + 2\sqrt{5})^{3}(4 − 2\sqrt{5})^{3}1^{4}2^{5} = −2^{11}.

The space ℂ[Z] has two of each of the non-trivial even representations.

4. Let Z be the bond graph of the fullerene C_{60} (Figure 8). Suppose that its hexagonal edges (the thicker ones in the figure) have weight 1 and its pentagonal edges (the thinner ones) have weight p. According to Tesler [42], the total weight of all matchings is

Pf(Z) = (1 − 2p + \frac{5 + \sqrt{5}}{2}p^{2})(1 − 2p + \frac{5 − \sqrt{5}}{2}p^{2})
(1 + 2p + 2p^{3} + 5p^{4})^{2}(1 + p^{2} + 2p^{3} + p^{4})^{3}.

In this case the space ℂ[Z] is 60-dimensional and decomposes as two copies of each 2-dimensional representation, four copies of the odd 4-dimensional representation, and six copies of the 6-dimensional representation. The factors from the 2-dimensional representation are at most quadratic and the factors of the 4dimensional representation are at most quartic. It follows that the factorization above coincidences with the factorization given by the symmetry principle.

V Gessel-Viennot

Some of the results in the section were independently discovered by Horst Sachs et al [1].

The Gessel-Viennot method is another method that counts combinatorial objects using determinants [12]. Let Z be a directed, plane graph with n sources (univalent vertices with outdegree 1) and n sinks (univalent vertices with indegree 1). Suppose further that the edges at each vertex are segregated, meaning that no four edges alternate in, out, in, out. Then the Gessel-Viennot method produces an n × n matrix whose determinant is the number of collections of n disjoint, directed paths in Z from the sources to the sinks. Each entry of the matrix is the number of paths from a source to a sink. The method has some ad hoc generalizations that produce Pfaffians [27,39]. It has been used to enumerate several classes of plane partitions [2,38].

Figure 9: Transforming Gessel-Viennot to Kasteleyn.

Given a graph Z suitably decorated for the Gessel-Viennot method, there is a related graph Z′ to which the permanent-determinant method applies. Namely, split each vertex of Z into an edge e, with all inward arrows at one end of e and all outward arrows at the other end (Figure 9). This operation induces a bijection betwen disjoint path collections in Z and matchings in Z′.

There is a corresponding relation between the Gessel-Viennot matrix GV (Z) and a Kasteleyn matrix M(Z′). Define a pivot operation to be the act of replacing an n × n matrix of the form

( \begin{matrix}M & v \\ w & 1 \end{matrix} )

by M − (v ⊗ w), where v and w are vectors and M is an (n − 1) × (n − 1) matrix. The determinant does not change under pivot operations. Starting with M(Z′), if we pivot at all entries corresponding to edges in Z′ which are contracted in Z, the result is the Gessel-Viennot matrix GV (Z) with some rows and columns negated. This proves that det GV (Z) is the number of matchings of Z′. It also suggests that any enumeration derived using the Gessel-Viennot method can also be understood using the permanent-determinant method.

It was pointed out to the author by Mihai Ciucu that there is a version of the Gessel-Viennot method for arbitrary graphs, whether planar or not. In this case the transformation of Figure 9 still produces the relation

det GV (Z) = det Z′,

where the right side is a weighted enumeration of matchings of Z′ in our sense. However, this more general setting cannot be interpreted via Theorem 3.

V A Cokernels

An integer n × n matrix M can be interpreted as a homomorphism from ℤ^{n} to itself. The cokernel is defined as the target divided by the image:

coker M = ℤ^{n}/(im M).

Alternatively, the cokernel is the abelian group on n generators whose relations are given by M. The cokernel is invariant under pivot operations, and the number of elements in the cokernel is | det(M)|. Moreover, the cokernel of a Kasteleyn matrix M(Z) depends only on the unweighted graph Z and not the particular choice of a flat weighting, and any corresponding Gessel-Viennot matrix also has the same cokernel.

Question 1. Is there a natural bijection, or an algebraic generalization of a bijection, between the cokernel of M(Z) and the set of matching of Z?

For any integer matrix M, the cokernel of M^{T} is naturally the Pontryagin dual of the cokernel of M. In other words, there is a natural Fourier transform map

Ψ : ℂ[coker M] → ℂ[coker M^{T}].

This map can be interpreted as a generalized bijection.

VI Other tricks

VI A Forcing planarity

Let Z be an arbitrary bipartite graph with some weighting. Then det(Z) is interesting as a weighted enumeration of the matchings of Z and as an algebraic quantity. At the same time, there is a simple way to convert Z to a plane graph without changing its determinant. Then ideas related to the permanent-determinant method apply. (Note that the number of matchings of Z in general will change. Together with the

Figure 10: Vertex splitting.

assumption that NP ≠ P, this would otherwise contradict the fact that the number of matchings for a general non-planar graph is a #P -hard quantity [43].)

In such a graph Z, we can triple an edge, i.e., replace it by three edges in series. If the weight of the original edge is w and the weights of three edges replacing it are a, b, and c, then det(Z) will not change if w = ac and b = −1. Edge tripling is a special case of vertex splitting, a more general operation in which a vertex is replaced by two edges in series (Figure 10). Vertex splitting changes det(Z) by a factor of ±a if one of the new edges has weight a and the other has weight −a.

Figure 11: A crossing replaced by a butterfly.

Pick a projection of Z in the plane, i.e., a drawing where edges are straight but may cross. After tripling the edges sufficiently, every edge crosses at most one other edge, and the convex hull of two crossing edges contain no vertices other than the endpoints of those edges. Then two edges that cross can be replaced by seven that do not cross according to Figure 11. Call the new subgraph a butterfly. If the top two horizontal edges of the butterfly (which are in bold in the figure) are given weight −1 and all other edges of the butterfly and the edges that cross have weight 1, then the operation of replacing the crossing by the butterfly can be reproduced by row and column operations on M(Z). It does not change the determinant if the edges are given suitable weights. Thus, at the expense of more vertices and edges, Z becomes planar.

VI B The Ising model

The partition function of the unmagnetized Ising model on a graph is the following weighted enumeration. Given two numbers a and b, called Boltzmann weights, and given a graph Z, compute the total weight of all functions s (states) from the vertices of Z to the set of spins {↑, ↓}, where the weight of a state s is the product of the weights of the edges, and the weight of an edge is a if the spins of its vertices agree and b if they disagree. In a generalization of the model, a and b can be different for different edges. If a = b = 1 for a given edge in this generalization, the edge can be ignored.

\begin{matrix}↑ \\ ↓ \\ ↑ \end{matrix}

Figure 12: An Ising state and its matching.

If Z is a plane graph, we can make Z triangular, meaning that all faces are triangles, at the expense of adding ignorable edges. Let Z′ be the dual graph with a vertex added in the middle of each edge. Let Z′′ be the edge graph of Z′. Then (exercise) there is a 2-to-1 map from the Ising states of Z to the perfect matchings of Z′′. The weights of Ising states can be matched up to a global factor by assigning weights to edges of Z′′. Thus the Hafnian-Pfaffian method can be used to find the total weight of all Ising states of Z.

More generally, if Z is any plane graph whose vertices have valence 1, 2, or 3, then the number of matchings of the edge graph Z′ of Z is a power of two. Indeed, the set of matchings can always be interpreted as an affine vector space over ℤ/2. A matching of Z′ is equivalent to an orientation of Z such that at each vertex, an odd number of edges are oriented outward (exercise). If the orientations of each individual edge are arbitrarily labelled 0 and 1, the constraints at the vertices are all linear. For example, the number of matchings of the edge graph of a dodecahedron (Section IV D) is a power of two. The bachelorhood vertex [21] for symmetric plane partitions is a similar construction.

VI C Tensor calculus

This section relates determinants of graphs to the formal setting of quantum link invariants [33]. We present no complete mathematical results, only a brief summary of how to discuss determinants of graphs in more algebraic terms. Another class of enumeration problems, planar ice and alternating-sign matrices, are related to the Jones polynomial and other quantum invariants based on the quantum group U_{q}(sl(2)).

The Ising model is an example of a state model, a general scheme where one has a set of atoms, a set of states for each atom, local weights which depend on the states of particular clusters of atoms, and the global weight of a state which is defined as the product of all local weights. (Most weighted enumerations of objects such as matchings and plane partitions can be described as state models.) Many natural state models can be interpreted as tensor expressions. In index notation, one can write an expressions of tensors over a common vector space V such as

A_{c}^{ab}B_{d}^{c}C_{b}^{d} …

Each index may only appear twice, once covariantly (as a subscript) and once contravariantly (as a superscript). Repeated indices are summed. For simplicity, suppose all indices are repeated so that the expression is scalar-valued. Although this description of index notation depends on choosing a basis for V, such a tensor expression is basis-independent. In state model terms, each index is called an atom and the matrix of each tensor is a set of local weights. Note also that there an oriented graph associated to a tensor expression, where each vertex corresponds to a tensor and each edge connecting to vertices corresponds to indices connecting the tensors. A tensor expression is a more versatile form for a state model because arbitrary an arbitrary linear transformation of V extends to transformations of tensors. In particular, V might be a group representation and the tensors might be invariant under the group action.

If Z is a bipartite, trivially weighted graph, then det(Z) has such an interpretation, except that the tensors are invariant under a supergroup action instead of a group action. Recall that a supervector space is a ℤ/2-graded vector space. An algebra structure on such a vector space is supercommutative if it is graded-commutative (odd vectors anticommute with each other, even-graded vectors commute with everything). A supergroup is a group object in the category of supercommutative algebras. It is like a group except that instead of a commutative algebra of real- or complex-valued functions on the group (with multiplication meaning pointwise multiplication), there is a supercommutative algebra A. The group law (in the finite-dimensional case) is expressed by a multiplication operation

m : A^{∗} ⊗ A^{∗} → A^{∗}

on the dual vector space. The particular supergroup of interest to us has the property that both A and A^{∗} are isomorphic to Λ(ℝ), an exterior algebra with one generator x. We consider tensors and tensor expressions over A viewed as a representation of itself.

The space A has an invariant multilinear function

y_{n} : A^{⊗n} → ℝ

given by

a_{1} ⊗ a_{2} ⊗ … ⊗ a_{n} ↦ μ(a_{1}a_{2} … a_{n}),

where the dual vector

μ : A → ℝ

is defined by

μ(1) = 0 μ(x) = 1.

The multilinear function y_{n} can be viewed as an element of (A^{∗})^{⊗n}. Similarly there is a dual tensor

x_{n} ∈ A^{⊗n}

using the algebra structure on A^{∗}. If each black vertex of Z is replaced by a copy of x_{n} and each white vertex by a copy of y_{n} in such a way that there is an index for each edge, then the tensors together form a scalar-valued expression, because each index appears twice and every index is contracted. This scalar-valued expression is exactly det(Z).

VII Plane partitions

Plane partitions are one of the most interesting applications of the permanent-determinant method [21]. A plane partition in a box is a collection of unit cubes in an a × b × c box (rectangular prism) such that below, behind, and to the left of each cube is either another cube or a wall. A plane partition in a box is equivalent to a tiling of a hexagon with sides of length a, b, c, a, b, and c by unit 60^{∘} triangles (Figure 13).

\begin{matrix}c & b & a \\ c & b & a \end{matrix}

Figure 13: A plane partition and a tiling.

Such a lozenge tiling is equivalent to a matching in a hexagonal mesh (technically known as chicken wire) graph Z(a, b, c) (Figure 14).

The total number of plane partitions in an a × b × c box is given by MacMahon’s formula:

N(a, b, c) = \frac{H(a)H(b)H(c)H(a + b + c)}{H(a + b)H(a + c)H(b + c)},  (3)

where

H(n) = (n − 1)!(n − 2)! … 3!2!1!

Figure 14: The graph Z(2, 2, 3) and a matching.

is the hyperfactorial function. One can enumerate plane partitions with symmetry, each corresponding to matchings which are invariant under some group action G on Z(a, b, c). If G acts freely, these are just the matchings of the quotient graph Z(a, b, c)/G. When G does not act freely, there is always a way to modify the quotient graph so that its matchings are equinumerous with the invariant matchings of Z(a, b, c). The number of plane partitions in each symmetry class has a formula similar to equation (3).

Number  Kind  Acronym
N_{3}(a, a, a)  Cyclically symmetric  CSPP
N_{5}(a, b, c)  Self-complementary  SCPP

N_{9}(2a, 2a, 2a)

Cyclically symmetric, self-complementary

CSSCPP

N_{6}(2a, b, b)  Transpose-complement TCPP

N_{8}(2a, 2a, 2a)

Cyclically symmetric, transpose-complement

CSTCPP

Table 2: Plane partitions and their numbers

A plane partition is cyclically symmetric if the corresponding matching is invariant under rotation by 120^{∘}. It is self-complementary if the matching is invariant under rotation by 180^{∘}. It is transpose-complement if the matching is invariant under a color-preserving reflection. The particular symmetry classes of plane partitions based on these symmetries that we will consider are given in Table 2. In the table the parameters of an enumeration N_{i}(a, b, c) refer to the three dimensions of the box. For example N_{6}(2a, b, b) is the number of TCPPs in a 2a × b × b box.

The invariant matchings corresponding to the first three symmetry classes are equivalent to matchings of Z(a, b, c)/G for suitable G. The partitions in the last two symmetry classes correspond to matchings of Z(a, b, c)//G, a graph which is obtained from the quotient graph by deleting those vertices that have a non-trivial stabilizer Figure 15: A deleted quotient graph for TCPPs.

Figure 16: A deleted quotient graph for CSTCPPs.

in G (Figures 15 and 16). In each case let Z_{i}(a, b, c) be the graph corresponding to N_{i}(a, b, c). In the last two cases, some of the vertices are vestigial, meaning that they can only be matched in one way. (These vertices are matched with bold edges in the figures.) Let Z′_{i}(a, b, c) be the graph Z(a, b, c) with vestigial vertices removed.

The q-enumeration N(a, b, c)_{q} of plane partitions is given by the natural q-analogue of equation (3), namely the one where each factorial is replaced by a q-factorial. Here the q-weight of a plane partition is q^{k} if there are k cubes. The q-enumeration is also the determinant of Z(a, b, c) if it is weighted with curvature q in each hexagonal face. Three of the other symmetry classes can also be q-enumerated, but we will consider only the q-enumeration of cyclically symmetric plane partitions, where as with unrestricted plane partitions, the weight of each cube is q.

The six symmetry classes that do involve complementation have no obvious qenumerations, but they do have natural −1 enumerations. In these cases the symmetry group G acts on individual cubes just as it does without complementation. But whereas in the four classes without complementation each orbit of cubes is either filled or empty, in the six classes with complementation each orbit is always half-filled.

Nonetheless, there is a natural move between symmetric plane partitions which replaces half of an orbit of cubes by the opposite half. Any two plane partitions in a given symmetry class differ by either an odd or an even number of moves. This defines a relative sign between them. The corresponding signed enumeration is a natural generalization of q-enumeration with q = −1. We conjecture that there is a product formula for the −1-enumeration of every symmetry class of plane partitions.

Stembridge [37] has found interesting patterns in signed enumerations of cyclically symmetric plane partitions called strange enumerations. In a strange enumeration, the weight of each plane partition is the product of the weights of cubes. Each cube has weight 1 or −1 depending on its position in the box. Consider plane partitions in the box [0, a]^{3} in Cartesian coordinates, and denote each unit cube by the coordinates of the corner farthest away from the origin. We will consider strange enumerations N_{3}(a, a, a)_{s,t,u}, where s is the sign (or weight) of cubes (i, i, i), t is the sign of cubes (i, j, j) with i ≠ j, and u is the sign of cubes (i, j, k) with i, j, and k all different. Similarly, let N(2a, 2b, 2c)_{s,t} be a signed (or weighted) enumeration of unrestricted plane partitions in a 2a × 2b × 2c box, where the cubes (a + i, b + i, c + i) (where i can be positive or negative) have weight s and the other cubes have weight t.

Figure 17: A Penrose-style lozenge tiling.

Finally, let a, b, and c have the same parity. We will consider lozenge tilings of an a, b + 1, c, a + 1, b, c + 1 hexagon with the middle unit triangle removed. Such tilings resemble a Penrose impossible triangle (Figure 17). Let N_{P} (a, b, c) be the number of these and let Z_{P} (a, b, c) be the corresponding graph. There is a product formula for N_{P} (a, b, c) [31] which has been proved by Okada and Krattenthaler [28]. A very short argument has been found by Ciucu for the case b = c [6] and generalized [4].

VII A Various relations

The properties of the permanent-determinant method yield various relations between the enumerations of plane partitions defined above. Many enumerations of plane partitions are round. An integer is round if it is a product of relatively small numbers. A polynomial is round if it is a product of cyclotomic polynomials of low degree. A round enumeration in combinatorics almost always has an explicit product formula.

Rotational symmetry of Z(a, a, a) implies that

N(a, a, a)_{q^{3}} = N_{3}(a, a, a)_{q}N_{3}(a, a, a)_{ωq}N_{3}(a, a, a)_{ω^{2}q},

where ω is a cube root of unity. This relation together with MacMahon’s formula for N(a, a, a)_{q} implies that N_{3}(a, a, a)_{q} is round, but it does not imply the explicit formula for N_{3}(a, a, a)_{q} conjectured by MacDonald and proved by Mills, Robbins, and Rumsey [25].

Rotational symmetry also tells us that

N(a, a, a)_{1,−1} = N_{3}(a, a, a)_{1,−1,−1}
N_{3}(a, a, a)_{ω,−1,−1}
N_{3}(a, a, a)_{ω^{2},−1,−1}.

The factor N_{3}(a, a, a)_{1,−1,−1} is a strange enumeration. This case is entirely analogous to N_{3}(a, a, a)_{q} because we know that N(a, a, a)_{1,−1} is round (see below). Therefore N_{3}(a, a, a)_{1,−1,−1} is round also, but the explicit formula conjectured by Stembridge is still open.

Reflection symmetry in Z(2a, b, b) tells us that

N(2a, b, b) = N_{6}(2a, b, b)N_{6}(2a, b, b)_{2},

and reflection symmetry in Z(2a + 1, b, b) tells us that

N(2a + 1, b, b) = 2N_{6}(2a, b, b)N_{6}(2a, b, b)_{2}.

Here the second factor is a certain 2-enumeration of TCPP’s (a weighting where certain faces have curvature 2). These two relations imply the known formula for N_{6}(2a, b, b) [36].

The method of Section IV C establishes the identities

|N_{1}(2a, 2b, 2c)_{−1,1}| = N_{5}(2a, 2b, 2c)^{2}
|N_{3}(2a, 2a, 2a)_{−1,1,1}| = N_{9}(2a, 2a, 2a)^{2}.

The second identity is one of Stembridge’s strange enumerations. Two other strange enumerations,|N_{3}(2a, 2a, 2a)_{−1,−1,1}| and |N_{3}(2a, 2a, 2a)_{−1,1,−1}|, can be recognized as perfect squares by the same method. However, these enumerations are not round numbers; in general they have large prime factors.

The construction in Section VI A applies to plane partitions as follows: Let Z be the disjoint union of two copies of the plane partition graph Z(a, b, c) with flat weighting. Arrange Z so that most of the horizontal edges of one copy are concentric with hexagons of the other copy, is in Figure 18. Now replace all of the crossings

Figure 18: Two copies of Z(2, 2, 2) overlaid.

by butterflies. Most of the long horizontal edges of the butterflies cancel in pairs (they are multiple edges with opposite weight). The new graph, after a little vertex splitting, is exactly the graph Z(2a, 2b, 2c), but the weighting is no longer flat. Rather it has curvature −1 in every face. Since

det(Z) = N(a, b, c)^{2},

the conclusion is that

N(2a, 2b, 2c)_{−1} = N(a, b, c)^{2}.

This relation is independently a corollary of MacMahon’s q-enumeration of plane partitions. Via Stembridge’s q = −1 phenomenon, it is also related to the enumeration of self-complementary plane partitions. Since the original graph Z could have been given a weighting with indeterminate curvature instead of a flat one, it generalizes to a new relation between generating functions for plane partitions in a 2a × 2b × 2c box and plane partitions in an a × b × c box.

Figure 19: Overlaying Z_{6}(4, 2, 2) and Z′_{6}(4, 3, 3).

Forcing planarity also establishes the identities

N(2a + 1, 2b, 2c)_{−1} = N(a, b, c)N(a + 1, b, c)
N(2a + 1, 2b + 1, 2c)_{−1} = N(a, b + 1, c)N(a + 1, b, c)
N_{6}(4a, 2b, 2b)_{−1} = N_{6}(2a, b, b)^{2}
N_{6}(4a + 2, 2b + 1, 2b + 1)_{−1} = N_{6}(2a, b + 1, b + 1)
N_{6}(2a + 2, b, b)
N_{6}(4a, 2b + 1, 2b + 1)_{−1} = N_{6}(2a, b, b)
N_{6}(2a, b + 1, b + 1).

The last three identities require some manipulations with vestigial vertices. For example, the last identity is derived by overlaying Z_{6}(2a, b, b) and Z′_{6}(2a, b + 1, b + 1) and then forcing planarity (Figure 19).

Figure 20: Two joined copies of N_{P} (1, 1, 1).

A more complicated use of Section VI A establishes the identities

|N(2a, 2b, 2c)_{1,−1}| = N(a, b, c)N(a, b, c)_{−1}^{2}  (4)

and

|N(2a + 1, 2b + 1, 2c + 1)_{1,−1}| = 2N_{P} (a, b, c)^{2}.  (5)

To derive equation (4), take two copies of Z(a, b, c), one flat and one with curvature −1 at the center face, and overlay them as in Figure 18. The first copy has determinant N(a, b, c), while by Section IV C, the second copy has determinant N(a, b, c)_{−1}^{2}. For equation (5), take two copies of Z_{P} (a, b, c) overlaid, but instead of deleting the middle vertices, connect them by an edge of weight 2, as in Figure 20. (In the figure, the connecting edge of weight 2 is in bold.) If each copy of Z_{P} (a, b, c) is weighted so that it would be flat if its middle vertex were removed, then the determinant of the combined graph is 2N_{P} (a, b, c)^{2}, since every matching has to contain the middle edge. But forcing planarity converts this graph to Z(2a + 1, 2b + 1, 2c + 1) with a certain weighting. The determinant of this graph is the left side of equation (5), as desired.

Symmetry of Z(a, a, a) yields the factorization:

N(a, a, a)_{1,−1} = N_{3}(a, a, a)_{1,−1,−1}
N_{3}(a, a, a)_{ω,−1,−1}
N_{3}(a, a, a)_{ω^{2},−1,−1}.

This implies that N_{3}(a, a, a)_{1,−1,−1} is a round number, but does not establish its explicit formula.

Finally, plane partitions in an a × b × c box are a good example of the connection between the permanent-determinant method and the Gessel-Viennot method. Here there are three Gessel-Viennot matrices, of order a × a, b × b, and c × c. They are also known as Carlitz matrices.

Question 2. What is the cokernel of a Kasteleyn matrix for plane partitions in an a × b × c box?

By Gessel-Viennot, if

min(a, b, c) = 1,

the cokernel is cyclic. But if

a = b = c = 2,

the cokernel is the non-cyclic abelian group ℤ/2 × ℤ/10.

VIII Historical note

Kasteleyn [18] gives an excellent exposition of both the Hafnian-Pfaffian method and its application to problems in statistical mechanics. His bibliography constitutes a nearly complete chronicle of the series of papers that led to its discovery. In this section, we give a summary of that chronicle.

Onsager’s solution of the Ising model [29] was the first convincing analysis of any interesting statistical mechanical model of a crystal. However, this paper contained difficult mathematics which left open the possibility of a simpler approach. With this motivation, Kac and Ward [17] announced a new solution eight years later, in which the partition function of the Ising model was expressed as the determinant of a relatively small matrix. The permutation expansion of the determinant was interpreted as a weighted enumeration. This paper attracted the attention of many strong physicists and mathematicians [26], but it contained a serious combinatorial error. Feynman recast the calculations in a correct but incomplete form in unpublished work. He replaced the error by a conjecture which was popularized by Harary, who was organizing a book on applications of graph theory to physics. Sherman proved the conjecture [35] and generalized both it and the Kac-Ward determinant to the Ising model for arbitrary plane graphs. Harary eventually substituted his reference to Sherman’s method by Kasteleyn’s survey [18].

Independently of Sherman, Hurst and Green [14] found a cleaner approach to the square-lattice Ising model in which the partition function is the Pfaffian of the antisymmetric incidence matrix of a nearly planar, weighted graph. The paper of Hurst and Green inspired Fisher and Temperley, and independently Kasteleyn, to enumerate perfect matchings in a square lattice with a special case of the Hafnian-Pfaffian method. Fisher saw that the method also works for finite hexagonal meshes (which already includes some enumerations of current interest). Independently Kasteleyn generalized the method to all plane graphs.

Later Percus [30] saw that since the square lattice is bipartite, the Hafnian-Pfaffian method reduces to the permanent-determinant method. With hindsight it seems that the only reason that Pfaffians and not determinants were used for the square lattice dimer model was that they arise naturally in the planar Ising model. (Mathematical physicists call weighted enumerations of perfect matchings dimer models.) Much later still, Little showed that K_{3,3}-free graphs are Pfaffian [24].

These results seemed to complete the story of the permanent-determinant method, until interest was renewed more recently in the context of enumerative combinatorics [9,10,15,21,22,31,40,45]. In the author’s opinion, one of the nicest new observations about the method is the fact that some of the minors of the inverse of a large Kasteleyn matrix are the probabilities of local configurations of edges [19]. For this reason and others, the method could well have some bearing on arctic circle phenomena in domino and lozenge tilings [8,16]. Another recent development is a satisfactory classification of bipartite Pfaffian graphs [34].

The Gessel-Viennot method was discovered by Gessel and Viennot [11,12] in the context of enumerative combinatorics, and completely independently of the permanentdeterminant method. The method was independently anticipated by Lindström [23] in the context of matroid theory. It has been widely influential in enumeration of plane partitions, even more so than the permanent-determinant method [2–4,7,20,27,28,38]. Yet another determinant variation which is likely related to the permanent-determinant method was recently found by Helfgott and Gessel [13].

References

[1] K. Al-Khnaifes and H. Sachs. Graphs, linear equations, determinants, and the number of perfect matchings. In Contemporary methods in graph theory, pages 47–71. Bibliographisches Inst., Mannheim, 1990.

[2] G. Andrews. Plane partitions V: The T. S. S. C. P. P. conjecture. J. Combin. Theory Ser. A, 66:28–39, 1994.

[3] G. E. Andrews and W. H. Burge. Determinant identities. Pacific J. Math., 158:1–14, 1993.

[4] M. Ciucu. Plane partitions I: A generalization of MacMahon’s formula.

math.CO/9808017.

[5] M. Ciucu. Enumeration of perfect matchings in graphs with reflective symmetry. J. Combin. Theory Ser. A, 77:67–97, 1997.

[6] M. Ciucu. Enumeration of lozenge tilings of punctured hexagons. J. Combin. Theory Ser. A, 83:268–272, 1998.

[7] M. Ciucu and C. Krattenthaler. Plane partitions II: 5 1/2 symmetry classes.

math.CO/9808018.

[8] H. Cohn, M. Larsen, and J. Propp. The shape of a typical boxed plane partition. New York J. Math., 4:137–165, 1998, math.CO/9801059.

[9] N. Elkies, G. Kuperberg, M. Larsen, and J. Propp. Alternating-sign matrices and domino tilings, I. J. Algebraic Combin., 1(2):111–132, 1992.

[10] N. Elkies, G. Kuperberg, M. Larsen, and J. Propp. Alternating-sign matrices and domino tilings, II. J. Algebraic Combin., 1(3):219–234, 1992.

[11] I. Gessel and G. Viennot. Binomial determinants, paths, and hook lengthformulas. Adv. in Math., 58:300–321, 1985.

[12] I. Gessel and G. Viennot. Determinants, paths, and plane partitions. Preprint, 1989.

[13] H. Helfgott and I. M. Gessel. Enumeration of tilings of diamonds and hexagons

with defects. math.CO/9810143.

[14] C. A. Hurst and H. S. Green. New solution of the Ising problem for a rectangular lattice. Journal of Chemical Physics, 33:1059–1062, 1960.

[15] W. Jockusch. Perfect matchings and perfect squares. J. Combin. Theory Ser. A, 67:100–115, 1994.

[16] W. Jockusch, J. Propp, and P. Shor. Random domino tilings and the arctic circle

theorem. math.CO/9801068.

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

[18] P. W. Kasteleyn. Graph theory and crystal physics. In F. Harary, editor, Graph Theory and Theoretical Physics. Academic Press, 1967.

[19] R. Kenyon. Local statistics of lattice dimers. Ann. Inst. H. Poincaré, Probabilités, 33:591–618, 1997.

[20] C. Krattenthaler. Determinant identities and a generalization of the number of totally symmetric self-complementary plane partitions. math.CO/9712202.

[21] G. Kuperberg. Symmetries of plane partitions and the permanent-determinant method. J. Combin. Theory Ser. A, 68(1):115–151, 1994.

[22] G. Kuperberg. Four symmetry classes of plane partitions under one roof. J. Combin. Theory Ser. A, 75(2):295–315, 1996.

[23] B. Lindström. On the vector representations of induced matroids. Bull. London Math. Soc., 5:85–90, 1973.

[24] C. H. C. Little. An extension of Kasteleyn’s method of enumerating the 1-factors of planar graphs. In Combinatorial Mathematics (Proc. Second Australian Conf., Univ. Melbourne, Melbourne, 1973), volume 403 of Lecture Notes in Mathematics, pages 63–72, 1974.

[25] W. H. Mills, D. P. Robbins, and H. Rumsey. Proof of the Macdonald conjecture. Invent. Math., 66:73–87, 1982.

[26] G. F. Newell and E. W. Montroll. On the theory of the Ising model of ferromagnetism. Reviews of Modern Physics, 25:353–389, 1953.

[27] S. Okada. On the generating functions for certain classes of plane partitions. J. Combin. Theory A, 51:1–23, 1989.

[28] S. Okada and C. Krattenthaler. The number of rhombus tilings of a “punctured” hexagon and the minor summation formula. math.CO/9712203.

[29] L. Onsager. Crystal statistics. I. A two-dimensional model with an order-disorder transition. Phys. Rev., 65:117–149, 1944.

[30] J. Percus. One more technique for the dimer problem. Journal of Mathematical Physics, 10:1881–1888, 1969.

[31] J. Propp. Twenty open problems in enumeration of matchings.

math.CO/9801060.

[32] M. Rasetti and T. Regge. Dimer covering and Ising model on lattices homogeneous under the icosahedral group. Riv. Nuovo Cimento, 4:1–34, 1981.

[33] N. Yu. Reshetikhin and V. G. Turaev. Ribbon graphs and their invariants derived from quantum groups. Comm. Math. Phys., 127:1–26, 1990.

[34] N. Robertson, P. D. Seymour, and R. Thomas. Permanents, Pfaffian orientations, and even directed circuits. Preprint, 1997.

[35] S. Sherman. Combinatorial aspects of the Ising model for ferromagnetism I. A conjecture of Feynman on paths and graphs. J. Math. Phys., 1:202–217, 1960.

[36] R. P. Stanley. Symmetries of plane partitions. J. Combin. Theory Ser. A, 43:103– 113, 1986.

[37] J. Stembridge. Strange enumerations of CSPP’s and TSPP’s. Preprint.

[38] J. Stembridge. The enumeration of totally symmetric plane partitions. Advances in Math., 111:227–243, 1995.

[39] J. R. Stembridge. Non-intersecting paths, Pfaffians, and plane partitions. Advances in Math., 83:96–131, 1990.

[40] G. Tesler. Matchings in graphs on non-oriented surfaces. In preparation.

[41] G. Tesler. Private communication.

[42] G. Tesler. The Kekulé covalent bond arrangements of C_{60}. Adv. in Appl. Math., 14:217–225, 1993.

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

[44] T. Van Zandt. Pstricks: PostScript macros for generic TEX. Available from CTAN.

[45] B.-Y. Yang. Two enumeration problems about the Aztec diamonds. PhD thesis, Massachusetts Institute of Technology, 1991.