매트로이드

조합론에서 **매트로이드**(메이트로이드)는 일차 독립의 성질을 공리화하여 얻은 조합론적 구조이다.언어=en언어=en언어=en언어=en언어=en언어=en 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다.
# 정의
**매트로이드**의 개념은 다양하게 정의될 수 있지만, 이 정의들은 서로 동치이다.
## 독립 집합을 통한 정의
**매트로이드** (E,\mathcal I)는 다음과 같은 데이터로 구성된다. * 집합 E * 집합족 \mathcal I\subseteq\operatorname{Pow}(E). 그 원소를 **독립 집합**(獨立集合, independent set)이라고 하며, 독립 집합이 아닌 E의 부분 집합을 **종속 집합**(從屬集合, dependent set)이라고 한다. 이 데이터는 다음 공리들을 만족시켜야 한다.언어=en§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\ne\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) 또는 **평탄면**(平坦面, 플랫)이라고 한다.
## 계수 함수를 통한 정의
**매트로이드** (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)\le|A\setminus B| * 임의의 A,B\subseteq E에 대하여, \operatorname{rank}(A|A\cap B)\ge\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를 **초평면**(超平面, 하이퍼플레인)이라고 한다.
## 정의들 사이의 관계
일부 정의들 사이의 관계는 다음과 같다. {| class=wikitable |- ! 독립 집합을 통한 정의 | — | 독립 집합이 아닌 집합 | 극대 독립 집합 | 극소 종속 집합 | 임의의 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언어=en§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로 표기한다. (이 용어는 벡터 공간의 부분 집합으로 나타내어지는 매트로이드의 경우, 매트로이드 직합은 해당 벡터 공간들의 직합에 해당하기 때문에 유래하였다.)
## 마이너
매트로이드 마이너 부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 **매트로이드 마이너**라고 한다. 이는 그래프 마이너의 일반화이다.
## 안둘레와 밖둘레
안둘레 매트로이드의 **안둘레**는 가장 작은 회로의 크기이다. 마찬가지로, 매트로이드의 **밖둘레**는 회로들의 크기의 상한이다.
# 성질

## 계수
유한 매트로이드의 서로 다른 기저들의 크기는 서로 같다. 만약 일반화 연속체 가설이 참이라면, 모든 (유한 또는 무한) 매트로이드들의 서로 다른 기저들의 크기는 서로 같은 기수이다.언어=en861, Theorem 2 이 경우, 기저의 크기를 매트로이드의 **계수**(係數, rank)라고 한다. 보다 일반적으로, 만약 \kappa\in\operatorname{Card} 이하에서 일반화 연속체 가설이 성립한다면 (즉, \forall\aleph_0\le\lambda\le\kappa\colon \lambda^+=2^\lambda), 크기가 \kappa 이하인 매트로이드의 모든 기저의 크기는 같다. 만약 선택 공리를 추가한 체르멜로-프렝켈 집합론(ZFC)이 무모순적이라면, “임의의 매트로이드에서, 기저들의 크기는 같다”라는 명제는 ZFC와 독립적이다.언어=en§4, Corollary 17
## 작은 매트로이드의 수
작은 크기의 매트로이드의 동형류의 수 및 고리 없는 매트로이드의 동형류의 수 및 단순 매트로이드의 동형류의 수는 다음과 같다.언어=en§5, Table 1, Table 2 {| class=wikitable || 매트로이드 동형류의 수
A55545 || 고리 없는 매트로이드 동형류의 수
A58718 || 단순 매트로이드 동형류의 수
A2773 || 주어진 집합 위의 매트로이드 구조의 수
A58673 || 주어진 집합 위의 고리 없는 매트로이드 구조의 수
A58712 || 주어진 집합 위의 단순 매트로이드 구조의 수
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이라고 하면, 다음이 성립한다.언어=enTheorem 3; (1) :n-\frac32\log_2n+\frac12\log_2\frac2\pi-o(1)\le \log_2\log_2m_n\le n-\frac32\log_2n+\frac12\log_2\frac2\pi+1+o(1)
## 범주론적 성질
임의의 두 유한 매트로이드 E, E' 사이의 함수 f\colon E\to E'에 대하여 다음 세 조건이 서로 동치이며, 이를 만족시키는 함수를 **강사상**(強寫像, strong morphism)이라고 하자. * 임의의 B\subseteq A\subseteq E에 대하여, \operatorname{rank}(f(A)|f(B)) \le \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\restriction (\operatorname{cl}_E(\varnothing))\right) 를 정의할 수 있다. 이들은 다음과 같은 수반 함자 관계를 이룬다.언어=enTheorem 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| \ge \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)^*이다. 이들의 성질을 비교하면 다음과 같다. {| class=wikitable ! 성질 !! \operatorname{Unif}(E,0) !! \operatorname{Unif}(E,0)^* |- ! 독립 집합 | 공집합 | 모든 집합 |- ! 기저 | 공집합 | 전체 집합 E |- ! 종속 집합 | 공집합이 아닌 집합 | (없음) |- ! 회로 | 한원소 집합 | (없음) |- ! 폐포 연산 | 전체 집합 값의 상수 함수 | 항등 함수 |- ! 닫힌집합 | 전체 집합 E | 모든 집합 |- ! 상대 계수 함수 | 0 값의 상수 함수 | 차집합의 크기 |} 이와 같은 두 종류의 매트로이드의 직합으로 표현될 수 있는 매트로이드를 **이산 매트로이드**(離散matroid, discrete matroid)라고 한다. 보다 일반적으로, 임의의 집합 E 및 자연수 0\le k에 대하여, **균등 매트로이드**(均等matroid, uniform matroid) \operatorname{Unif}(E,k)는 E 위의 다음과 같은 매트로이드이다. :\mathcal I=\\{S\subseteq E\colon |S|\le 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\ne\\{\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년에 도입하였다.언어=en 1938년에 일본의 나카자와 다케오(中澤 武雄, 1913~1946)가 동일한 개념을 독립적으로 발견하였으나,언어=de언어=de언어=de언어=en 크게 알려지지 못했다. 이후 윌리엄 토머스 텃이 매트로이드 이론을 발달시켰고, 텃 다항식과 같은 중요한 개념들을 발견하였다.언어=en 1970년에 잔카를로 로타와 헨리 하울런드 크레이포(Henry Howland Crapo)는 매트로이드 이론에 대한 최초의 책을 출판하였다.언어=en (이 책에서는 “매트로이드” 대신 “조합 기하”(combinatorial geometry)라는 용어가 사용되었다.) 이듬해에 윌리엄 토머스 텃은 매트로이드 이론에 대한 둘째 책을 출판하였다.언어=en 무한 매트로이드의 올바른 정의는 오랫동안 미해결 문제였다. 1966년에 리하르트 라도는 무한 매트로이드의 올바른 정의에 대한 문제를 제기하였다.언어=en263, §6(c), Problem P531 데니스 힉스(Denis A. Higgs, 1932~2011)는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 “B-매트로이드”(B-matroid)라는 개념이었다.언어=en 이후 1978년에 제임스 옥슬리(James G. Oxley)는 “B-매트로이드”의 모임이 쌍대성을 가지며 매트로이드 마이너에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다.언어=en 이후 2010년에 이 “B-매트로이드”에 대한 여러 자연스러운 공리화들이 발견되었으며, 이후 이 개념이 무한 매트로이드의 통상적인 정의로 굳어지게 되었다.