파프 방향

그래프 이론에서 파프 방향(Pfaff方向, 영어: Pfaffian orientation)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.

정의

그래프 $\Gamma$ 위의 유향 그래프 구조를 그래프의 방향(영어: orientation)이라고 한다. $\Gamma$의 방향은 부분 집합

$D\subseteq \operatorname {V} (\Gamma )\times \operatorname {V} (\Gamma )$

$\{\{u,v\}\colon (u,v)\in D\}=\operatorname {E} (\Gamma )$

로 표시된다.

홀수 순환

다음이 주어졌다고 하자.

• 유향 그래프 $(\Gamma ,D)$
• $\Gamma$ 속의 (꼭짓점과 변이 겹치지 않는) 짝수 길이의 순환 $C=(v_{0},v_{1},\dotsc ,v_{2n-1},v_{2n}=v_{0})$

만약 $C$를 (시계 방향 또는 반시계 방향으로) 순회(巡廻)할 때, $D$와 일치하는 방향으로 순회되는 변이 홀수 개라면, 즉

$2\nmid |\{i\in \mathbb {Z} /(2n)\colon (v_{i},v_{i+1})\in D\}|$

이라면, $C$를 $D$-홀수 순환(영어: $D$-oddly oriented cycle)이라고 한다.

($C$의 길이가 짝수이므로, $C$의 순회 방향은 상관이 없다.)

부합의 부호

다음이 주어졌다고 하자.

• 유한 그래프 $\Gamma$
• $\Gamma$의 방향 $D\subseteq \operatorname {V} (\Gamma )^{2}$
• $\Gamma$의 완벽 부합 $M\subseteq \operatorname {E} (\Gamma )$
• $\operatorname {V} (\Gamma )$ 위의 임의의 전순서. 이에 따라, $\Gamma$의 꼭짓점 집합이 $\{1,2,\dotsc ,2n\}$이라고 여길 수 있다.

이제, $M$의 원소들이 (임의의 순서로)

$\{(v_{1},v_{2}),(v_{3},v_{4}),\dotsc ,(v_{2n-1},v_{2n})\}$

이라고 하자. 그렇다면, $M$의 $D$-부호는 다음과 같다.

$\operatorname {sgn} _{D}(M)=\operatorname {sgn} {\begin{pmatrix}1&2&\dotsm &2n-2&2n\\v_{1}&v_{2}&\dotsm &v_{2n-2}&v_{2n}\end{pmatrix}}\in \{+1,-1\}$

여기서 우변은 순열의 부호, 즉 군 준동형 $\operatorname {sgn} \colon \operatorname {Sym} (n)\to \operatorname {Cyc} (2)=\{\pm 1\}$이다.

이 값은 $M$의 원소들의 전순서에 의존하지 않지만, 물론 $\operatorname {V} (\Gamma )$ 위의 전순서에는 의존한다.

파프 방향

다음이 주어졌다고 하자.

• 그래프 $\Gamma$
• $\Gamma$의 방향 $D$

이제, $\operatorname {V} (\Gamma )$ 위에 임의의 전순서를 부여하였을 때, 만약 $\Gamma$ 위의 임의의 두 완벽 부합 $M$, $M'$에 대하여

$\operatorname {sgn} _{D}(M)=\operatorname {sgn} _{D}(M')$

이라면, $D$를 $\Gamma$의 파프 방향이라고 한다.

보다 일반적으로, 다음이 주어졌다고 하자. 다음이 주어졌다고 하자.

• 유한 그래프 $\Gamma$
• $\Gamma$의 방향 $D_{1},\dotsc ,D_{k}$
• 유리수 $\alpha _{1},\dotsc ,\alpha _{k}$

만약 $\operatorname {V} (\Gamma )$에 임의의 전순서를 부여하였을 때, 임의의 완벽 부합 $M\subseteq \operatorname {E} (\Gamma )$에 대하여,

$\alpha _{1}\operatorname {sgn} _{D_{1}}(M)+\dotsb +\alpha _{k}\operatorname {sgn} _{D_{k}}(M)=1$

이라면,

$(D_{i},\alpha _{i})_{1\leq i\leq k}$

를 $\Gamma$ 위의 $k$-파프 방향이라고 한다.

성질

완벽 부합의 수

유한 그래프 $\Gamma$ 위의 $k$-파프 방향 $(D_{i},\alpha _{i})_{1\leq i\leq k}$이 주어졌다고 하자. 그렇다면, $\Gamma$의 완벽 부합의 수

$\operatorname {Z} _{\Gamma }(1,0)$

은 다음과 같다.

$\operatorname {Z} _{\Gamma }(1,0)=\left|\sum _{i=1}^{k}\alpha _{i}\operatorname {Pf} \left(\operatorname {Inc} (\Gamma ,D_{i})\right)\right|$

여기서

• $\operatorname {Pf} (-)$은 짝수 크기 반대칭 행렬의 파피안이다.
• $\operatorname {Inc} (\Gamma ,D)$는 유향 그래프 $(\Gamma ,D)$의 부호 인접 행렬이다. 즉, 다음과 같다.

  $\langle u|\operatorname {Inc} (\Gamma ,D)|v\rangle ={\begin{cases}1&(u,v)\in D\\-1&(v,u)\in D\\0&(u,v),(v,u)\not \in D\end{cases}}\qquad (u,v\in \operatorname {V} (\Gamma ))$

카스텔레인 방향

다음이 주어졌다고 하자.

• 유한 유향 그래프 $(\Gamma ,D)$
• 콤팩트 유향 곡면 $\Sigma \cong (\mathbb {T} ^{2})^{\#g}$. 그 종수가 $g\in \mathbb {N}$라고 하자.
• 매장 $\Gamma \hookrightarrow \Sigma$. 이에 따라, $(\Sigma ,\Gamma )$는 유한 CW 복합체를 이룬다. (즉, $\Gamma \setminus \Sigma$는 유한 개의 2차원 열린 공들의 분리합집합이다.)

그렇다면, 만약 다음 조건이 성립한다면, $D$를 카스텔레인 방향(Kasteleyn方向, 영어: Kasteleyn orientation)이라고 한다.

• $(\Sigma ,\Gamma )$의 임의의 2-세포의 경계 $C\subseteq \Gamma$은 $D$-홀수 순환이다.

$(\Sigma ,\Gamma )$ 위의 카스텔레인 방향들은 $\Sigma$ 위의 세타 지표, 즉 스핀 구조와 표준적으로 일대일 대응한다. 이에 따라, $(\Sigma ,\Gamma )$ 위에는 $4^{g}$개의 카스텔레인 방향들이 존재하며, 이들에 적절한

$\alpha _{i}=\pm 2^{-g}$

계수를 부여할 경우 이들은 $4^{g}$-파프 방향을 이룬다.

특히, $g=0$일 경우, 임의의 평면 그래프 위의 카스텔레인 방향은 (1-)파프 방향을 이룬다. 이에 따라, 모든 평면 그래프는 파프 방향을 갖는다.

역사

피터르 빌럼 카스텔레인(네덜란드어: Pieter Willem Kasteleyn, 1924~1996)이 도입하였다. “파프 방향”이라는 용어는 요한 프리드리히 파프의 이름을 딴 것이다. 파프는 파피안을 도입하였는데, 파프 방향의 부호 인접 행렬의 파피안으로 완벽 부합의 수를 계산할 수 있기 때문에 이와 같은 이름이 붙었다.

참고 문헌

• Thomas, Robin (2007). 〈A survey of Pfaffian orientations of graphs〉 (PDF). 《Proceedings of the International Congress of Mathematicians, Madrid, August 22–30, 2006. Volume Ⅲ. Invited lectures》 (영어). 963–984쪽. doi:10.4171/022-3/47. ISBN 978-3-03719-022-7. Zbl 1101.05054. 
• Cimasoni, David (2014). “The geometry of dimer models”. 《Winter Braids Lecture Notes》 (영어) 1: 2. arXiv:1409.4631. Bibcode:2014arXiv1409.4631C. doi:10.5802/wbln.3. 
• Nguyen, Jeanette (2008년 5월 15일). 《Perfect matchings and Kasteleyn orientation》 (PDF) (영어). 학사 학위 논문 (지도 교수 Dion Gijswijt). 암스테르담 대학교. 2019년 1월 10일에 원본 문서 (PDF)에서 보존된 문서. 2017년 6월 28일에 확인함. 

외부 링크

• Schwartz, Rich (2013년 4월 8일). “Kasteleyn’s formula for perfect matchings” (PDF) (영어).