매트로이드 문서 원본 보기

{{위키데이터 속성 추적}}
[[조합론]]에서 '''매트로이드'''({{llang|en|matroid|메이트로이드}})는 [[일차 독립]]의 성질을 공리화하여 얻은 조합론적 구조이다.<ref>{{서적 인용|이름=Gary|성=Gordon|이름2=Jennifer|성2=McNulty|제목=Matroids: a geometric introduction|isbn=978-052176724-8|출판사=Cambridge University Press |날짜=2012-09|doi=10.1017/CBO9781139049443|언어=en}}</ref><ref>{{서적 인용|last=Oxley|first=James G. | 날짜=1992|title=Matroid theory|url=https://archive.org/details/matroidtheory0000oxle|publisher=Oxford University Press|location=Oxford|isbn=0-19-853563-5|mr=1207587|zbl=0784.05002|언어=en}}</ref><ref>{{서적 인용|last=Recski|first=András|날짜=1989|title=Matroid theory and its applications in electric network theory and in statics|url=https://archive.org/details/matroidtheoryits0000recs|publisher=Springer-Verlag, Akademiai Kiado|isbn=3-540-15285-7|mr=1027839|언어=en}}</ref><ref>{{서적 인용|last=Bryant|first=Victor|이름2=Hazel|성2=Perfect|날짜=1980|title=Independence theory in combinatorics|url=https://archive.org/details/independencetheo0000brya|publisher=Chapman and Hall|location=London and New York|isbn=0-412-22430-5|언어=en}}</ref><ref>{{서적 인용|last=Welsh|first=Dominic James Anthony|날짜=1976|title=Matroid theory|publisher=Academic Press|isbn=0-12-744050-X|zbl=0343.05002|series=London Mathematical Society Monographs | volume=8|언어=en}}</ref><ref>{{저널 인용|성=Wilson|이름=Robin James|제목=An introduction to matroid theory|저널=The American Mathematical Monthly|권=80|호=5|날짜=1973-05|쪽=500–525|doi=10.2307/2319608|jstor=2319608|zbl=0275.05018|언어=en}}</ref> [[그래프 이론]] · [[선형대수학]] · [[체론]] 등의 다양한 분야에 응용된다.

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

=== 독립 집합을 통한 정의 ===
'''매트로이드''' <math>(E,\mathcal I)</math>는 다음과 같은 데이터로 구성된다.
* [[집합]] <math>E</math>
* [[집합족]] <math>\mathcal I\subseteq\operatorname{Pow}(E)</math>. 그 원소를 '''독립 집합'''(獨立集合, {{llang|en|independent set}})이라고 하며, 독립 집합이 아닌 <math>E</math>의 [[부분 집합]]을 '''종속 집합'''(從屬集合, {{llang|en|dependent set}})이라고 한다.
이 데이터는 다음 공리들을 만족시켜야 한다.<ref name="BDKPW">{{저널 인용|제목=Axioms for infinite matroids|이름=Henning|성=Bruhn|이름2=Reinhard|성2=Diestel|이름3=Matthias|성3=Kriesell|이름4=Rudi A.|성4=Pendavingh|이름5=Paul |성5=Wollan|arxiv=1003.3919|doi=10.1016/j.aim.2013.01.011|bibcode=2010arXiv1003.3919B|저널=Advances in Mathematics|권=239|날짜=2013-06-01|쪽=18–46|zbl=1279.05013|언어=en}}</ref>{{rp|§1.1}}
* (공집합의 독립성) [[공집합]]은 독립 집합이다. 즉, <math>\varnothing\in\mathcal I</math>이다.
* (유전성 {{llang|en|hereditary property}}) 독립 집합의 부분집합은 독립이다. 즉, 만약 <math>B\subseteq A\in\mathcal I</math>라면 <math>B\in\mathcal I</math>이다.
* (추가성 {{llang|en|augmentation property}}) 만약 <math>A, B\in\mathcal I</math>이며, <math>A</math>는 <math>\mathcal I</math>의 [[극대 원소]]이지만 <math>B</math>는 <math>\mathcal I</math>의 [[극대 원소]]가 아니라면, <math>B\cup\{a\}\in\mathcal I</math>인 <math>a\in A\setminus B</math>가 존재한다.
* (국소적 극대 독립 집합의 존재) 만약 <math>\mathcal I\ni A\subset B\subset E</math>라면, 닫힌 [[구간]] <math>\mathcal I\cap [A,B]=\{S\in\mathcal I\colon A\subseteq S\subset B\}</math>는 [[극대 원소]]를 갖는다.
만약 <math>E</math>가 [[유한 집합]]이라면, 마지막 조건은 자동적으로 성립된다.

=== 기저를 통한 정의 ===
'''매트로이드''' <math>(E,\mathcal B)</math>는 다음과 같은 데이터로 구성된다.
* [[집합]] <math>E</math>
* [[집합족]] <math>\mathcal B\subseteq\operatorname{Pow}(E)</math>. 그 원소를 '''기저'''(基底, {{llang|en|basis}})라고 하며, 기저의 부분 집합을 '''독립 집합'''이라고 한다.
이는 다음 조건들을 만족시켜야 한다.<ref name="BDKPW"/>{{rp|§1.2}}
* <math>\mathcal B\ne\varnothing</math>
* (추가성) 임의의 <math>B,B'\in\mathcal B</math> 및 <math>x\in B\setminus B'</math>에 대하여, 다음 조건을 만족시키는 <math>x'\in B'\setminus B</math>가 항상 존재한다.
*: <math>(B\setminus\{x\})\cup\{x'\}\in \mathcal B</math>
* (국소적 극대 독립 집합의 존재) 임의의 [[부분 집합]] <math>E'\subseteq E</math> 및 기저 <math>B\in\mathcal B</math> 및 독립 집합 <math>I\subseteq B\cap E'</math>에 대하여, 다음 두 조건을 만족시키는 기저 <math>B'\in\mathcal B</math> 및 독립 집합 <math>I'\subseteq B'</math>이 존재한다.
** <math>I\subseteq I'\subseteq B'\in\mathcal B</matH>
** 임의의 <math>I'\subseteq C\in\mathcal B</math>에 대하여, <math>(E'\setminus I')\cap C=\varnothing</math>이다.

=== 회로를 통한 정의 ===
'''매트로이드''' <math>(E,\mathcal C)</math>는 다음과 같은 데이터로 주어진다.
* 집합 <math>E</math>
* [[집합족]] <math>\mathcal C\subseteq\operatorname{Pow}(E)</math>. 그 원소를 '''회로'''(回路, {{llang|en|circuit}})라고 한다. 회로를 [[부분 집합]]으로 포함하지 않는 집합을 '''독립 집합'''이라고 한다.
이 데이터는 다음 공리들을 만족시켜야 한다.<ref name="BDKPW"/>{{rp|§1.4}}
* (공집합의 독립성) [[공집합]]은 회로가 아니다. 즉, <math>\varnothing\not\in\mathcal C</math>이다.
* 임의의 <math>C,C'\in\mathcal C</math>에 대하여, <math>C\subseteq C'</math>라면 <math>C=C'</math>이다.
* (회로의 제거) 임의의 회로 <math>C\in\mathcal C</math> 및 회로의 족 <math>\mathcal U\subseteq\mathcal C</math>이 주어졌으며, 집합 <math>X\subseteq E</math>가 <math>\forall U\in\mathcal U\colon|X\cap U|=1</math>를 만족시킨다고 하자. 이제, <math>\textstyle Y= C\setminus\bigcup\mathcal U</math>로 놓자. 그렇다면, <math>\forall x\colon x\in f(x)</math>인 함수 <math>\textstyle f\colon Y\to\mathcal C\cap\operatorname{Pow}(Y\setminus X)</math>가 존재한다.
* (국소적 극대 독립 집합의 존재) 임의의 부분 집합 <math>E'\subseteq E</math> 및 독립 집합 <math>I\subseteq E'</math>에 대하여, <math>I</math>를 포함하며 <math>E'</math>에 포함되는 독립 집합들의 [[부분 순서 집합]]은 적어도 하나 이상의 [[극대 원소]]를 갖는다.

=== 폐포를 통한 정의 ===
'''매트로이드''' <math>(E,\operatorname{cl})</math>는 다음과 같은 데이터로 주어진다.
* 집합 <math>E</math>
* 함수 <Math>\operatorname{cl}\colon\operatorname{Pow}(E)\to\operatorname{Pow}(E)</math>. 이를 '''[[폐포 연산|폐포]]'''라고 한다. 또한, [[부분 집합]] <math>D\subseteq E</math>에 대하여, 만약 <math>x\in D \cap \operatorname{cl}(D\setminus\{x\})</math>인 <math>x</math>가 존재한다면, <math>D</math>를 '''종속 집합'''이라고 하며, 종속 집합이 아닌 부분 집합을 '''독립 집합'''이라고 한다.
이 데이터는 다음 조건들을 만족시켜야 한다.<ref name="BDKPW"/>{{rp|§1.3}}
* <math>\operatorname{cl}</math>은 [[폐포 연산]]이다. 즉,
** 임의의 <math>X\subseteq E</math>에 대하여, <math>X\subseteq\operatorname{cl}(X)=\operatorname{cl}(\operatorname{cl}(X))</math>
** 임의의 <math>X\subseteq Y\subseteq E</math>에 대하여, <math>\operatorname{cl}(X)\subseteq\operatorname{cl}(Y)</math>
* 임의의 [[부분 집합]] <math>X\subseteq E</math>에 대하여, <math>E</math> 위의 다음 [[이항 관계]]는 [[대칭 관계]]이다.
*: <math>x\sim_X y \iff x\in\operatorname{cl}(X\cup\{y\})\setminus\operatorname{cl}(X)</math>
* (국소적 극대 독립 집합의 존재) 임의의 [[부분 집합]] <math>E'\subseteq E</math> 및 독립 집합 <math>I\subseteq E'</math>에 대하여, 다음 조건을 만족시키는 독립 집합 <math>I\subseteq I'\subseteq E'</math>이 존재한다.
*: <math>I'</math>은 극대적이다. 즉, 임의의 <math>x\in E'\setminus I'</math>에 대하여, <math>E'\cup\{x\}</math>는 종속 집합이다.

<math>\operatorname{cl}(S)=S</math>인 집합 <math>S</math>를 '''닫힌집합'''(-集合, {{llang|en|closed set}}) 또는 '''평탄면'''(平坦面, {{llang|en|flat|플랫}})이라고 한다.

=== 계수 함수를 통한 정의 ===
'''매트로이드''' <math>(E,\operatorname{rank})</math>는 다음과 같은 데이터로 주어진다.
* 집합 <math>E</math>.
* 함수 <Math>\operatorname{rank}(-|-)\colon\operatorname{Pair}(E)\to\mathbb N\sqcup\{\infty\}</math>. 이를 '''상대 계수 함수'''(相對係數函數, {{llang|en|relative rank function}})라고 한다. 또한, [[부분 집합]] <math>I\subseteq E</math>가 <math>\forall x\in I\colon\operatorname{rank}(I|I\setminus \{x\})>0</math>를 만족시킨다면, <math>I</math>를 '''독립 집합'''이라고 하자.

여기서
:<math>\operatorname{Pair}(E)=\{(S,T)\subseteq E\colon T\subseteq S\}\subseteq\operatorname{Pow}(E)^2</math>
는 <math>E</math> 속의, 길이 2의 [[사슬 (순서론)|사슬]]들의 집합이다.

이 데이터는 다음 조건들을 만족시켜야 한다.<ref name="BDKPW"/>{{rp|§1.5}}
* 임의의 <math>(A,B)\in\operatorname{Pair}(E)</math>에 대하여, <math>\operatorname{rank}(A|B)\le|A\setminus B|</math>
* 임의의 <math>A,B\subseteq E</math>에 대하여, <math>\operatorname{rank}(A|A\cap B)\ge\operatorname{rank}(A\cup B|B)</math>
* (유한 [[사슬 (순서론)|사슬]]에 대한 분해) 임의의 <math>C\subseteq B\subseteq A\subseteq E</math>에 대하여, <math>\operatorname{rank}(A|C)=\operatorname{rank}(A|B)+\operatorname{rank}(B|C)</math>
* 임의의 [[집합족]] <math>\mathcal U\subseteq E</math>에 대하여, 만약 <math>\textstyle\forall U\in\mathcal U\colon\operatorname{rank}(U|\bigcap\mathcal U)=0</math>이라면, <math>\textstyle\operatorname{rank}(\bigcup\mathcal U|\bigcap\mathcal U)=0</math>이다.
* (국소적 극대 독립 집합의 존재) 임의의 부분 집합 <math>E'\subseteq E</math> 및 독립 집합 <math>I\subseteq E'</math>에 대하여, <math>I</math>를 포함하며 <math>E'</math>에 포함되는 독립 집합들의 [[부분 순서 집합]]은 적어도 하나 이상의 [[극대 원소]]를 갖는다.

매트로이드 <math>E</math> 속에서, [[부분 집합]] <math>F\subseteq E</math>가
:<math>\operatorname{rank}(E|F)=1</math>
를 만족시키는 것들 가운데 ([[부분 집합]] 관계에 대하여) [[극대 원소]]라면, <math>F</math>를 '''초평면'''(超平面, {{llang|en|hyperplane|하이퍼플레인}})이라고 한다.

=== 정의들 사이의 관계 ===
일부 정의들 사이의 관계는 다음과 같다.
{| class=wikitable style="font-size: smaller"
! 정의 !! 독립 집합 <math>I</math> !! 종속 집합 <math>D</math> !! 기저 <math>B</math> !! 회로 <math>C</math> !! 닫힌집합 <math>F</math>
|-
! 독립 집합을 통한 정의
| —
| 독립 집합이 아닌 집합
| [[극대 원소|극대]] 독립 집합
| [[극소 원소|극소]] 종속 집합
| 임의의 <math>F\supseteq I\in\mathcal I</math> 및 <math>x\in E</math>에 대하여, <Math>I\cup\{x\}\in\mathcal I\implies x\in F</math>
|-
! 기저를 통한 정의
| <math>\exists B\in\mathcal B\colon I\subseteq B</math> || <math>\forall B\in\mathcal B\colon D\not\subseteq B</math>
|| — || 모든 [[진부분 집합]]이 기저이지만, 기저가 아닌 집합
|-
! 회로를 통한 정의
| <math>\forall C\in\mathcal C\colon C\not\subseteq I</math> || <math>\exists C\in\mathcal C\colon C\subseteq D</math> || 회로를 포함하지 않는 [[극대 원소|극대]] 집합 || —
|-
! 계수를 통한 정의
| <math>\forall x\in I\colon\operatorname{rank}(I|I\setminus\{x\})>0</math>
| <math>\exists x\in D\colon\operatorname{rank}(D|D\setminus\{x\})=0</math>
| 극대 독립 집합
| 극소 종속 집합
| 임의의 <math>x\in E</math>에 대하여 <math>x\in F\iff \operatorname{rank}(E\cup\{x\}|E)=0</math>
|-
! 폐포를 통한 정의
| <math>\forall x\in I\colon x\not\in\operatorname{cl}(I\setminus\{x\})</math>
| <math>\exists x\in D\colon x\in\operatorname{cl}(D\setminus\{x\})</math>
| 독립 집합이며, 또한 [[고정점]]을 갖지 않는, <math>\forall x\in B\colon f(x)\in \operatorname{cl}(I\setminus\{x,f(x)\})</math>인 함수 <math>f\colon B\to B</math>가 존재
| 종속 집합이며, 임의의 <math>x,y\in C</math>에 대하여 <math>y\in\operatorname{cl}(C\setminus\{x,y\})\implies x=y</math>
| <math>F=\operatorname{cl}F</math>
|}

매트로이드 <math>(E,\mathcal I)</math>의 부분 집합 <math>S</math>의 폐포 <math>\operatorname{cl}(S)</math>는 독립 집합들로부터 다음과 같이 정의된다.
:<math>\operatorname{cl}(S) = S \cup \{x\in E\colon \exists I\in\mathcal I\colon I\cup\{x\}\not\in\mathcal I\}</math>

매트로이드 <math>(E,\mathcal I)</math>의 부분 집합 <math>S</math>의 폐포 <math>\operatorname{cl}(S)</math>는 마찬가지로 상대 계수 함수로부터 다음과 같이 정의된다.
:<math>\operatorname{cl}(S) = \max \{S'\subseteq E\colon \operatorname{rank}(S'|S)=0\}</math>
(이러한 [[최대 원소]]가 항상 유일하게 존재함을 보일 수 있다.)

매트로이드 <math>(E,\mathcal I)</math>의 상대 계수 함수는 독립 집합들로부터 다음과 같이 정의된다.
:<math>\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))\}</math>

== 종류 ==
=== 유한성 ===
매트로이드 <math>(E,\mathcal I)</math>에 대하여,
* 만약 <math>E</math>가 [[유한 집합]]이라면, <math>(E,\mathcal I)</math>를 '''유한 매트로이드'''(有限matroid, {{llang|en|finite matroid}})라고 한다.
* 만약 모든 회로가 [[유한 집합]]이라면 (즉, 임의의 <math>A\subseteq E</math>에 대하여, 만약 <math>A</math>의 모든 유한 부분 집합이 독립 집합인 경우 <math>A</math> 또한 독립 집합이라면), <math>(E,\mathcal I)</math>를 '''유한형 매트로이드'''(有限形matroid, {{llang|en|finitary matroid}})라고 한다.<ref name="BDKPW"/>{{rp|18, §0}}
* 만약 모든 회로와 쌍대 회로의 [[교집합]]이 유한 집합이라면, <Math>(E,\mathcal I)</math>를 '''유순 매트로이드'''(柔順matroid, {{llang|en|tame matroid}})라고 한다.<ref name="BDKPW"/>{{rp|28, §2.6}}<ref>{{저널 인용|이름=Nathan|성=Bowler|이름2=Johannes|성2=Carmesin|제목=Matroids with an infinite circuit-cocircuit intersection|arxiv=1202.3406|bibcode=2012arXiv1202.3406C|doi=10.1016/j.jctb.2014.02.005|저널=Journal of Combinatorial Theory B|권=107|날짜=2014-07|쪽=78–91|언어=en}}</ref>{{rp|§1}}
즉, 다음과 같은 함의 관계가 존재한다.
:유한 매트로이드 ⇒ 유한형 매트로이드 ⇒ 유순 매트로이드 ⇒ 매트로이드

=== 작은 회로의 부재 ===
크기 1의 회로는 '''고리'''({{llang|en|loop}})라고 하며, 크기 2의 회로는 '''평행변'''(平行邊, {{llang|en|parallel lines}})이라고 한다. (이러한 용어는 [[다중 그래프]]에 대응되는 [[순환 그래프]]에서 유래하였다.)

모든 회로의 크기가 2 이상인 매트로이드를 '''단순 매트로이드'''({{llang|en|simple matroid}})라고 한다. 모든 회로의 크기가 1 이상인 매트로이드를 '''고리 없는 매트로이드'''({{llang|en|loopless matroid}})라고 한다.

== 연산 ==
=== 부분 매트로이드 ===
매트로이드 <math>(E,\mathcal I)</math>의 [[부분 집합]] <math>S\subseteq E</math> 위에서, <math>(S,\mathcal I\cap\operatorname{Pow}(S))</math>는 매트로이드를 이룬다. 이를 <math>E</math>의 '''부분 매트로이드'''({{llang|en|submatroid}})라고 한다. 매트로이드의 부분 집합 <math>S</math>의 '''계수'''는 부분 매트로이드로서의 계수이다.

=== 쌍대 매트로이드 ===
매트로이드 <math>(E,\mathcal I)</math>의 '''쌍대 매트로이드''' <math>(E^*,\mathcal I^*)</math>는 다음과 같이 정의된다. 집합으로서, <math>E=E^*</math>이지만,
:<math>\mathcal I^*=\{S\in\mathcal P(E)\colon\operatorname{cl}_{\mathcal I}(E\setminus S)=E\}</math>
이다. 이에 따라, <math>E</math>의 기저는 항상 <math>E^*</math>의 기저의 [[여집합]]이다.

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

=== 직합 ===
두 매트로이드 <math>(E_1,\mathcal I_1)</math>, <math>(E_2,\mathcal I_2)</math>가 주어졌을 때, [[분리합집합]]
:<math>E=E_1\sqcup E_2</math>
위에 매트로이드 구조
:<math>\mathcal I=\{I_1\sqcup I_2\colon I_1\in\mathcal I_1,\;I_2\in\mathcal I_2\}</math>
를 부여할 수 있다. 이를 이 두 매트로이드의 '''직합'''(直合, {{llang|en|direct sum}})이라고 하며, <math>E_1\oplus E_2</math>로 표기한다. (이 용어는 [[벡터 공간]]의 부분 집합으로 나타내어지는 매트로이드의 경우, 매트로이드 직합은 해당 [[벡터 공간]]들의 [[직합]]에 해당하기 때문에 유래하였다.)

=== 마이너 ===
{{본문|매트로이드 마이너}}
부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 '''[[매트로이드 마이너]]'''라고 한다. 이는 [[그래프 마이너]]의 일반화이다.

=== 안둘레와 밖둘레 ===
{{본문|안둘레}}
매트로이드의 '''[[안둘레]]'''는 가장 작은 회로의 크기이다. 마찬가지로, 매트로이드의 '''[[안둘레|밖둘레]]'''는 회로들의 크기의 [[상한]]이다.

== 성질 ==
=== 계수 ===
유한 매트로이드의 서로 다른 기저들의 [[집합의 크기|크기]]는 서로 같다.

만약 [[일반화 연속체 가설]]이 참이라면, 모든 (유한 또는 무한) 매트로이드들의 서로 다른 기저들의 [[집합의 크기|크기]]는 서로 같은 [[기수 (수학)|기수]]이다.<ref>{{저널 인용|이름=Denis A.|성=Higgs|제목=Equicardinality of bases in B-matroids|저널=Canadian Mathematical Bulletin|권=12|날짜=1969-03|쪽=861–862|doi=10.4153/CMB-1969-112-6|issn=0008-4395|언어=en}}</ref>{{rp|861, Theorem 2}} 이 경우, 기저의 크기를 매트로이드의 '''계수'''(係數, {{llang|en|rank}})라고 한다. 보다 일반적으로, 만약 <math>\kappa\in\operatorname{Card}</math> 이하에서 [[일반화 연속체 가설]]이 성립한다면 (즉, <math>\forall\aleph_0\le\lambda\le\kappa\colon \lambda^+=2^\lambda</math>), 크기가 <math>\kappa</math> 이하인 매트로이드의 모든 기저의 크기는 같다.

만약 [[선택 공리]]를 추가한 [[체르멜로-프렝켈 집합론]](ZFC)이 무모순적이라면, “임의의 매트로이드에서, 기저들의 [[집합의 크기|크기]]는 같다”라는 명제는 ZFC와 독립적이다.<ref>{{저널 인용|url=http://www.math.uni-hamburg.de/home/geschke/papers/UniformMatroid7.pdf | doi=10.1090/proc/12667  | 제목=Self-dual uniform matroids on infinite sets | 이름1=Nathan | 성1=Bowler | 이름2=Stefan | 성2=Geschke | mr=3430826 | 저널=Proceedings of the American Mathematical Society | 권= 144 |날짜=2016|쪽= 459–471 | issn=0002-9939 | 언어=en}}</ref>{{rp|§4, Corollary 17}}

=== 작은 매트로이드의 수 ===
작은 크기의 매트로이드의 동형류의 수 및 고리 없는 매트로이드의 동형류의 수 및 단순 매트로이드의 동형류의 수는 다음과 같다.<ref>{{저널 인용|arxiv=math/0702316|제목=Matroids with nine elements|이름=Dillon|성=Mayhew|이름2=Gordon F.|성2=Royle|bibcode=2007math......2316M|날짜=2007|언어=en}}</ref>{{rp|§5, Table 1, Table 2}}
{| class=wikitable style="text-align: right"
! 크기 || 매트로이드 동형류의 수<br>{{OEIS|A55545}} || 고리 없는 매트로이드 동형류의 수<br>{{OEIS|A58718}} || 단순 매트로이드 동형류의 수<br>{{OEIS|A2773}} || 주어진 집합 위의 매트로이드 구조의 수<br> {{OEIS|A58673}} || 주어진 집합 위의 고리 없는 매트로이드 구조의 수<br>{{OEIS|A58712}} || 주어진 집합 위의 단순 매트로이드 구조의 수<br>{{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
|}

크기가 <math>n</math>인 집합 위의 매트로이드 구조의 수를 <math>m_n</math>이라고 하면, 다음이 성립한다.<ref>{{저널 인용|제목=On the number of matroids|arxiv=1206.6270|bibcode=2012arXiv1206.6270B|이름=Nikhil |성=Bansal|이름2=Rudi A. |성2=Pendavingh|이름3=Jorn G.|성3=van der Pol|doi=10.1007/s00493-014-3029-z|저널=Combinatorica|날짜=2015-04|권=35|호=3|쪽=253–277|issn= 0209-9683|언어=en}}</ref>{{rp|Theorem 3; (1)}}
:<math>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)</math>

=== 범주론적 성질 ===
임의의 두 유한 매트로이드 <math>E</math>, <math>E'</math> 사이의 함수 <math>f\colon E\to E'</math>에 대하여 다음 세 조건이 서로 [[동치]]이며, 이를 만족시키는 함수를 '''강사상'''(強寫像, {{llang|en|strong morphism}})이라고 하자.
* 임의의 <math>B\subseteq A\subseteq E</math>에 대하여, <math>\operatorname{rank}(f(A)|f(B)) \le \operatorname{rank}(A|B)</math>이다.
* 임의의 <math>A\subseteq E</math>에 대하여, <math>\operatorname{cl}(f(A))=f(\operatorname{cl}(A))</math>이다.
* <math>E</math>의 닫힌집합의 [[상 (수학)|상]]은 항상 <math>E'</math>의 닫한집합이다.

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

그렇다면, <math>\operatorname{finMatr}</math>는 [[구체적 범주]]이며, 망각 함자
:<math>|-|\colon \operatorname{finMatr}\to\operatorname{finSet}</math>
가 존재한다. 이 밖에도, 균등 매트로이드 [[함자 (수학)|함자]]
:<math>\operatorname{Unif}(-,0) \colon\operatorname{finSet} \to \operatorname{finMatr}</math>
:<math>\operatorname{Unif}(-,0)^* \colon\operatorname{finSet} \to \operatorname{finMatr}</math>
:<math>\operatorname{Unif}(-,0) \colon S\mapsto \operatorname{Unif}(S,0) </math>
:<math>\operatorname{Unif}(-,0)^* \colon S\mapsto \operatorname{Unif}(S,0)^* = \operatorname{Unif}(S,|S|) </math>
및
:<math>(-)_0 \colon\operatorname{finMatr} \to \operatorname{finSet}</math>
:<math>(-)_0 \colon E \mapsto \operatorname{cl}_E(\varnothing)</math>
:<math>(-)_0 \colon (E \xrightarrow f E') \mapsto \left(f\restriction (\operatorname{cl}_E(\varnothing))\right)</math>
를 정의할 수 있다. 이들은 다음과 같은 [[수반 함자]] 관계를 이룬다.<ref name="HP">{{저널 인용|제목=The category of matroids | 이름=Chris | 성=Heunen | 이름2=Vaia | 성2=Patta | doi=10.1007/s10485-017-9490-2 | 저널=Applied Categorical Structures | 날짜=2017 | 권=25 | issn= 0927-2852 | arxiv=1512.01390 | bibcode=2015arXiv151201390H |언어=en}}</ref>{{rp|Theorem 2.9}}
:<math>\operatorname{Unif}(-,0)^* \dashv |-| \dashv \operatorname{Unif}(-,0) \dashv (-)_0</math>
즉, 균등 매트로이드 <math>\operatorname{Unif}(S,0)^*</math>은 “자유 매트로이드”이며, <math>\operatorname{Unif}(S,0)</math>은 “쌍대 자유 매트로이드”이다.

<math>\operatorname{finMatr}</math>는 모든 유한 [[쌍대곱]]을 갖지만, 모든 유한 [[곱 (범주론)|곱]]을 갖지 못하며, 또한 유한 [[쌍대 극한]] 가운데 일부는 존재하지 못한다.,<ref name="HP"/>{{rp|§3}}

== 예 ==
=== 균등 매트로이드 ===
임의의 집합 <math>E</math> 위에,
:<math>\mathcal I=\{\varnothing\}</math>
:<math>\mathcal B=\{\varnothing\}</math>
:<math>\mathcal C=\{\{x\}\colon x\in E\}</math>
:<math>\operatorname{rank}(A|B)=0\qquad(B\subseteq A\subseteq E)</math>
:<math>\operatorname{cl}(A)=E\qquad(A\subseteq E)</math>
를 부여하면, 이는 매트로이드를 이룬다. 이를 <math>\operatorname{Unif}(E,0)</math>라고 하자.

마찬가지로, 임의의 집합 <math>E</math> 위에,
:<math>\mathcal I=\operatorname{Pow}(E)</math>
:<math>\mathcal B=\{E\}</math>
:<math>\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)</math>
:<math>\operatorname{cl}(A)=A\qquad(A\subseteq E)</math>
을 부여하면, 이는 매트로이드를 이룬다. 이는 <math>\operatorname{Unif}(E,0)</math>의 쌍대 매트로이드 <math>\operatorname{Unif}(E,0)^*</math>이다.

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

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

이와 같은 두 종류의 매트로이드의 직합으로 표현될 수 있는 매트로이드를 '''이산 매트로이드'''(離散matroid, {{llang|en|discrete matroid}})라고 한다.

보다 일반적으로, 임의의 집합 <math>E</math> 및 자연수 <math>0\le k</math>에 대하여, '''균등 매트로이드'''(均等matroid, {{llang|en|uniform matroid}}) <math>\operatorname{Unif}(E,k)</math>는 <math>E</math> 위의 다음과 같은 매트로이드이다.
:<math>\mathcal I=\{S\subseteq E\colon |S|\le k\}</math>
:<math>\mathcal B=\{S\subseteq E\colon |S| =k\}</math>
:<math>\mathcal C=\{S\subseteq E\colon |S| =k+1\}</math>
이는 항상 유한형 매트로이드이다.

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

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

=== 그래프의 매트로이드 ===
{{본문|순환 매트로이드}}
모든 [[그래프]]에는 '''[[순환 매트로이드]]'''라는 유한형 매트로이드 및 그 쌍대 매트로이드인 '''접합 매트로이드'''가 대응된다.

=== 작은 크기의 매트로이드 ===
공집합 위에는 유일한 매트로이드 구조가 존재하며, 이는 균등 매트로이드 <math>\operatorname{Unif}(0,0)</math>이다.

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

==== 크기 1 ====
크기 1의 매트로이드 동형류들은 다음 두 가지이다.
* <math>\operatorname{Unif}(1,1)</math> (계수 1). 이는 한 변을 갖는 [[경로 그래프]] <math>P_2</math>의 [[순환 매트로이드]]이다.
* <math>\operatorname{Unif}(1,0)</math> (계수 0). 이는 하나의 꼭짓점과 하나의 변을 갖는 [[다중 그래프]]의 [[순환 매트로이드]]이다.

==== 크기 2 ====
크기 2의 매트로이드 동형류들은 다음 네 가지이다.
* <math>\operatorname{Unif}(2,2)</math> (계수 2)
* <math>\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(1,0)</math> (계수 1)
* <math>\operatorname{Unif}(2,1)</math> (계수 1)
* <math>\operatorname{Unif}(2,0)</math> (계수 0)
이 가운데 단순 매트로이드인 것은 첫째 밖에 없다.

==== 크기 3 ====
크기 3의 매트로이드 동형류들은 다음 여덟 가지이다.
* <math>\operatorname{Unif}(3,3)</math> (계수 3)
* <math>\operatorname{Unif}(3,2)</math> (계수 2)
* <math>\operatorname{Unif}(2,2)\oplus\operatorname{Unif}(1,0)</math> (계수 2)
* <math>\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,1)</math> (계수 2)
* <math>\operatorname{Unif}(3,1)</math> (계수 1)
* <math>\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,0)</math> (계수 1)
* <math>\operatorname{Unif}(2,0)\oplus\operatorname{Unif}(1,1)</math> (계수 1)
* <math>\operatorname{Unif}(3,0)</math> (계수 0)
이 가운데 단순 매트로이드인 것은 처음 두 개이다.

==== 크기 4 ====
크기 4의 매트로이드는 총 17개가 있으며, 하나를 제외하고는 나머지는 균등 매트로이드들의 직합으로 표현될 수 있다.
* 계수 0:
** <math>\operatorname{Unif}(4,0)</math>
* 계수 1:
** <math>\operatorname{Unif}(4,1)</math>
** <math>\operatorname{Unif}(3,1)\oplus\operatorname{Unif}(1,0)</math>
** <math>\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(2,0)</math>
** <math>\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(3,0)</math>
* 계수 2:
** <math>\operatorname{Unif}(4,2)</math>
** <math>\operatorname{Unif}(3,1)\oplus\operatorname{Unif}(1,1)</math>
** <math>\operatorname{Unif}(3,2)\oplus\operatorname{Unif}(1,0)</math>
** <math>\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(2,1)</math>
** <math>\operatorname{Unif}(2,2)\oplus\operatorname{Unif}(2,0)</math>
** <math>\operatorname{Unif}(2,1)\oplus\operatorname{Unif}(1,1)\oplus\operatorname{Unif}(1,0)</math>
** 균등 매트로이드의 직합이 아닌 매트로이드 <math>X</math>

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

여기서, 매트로이드 <math>X</math>는 다음과 같다.
:<math>E=\{\mathsf a,\mathsf b,\mathsf c,\mathsf d\}</math>
:<math>\mathcal B=\{S\subseteq E\colon |S|=2,\;S\ne\{\mathsf a,\mathsf b\}\}</math>
:<math>\mathcal C=\left\{\{\mathsf a,\mathsf b\},\{\mathsf b,\mathsf c,\mathsf d\},\{\mathsf a,\mathsf c,\mathsf d\}\right\}</math>

이는 다음과 같은 [[다중 그래프]]에 대응하는 [[순환 매트로이드]]이다.
:[[파일:Shannon multigraph 3.svg|150px]]

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

== 역사 ==
매트로이드의 개념은 [[해슬러 휘트니]]가 1935년에 도입하였다.<ref>{{저널 인용|last=Whitney|first=Hassler|authorlink=해슬러 휘트니|날짜=1935|title=On the abstract properties of linear dependence|url=https://archive.org/details/sim_american-journal-of-mathematics_1935-07_57_3/page/n49|journal=American Journal of Mathematics |volume=57|pages=509–533|doi=10.2307/2371182|issue=3||mr=1507091|jstor=2371182|zbl=0012.00404|jfm=61.0073.03|언어=en}}</ref> 1938년에 일본의 [[나카자와 다케오]]({{llang|ja|中澤 武雄}}, 1913~1946)가 동일한 개념을 독립적으로 발견하였으나,<ref>{{저널 인용|제목=Zur Axiomatik der linearen Abhängigkeit Ⅰ|성=Nakasawa|이름=Takeo|저널=Science reports of the Tokyo Bunrika Daigaku A|권=2|쪽=235–255|날짜=1935|출판사=東京文理科大学|url=http://jairo.nii.ac.jp/0025/00023234/en|zbl=0012.22001|jfm=61.1341.03|언어=de}}</ref><ref>{{저널 인용|제목=Zur Axiomatik der linearen Abhängigkeit Ⅱ|성=Nakasawa|이름=Takeo|저널=Science reports of the Tokyo Bunrika Daigaku A|권=3|쪽=45–69|날짜=1936|출판사=東京文理科大学|url=http://jairo.nii.ac.jp/0025/00023236/en|zbl=0013.31406|jfm=62.0649.01|언어=de}}</ref><ref>{{저널 인용|제목=Zur Axiomatik der linearen Abhängigkeit Ⅲ|성=Nakasawa|이름=Takeo|저널=Science reports of the Tokyo Bunrika Daigaku A|권=3|쪽=123–136|날짜=1936|출판사=東京文理科大学|url=http://jairo.nii.ac.jp/0025/00023235/en|zbl=0016.03704|jfm=62.1400.01|언어=de}}</ref><ref>{{서적 인용|제목=A lost mathematician, Takeo Nakasawa: the forgotten father of matroid theory|날짜=2009|이름=Hirokazu|성=Nishimura|이름2=Susumu|성2= Kuroda |출판사=Springer-Verlag|doi=10.1007/978-3-7643-8573-6|isbn=978-3-7643-8572-9|zbl=1163.01001 | 언어=en}}</ref> 크게 알려지지 못했다.

이후 [[윌리엄 토머스 텃]]이 매트로이드 이론을 발달시켰고, [[텃 다항식]]과 같은 중요한 개념들을 발견하였다.<ref>{{저널 인용|last=Tutte|first=William Thomas |저자링크=윌리엄 토머스 텃|날짜=1965|title=Lectures on matroids|journal=Journal of Research of the National Bureau of Standards (U.S.A.) B |volume=69|pages=1–47|doi=10.6028/jres.069b.001|zbl= 0151.33801|언어=en}}</ref>

1970년에 [[잔카를로 로타]]와 헨리 하울런드 크레이포({{llang|en|Henry Howland Crapo}})는 매트로이드 이론에 대한 최초의 책을 출판하였다.<ref>{{서적 인용|성=Crapo|이름=Henry Howland|성2=Rota|이름2=Gian-Carlo|저자링크2=잔카를로 로타|제목=On the Foundations of Combinatorial Theory Ⅱ. Combinatorial geometries|출판사=Massachusetts Institute of Technology Press|날짜=1970|isbn=978-0-262-53016-3|mr=0290980|언어=en}}</ref> (이 책에서는 “매트로이드” 대신 “조합 기하”({{llang|en|combinatorial geometry}})라는 용어가 사용되었다.) 이듬해에 윌리엄 토머스 텃은 매트로이드 이론에 대한 둘째 책을 출판하였다.<ref>{{서적 인용 | zbl=0231.05027 | last=Tutte | first=William Thomas | 저자링크=윌리엄 토머스 텃|title=Introduction to the theory of matroids | 총서=Modern Analytic and Computational Methods in Science and Mathematics | volume=37 | publisher= Elsevier | 날짜=1971|언어=en }}</ref>

무한 매트로이드의 올바른 정의는 오랫동안 미해결 문제였다. 1966년에 [[리하르트 라도]]는 무한 매트로이드의 올바른 정의에 대한 문제를 제기하였다.<ref>{{저널 인용|url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-cmv14i1n20 | 제목=Abstract linear dependence | 이름=Richard | 성=Rado | 저자링크=리하르트 라도 | 저널=Colloquim Mathematicae | 권=14 | 호=1 | 쪽=257–264 | 날짜=1966 | issn=0010-1354 | zbl=0136.26203 | 언어=en}}</ref>{{rp|263, §6(c), Problem P531}} 데니스 힉스({{llang|en|Denis A. Higgs}}, 1932~2011)는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 “B-매트로이드”({{llang|en|B-matroid}})라는 개념이었다.<ref>{{저널 인용|이름=Denis A.|성=Higgs|날짜=1969|제목=Matroids and duality|저널=Colloquium Mathematicae|issn=0010-1354 | 권=20|호=2 | 쪽=215–20 |url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.desklight-fc62099c-b98b-4023-b9aa-a1dc5d1314aa | zbl=0192.33402 | 언어=en}}</ref>

이후 1978년에 제임스 옥슬리({{llang|en|James G. Oxley}})는 “B-매트로이드”의 모임이 쌍대성을 가지며 [[매트로이드 마이너]]에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다.<ref>{{저널 인용|이름=James G.|성=Oxley|제목=Infinite matroids|저널=Proceedings of the London Mathematical Society|권=37|날짜=1978-09|호=3|쪽=259–272|doi=10.1112/plms/s3-37.2.259|zbl=0436.05017|언어=en}}</ref> 이후 2010년에 이 “B-매트로이드”에 대한 여러 자연스러운 공리화들이 발견되었으며,<ref name="BDKPW"/> 이후 이 개념이 무한 매트로이드의 통상적인 정의로 굳어지게 되었다.

== 각주 ==
{{각주}}

== 외부 링크 ==
* {{eom|title=Matroid}}
* {{eom|title=Tutte polynomial}}
* {{매스월드|id=Matroid|title=Matroid}}
* {{매스월드|id=OrientedMatroid|title=Oriented matroid}}
* {{nlab|id=matroid|title=Matroid}}
* {{웹 인용|url=http://userhome.brooklyn.cuny.edu/skingan/matroids/|제목=Matroid theory|이름= Sandra|성= Kingan|언어=en}}
* {{웹 인용|url=http://matroidunion.org/|제목=Matroid Union|이름=Dillon|성=Mayhew|이름2=Stefan|성2=van Zwam|이름3= Peter|성3= Nelson|이름4= Irene |성4=Pivotto|이름5= Tony |성5=Huynh|이름6= Nathan|성6= Bowler|언어=en}}
* {{웹 인용|url=https://homepages.dias.ie/dukes/matroid.html|제목=The number of matroids up to ''n''=8|이름=W. M. B.|성=Dukes|언어=en}}

{{전거 통제}}

[[분류:매트로이드 이론| ]]
[[분류:집합족]]
[[분류:폐포 연산자]]