# The Number of Perfect Matchings in Hexagons on the Torus by Pfaffians

Authors: Shouliu Wei; Fuliang Lu; Xiaoling Ke
Journal: Journal of Mathematics
 (2022)

---

## Abstract

LetG be a (molecular) graph. A perfect matching of G is defined as a set of edges which are independent and cover every vertex of G exactly once. In the article, we present the formula on the number of the perfect matchings of two types of hexagons on the torus by Pfaffians.


---

## Body

## 1. Introduction

A hexagonal system, or benzenoid system [1], or honeycomb lattice, is a finite connected subgraph of the infinite hexagonal lattice without cut vertices or non-hexagonal interior faces. Hansen and Zheng [2] and Gutman et al. [3] considered the problem about the normal components of benzenoid systems, respectively.A perfect matching of a (molecular) graphG is defined as a set of edges which are independent and cover every vertex of G exactly once. It is also named as Kekulé structure in organic chemistry and closed-packed dimer in statistical physics, respectively. Denote the number of perfect matchings of G by ΦG. In the 1930s, Cyvin and Lovász et al. [4–6] firstly focused on the problems about the perfect matchings of a graph for two different and unrelated purposes. The number of perfect matchings or Kekulé structures had been widely used in various problems in the chemical fields [4, 7–9]. Cyvin et al. [10–14] discussed the enumeration of Kekulé structures for all kinds of benzenoids. Qian and Zhang presented the number of Kekulé structures for capped armchair nanotubes and capped zigzag nanotubes by transfer matrix method in [15, 16], respectively. Yan et al. [17] further discussed the problem about the perfect matchings for one type of hexagons on a cylinder (cf. Figure 1(a)). Li and Zhang also obtained the number of perfect matchings for two types of hexagons on the cylinder and the Möbius strip in [18] (cf. Figure 1).Figure 1
Two types of hexagons.
(a)(b)LetG=VG,EG and H=VH,EH be two given graphs. Let G×H denote the Cartesian product of G with H, where VG×H=VG×VH,EG×H=u1,u2,v1,v2u1=v1 and u2,v2∈EH, or u2=v2 and u1,v1∈EG. A hexagonal cylinder, which is denoted by HS, of length 2m and breadth n is a graph obtained from the Cartesian product of a 2m-cycle (x1u1x2u2⋯xmum) and an n-path (12⋯n) by deleting the set of edges
(1)xi,2s+1,xi,2s+20≤s≤n−12−1,1≤i≤m∪ui,2s,ui,2s+10≤s≤n−12,1≤i≤m.Letx1u1x2u2⋯xmum and y1v1y2v2⋯ymvm indicate the vertices of two cycles on the upper and lower boundaries of HS, respectively, where xi corresponds to yi and ui corresponds to vii=12,⋯,m (cf. Figure 2). Without loss of generality, suppose further that both ui and vi are the vertices of degree 3. The graphs H2m,n,r, 0≤r≤m/2 and i=12,⋯,m, are from HS by adding all edges xiyi−r, where i−r is modulo m (cf. Figure 2). Clearly, H2m,n,r has a natural embedding on a torus.Figure 2
Plane spanning subgraphs ofH2m,n,r: (a) n is even and (b) n is odd.
(a)(b)The enumerations of perfect matchings ofH2m,n,r are considered by Wu [19] and Klein [20], where Klein gave the formula of the number of perfect matchings of H2m,n,r by transfer matrix method when both n and r are odd or even. In the present article, we consider further the problem involving perfect matchings of H2m,n,r by crossing orientation given by Tesler and the plane model of a graph.


## 2. Pfaffian Orientation

LetG=VG,EG be an undirected graph, where VG=1,2,3,⋯,2p is the vertex set of G. Let each edge i,j of a graph G have a weight denoted by ωij. And the weight ωij=1 for all edges in each unweighted graph. Suppose that G⟶ is an arbitrary orientation of G. If the direction of an edge i,j in G⟶ is from the vertex i to vertex j, then i,j denotes the arc of G⟶ and the set of all the arcs of it is denoted by EG⟶. Denote the skew adjacency matrix of G⟶ by AG⟶. And it is defined as
(2)AG⟶=aij2p×2p,where
(3)aij=ωij,ifi,j∈EG⟶;−ωij,ifj,i∈EG⟶;0,otherwise.Suppose thatM=j1,j1′,⋯,jp,jp′ is a perfect matching. Then the signed weight of the perfect matching M is
(4)ωM=sgn12⋯2p−12pj1j1′⋯jpjp′⋅aj1j1′⋯ajpjp′,where
(5)sgn12⋯2p−12pj1j1′⋯jpjp′=1,ifthepermutationiseven;−1,ifthepermutationisodd.One can define the Pfaffian of the matrixA as
(6)PfA=∑MωM,where M is over all perfect matchings of G.Theorem 1 ([21]).
IfA=aij2p×2p is a skew symmetric matrix, then
(7)detA=PfA2.For the perfect matchingM, denote its signed weight by ωM. One can think the sign of ωM is just the sign of the perfect matchingM. For an orientation G⟶ of a graph, if the signs of its all perfect matchings are the same, then the orientation is a Pfaffian orientation of G. If a graph has a Pfaffian orientation, then the graph is named to be Pfaffian.Theorem 2 ([6]).
Let a graphG be Pfaffian. If G⟶ is a Pfaffian orientation of G, then
(8)ΦG=PfAG⟶=detAG⟶.
Kasteleyn [22] presented the Pfaffian orientations for planar graphs and also interpreted that the perfect matchings of a graph which is embedded on a surface with genus g can be computed as a linear combination of 4g Pfaffians of the graph. Galllucio and Loebl [23], and Tesler [24] proved Kasteleyn’s conclusion, independently. There are some related results about using Pfaffian to enumerate perfect matchings in the references [17, 25–31].


## 3. Plane Model onH2m,n,r

LetP denote a 4-polygon with four sides p1,p2,p1′,p2′. Suppose that G is a graph embedded on a torus. A drawing of a graph G is defined as a plane model of G, in which if all the edges of the graph G could be divided into E0,E1 and E2, and not only the subgraph induced by E0 is a spanning plane graph, which wholly contained inside P, but also the edges in E1 and E2 from the sides pj to pj′ of P do not cross.Noting thatH2m,n,r is a graph which may be embedded on a torus, now we can give a plane model of H2m,n,r by the definition above-mentioned such that the edges of H2m,n,r are separated into E0,E1 and E2. Moreover, the subgraph induced by E0 is a spanning plane graph. The spanning plane graph is wholly contained inside P, and its edges in E1 and E2 from the sides pj and pj′ of P do not cross (cf. Figure 2). If n is odd, a plane model of H2m,n,r is shown as in Figure 3(b). If n is even, a plane model of H2m,n,r is shown as in Figure 4(b). It is obvious that every edge in E1 crosses each every in E2 exactly once. For simplicity, suppose that 1,2,⋯,2mn are 2mn vertices of H2m,n,r and EH2m,n,r denote the edge set. Then E0,E1 and E2 are represented as the followings:
(1)
Ifn is even, then we have
(9)E1=2t−1n+1,2tnt=1,2,⋯,m;E2=2t−2n+1,2m−2r+2t−2n+2t=1,2,⋯,r∪h,2m−1n+hh=1,2,⋯,n;E0=EH2m,n,r/E1∪E2.(2)
Ifn is even, then we have
(10)E1=2t−1n+1,2tnt=1,2,⋯,m;E2=2t−2n+1,2m−2r+2t−1n+2t=1,2,⋯,r∪h,2m−1n+hh=1,2,⋯,n;E0=EH2m,n,r/E1∪E2Figure 3
H2m,n,r embedded on a torus and a corresponding plane model, where n is odd.
(a)(b)Figure 4
H2m,n,r embedded on a torus and a corresponding plane model, where n is even.
(a)(b)An orientation of a graph embedded on a torus in a plane model isthe crossing orientation if it conforms to the rule of cross orientation in reference [24]. For the graph G which is embedded on torus, let Xx1,x2 be its skew adjacent matrix, with the edges in E0 having weight 1 and the edges in Ej having weight xjj=1,2. A formula computing the number for perfect matchings in G was presented by Tesler [24]:
(11)ΦG=12PfX1,1+PfX−1,1+PfX1,−1−PfX−1,−1.Theorem 3 ([24]).
(a)
A graph may be oriented such that every perfect matchingM has sign
(12)ωM=ω0−1κM,where the constant ω0=±1 could be explained as the sign of a perfect matching without crossing edges if the edges exist, and κM denotes the number of times edges in M cross.
(b)
An orientation of a graph satisfies (a) if and only if the orientation is a crossing orientationAccording to the crossing orientation by Tesler, one crossing orientation ofH2m,n,r where n is even or n is odd is indicated in Figures 5 and 6. Figure 5(a) and Figure 5(b) give an orientations of all the edges E0∪E1 and E0∪E2 when n is even, respectively. Figures 6(a) and 6(b) give the orientations of the edges E0∪E1 and E0∪E2 when n is odd, respectively.Figure 5
A crossing orientation ofH2m,n,r, where n is even.
(a)(b)Figure 6
A crossing orientation ofH2m,n,r, where n is odd.
(a)(b)


## 4. The Sign Weights of Perfect Matchings ofH2m,n,r

Let the weight of edge ofE0 in H2m,n,r be 1. Suppose that x and y are the weight of edge of E1 (Referring to Figures 5(a) and 6(a)) and E2 (Referring to Figures 5(b) and 6(b)) in H2m,n,r, respectively. Let Xx,yx,y=±1 be the skew adjacency matrix of H2m,n,r if n is even and Yx,yx,y=±1 the skew adjacency matrix of H2m,n,r if n is odd. To determine the sign of Pfaffians PfXx,y and PfYx,y, the perfect matchings in H2m,n,r are distinguished into four classes. The perfect matchings belonging to class 1 are those that have odd number of edges both in E1 and in E2. The perfect matchings belonging to class 2.have odd number of edges inE1 and even number of edges in E2. The perfect matchings belonging to class 3 have even number of edges in E1 and odd number of edges in E2. The perfect matchings belonging to class 4 have even number of edges both in E1 and in E2. Clearly, κM is always even, where the perfect matching M lies in three classes other than class 1.It is convenient to consider the case wheny=±1. For simplicity, let x and x2 denote the odd power and even power, respectively. In light of the method deciding the sign of perfect matchings by Lu, Zhang and Lin [29], we also can obtain the sings of all the perfect matchings in H2m,n,r. If y=1, the signs of perfect matchings in three classes other than class 1 are always positive by Theorem 3. If y=−1, the signs of perfect matchings in three classes other than class 3 are always positive by Theorem 3 because that the perfect matching belonging to class 1 contains an odd of number edges in E2 and κM is always even. Therefore, we can decide the sign weights of all the perfect matchings of H2m,n,r shown as in Table 1.Table 1
The sign weights of perfect matchings inH2m,n,r.
ClasssThe signs of the perfect matchingsx,y=1x,y=−11−xx2xx3x2−x24x2x2From Table1, we can observe that the signs of perfect matchings belonging to classes 3 and 4 when y=1 are always positive and the signs of perfect matchings in classes 1 and 2 when y=1 are always positive. Then by formula (11) we have the following result.Lemma 4.
The number for perfect matchings inH2m,n,r is equal to the sum of the number for perfect matchings belonging to classes 3 and 4 when y=1 and that belonging to classes 1 and 2 when y=−1.


## 5. Perfect Matchings ofH2m,n,r

Suppose thatV is a skew block circulant matrix or block circulant matrix as follows:
(13)V=V0V1⋯Vm−1−Vm−1V0⋯Vm−2⋮⋮⋱⋮−V1−V2⋯V0or(14)V=V0V1⋯Vm−1Vm−1V0⋯Vm−2⋮⋮⋱⋮V1V2⋯V0.Then its determinant(15)detV=∏t=0m−1detJt,where
(16)Jt=V0+ωtV1+ωt2V2+⋯+ωtm−1Vm−1ωt=cos2tπm+isin2tπm,ifVisablockcirculantmatrix;cos2t+1πm+isin2t+1πm,ifVisaskewblockcirculantmatrix.LetH⟶m,2n,r be a crossing orientation of the plane model of H2m,n,r as shown in Figures 5 and 6. We can obtain the Pfafian of the matrix corresponding H⟶m,2n,r by formula (11) and Theorem 1. Consequently, an expression computing the number for perfect matchings in H⟶m,2n,r can be obtained by formula (11).Theorem 5.
Ifn is even, then
(17)ΦH2m,n,r=fx,1+fx,−1,where fx,1 and fx,−1 denote the sum of coefficients of even terms in PfXx,1=detXx,1 and the sum of coefficients of odd terms in PfXx,−1=detXx,−1, respectively; φt=2t+1π/m and θt=2tπ/m;
(18)detXx,1=∏t=0m−1−1n/22ncosφt−1n−2n/2−1n/2+1cosφt−1n/2−1n/2cosrφt+isinrφt+cosrφt−isinrφtx+x2and
(19)detXx,−1=∏t=0m−1−1n/22ncosθt−1n−2n/2−1n/2+1cosθt−1n/2−1n/2cosrθt+isinrθt+cosrθt−isinrθtx+x2.Proof.
Recall thatH⟶m,2n,r is a crossing orientation in the plane model of H2m,n,r. Then the elements of XH⟶m,2n,r which can be read off from Figure 5 have the following form when n is even:
(20)XH⟶m,2n,r=Xx,y=Xijx,y,where Xijx,y is the n×n matrix. If i≤j,
(21)Xijx,y=Ax,ifj=i,i=1,2,⋯,m−1,m;B,ifj=i+1,i=1,2,⋯,m−2,m−1;C,ifj=i+r,i=1,2,⋯,m−r−1,m−r;Cy,ifj=i+m−r,i=1,2,⋯,r−1,r;By,ifi=1,j=m;02n,others.
Ifi>j, then Xij=−XjiT (XjiT is the transpose of Xij). Let Aii=1,2,3,4 be an n×n matrix as follows:
(22)A1=000000⋯00000000⋯00000100⋯0000−1000⋯00000001⋯000000−10⋯00⋮⋮⋮⋮⋮⋮⋱⋮⋮000000⋯01000000⋯−10,A4=000⋯00x001⋯0000−10⋯000⋮⋮⋮⋱⋮⋮⋮000⋯010000⋯−100−x00⋯000,A2=−10⋯0001⋯00⋮⋮⋱⋮⋮00⋯−1000⋯01,A3=−A2.
Then the matricesAx,B,C,By and Cy can be expressed by the following forms:
(23)and
(24)
Let02n be a 2n×2n matrix. If y=1, then the matrix of H⟶m,2n,r=Xx,y is a skew block circulant matrix, i.e.,
(25)Xx,1=scircAx,B,02n,⋯,02n⏞r−2,C,02n,⋯,02n,CT,02n,⋯,02n⏞r−2,BT.
Ify=−1, then the skew adjacency matrix of H⟶m,2n,r=Xx,y is a block circulant matrix, i.e.,
(26)Xx,−1=scircAx,B,02n,⋯,02n⏞r−2,C,02n,⋯,02n,−CT,02n,⋯,02n⏞r−2,−BT.
Therefore by formula (15) we obtain that
(27)detBx,y=∏t=0m−1detJt,where
(28)Jt=Ax+ωtB−ωt−1BT+ωtrC−ωt−rCT(29)ωt=cos2tπm+isin2tπm,ify=−1;cos2t+1πm+isin2t+1πm,ify=1.
Now we turn to calculate the determinantdetJt of Jt. By formula (28), we have
(30)detJt=J1J2J3J4,where
(31)J1=0ωt−r00⋯0x−ωt−r000⋯000001⋯0000−10⋱⋮⋮⋮⋮⋮⋱⋯⋮⋮0000⋯010000⋯−10,J4=000⋯00x001⋯0000−10⋯000⋮⋮⋮⋱⋮⋮⋮000⋯010000⋯−100−x00⋯000,J1=−1+ωt−1000⋯0001−ωt−100⋯0000−1+ωt−10⋯000001−ωt−1⋱⋮⋮⋮⋮⋮⋱⋯⋮⋮0000⋯−1+ωt−100000⋯01−ωt−1and
(32)J3=1−ωt−1000⋯000−1+ωt−100⋯00001−ωt−10⋯00000−1+ωt−1⋱⋮⋮⋮⋮⋮⋱⋯⋮⋮0000⋯1−ωt−100000⋯0−1+ωt−1.
It is convenient to calculate that we adjust appropriately the order of labeling for the vertices ofH2m,n,r such that the determinant detJt turn out to be the following:
(33)detJt=0ωt−r−1+ωt−1−ωt−r01−ωt−1−1+ωt01−101−ωt−1+ωt−101⋱⋱⋱0−x1−ωtx0=−xωtr−1−ωt−1n/21−ωtn/2−xωt−r+1−ωt−1n/2ωt−1n/2=−1n/2ωt+ωt−1−2n/2−xωtrωt+ωt−1−2n/2−xωt−r.
Letφt=2t+1π/m and θt=2tπ/m. Then it is not difficult to obtain the expressions of ωt,ωt−1 and ωt+ωt−1 when y=1 and y=−1 by formula (29). Thus we have the determinant detJt if y=1, i.e.,
(34)detJt=−1n/22ncosφt−1n−2n/2−1n/2+1cosφt−1n/2−1n/2cosrφt+isinrφt+cosrφt−isinrφtx+x2.
Ify=−1, then we have
(35)detJt=−1n/22ncosθt−1n−2n/2−1n/2+1cosθt−1n/2−1n/2cosrθt+isinrθt+cosrθt−isinrθtx+x2.
Consequently, by formula (27) we have
(36)detXx,1=∏t=0m−1detJt=∏t=0m−1−1n/22ncosφt−1n−2n/2−1n/2+1cosφt−1n/2−1n/2cosrφt+isinrφt+cosrφt−isinrφtx+x2and
(37)detXx,−1=∏t=0m−1detJt=∏t=0m−1−1n/22ncosθt−1n−2n/2−1n/2+1cosθt−1n/2−1n/2cosrθt+isinrθt+cosrθt−isinrθtx+x2.
Note thatx and x2 in Table 1 denote the odd power and even power of x, respectively. Thus the number for perfect matchings in H2m,n,r is equal to the sum of coefficients of even terms in PfXx,1=detXx,1 and coefficients of odd terms in PfXx,−1=detXx,−1 by Lemma 4 and Theorem 2. Consequently, we get a expression for the number for perfect matchings in H2m,n,r by detXx,1, detXx,−1 and Theorem 1 when n is even.Theorem 6.
Ifn is odd, then
(38)ΦH2m,n,r=gx,1+gx,−1,where gx,1 and gx,−1 denote the sum of coefficients of even terms in PfYx,1=detYx,1 and the sum of coefficients of odd terms in PfYx,−1=detYx,−1, respectively; φt=2t+1π/m and θt=2tπ/m;
(39)detYx,1=∏t=0m−1−2n+1/2cosφt−1n+1/2+−2n−1/2cosφt−1n−1/2cosrφt−2cosr−1φtx+x2detYx,−1=∏t=0m−1−2n+1/2cosθt−1n+1/2+−2n−1/2cosθt−1n−1/2cosrθt−2cosr−1θtx+x2.Proof.
LetYx,y=YH⟶2m,n,r be the skew adjacent matrix which elements can be read off from Figure 6. By the same calculation process in Theorem 1, we have the results as follows:
Ify=1, then detJt is expressed by
(40)detJt=−2n+1/2cosφt−1n+1/2−−1n+1/22n−1/2cosφt−1n−1/2cosrφt−2cosr−1φtx+x2.
Ify=−1, then detJt is expressed by
(41)detJt=−2n+1/2cosθt−1n+1/2−−1n+1/22n−1/2cosθt−1n−1/2cosrθt−2cosr−1θtx+x2.
Consequently, by formula (27) we have
(42)detYx,1=∏t=0m−1detJt=∏t=0m−1−2n+1/2cosφt−1n+1/2−−1n+1/22n−1/2cosφt−1n−1/2cosrφt−2cosr−1φtx+x2and
(43)detYx,−1=∏t=0m−1detJt=∏t=0m−1−2n+1/2cosθt−1n+1/2−−1n+1/22n−1/2cosθt−1n−1/2cosrθt−2cosr−1θtx+x2.
Thus we get an expression of the number for perfect matchings inH2m,n,r by detYx,1, detYx,−1 and Theorem 1 when n is odd.



---

*Source: 4120166-2022-09-21.xml*