매트로이드 마이너

매트로이드 이론에서 매트로이드 마이너(영어: matroid minor)는 주어진 매트로이드에서 일부 원소를 “삭제”하거나, 일부 원소를 “축약”하여 얻어지는 매트로이드이다. 그래프 마이너의 일반화이다.

정의

(유한 또는 무한) 매트로이드 $(X,{\mathcal {I}})$가 주어졌다고 하자. 그렇다면, 그 부분 집합 $S\subseteq X$에 대하여,

$X\upharpoonright S=(S,\{I\cap S\}_{I\in {\mathcal {I}}})$

역시 매트로이드를 이룬다.^{:Theorem 3.4} 이를 $X$의 $S$로의 제한이라고 한다. (즉, 이 과정은 $X\setminus S$의 삭제(영어: deletion)이다.)

증명:

${\mathcal {I}}_{S}=\{I\cap S\}_{I\in {\mathcal {I}}}=\{I\in {\mathcal {I}}\colon I\subseteq S\}$로 놓자. (유한 또는 무한) 매트로이드의 네 공리들^:§1.1은 다음과 같이 확인할 수 있다.

• (I1) $\varnothing \in \{I\cap S\}_{I\in {\mathcal {I}}}$: 자명하게 참이다.
• (I2) 만약 $J\subseteq I\in {\mathcal {I}}$일 때, $J\cap S\subseteq I\cap S\in {\mathcal {I}}_{S}$이므로 $J\cap S\in {\mathcal {I}}_{S}$이다.
• (IM) 임의의 $I\in {\mathcal {I}}_{S}\subseteq {\mathcal {I}}$ 및 $I\subseteq T\subseteq S\subseteq X$에 대하여, $\{J\in {\mathcal {I}}_{S}\colon I\subseteq J\subseteq T\}=\{J\in {\mathcal {I}}\colon I\subseteq J\subseteq T\}$는 매트로이드의 공리에 따라 극대 원소를 갖는다.

유일하게 자명하지 않은 것은 공리 (I3)이다.

임의의 $I\in {\mathcal {I}}_{S}$, $J\in \max {\mathcal {I}}_{S}$가 주어졌다고 하자. 그렇다면, (IM) 공리를 사용하여,

$J\subseteq J'\in \max {\mathcal {I}}$

를 찾을 수 있으며, $J\in \max {\mathcal {I}}_{S}$이므로

$J'\cap S=J$

이다.

(I3) 공리를 거듭 사용하여,

$I\subseteq I'\subseteq I\cup J'$

$I'\in \max {\mathcal {I}}$

인 $I'$을 찾을 수 있다.

이제,

$I'\cap S\in \max {\mathcal {I}}_{S}$

$I\subseteq I'\cap S\subseteq I\cup J$

를 보이면 족하다. 이 가운데 유일하게 자명하지 않은 것은 $I'\cap S\subseteq I\cup J$이며, 그 증명은

$I'\cap S\subseteq (I\cup J')\cap S=(I\cap S)\cup (J'\cap S)=I\cup J$

이다.

(유한 또는 무한) 매트로이드 $(X,{\mathcal {I}})$가 주어졌다고 하자. 그렇다면, 그 부분 집합 $S\subseteq X$에 대하여, 쌍대 매트로이드의 제한의 쌍대 매트로이드

$X.S=(X^{*}\upharpoonright S)^{*}=\left(S,\bigcup _{B\in \max {\mathcal {I}}}\operatorname {Pow} (S\setminus B)\right)$

를 정의할 수 있다. ($\operatorname {Pow} (-)$는 멱집합이다.) 이는 매트로이드를 이루며, 이를 $X$의, $S$로의 축약(영어: contraction)하여 얻는 매트로이드라고 한다.^:§3 (즉, 이 과정은 $X\setminus S$의 축약이라고 한다.)

축약과 제한을 거듭 사용하여 얻는 매트로이드

$(X',{\mathcal {I}}')$

$X'\subseteq X$

를 $X$의 마이너라고 한다.

성질

그래프와의 관계

그래프 마이너는 매트로이드 마이너의 특수한 경우이다. 구체적으로, (유한 또는 무한) 그래프 $\Gamma$의 (유한형) 순환 매트로이드를 $\operatorname {M} (\Gamma )$라고 하자.

또한, 임의의 변의 집합

$S\subseteq \operatorname {M} (\Gamma )$

이 주어졌다고 하자.

그렇다면, 다음이 성립한다.

$\operatorname {M} (\Gamma \upharpoonright S)=\operatorname {M} (\Gamma )\upharpoonright S$

$\operatorname {M} (\Gamma .S)=\operatorname {M} (\Gamma ).S$

$\operatorname {M} (\Gamma \sqcup K_{0})=\operatorname {M} (\Gamma )$

즉,

• 그래프에서 $S$에 속하지 않는 변들의 삭제는 순환 매트로이드에서 $S$에 속하지 않는 원소들의 삭제와 같다.
• 그래프에서 $S$에 속하지 않는 변들의 축약은 순환 매트로이드에서 $S$에 속하지 않는 원소들의 축약과 같다.
• 그래프에서, 홑 꼭짓점(아무 변과 결합하지 않는 꼭짓점)의 삭제는 그 순환 매트로이드에 영향을 주지 않는다.

이에 따라, 그래프의 순환 매트로이드의 매트로이드 마이너는 그래프 마이너의 순환 매트로이드이다.

정렬 원순서가 아님

유한 그래프의 그래프 마이너 관계는 정렬 원순서를 이룬다 (로버트슨-시모어 정리). 즉, 유한 그래프의 순환 매트로이드들로 국한하였을 때, 매트로이드 마이너 관계는 정렬 원순서를 이룬다.

그러나 모든 유한 매트로이드의 집합 위에서, 매트로이드 마이너 관계는 정렬 원순서를 이루지 못한다.

참고 문헌

• Geelen, Jim; Gerards, Bert; Whittle, Geoff (2013년 7월). 〈Structure in minor-closed classes of matroids〉 (PDF). Blackburn, Simon R.; Gerke, Stefanie; Wildon, Mark. 《Surveys in combinatorics 2013》. London Mathematical Society Lecture Note Series (영어) 409. Cambridge University Press. 327–362쪽. doi:10.1017/CBO9781139506748.009. ISBN 978-1-107-65195-1. 
• Truemper, Klaus (1992). 《Matroid decomposition》 (영어). Boston: Academic Press. ISBN 0-12-701225-7. MR 1170126. Zbl 0760.05001. 2017년 11월 7일에 원본 문서에서 보존된 문서. 2017년 7월 9일에 확인함. 

외부 링크

• Geelen, Jim (2013년 9월 2일). “Matroids with no M(K₄)-minor”. 《Matroid Union》 (영어).