% First paper on Pfaffians, revised version % accepted on Elec. J. Comb. sent December 98 \documentclass[12pt,fleqn]{article} \usepackage{latexsym} %Definizioni Latex Anna \newtheorem{Definition}{\bf Definition}[section] \newtheorem{Example}[Definition]{\bf Example} \newtheorem{Remark}[Definition]{\bf Remark} \newtheorem{Lemma}[Definition]{\bf Lemma} \newtheorem{Theorem}[Definition]{\bf Theorem} \newtheorem{Corollary}[Definition]{\bf Corollary} \newtheorem{Proposition}[Definition]{\bf Proposition} \textwidth 15.2 cm %************** \textheight 229 mm %************** \oddsidemargin 0 cm %************** \topmargin -\headheight %************** \newcommand{\bform}{\begin{displaymath}} \newcommand{\eform}{\end{displaymath}\smallskip} \newcommand{\beqn}[1]{\begin{equation}\label{#1}} \newcommand{\eeqn}{\end{equation}\smallskip} \newcommand{\beqna}[1]{\begin{eqnarray}\label{#1}} \newcommand{\eeqna}{\end{eqnarray}\smallskip} \newcommand{\beqnan}{\begin{eqnarray*}} \newcommand{\eeqnan}{\end{eqnarray*}\smallskip} \newcommand{\tr}[1]{#1^{\scriptscriptstyle T}} \newcommand{\rif}[1]{(\ref{#1})} \newcommand{\vect}[2]{\left(\begin{array}{c} #1\\#2 \end{array}\right)} \newcommand{\done}{\hfill$\Box$\par} \def\Re{I\!\!R} \def\gt{>} \def\lt{<} \def\sp{\;\;} \def\wug{=^{\!\!\!\!\!^{2}}} \def\wnug{\ne^{\!\!\!\!\!^{2}}} \def\prec{<^{\!\!\!\!\!^{L}}} \def\prece{\le^{\!\!\!\!\!^{L}}} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 6 (1999), \#R6\hfill} \begin{document} \date{} \begin{titlepage} \thispagestyle{empty} \title{\large {\bf On the Theory of Pfaffian Orientations.}\\ {\bf I. Perfect Matchings and Permanents.}} \author{ \thanks {Supported by NATO-CNR Fellowship} \normalsize {\bf Anna Galluccio}\\ {\normalsize Istituto di Analisi dei Sistemi ed} \\ {\normalsize Informatica - CNR}\\ {\normalsize viale Manzoni 30}\\ {\normalsize 00185 Roma}\\ {\normalsize ITALY}\\ {\normalsize galluccio@iasi.rm.cnr.it} \and \thanks{Supported by DONET, GACR 0194 and GAUK 194} \normalsize {\bf Martin Loebl}\\ {\normalsize Department of Applied Mathematics }\\ {\normalsize Charles University}\\ {\normalsize Malostranske n. 25}\\ {\normalsize 118 00 Praha 1}\\ %{\normalsize and University of Waterloo }\\ {\normalsize CZECH REPUBLIC}\\ {\normalsize loebl@kam.ms.mff.cuni.cz} } \maketitle \begin{center} Received May 7, 1998; Accepted October 28, 1998. \end{center} \bigskip \begin{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. \end{abstract} \bigskip \begin{center} {\bf Mathematical Reviews Subject Numbers} 05B35, 05C15, 05A15 \end{center} \end{titlepage} \section{Introduction} The theory of Pfaffian orientations of graphs has been introduced by Kasteleyn \cite{kast,KAST1,KAST2} in early sixties to solve some enumeration problems arising from statistical physics \cite{kw,pw}. He proved fundamental results in the planar case and extended his approach to toroidal grids \cite{KAST2,KAST1,kast}. The case of general toroidal graphs was also considered in an unpublished manuscript by Barahona \cite{b2}. 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\'olya in \cite{Polya}. A graph is a pair $G=(V,E)$ where $V$ is a set of {\it vertices} and $E$ is a set of unordered pairs of elements of $V$, called {\it 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 {\it endvertices} of $e$. We associate with each edge $e$ of $G$ a variable $x_e$ and we let $x=(x_e:e\in E)$. For each $M\subset E$, let $x(M)$ denote the product of the variables of the edges of $M$. A graph $G'=(V',E')$ is called a {\it subgraph} of a graph $G=(V,E)$ if $V'\subset V$ and $E'\subset E$. A {\it 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_jv_{j+1}$, and $v_i\neq v_j$ for $i1$. In order to deduce it we start with another corollary of Theorem~\ref{sgn2}. \begin{Corollary} \label{function} 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\Delta P)$ is a function of $r(D)$ and $t(M_0\Delta P)$ only. Let us denote this function by $\sigma (r(D),t(M_0\Delta P))$. \end{Corollary} \begin{Lemma} \label{sgn22} Let $r=(r_1,\dots,r_{2g})$ and $t=(t_1,\dots,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,\dots,g-1$. Then $$\sigma(r,t)=\prod_{j=0}^{g-1} \sigma(r(j),t(j)).$$ \end{Lemma} {\bf Proof.} By Corollary~\ref{function}, we have that $sgn(D,{\cal C})=sgn(D',{\cal C}')$ if and only if $r(D)=r(D')$ and $t({\cal C})=t({\cal C}')$. This implies that we can restrict ourselves to consider the following case: $G=C_0\cup M_0 \cup {\cal C}$ is a proper $g$-graph, $D$ is a relevant orientation of $G$ such that $r(D)=r$ and ${\cal C}$ consists of a set of vertex-disjoint cycles $C_1,\dots,C_k$ satisfying the following properties: \begin{enumerate} \item each $C_i$ is alternating with respect to the perfect matching $M_0$, \item for each $i,j$ $|E^i_j| \leq 1$, \item for each $i$ there is at most one $j$ such that $|C_j \cap (E^i_1 \cup E^i_2)| \geq 1$, \item for each $C_j$ there is exactly one $i$ such that $C_j$ intersects $E^i_1\cup E^i_2$, \item $t({\cal C})=t$. \end{enumerate} Hence, $$\sigma(r,t)=sgn(D,{\cal C})= \prod_{i=1}^k sgn(D,C_i)= \prod_{i=1}^k sgn(D_i,C_i)$$ where $D_i$ is the restriction of $D$ to $C_0\cup C_i$. Observe that, by Corollary~\ref{toro}, $\sigma(z_1,z_2)=1$ if $z_2=(0,0 )$. Hence, using Corollary~\ref{function}, we have that $\prod_{i=1}^k sgn(D_i,C_i)= \prod_{j=0}^{g-1} \sigma(r^j,t^j)$ as claimed. \done \begin{Theorem} \label{pm} Let $G$ be a proper $g$-graph. Then $${\cal P}(G,x)={\cal L}_g(G,x)=\sum _{i=1}^{4^g} c(r(D_i)) {\cal P}(D_i,M_0)$$ where $D_i$, $i=1,\dots,4^g$, are the relevant orientations of $G$. \end{Theorem} \medskip\noindent {\bf Proof.} Let $P$ be a perfect matching of $G$. In each term ${\cal P}(D_i,M_0)$, the coefficient of $x(P)$ is $sgn(D_i,M_0\Delta P)$. By Corollary~\ref{function}, $sgn(D_i,M_0\Delta P)=\sigma(r(D_i),t(M_0\Delta P))$. Let $${\cal K}_g(t(M_0\Delta P))= \sum _{i=1}^{4^g} c(r(D_i)) \sigma(r(D_i),t(M_0\Delta P))$$ denote the coefficient of $x(P)$ in ${\cal L}_g (G,x)$. To prove the theorem it suffices to prove the following claim: \medskip\noindent {\bf Claim.} {\it ${\cal K}_g(t(M_0\Delta P))=1$ for each $t(M_0\Delta P)$.} \smallskip\noindent The proof of the claim is by induction on $g$. The basis of the induction when $g=1$ is proved in Corollary~\ref{sgn4}. To prove the inductive step we introduce the following notation: if $z$ is a $2g$-dimensional vector then we let $z=(z(0),\dots,z(g-1))$ where $z(i)=(z_{2i+1},z_{2i+2})$. We call two relevant orientations $D$ and $D'$ of $G$ {\it equivalent} if $(r(D)(1),\dots,r(D)(g-1))=(r(D')(1),\dots,r(D')(g-1))$. Clearly, the equivalence classes consist of $4$ elements; let ${\cal R}_1,\dots,{\cal R}_{4^{g-1}}$ be the equivalence classes of the relevant orientations of $G$ and let ${\cal R}_j=\{D^j_1,D^j_2,D^j_3,D^j_4\}$, $j=1,\dots,4^{g-1}$. Finally let $r(D^j_i)(k)=r^j_i(k)$, $k=0,\dots,g-1$ and let $t=t(M_0\Delta P)$. We have that $${\cal K}_g(t)=\sum_{j=1}^{4^{g-1}} \sum_{i=1}^4 c(r(D^j_i))\sigma(r(D^j_i),t).$$ Now, by Lemma~\ref{sgn22}, this equals $$\sum_{j=1}^{4^{g-1}} \sum_{i=1}^4 c(r^j_i(0))c(r^j_i(1),\dots,r^j_i(g-1))\prod_{k=0}^{g-1} \sigma(r^j_i(k),t(k)).$$ By the definition of the equivalence classes, $r^j_1(k)=r^j_2(k)=r^j_3(k)=r^j_4(k)$ for $k\ge 1$ and $j=1,\dots,4^{g-1}$. Hence, we let $r^j_i(k)=r^j(k)$ and write the above summation as: $$\sum_{j=1}^{4^{g-1}} c(r^j(1),\dots,r^j(g-1))\prod_{k=1}^{g-1} \sigma(r^j(k),t(k)) \sum_{i=1}^4 c(r^j_i(0))\sigma(r^j_i(0),t(0))$$. The internal sum equals to 1 for each $j=1,\dots,4^{g-1}$ by the basis step of the induction, and hence, using Lemma~\ref{sgn22} in the external sum, we can write the above summation as $$\sum_{j=1}^{4^{g-1}} c(r^j(1),\dots,r^j(g-1))\sigma((r^j(1),\dots,r^j(g-1)),(t(1),\dots,t(g-1))) =$$ $${\cal K}_{g-1}(t(1),\dots,t(g-1))=1,$$ by the inductive hypothesis for $g-1$. \hfill {\bf End of Claim.} \done \bigskip As a consequence of Theorem~\ref{Kastel} and Theorem~\ref{pm}, we have: \begin{Corollary} \label{pm1} Let $G$ be a proper $g$-graph. Then $s(D_i,M_0)=s(D_j,M_0)$ for each $i,j\in \{1,\dots,4^g\}$ and $${\cal P}(G,x)={\cal L}_g(G,x)=s(D_1,M_0)\sum _{i=1}^{4^g} c(r(D_i)) Pf(A(D_i))$$ where $D_i$, $i=1,\dots,4^g$, are the relevant orientations of $G$. \end{Corollary} \bigskip \begin{Theorem} \label{genus} Let $G$ be a graph embeddable on an orientable surface of genus $g$. Then ${\cal 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$. \end{Theorem} \medskip\noindent {\bf Proof.} As observed in the previous section, any orientable surface ${\cal 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 ${\cal 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\geq 1$, by a path $P_e=(u,e_1,v_1,\dots,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\in 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 ${\cal P}(G',x')={\cal P}(G,x)$. %Let us construct a proper $g$-graph $G'$ as described in Theorem~\ref{Proper}. Now, by Theorem~\ref{pm}, ${\cal P}(G',x')$ may be written as a linear combination of $4^g$ terms $Pf(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 $Pf(A(D'))=Pf(A(D))$ or $Pf(A(D'))=-Pf(A(D))$. We construct $D$ from $D'$ in two steps: \begin{enumerate} \item[1.] delete the edges $e$ of $G'-G$ with $x'_e=0$, \item[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. \end{enumerate} 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\Delta Q)=sgn(D',P'\Delta Q')$ for each pair of perfect matchings $P,Q$ of $G$. The claim now follows from Theorem~\ref{Kastel}. This finishes the proof of the theorem. \done \section{Pfaffian Graphs, Exact Matching, and Permanents} The results of the previous section have interesting algorithmic implications. \begin{Theorem} Let $g$ and $k$ be fixed positive integers. Let ${\cal 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 ${\cal P}(G,x)$ may be determined in polynomial time for $G\in {\cal G}$. \end{Theorem} \medskip\noindent {\bf Proof.} It follows from Theorems~\ref{pm} and \ref{genus} that ${\cal 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 ${\cal P}(D,M)$ and $Pf(A(D))$ may be determined efficiently. Let $M=\{\{i_1j_1\},\dots,\{i_nj_n\}\}$, $i_k