파프 방향

틀:위키데이터 속성 추적 그래프 이론에서 파프 방향(Pfaff方向, 틀:Llang)은 그래프 위의 완벽 부합의 수를 쉽게 계산할 수 있게 하는 유향 그래프 구조이다.

정의

그래프 $\mathrm{\Gamma }$ 위의 유향 그래프 구조를 그래프의 방향(틀:Llang)이라고 한다. $\mathrm{\Gamma }$의 방향은 부분 집합

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

$\{\{u,v\}:(u,v)\in D\}=\mathrm{E}(\mathrm{\Gamma })$

로 표시된다.

홀수 순환

다음이 주어졌다고 하자.

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

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

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

이라면, $C$를 $D$-홀수 순환(틀:Llang)이라고 한다.

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

부합의 부호

다음이 주어졌다고 하자.

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

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

$\{(v_1,v_2),(v_3,v_4),\dots ,(v_{2n-1},v_{2n})\}$

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

${\mathrm{sgn}}_D(M)=\mathrm{sgn}\left(\begin{array}{ccccc}1& 2& \cdots & 2n-2& 2n\\ v_1& v_2& \cdots & v_{2n-2}& v_{2n}\end{array}\right)\in \{+1,-1\}$

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

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

파프 방향

다음이 주어졌다고 하자.

• 그래프 $\mathrm{\Gamma }$
• $\mathrm{\Gamma }$의 방향 $D$

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

${\mathrm{sgn}}_D(M)={\mathrm{sgn}}_D(M^{\prime })$

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

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

• 유한 그래프 $\mathrm{\Gamma }$
• $\mathrm{\Gamma }$의 방향 $D_1,\dots ,D_k$
• 유리수 ${\alpha }_1,\dots ,{\alpha }_k$

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

${\alpha }_1{\mathrm{sgn}}_{D_1}(M)+\cdots +{\alpha }_k{\mathrm{sgn}}_{D_k}(M)=1$

이라면,

$(D_i,{\alpha }_i{)}_{1\le i\le k}$

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

성질

완벽 부합의 수

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

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

은 다음과 같다.

${\mathrm{Z}}_{\mathrm{\Gamma }}(1,0)=|\sum _{i=1}^k{\alpha }_i\mathrm{Pf}(\mathrm{Inc}(\mathrm{\Gamma },D_i))|$

여기서

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

  $⟨u|\mathrm{Inc}(\mathrm{\Gamma },D)|v⟩=\{\begin{array}{cc}1& (u,v)\in D\\ -1& (v,u)\in D\\ 0& (u,v),(v,u)\in ̸D\end{array}(u,v\in \mathrm{V}(\mathrm{\Gamma }))$

카스텔레인 방향

다음이 주어졌다고 하자.

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

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

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

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

${\alpha }_i=\pm 2^{-g}$

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

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

역사

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

참고 문헌

• 틀:서적 인용
• 틀:저널 인용
• 틀:서적 인용

외부 링크

• 틀:웹 인용