매트로이드

조합론에서 매트로이드(영어: matroid 메이트로이드^[*])는 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이다. 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다.

정의

매트로이드의 개념은 다양하게 정의될 수 있지만, 이 정의들은 서로 동치이다.

독립 집합을 통한 정의

매트로이드 $(E,{\mathcal {I}})$는 다음과 같은 데이터로 구성된다.

• 집합 $E$
• 집합족 ${\mathcal {I}}\subseteq \operatorname {Pow} (E)$. 그 원소를 독립 집합(獨立集合, 영어: independent set)이라고 하며, 독립 집합이 아닌 $E$의 부분 집합을 종속 집합(從屬集合, 영어: dependent set)이라고 한다.

이 데이터는 다음 공리들을 만족시켜야 한다.^:§1.1

• (공집합의 독립성) 공집합은 독립 집합이다. 즉, $\varnothing \in {\mathcal {I}}$이다.
• (유전성 영어: hereditary property) 독립 집합의 부분집합은 독립이다. 즉, 만약 $B\subseteq A\in {\mathcal {I}}$라면 $B\in {\mathcal {I}}$이다.
• (추가성 영어: augmentation property) 만약 $A,B\in {\mathcal {I}}$이며, $A$는 ${\mathcal {I}}$의 극대 원소이지만 $B$는 ${\mathcal {I}}$의 극대 원소가 아니라면, $B\cup \{a\}\in {\mathcal {I}}$인 $a\in A\setminus B$가 존재한다.
• (국소적 극대 독립 집합의 존재) 만약 ${\mathcal {I}}\ni A\subset B\subset E$라면, 닫힌 구간 ${\mathcal {I}}\cap [A,B]=\{S\in {\mathcal {I}}\colon A\subseteq S\subset B\}$는 극대 원소를 갖는다.

만약 $E$가 유한 집합이라면, 마지막 조건은 자동적으로 성립된다.

기저를 통한 정의

매트로이드 $(E,{\mathcal {B}})$는 다음과 같은 데이터로 구성된다.

• 집합 $E$
• 집합족 ${\mathcal {B}}\subseteq \operatorname {Pow} (E)$. 그 원소를 기저(基底, 영어: basis)라고 하며, 기저의 부분 집합을 독립 집합이라고 한다.

이는 다음 조건들을 만족시켜야 한다.^:§1.2

• ${\mathcal {B}}\neq \varnothing$
• (추가성) 임의의 $B,B'\in {\mathcal {B}}$ 및 $x\in B\setminus B'$에 대하여, 다음 조건을 만족시키는 $x'\in B'\setminus B$가 항상 존재한다.

  $(B\setminus \{x\})\cup \{x'\}\in {\mathcal {B}}$

• (국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 기저 $B\in {\mathcal {B}}$ 및 독립 집합 $I\subseteq B\cap E'$에 대하여, 다음 두 조건을 만족시키는 기저 $B'\in {\mathcal {B}}$ 및 독립 집합 $I'\subseteq B'$이 존재한다.
  • $I\subseteq I'\subseteq B'\in {\mathcal {B}}$
  • 임의의 $I'\subseteq C\in {\mathcal {B}}$에 대하여, $(E'\setminus I')\cap C=\varnothing$이다.

회로를 통한 정의

매트로이드 $(E,{\mathcal {C}})$는 다음과 같은 데이터로 주어진다.

• 집합 $E$
• 집합족 ${\mathcal {C}}\subseteq \operatorname {Pow} (E)$. 그 원소를 회로(回路, 영어: circuit)라고 한다. 회로를 부분 집합으로 포함하지 않는 집합을 독립 집합이라고 한다.

이 데이터는 다음 공리들을 만족시켜야 한다.^:§1.4

• (공집합의 독립성) 공집합은 회로가 아니다. 즉, $\varnothing \not \in {\mathcal {C}}$이다.
• 임의의 $C,C'\in {\mathcal {C}}$에 대하여, $C\subseteq C'$라면 $C=C'$이다.
• (회로의 제거) 임의의 회로 $C\in {\mathcal {C}}$ 및 회로의 족 ${\mathcal {U}}\subseteq {\mathcal {C}}$이 주어졌으며, 집합 $X\subseteq E$가 $\forall U\in {\mathcal {U}}\colon |X\cap U|=1$를 만족시킨다고 하자. 이제, $\textstyle Y=C\setminus \bigcup {\mathcal {U}}$로 놓자. 그렇다면, $\forall x\colon x\in f(x)$인 함수 $\textstyle f\colon Y\to {\mathcal {C}}\cap \operatorname {Pow} (Y\setminus X)$가 존재한다.
• (국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$에 대하여, $I$를 포함하며 $E'$에 포함되는 독립 집합들의 부분 순서 집합은 적어도 하나 이상의 극대 원소를 갖는다.

폐포를 통한 정의

매트로이드 $(E,\operatorname {cl} )$는 다음과 같은 데이터로 주어진다.

• 집합 $E$
• 함수 $\operatorname {cl} \colon \operatorname {Pow} (E)\to \operatorname {Pow} (E)$. 이를 폐포라고 한다. 또한, 부분 집합 $D\subseteq E$에 대하여, 만약 $x\in D\cap \operatorname {cl} (D\setminus \{x\})$인 $x$가 존재한다면, $D$를 종속 집합이라고 하며, 종속 집합이 아닌 부분 집합을 독립 집합이라고 한다.

이 데이터는 다음 조건들을 만족시켜야 한다.^:§1.3

• $\operatorname {cl}$은 폐포 연산이다. 즉,
  • 임의의 $X\subseteq E$에 대하여, $X\subseteq \operatorname {cl} (X)=\operatorname {cl} (\operatorname {cl} (X))$
  • 임의의 $X\subseteq Y\subseteq E$에 대하여, $\operatorname {cl} (X)\subseteq \operatorname {cl} (Y)$
• 임의의 부분 집합 $X\subseteq E$에 대하여, $E$ 위의 다음 이항 관계는 대칭 관계이다.

  $x\sim _{X}y\iff x\in \operatorname {cl} (X\cup \{y\})\setminus \operatorname {cl} (X)$

• (국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$에 대하여, 다음 조건을 만족시키는 독립 집합 $I\subseteq I'\subseteq E'$이 존재한다.

  $I'$은 극대적이다. 즉, 임의의 $x\in E'\setminus I'$에 대하여, $E'\cup \{x\}$는 종속 집합이다.

$\operatorname {cl} (S)=S$인 집합 $S$를 닫힌집합(-集合, 영어: closed set) 또는 평탄면(平坦面, 영어: flat 플랫^[*])이라고 한다.

계수 함수를 통한 정의

매트로이드 $(E,\operatorname {rank} )$는 다음과 같은 데이터로 주어진다.

• 집합 $E$.
• 함수 $\operatorname {rank} (-|-)\colon \operatorname {Pair} (E)\to \mathbb {N} \sqcup \{\infty \}$. 이를 상대 계수 함수(相對係數函數, 영어: relative rank function)라고 한다. 또한, 부분 집합 $I\subseteq E$가 $\forall x\in I\colon \operatorname {rank} (I|I\setminus \{x\})>0$를 만족시킨다면, $I$를 독립 집합이라고 하자.

여기서

$\operatorname {Pair} (E)=\{(S,T)\subseteq E\colon T\subseteq S\}\subseteq \operatorname {Pow} (E)^{2}$

는 $E$ 속의, 길이 2의 사슬들의 집합이다.

이 데이터는 다음 조건들을 만족시켜야 한다.^:§1.5

• 임의의 $(A,B)\in \operatorname {Pair} (E)$에 대하여, $\operatorname {rank} (A|B)\leq |A\setminus B|$
• 임의의 $A,B\subseteq E$에 대하여, $\operatorname {rank} (A|A\cap B)\geq \operatorname {rank} (A\cup B|B)$
• (유한 사슬에 대한 분해) 임의의 $C\subseteq B\subseteq A\subseteq E$에 대하여, $\operatorname {rank} (A|C)=\operatorname {rank} (A|B)+\operatorname {rank} (B|C)$
• 임의의 집합족 ${\mathcal {U}}\subseteq E$에 대하여, 만약 $\textstyle \forall U\in {\mathcal {U}}\colon \operatorname {rank} (U|\bigcap {\mathcal {U}})=0$이라면, $\textstyle \operatorname {rank} (\bigcup {\mathcal {U}}|\bigcap {\mathcal {U}})=0$이다.
• (국소적 극대 독립 집합의 존재) 임의의 부분 집합 $E'\subseteq E$ 및 독립 집합 $I\subseteq E'$에 대하여, $I$를 포함하며 $E'$에 포함되는 독립 집합들의 부분 순서 집합은 적어도 하나 이상의 극대 원소를 갖는다.

매트로이드 $E$ 속에서, 부분 집합 $F\subseteq E$가

$\operatorname {rank} (E|F)=1$

를 만족시키는 것들 가운데 (부분 집합 관계에 대하여) 극대 원소라면, $F$를 초평면(超平面, 영어: hyperplane 하이퍼플레인^[*])이라고 한다.

정의들 사이의 관계

일부 정의들 사이의 관계는 다음과 같다.

정의	독립 집합 $I$	종속 집합 $D$	기저 $B$	회로 $C$	닫힌집합 $F$
독립 집합을 통한 정의	—	독립 집합이 아닌 집합	극대 독립 집합	극소 종속 집합	임의의 $F\supseteq I\in {\mathcal {I}}$ 및 $x\in E$에 대하여, $I\cup \{x\}\in {\mathcal {I}}\implies x\in F$
기저를 통한 정의	$\exists B\in {\mathcal {B}}\colon I\subseteq B$	$\forall B\in {\mathcal {B}}\colon D\not \subseteq B$	—	모든 진부분 집합이 기저이지만, 기저가 아닌 집합
회로를 통한 정의	$\forall C\in {\mathcal {C}}\colon C\not \subseteq I$	$\exists C\in {\mathcal {C}}\colon C\subseteq D$	회로를 포함하지 않는 극대 집합	—
계수를 통한 정의	$\forall x\in I\colon \operatorname {rank} (I|I\setminus \{x\})>0$	$\exists x\in D\colon \operatorname {rank} (D|D\setminus \{x\})=0$	극대 독립 집합	극소 종속 집합	임의의 $x\in E$에 대하여 $x\in F\iff \operatorname {rank} (E\cup \{x\}|E)=0$
폐포를 통한 정의	$\forall x\in I\colon x\not \in \operatorname {cl} (I\setminus \{x\})$	$\exists x\in D\colon x\in \operatorname {cl} (D\setminus \{x\})$	독립 집합이며, 또한 고정점을 갖지 않는, $\forall x\in B\colon f(x)\in \operatorname {cl} (I\setminus \{x,f(x)\})$인 함수 $f\colon B\to B$가 존재	종속 집합이며, 임의의 $x,y\in C$에 대하여 $y\in \operatorname {cl} (C\setminus \{x,y\})\implies x=y$	$F=\operatorname {cl} F$

매트로이드 $(E,{\mathcal {I}})$의 부분 집합 $S$의 폐포 $\operatorname {cl} (S)$는 독립 집합들로부터 다음과 같이 정의된다.

$\operatorname {cl} (S)=S\cup \{x\in E\colon \exists I\in {\mathcal {I}}\colon I\cup \{x\}\not \in {\mathcal {I}}\}$

매트로이드 $(E,{\mathcal {I}})$의 부분 집합 $S$의 폐포 $\operatorname {cl} (S)$는 마찬가지로 상대 계수 함수로부터 다음과 같이 정의된다.

$\operatorname {cl} (S)=\max\{S'\subseteq E\colon \operatorname {rank} (S'|S)=0\}$

(이러한 최대 원소가 항상 유일하게 존재함을 보일 수 있다.)

매트로이드 $(E,{\mathcal {I}})$의 상대 계수 함수는 독립 집합들로부터 다음과 같이 정의된다.

$\operatorname {rank} (A|B)=\max\{|I\setminus J|\colon E\supseteq I\supseteq J,\;I\in {\mathcal {I}}\cap \operatorname {Pow} (A),\;J\in \max({\mathcal {I}}\cap \operatorname {Pow} (B))\}$

종류

유한성

매트로이드 $(E,{\mathcal {I}})$에 대하여,

• 만약 $E$가 유한 집합이라면, $(E,{\mathcal {I}})$를 유한 매트로이드(有限matroid, 영어: finite matroid)라고 한다.
• 만약 모든 회로가 유한 집합이라면 (즉, 임의의 $A\subseteq E$에 대하여, 만약 $A$의 모든 유한 부분 집합이 독립 집합인 경우 $A$ 또한 독립 집합이라면), $(E,{\mathcal {I}})$를 유한형 매트로이드(有限形matroid, 영어: finitary matroid)라고 한다.^{:18, §0}
• 만약 모든 회로와 쌍대 회로의 교집합이 유한 집합이라면, $(E,{\mathcal {I}})$를 유순 매트로이드(柔順matroid, 영어: tame matroid)라고 한다.^{:28, §2.6:§1}

즉, 다음과 같은 함의 관계가 존재한다.

유한 매트로이드 ⇒ 유한형 매트로이드 ⇒ 유순 매트로이드 ⇒ 매트로이드

작은 회로의 부재

크기 1의 회로는 고리(영어: loop)라고 하며, 크기 2의 회로는 평행변(平行邊, 영어: parallel lines)이라고 한다. (이러한 용어는 다중 그래프에 대응되는 순환 그래프에서 유래하였다.)

모든 회로의 크기가 2 이상인 매트로이드를 단순 매트로이드(영어: simple matroid)라고 한다. 모든 회로의 크기가 1 이상인 매트로이드를 고리 없는 매트로이드(영어: loopless matroid)라고 한다.

연산

부분 매트로이드

매트로이드 $(E,{\mathcal {I}})$의 부분 집합 $S\subseteq E$ 위에서, $(S,{\mathcal {I}}\cap \operatorname {Pow} (S))$는 매트로이드를 이룬다. 이를 $E$의 부분 매트로이드(영어: submatroid)라고 한다. 매트로이드의 부분 집합 $S$의 계수는 부분 매트로이드로서의 계수이다.

쌍대 매트로이드

매트로이드 $(E,{\mathcal {I}})$의 쌍대 매트로이드 $(E^{*},{\mathcal {I}}^{*})$는 다음과 같이 정의된다. 집합으로서, $E=E^{*}$이지만,

${\mathcal {I}}^{*}=\{S\in {\mathcal {P}}(E)\colon \operatorname {cl} _{\mathcal {I}}(E\setminus S)=E\}$

이다. 이에 따라, $E$의 기저는 항상 $E^{*}$의 기저의 여집합이다.

이 연산은 쌍대성을 가진다. 즉, $E^{**}=E$이다.

직합

두 매트로이드 $(E_{1},{\mathcal {I}}_{1})$, $(E_{2},{\mathcal {I}}_{2})$가 주어졌을 때, 분리합집합

$E=E_{1}\sqcup E_{2}$

위에 매트로이드 구조

${\mathcal {I}}=\{I_{1}\sqcup I_{2}\colon I_{1}\in {\mathcal {I}}_{1},\;I_{2}\in {\mathcal {I}}_{2}\}$

를 부여할 수 있다. 이를 이 두 매트로이드의 직합(直合, 영어: direct sum)이라고 하며, $E_{1}\oplus E_{2}$로 표기한다. (이 용어는 벡터 공간의 부분 집합으로 나타내어지는 매트로이드의 경우, 매트로이드 직합은 해당 벡터 공간들의 직합에 해당하기 때문에 유래하였다.)

마이너

 이 부분의 본문은 매트로이드 마이너입니다.

부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 매트로이드 마이너라고 한다. 이는 그래프 마이너의 일반화이다.

안둘레와 밖둘레

 이 부분의 본문은 안둘레입니다.

매트로이드의 안둘레는 가장 작은 회로의 크기이다. 마찬가지로, 매트로이드의 밖둘레는 회로들의 크기의 상한이다.

성질

계수

유한 매트로이드의 서로 다른 기저들의 크기는 서로 같다.

만약 일반화 연속체 가설이 참이라면, 모든 (유한 또는 무한) 매트로이드들의 서로 다른 기저들의 크기는 서로 같은 기수이다.^{:861, Theorem 2} 이 경우, 기저의 크기를 매트로이드의 계수(係數, 영어: rank)라고 한다. 보다 일반적으로, 만약 $\kappa \in \operatorname {Card}$ 이하에서 일반화 연속체 가설이 성립한다면 (즉, $\forall \aleph _{0}\leq \lambda \leq \kappa \colon \lambda ^{+}=2^{\lambda }$), 크기가 $\kappa$ 이하인 매트로이드의 모든 기저의 크기는 같다.

만약 선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)이 무모순적이라면, “임의의 매트로이드에서, 기저들의 크기는 같다”라는 명제는 ZFC와 독립적이다.^{:§4, Corollary 17}

작은 매트로이드의 수

작은 크기의 매트로이드의 동형류의 수 및 고리 없는 매트로이드의 동형류의 수 및 단순 매트로이드의 동형류의 수는 다음과 같다.^{:§5, Table 1, Table 2}

크기	매트로이드 동형류의 수 (OEIS의 수열 A55545)	고리 없는 매트로이드 동형류의 수 (OEIS의 수열 A58718)	단순 매트로이드 동형류의 수 (OEIS의 수열 A2773)	주어진 집합 위의 매트로이드 구조의 수 (OEIS의 수열 A58673)	주어진 집합 위의 고리 없는 매트로이드 구조의 수 (OEIS의 수열 A58712)	주어진 집합 위의 단순 매트로이드 구조의 수 (OEIS의 수열 A58721)
0	1	1	1	1	1	0
1	2	1	1	2	1	0
2	4	2	1	5	2	1
3	8	4	2	16	6	2
4	17	9	4	68	27	7
5	38	21	9	406	165	49
6	98	60	26	3807	2135	733
7	306	208	101	75164	55129	29760
8	1724	1418	950	10607540	10094077	9000402
9	383172	381448	376467

크기가 $n$인 집합 위의 매트로이드 구조의 수를 $m_{n}$이라고 하면, 다음이 성립한다.^{:Theorem 3; (1)}

$n-{\frac {3}{2}}\log _{2}n+{\frac {1}{2}}\log _{2}{\frac {2}{\pi }}-o(1)\leq \log _{2}\log _{2}m_{n}\leq n-{\frac {3}{2}}\log _{2}n+{\frac {1}{2}}\log _{2}{\frac {2}{\pi }}+1+o(1)$

범주론적 성질

임의의 두 유한 매트로이드 $E$, $E'$ 사이의 함수 $f\colon E\to E'$에 대하여 다음 세 조건이 서로 동치이며, 이를 만족시키는 함수를 강사상(強寫像, 영어: strong morphism)이라고 하자.

• 임의의 $B\subseteq A\subseteq E$에 대하여, $\operatorname {rank} (f(A)|f(B))\leq \operatorname {rank} (A|B)$이다.
• 임의의 $A\subseteq E$에 대하여, $\operatorname {cl} (f(A))=f(\operatorname {cl} (A))$이다.
• $E$의 닫힌집합의 상은 항상 $E'$의 닫한집합이다.

유한 매트로이드와 강사상의 작은 범주를 $\operatorname {finMatr}$라고 하자. 또한, 유한 집합과 함수의 작은 범주를 $\operatorname {finSet}$라고 하자.

그렇다면, $\operatorname {finMatr}$는 구체적 범주이며, 망각 함자

$|-|\colon \operatorname {finMatr} \to \operatorname {finSet}$

가 존재한다. 이 밖에도, 균등 매트로이드 함자

$\operatorname {Unif} (-,0)\colon \operatorname {finSet} \to \operatorname {finMatr}$

$\operatorname {Unif} (-,0)^{*}\colon \operatorname {finSet} \to \operatorname {finMatr}$

$\operatorname {Unif} (-,0)\colon S\mapsto \operatorname {Unif} (S,0)$

$\operatorname {Unif} (-,0)^{*}\colon S\mapsto \operatorname {Unif} (S,0)^{*}=\operatorname {Unif} (S,|S|)$

및

$(-)_{0}\colon \operatorname {finMatr} \to \operatorname {finSet}$

$(-)_{0}\colon E\mapsto \operatorname {cl} _{E}(\varnothing )$

$(-)_{0}\colon (E{\xrightarrow {f}}E')\mapsto \left(f\upharpoonright (\operatorname {cl} _{E}(\varnothing ))\right)$

를 정의할 수 있다. 이들은 다음과 같은 수반 함자 관계를 이룬다.^{:Theorem 2.9}

$\operatorname {Unif} (-,0)^{*}\dashv |-|\dashv \operatorname {Unif} (-,0)\dashv (-)_{0}$

즉, 균등 매트로이드 $\operatorname {Unif} (S,0)^{*}$은 “자유 매트로이드”이며, $\operatorname {Unif} (S,0)$은 “쌍대 자유 매트로이드”이다.

$\operatorname {finMatr}$는 모든 유한 쌍대곱을 갖지만, 모든 유한 곱을 갖지 못하며, 또한 유한 쌍대 극한 가운데 일부는 존재하지 못한다.,^:§3

예

균등 매트로이드

임의의 집합 $E$ 위에,

${\mathcal {I}}=\{\varnothing \}$

${\mathcal {B}}=\{\varnothing \}$

${\mathcal {C}}=\{\{x\}\colon x\in E\}$

$\operatorname {rank} (A|B)=0\qquad (B\subseteq A\subseteq E)$

$\operatorname {cl} (A)=E\qquad (A\subseteq E)$

를 부여하면, 이는 매트로이드를 이룬다. 이를 $\operatorname {Unif} (E,0)$라고 하자.

마찬가지로, 임의의 집합 $E$ 위에,

${\mathcal {I}}=\operatorname {Pow} (E)$

${\mathcal {B}}=\{E\}$

$\operatorname {rank} (A|B)={\begin{cases}|A\setminus B|&|A\setminus B|<\aleph _{0}\\\infty &|A\setminus B|\geq \aleph _{0}\end{cases}}\qquad (B\subseteq A\subseteq E)$

$\operatorname {cl} (A)=A\qquad (A\subseteq E)$

을 부여하면, 이는 매트로이드를 이룬다. 이는 $\operatorname {Unif} (E,0)$의 쌍대 매트로이드 $\operatorname {Unif} (E,0)^{*}$이다.

이들의 성질을 비교하면 다음과 같다.

성질	$\operatorname {Unif} (E,0)$	$\operatorname {Unif} (E,0)^{*}$
독립 집합	공집합	모든 집합
기저	공집합	전체 집합 $E$
종속 집합	공집합이 아닌 집합	(없음)
회로	한원소 집합	(없음)
폐포 연산	전체 집합 값의 상수 함수	항등 함수
닫힌집합	전체 집합 $E$	모든 집합
상대 계수 함수	0 값의 상수 함수	차집합의 크기

이와 같은 두 종류의 매트로이드의 직합으로 표현될 수 있는 매트로이드를 이산 매트로이드(離散matroid, 영어: discrete matroid)라고 한다.

보다 일반적으로, 임의의 집합 $E$ 및 자연수 $0\leq k$에 대하여, 균등 매트로이드(均等matroid, 영어: uniform matroid) $\operatorname {Unif} (E,k)$는 $E$ 위의 다음과 같은 매트로이드이다.

${\mathcal {I}}=\{S\subseteq E\colon |S|\leq k\}$

${\mathcal {B}}=\{S\subseteq E\colon |S|=k\}$

${\mathcal {C}}=\{S\subseteq E\colon |S|=k+1\}$

이는 항상 유한형 매트로이드이다.

만약 $E$가 유한 집합일 때, $\operatorname {Unif} (E,k)$의 쌍대 매트로이드는 $\operatorname {Unif} (E,|E|-k)$이다. 만약 $E$가 무한 집합이라면, $\operatorname {Unif} (E,k)$의 쌍대 매트로이드는 더 이상 유한형 매트로이드가 아니다.

벡터 공간의 부분 집합의 매트로이드

체 $K$에 대한 유한 차원 벡터 공간 $V$의 유한 부분 중복집합 $E\subset V$를 생각하자. (임의로 순서를 잡으면, 이는 $K$에 대한 행렬로 나타낼 수 있다.) ${\mathcal {I}}(E)\subset {\mathcal {P}}(E)$가 $E$의 일차독립 부분 중복집합들의 집합이라고 하면, $(E,{\mathcal {I}}(E))$는 매트로이드를 이룬다. 이를 선형 매트로이드(영어: linear matroid)라고 한다.

그래프의 매트로이드

 이 부분의 본문은 순환 매트로이드입니다.

모든 그래프에는 순환 매트로이드라는 유한형 매트로이드 및 그 쌍대 매트로이드인 접합 매트로이드가 대응된다.

작은 크기의 매트로이드

공집합 위에는 유일한 매트로이드 구조가 존재하며, 이는 균등 매트로이드 $\operatorname {Unif} (0,0)$이다.

이는 무변 그래프의 순환 매트로이드이자, 임의의 벡터 공간 속의 공집합으로부터 정의되는 선형 매트로이드이다.

크기 1

크기 1의 매트로이드 동형류들은 다음 두 가지이다.

• $\operatorname {Unif} (1,1)$ (계수 1). 이는 한 변을 갖는 경로 그래프 $P_{2}$의 순환 매트로이드이다.
• $\operatorname {Unif} (1,0)$ (계수 0). 이는 하나의 꼭짓점과 하나의 변을 갖는 다중 그래프의 순환 매트로이드이다.

크기 2

크기 2의 매트로이드 동형류들은 다음 네 가지이다.

• $\operatorname {Unif} (2,2)$ (계수 2)
• $\operatorname {Unif} (1,1)\oplus \operatorname {Unif} (1,0)$ (계수 1)
• $\operatorname {Unif} (2,1)$ (계수 1)
• $\operatorname {Unif} (2,0)$ (계수 0)

이 가운데 단순 매트로이드인 것은 첫째 밖에 없다.

크기 3

크기 3의 매트로이드 동형류들은 다음 여덟 가지이다.

• $\operatorname {Unif} (3,3)$ (계수 3)
• $\operatorname {Unif} (3,2)$ (계수 2)
• $\operatorname {Unif} (2,2)\oplus \operatorname {Unif} (1,0)$ (계수 2)
• $\operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,1)$ (계수 2)
• $\operatorname {Unif} (3,1)$ (계수 1)
• $\operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,0)$ (계수 1)
• $\operatorname {Unif} (2,0)\oplus \operatorname {Unif} (1,1)$ (계수 1)
• $\operatorname {Unif} (3,0)$ (계수 0)

이 가운데 단순 매트로이드인 것은 처음 두 개이다.

크기 4

크기 4의 매트로이드는 총 17개가 있으며, 하나를 제외하고는 나머지는 균등 매트로이드들의 직합으로 표현될 수 있다.

• 계수 0:
  • $\operatorname {Unif} (4,0)$
• 계수 1:
  • $\operatorname {Unif} (4,1)$
  • $\operatorname {Unif} (3,1)\oplus \operatorname {Unif} (1,0)$
  • $\operatorname {Unif} (2,1)\oplus \operatorname {Unif} (2,0)$
  • $\operatorname {Unif} (1,1)\oplus \operatorname {Unif} (3,0)$
• 계수 2:
  • $\operatorname {Unif} (4,2)$
  • $\operatorname {Unif} (3,1)\oplus \operatorname {Unif} (1,1)$
  • $\operatorname {Unif} (3,2)\oplus \operatorname {Unif} (1,0)$
  • $\operatorname {Unif} (2,1)\oplus \operatorname {Unif} (2,1)$
  • $\operatorname {Unif} (2,2)\oplus \operatorname {Unif} (2,0)$
  • $\operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,1)\oplus \operatorname {Unif} (1,0)$
  • 균등 매트로이드의 직합이 아닌 매트로이드 $X$

계수 3 및 계수 4의, 크기 4의 매트로이드들은 각각 계수 1 및 계수 0의 것들의 쌍대 매트로이드로 얻어진다.

여기서, 매트로이드 $X$는 다음과 같다.

$E=\{{\mathsf {a}},{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\}$

${\mathcal {B}}=\{S\subseteq E\colon |S|=2,\;S\neq \{{\mathsf {a}},{\mathsf {b}}\}\}$

${\mathcal {C}}=\left\{\{{\mathsf {a}},{\mathsf {b}}\},\{{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\},\{{\mathsf {a}},{\mathsf {c}},{\mathsf {d}}\}\right\}$

이는 다음과 같은 다중 그래프에 대응하는 순환 매트로이드이다.

마찬가지로, 이는 (예를 들어) 다음과 같은 실수 벡터 공간 $\mathbb {R} ^{2}$의 부분 집합 $\{{\mathsf {a}},{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\}$에 대응되는 매트로이드와 동형이다.

${\mathsf {a}}=(1,0)$

${\mathsf {b}}=(2,0)$

${\mathsf {c}}=(0,1)$

${\mathsf {d}}=(1,1)$

역사

매트로이드의 개념은 해슬러 휘트니가 1935년에 도입하였다. 1938년에 일본의 나카자와 다케오(일본어: 中澤 武雄, 1913~1946)가 동일한 개념을 독립적으로 발견하였으나, 크게 알려지지 못했다.

이후 윌리엄 토머스 텃이 매트로이드 이론을 발달시켰고, 텃 다항식과 같은 중요한 개념들을 발견하였다.

1970년에 잔카를로 로타와 헨리 하울런드 크레이포(영어: Henry Howland Crapo)는 매트로이드 이론에 대한 최초의 책을 출판하였다. (이 책에서는 “매트로이드” 대신 “조합 기하”(영어: combinatorial geometry)라는 용어가 사용되었다.) 이듬해에 윌리엄 토머스 텃은 매트로이드 이론에 대한 둘째 책을 출판하였다.

무한 매트로이드의 올바른 정의는 오랫동안 미해결 문제였다. 1966년에 리하르트 라도는 무한 매트로이드의 올바른 정의에 대한 문제를 제기하였다.^{:263, §6(c), Problem P531} 데니스 힉스(영어: Denis A. Higgs, 1932~2011)는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 “B-매트로이드”(영어: B-matroid)라는 개념이었다.

이후 1978년에 제임스 옥슬리(영어: James G. Oxley)는 “B-매트로이드”의 모임이 쌍대성을 가지며 매트로이드 마이너에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다. 이후 2010년에 이 “B-매트로이드”에 대한 여러 자연스러운 공리화들이 발견되었으며, 이후 이 개념이 무한 매트로이드의 통상적인 정의로 굳어지게 되었다.

외부 링크

• “Matroid”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• “Tutte polynomial”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Matroid”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Weisstein, Eric Wolfgang. “Oriented matroid”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• “Matroid”. 《nLab》 (영어). 
• Kingan, Sandra. “Matroid theory” (영어). 
• Mayhew, Dillon; van Zwam, Stefan; Nelson, Peter; Pivotto, Irene; Huynh, Tony; Bowler, Nathan. “Matroid Union” (영어). 
• Dukes, W. M. B. “The number of matroids up to n=8” (영어).