조합론 에서 매트로이드 (영어 : matroid 메이트로이드[* ] )는 일차 독립 의 성질을 공리화하여 얻은 조합론적 구조이다.[ 1] [ 2] [ 3] [ 4] [ 5] [ 6] 그래프 이론 · 선형대수학 · 체론 등의 다양한 분야에 응용된다.
매트로이드 의 개념은 다양하게 정의될 수 있지만, 이 정의들은 서로 동치 이다.
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
집합
E
{\displaystyle E}
집합족
I
⊆
Pow
(
E
)
{\displaystyle {\mathcal {I}}\subseteq \operatorname {Pow} (E)}
독립 집합 (獨立集合, 영어 : independent set )이라고 하며, 독립 집합이 아닌
E
{\displaystyle E}
부분 집합 을 종속 집합 (從屬集合, 영어 : dependent set )이라고 한다.이 데이터는 다음 공리들을 만족시켜야 한다.[ 7] :§1.1
(공집합의 독립성) 공집합 은 독립 집합이다. 즉,
∅
∈
I
{\displaystyle \varnothing \in {\mathcal {I}}}
(유전성 영어 : hereditary property ) 독립 집합의 부분집합은 독립이다. 즉, 만약
B
⊆
A
∈
I
{\displaystyle B\subseteq A\in {\mathcal {I}}}
B
∈
I
{\displaystyle B\in {\mathcal {I}}}
(추가성 영어 : augmentation property ) 만약
A
,
B
∈
I
{\displaystyle A,B\in {\mathcal {I}}}
A
{\displaystyle A}
I
{\displaystyle {\mathcal {I}}}
극대 원소 이지만
B
{\displaystyle B}
I
{\displaystyle {\mathcal {I}}}
극대 원소 가 아니라면,
B
∪
{
a
}
∈
I
{\displaystyle B\cup \{a\}\in {\mathcal {I}}}
a
∈
A
∖
B
{\displaystyle a\in A\setminus B}
(국소적 극대 독립 집합의 존재) 만약
I
∋
A
⊂
B
⊂
E
{\displaystyle {\mathcal {I}}\ni A\subset B\subset E}
구간
I
∩
[
A
,
B
]
=
{
S
∈
I
:
A
⊆
S
⊂
B
}
{\displaystyle {\mathcal {I}}\cap [A,B]=\{S\in {\mathcal {I}}\colon A\subseteq S\subset B\}}
극대 원소 를 갖는다. 만약
E
{\displaystyle E}
유한 집합 이라면, 마지막 조건은 자동적으로 성립된다.
매트로이드
(
E
,
B
)
{\displaystyle (E,{\mathcal {B}})}
집합
E
{\displaystyle E}
집합족
B
⊆
Pow
(
E
)
{\displaystyle {\mathcal {B}}\subseteq \operatorname {Pow} (E)}
기저 (基底, 영어 : basis )라고 하며, 기저의 부분 집합을 독립 집합 이라고 한다.이는 다음 조건들을 만족시켜야 한다.[ 7] :§1.2
B
≠
∅
{\displaystyle {\mathcal {B}}\neq \varnothing }
(추가성) 임의의
B
,
B
′
∈
B
{\displaystyle B,B'\in {\mathcal {B}}}
x
∈
B
∖
B
′
{\displaystyle x\in B\setminus B'}
x
′
∈
B
′
∖
B
{\displaystyle x'\in B'\setminus B}
(
B
∖
{
x
}
)
∪
{
x
′
}
∈
B
{\displaystyle (B\setminus \{x\})\cup \{x'\}\in {\mathcal {B}}}
(국소적 극대 독립 집합의 존재) 임의의 부분 집합
E
′
⊆
E
{\displaystyle E'\subseteq E}
B
∈
B
{\displaystyle B\in {\mathcal {B}}}
I
⊆
B
∩
E
′
{\displaystyle I\subseteq B\cap E'}
B
′
∈
B
{\displaystyle B'\in {\mathcal {B}}}
I
′
⊆
B
′
{\displaystyle I'\subseteq B'}
I
⊆
I
′
⊆
B
′
∈
B
{\displaystyle I\subseteq I'\subseteq B'\in {\mathcal {B}}}
임의의
I
′
⊆
C
∈
B
{\displaystyle I'\subseteq C\in {\mathcal {B}}}
(
E
′
∖
I
′
)
∩
C
=
∅
{\displaystyle (E'\setminus I')\cap C=\varnothing }
매트로이드
(
E
,
C
)
{\displaystyle (E,{\mathcal {C}})}
집합
E
{\displaystyle E}
집합족
C
⊆
Pow
(
E
)
{\displaystyle {\mathcal {C}}\subseteq \operatorname {Pow} (E)}
회로 (回路, 영어 : circuit )라고 한다. 회로를 부분 집합 으로 포함하지 않는 집합을 독립 집합 이라고 한다.이 데이터는 다음 공리들을 만족시켜야 한다.[ 7] :§1.4
(공집합의 독립성) 공집합 은 회로가 아니다. 즉,
∅
∉
C
{\displaystyle \varnothing \not \in {\mathcal {C}}}
임의의
C
,
C
′
∈
C
{\displaystyle C,C'\in {\mathcal {C}}}
C
⊆
C
′
{\displaystyle C\subseteq C'}
C
=
C
′
{\displaystyle C=C'}
(회로의 제거) 임의의 회로
C
∈
C
{\displaystyle C\in {\mathcal {C}}}
U
⊆
C
{\displaystyle {\mathcal {U}}\subseteq {\mathcal {C}}}
X
⊆
E
{\displaystyle X\subseteq E}
∀
U
∈
U
:
|
X
∩
U
|
=
1
{\displaystyle \forall U\in {\mathcal {U}}\colon |X\cap U|=1}
Y
=
C
∖
⋃
U
{\displaystyle \textstyle Y=C\setminus \bigcup {\mathcal {U}}}
∀
x
:
x
∈
f
(
x
)
{\displaystyle \forall x\colon x\in f(x)}
f
:
Y
→
C
∩
Pow
(
Y
∖
X
)
{\displaystyle \textstyle f\colon Y\to {\mathcal {C}}\cap \operatorname {Pow} (Y\setminus X)}
(국소적 극대 독립 집합의 존재) 임의의 부분 집합
E
′
⊆
E
{\displaystyle E'\subseteq E}
I
⊆
E
′
{\displaystyle I\subseteq E'}
I
{\displaystyle I}
E
′
{\displaystyle E'}
부분 순서 집합 은 적어도 하나 이상의 극대 원소 를 갖는다. 매트로이드
(
E
,
cl
)
{\displaystyle (E,\operatorname {cl} )}
집합
E
{\displaystyle E}
함수
cl
:
Pow
(
E
)
→
Pow
(
E
)
{\displaystyle \operatorname {cl} \colon \operatorname {Pow} (E)\to \operatorname {Pow} (E)}
폐포 부분 집합
D
⊆
E
{\displaystyle D\subseteq E}
x
∈
D
∩
cl
(
D
∖
{
x
}
)
{\displaystyle x\in D\cap \operatorname {cl} (D\setminus \{x\})}
x
{\displaystyle x}
D
{\displaystyle D}
종속 집합 이라고 하며, 종속 집합이 아닌 부분 집합을 독립 집합 이라고 한다. 이 데이터는 다음 조건들을 만족시켜야 한다.[ 7] :§1.3
cl
{\displaystyle \operatorname {cl} }
폐포 연산 이다. 즉,
임의의
X
⊆
E
{\displaystyle X\subseteq E}
X
⊆
cl
(
X
)
=
cl
(
cl
(
X
)
)
{\displaystyle X\subseteq \operatorname {cl} (X)=\operatorname {cl} (\operatorname {cl} (X))}
임의의
X
⊆
Y
⊆
E
{\displaystyle X\subseteq Y\subseteq E}
cl
(
X
)
⊆
cl
(
Y
)
{\displaystyle \operatorname {cl} (X)\subseteq \operatorname {cl} (Y)}
임의의 부분 집합
X
⊆
E
{\displaystyle X\subseteq E}
E
{\displaystyle E}
이항 관계 는 대칭 관계 이다.
x
∼
X
y
⟺
x
∈
cl
(
X
∪
{
y
}
)
∖
cl
(
X
)
{\displaystyle x\sim _{X}y\iff x\in \operatorname {cl} (X\cup \{y\})\setminus \operatorname {cl} (X)}
(국소적 극대 독립 집합의 존재) 임의의 부분 집합
E
′
⊆
E
{\displaystyle E'\subseteq E}
I
⊆
E
′
{\displaystyle I\subseteq E'}
I
⊆
I
′
⊆
E
′
{\displaystyle I\subseteq I'\subseteq E'}
I
′
{\displaystyle I'}
x
∈
E
′
∖
I
′
{\displaystyle x\in E'\setminus I'}
E
′
∪
{
x
}
{\displaystyle E'\cup \{x\}}
cl
(
S
)
=
S
{\displaystyle \operatorname {cl} (S)=S}
S
{\displaystyle S}
닫힌집합 (-集合, 영어 : closed set ) 또는 평탄면 (平坦面, 영어 : flat 플랫[* ] )이라고 한다.
매트로이드
(
E
,
rank
)
{\displaystyle (E,\operatorname {rank} )}
집합
E
{\displaystyle E}
함수
rank
(
−
|
−
)
:
Pair
(
E
)
→
N
⊔
{
∞
}
{\displaystyle \operatorname {rank} (-|-)\colon \operatorname {Pair} (E)\to \mathbb {N} \sqcup \{\infty \}}
상대 계수 함수 (相對係數函數, 영어 : relative rank function )라고 한다. 또한, 부분 집합
I
⊆
E
{\displaystyle I\subseteq E}
∀
x
∈
I
:
rank
(
I
|
I
∖
{
x
}
)
>
0
{\displaystyle \forall x\in I\colon \operatorname {rank} (I|I\setminus \{x\})>0}
I
{\displaystyle I}
독립 집합 이라고 하자. 여기서
Pair
(
E
)
=
{
(
S
,
T
)
⊆
E
:
T
⊆
S
}
⊆
Pow
(
E
)
2
{\displaystyle \operatorname {Pair} (E)=\{(S,T)\subseteq E\colon T\subseteq S\}\subseteq \operatorname {Pow} (E)^{2}}
는
E
{\displaystyle E}
사슬 들의 집합이다.
이 데이터는 다음 조건들을 만족시켜야 한다.[ 7] :§1.5
임의의
(
A
,
B
)
∈
Pair
(
E
)
{\displaystyle (A,B)\in \operatorname {Pair} (E)}
rank
(
A
|
B
)
≤
|
A
∖
B
|
{\displaystyle \operatorname {rank} (A|B)\leq |A\setminus B|}
임의의
A
,
B
⊆
E
{\displaystyle A,B\subseteq E}
rank
(
A
|
A
∩
B
)
≥
rank
(
A
∪
B
|
B
)
{\displaystyle \operatorname {rank} (A|A\cap B)\geq \operatorname {rank} (A\cup B|B)}
(유한 사슬 에 대한 분해) 임의의
C
⊆
B
⊆
A
⊆
E
{\displaystyle C\subseteq B\subseteq A\subseteq E}
rank
(
A
|
C
)
=
rank
(
A
|
B
)
+
rank
(
B
|
C
)
{\displaystyle \operatorname {rank} (A|C)=\operatorname {rank} (A|B)+\operatorname {rank} (B|C)}
임의의 집합족
U
⊆
E
{\displaystyle {\mathcal {U}}\subseteq E}
∀
U
∈
U
:
rank
(
U
|
⋂
U
)
=
0
{\displaystyle \textstyle \forall U\in {\mathcal {U}}\colon \operatorname {rank} (U|\bigcap {\mathcal {U}})=0}
rank
(
⋃
U
|
⋂
U
)
=
0
{\displaystyle \textstyle \operatorname {rank} (\bigcup {\mathcal {U}}|\bigcap {\mathcal {U}})=0}
(국소적 극대 독립 집합의 존재) 임의의 부분 집합
E
′
⊆
E
{\displaystyle E'\subseteq E}
I
⊆
E
′
{\displaystyle I\subseteq E'}
I
{\displaystyle I}
E
′
{\displaystyle E'}
부분 순서 집합 은 적어도 하나 이상의 극대 원소 를 갖는다. 매트로이드
E
{\displaystyle E}
부분 집합
F
⊆
E
{\displaystyle F\subseteq E}
rank
(
E
|
F
)
=
1
{\displaystyle \operatorname {rank} (E|F)=1}
를 만족시키는 것들 가운데 (부분 집합 관계에 대하여) 극대 원소 라면,
F
{\displaystyle F}
초평면 (超平面, 영어 : hyperplane 하이퍼플레인[* ] )이라고 한다.
일부 정의들 사이의 관계는 다음과 같다.
정의
독립 집합
I
{\displaystyle I}
종속 집합
D
{\displaystyle D}
기저
B
{\displaystyle B}
회로
C
{\displaystyle C}
닫힌집합
F
{\displaystyle F}
독립 집합을 통한 정의
—
독립 집합이 아닌 집합
극대 독립 집합
극소 종속 집합
임의의
F
⊇
I
∈
I
{\displaystyle F\supseteq I\in {\mathcal {I}}}
x
∈
E
{\displaystyle x\in E}
I
∪
{
x
}
∈
I
⟹
x
∈
F
{\displaystyle I\cup \{x\}\in {\mathcal {I}}\implies x\in F}
기저를 통한 정의
∃
B
∈
B
:
I
⊆
B
{\displaystyle \exists B\in {\mathcal {B}}\colon I\subseteq B}
∀
B
∈
B
:
D
⊈
B
{\displaystyle \forall B\in {\mathcal {B}}\colon D\not \subseteq B}
—
모든 진부분 집합 이 기저이지만, 기저가 아닌 집합
회로를 통한 정의
∀
C
∈
C
:
C
⊈
I
{\displaystyle \forall C\in {\mathcal {C}}\colon C\not \subseteq I}
∃
C
∈
C
:
C
⊆
D
{\displaystyle \exists C\in {\mathcal {C}}\colon C\subseteq D}
회로를 포함하지 않는 극대 집합
—
계수를 통한 정의
∀
x
∈
I
:
rank
(
I
|
I
∖
{
x
}
)
>
0
{\displaystyle \forall x\in I\colon \operatorname {rank} (I|I\setminus \{x\})>0}
∃
x
∈
D
:
rank
(
D
|
D
∖
{
x
}
)
=
0
{\displaystyle \exists x\in D\colon \operatorname {rank} (D|D\setminus \{x\})=0}
극대 독립 집합
극소 종속 집합
임의의
x
∈
E
{\displaystyle x\in E}
x
∈
F
⟺
rank
(
E
∪
{
x
}
|
E
)
=
0
{\displaystyle x\in F\iff \operatorname {rank} (E\cup \{x\}|E)=0}
폐포를 통한 정의
∀
x
∈
I
:
x
∉
cl
(
I
∖
{
x
}
)
{\displaystyle \forall x\in I\colon x\not \in \operatorname {cl} (I\setminus \{x\})}
∃
x
∈
D
:
x
∈
cl
(
D
∖
{
x
}
)
{\displaystyle \exists x\in D\colon x\in \operatorname {cl} (D\setminus \{x\})}
독립 집합이며, 또한 고정점 을 갖지 않는,
∀
x
∈
B
:
f
(
x
)
∈
cl
(
I
∖
{
x
,
f
(
x
)
}
)
{\displaystyle \forall x\in B\colon f(x)\in \operatorname {cl} (I\setminus \{x,f(x)\})}
f
:
B
→
B
{\displaystyle f\colon B\to B}
종속 집합이며, 임의의
x
,
y
∈
C
{\displaystyle x,y\in C}
y
∈
cl
(
C
∖
{
x
,
y
}
)
⟹
x
=
y
{\displaystyle y\in \operatorname {cl} (C\setminus \{x,y\})\implies x=y}
F
=
cl
F
{\displaystyle F=\operatorname {cl} F}
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
S
{\displaystyle S}
cl
(
S
)
{\displaystyle \operatorname {cl} (S)}
cl
(
S
)
=
S
∪
{
x
∈
E
:
∃
I
∈
I
:
I
∪
{
x
}
∉
I
}
{\displaystyle \operatorname {cl} (S)=S\cup \{x\in E\colon \exists I\in {\mathcal {I}}\colon I\cup \{x\}\not \in {\mathcal {I}}\}}
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
S
{\displaystyle S}
cl
(
S
)
{\displaystyle \operatorname {cl} (S)}
cl
(
S
)
=
max
{
S
′
⊆
E
:
rank
(
S
′
|
S
)
=
0
}
{\displaystyle \operatorname {cl} (S)=\max\{S'\subseteq E\colon \operatorname {rank} (S'|S)=0\}}
(이러한 최대 원소 가 항상 유일하게 존재함을 보일 수 있다.)
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
rank
(
A
|
B
)
=
max
{
|
I
∖
J
|
:
E
⊇
I
⊇
J
,
I
∈
I
∩
Pow
(
A
)
,
J
∈
max
(
I
∩
Pow
(
B
)
)
}
{\displaystyle \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
,
I
)
{\displaystyle (E,{\mathcal {I}})}
만약
E
{\displaystyle E}
유한 집합 이라면,
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
유한 매트로이드 (有限matroid, 영어 : finite matroid )라고 한다.
만약 모든 회로가 유한 집합 이라면 (즉, 임의의
A
⊆
E
{\displaystyle A\subseteq E}
A
{\displaystyle A}
A
{\displaystyle A}
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
유한형 매트로이드 (有限形matroid, 영어 : finitary matroid )라고 한다.[ 7] :18, §0
만약 모든 회로와 쌍대 회로의 교집합 이 유한 집합이라면,
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
유순 매트로이드 (柔順matroid, 영어 : tame matroid )라고 한다.[ 7] :28, §2.6 [ 8] :§1 즉, 다음과 같은 함의 관계가 존재한다.
유한 매트로이드 ⇒ 유한형 매트로이드 ⇒ 유순 매트로이드 ⇒ 매트로이드 크기 1의 회로는 고리 (영어 : loop )라고 하며, 크기 2의 회로는 평행변 (平行邊, 영어 : parallel lines )이라고 한다. (이러한 용어는 다중 그래프 에 대응되는 순환 그래프 에서 유래하였다.)
모든 회로의 크기가 2 이상인 매트로이드를 단순 매트로이드 (영어 : simple matroid )라고 한다. 모든 회로의 크기가 1 이상인 매트로이드를 고리 없는 매트로이드 (영어 : loopless matroid )라고 한다.
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
부분 집합
S
⊆
E
{\displaystyle S\subseteq E}
(
S
,
I
∩
Pow
(
S
)
)
{\displaystyle (S,{\mathcal {I}}\cap \operatorname {Pow} (S))}
E
{\displaystyle E}
부분 매트로이드 (영어 : submatroid )라고 한다. 매트로이드의 부분 집합
S
{\displaystyle S}
계수 는 부분 매트로이드로서의 계수이다.
매트로이드
(
E
,
I
)
{\displaystyle (E,{\mathcal {I}})}
쌍대 매트로이드
(
E
∗
,
I
∗
)
{\displaystyle (E^{*},{\mathcal {I}}^{*})}
E
=
E
∗
{\displaystyle E=E^{*}}
I
∗
=
{
S
∈
P
(
E
)
:
cl
I
(
E
∖
S
)
=
E
}
{\displaystyle {\mathcal {I}}^{*}=\{S\in {\mathcal {P}}(E)\colon \operatorname {cl} _{\mathcal {I}}(E\setminus S)=E\}}
이다. 이에 따라,
E
{\displaystyle E}
E
∗
{\displaystyle E^{*}}
여집합 이다.
이 연산은 쌍대성을 가진다. 즉,
E
∗
∗
=
E
{\displaystyle E^{**}=E}
두 매트로이드
(
E
1
,
I
1
)
{\displaystyle (E_{1},{\mathcal {I}}_{1})}
(
E
2
,
I
2
)
{\displaystyle (E_{2},{\mathcal {I}}_{2})}
분리합집합
E
=
E
1
⊔
E
2
{\displaystyle E=E_{1}\sqcup E_{2}}
위에 매트로이드 구조
I
=
{
I
1
⊔
I
2
:
I
1
∈
I
1
,
I
2
∈
I
2
}
{\displaystyle {\mathcal {I}}=\{I_{1}\sqcup I_{2}\colon I_{1}\in {\mathcal {I}}_{1},\;I_{2}\in {\mathcal {I}}_{2}\}}
를 부여할 수 있다. 이를 이 두 매트로이드의 직합 (直合, 영어 : direct sum )이라고 하며,
E
1
⊕
E
2
{\displaystyle E_{1}\oplus E_{2}}
벡터 공간 의 부분 집합으로 나타내어지는 매트로이드의 경우, 매트로이드 직합은 해당 벡터 공간 들의 직합 에 해당하기 때문에 유래하였다.)
부분 매트로이드를 취하는 연산 및 쌍대 매트로이드의 부분 매트로이드의 쌍대 매트로이드를 취하는 연산을 반복하여 얻는 매트로이드를 매트로이드 마이너 그래프 마이너 의 일반화이다.
이 부분의 본문은
안둘레 입니다.
매트로이드의 안둘레 밖둘레 상한 이다.
유한 매트로이드의 서로 다른 기저들의 크기 는 서로 같다.
만약 일반화 연속체 가설 이 참이라면, 모든 (유한 또는 무한) 매트로이드들의 서로 다른 기저들의 크기 는 서로 같은 기수 이다.[ 9] :861, Theorem 2 계수 (係數, 영어 : rank )라고 한다. 보다 일반적으로, 만약
κ
∈
Card
{\displaystyle \kappa \in \operatorname {Card} }
일반화 연속체 가설 이 성립한다면 (즉,
∀
ℵ
0
≤
λ
≤
κ
:
λ
+
=
2
λ
{\displaystyle \forall \aleph _{0}\leq \lambda \leq \kappa \colon \lambda ^{+}=2^{\lambda }}
κ
{\displaystyle \kappa }
만약 선택 공리 를 추가한 체르멜로-프렝켈 집합론 (ZFC)이 무모순적이라면, “임의의 매트로이드에서, 기저들의 크기 는 같다”라는 명제는 ZFC와 독립적이다.[ 10] :§4, Corollary 17
작은 크기의 매트로이드의 동형류의 수 및 고리 없는 매트로이드의 동형류의 수 및 단순 매트로이드의 동형류의 수는 다음과 같다.[ 11] :§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
{\displaystyle n}
m
n
{\displaystyle m_{n}}
[ 12] :Theorem 3; (1)
n
−
3
2
log
2
n
+
1
2
log
2
2
π
−
o
(
1
)
≤
log
2
log
2
m
n
≤
n
−
3
2
log
2
n
+
1
2
log
2
2
π
+
1
+
o
(
1
)
{\displaystyle 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
{\displaystyle E}
E
′
{\displaystyle E'}
f
:
E
→
E
′
{\displaystyle f\colon E\to E'}
동치 이며, 이를 만족시키는 함수를 강사상 (強寫像, 영어 : strong morphism )이라고 하자.
임의의
B
⊆
A
⊆
E
{\displaystyle B\subseteq A\subseteq E}
rank
(
f
(
A
)
|
f
(
B
)
)
≤
rank
(
A
|
B
)
{\displaystyle \operatorname {rank} (f(A)|f(B))\leq \operatorname {rank} (A|B)}
임의의
A
⊆
E
{\displaystyle A\subseteq E}
cl
(
f
(
A
)
)
=
f
(
cl
(
A
)
)
{\displaystyle \operatorname {cl} (f(A))=f(\operatorname {cl} (A))}
E
{\displaystyle E}
상 은 항상
E
′
{\displaystyle E'}
유한 매트로이드와 강사상의 작은 범주 를
finMatr
{\displaystyle \operatorname {finMatr} }
유한 집합 과 함수 의 작은 범주 를
finSet
{\displaystyle \operatorname {finSet} }
그렇다면,
finMatr
{\displaystyle \operatorname {finMatr} }
구체적 범주 이며, 망각 함자
|
−
|
:
finMatr
→
finSet
{\displaystyle |-|\colon \operatorname {finMatr} \to \operatorname {finSet} }
가 존재한다. 이 밖에도, 균등 매트로이드 함자
Unif
(
−
,
0
)
:
finSet
→
finMatr
{\displaystyle \operatorname {Unif} (-,0)\colon \operatorname {finSet} \to \operatorname {finMatr} }
Unif
(
−
,
0
)
∗
:
finSet
→
finMatr
{\displaystyle \operatorname {Unif} (-,0)^{*}\colon \operatorname {finSet} \to \operatorname {finMatr} }
Unif
(
−
,
0
)
:
S
↦
Unif
(
S
,
0
)
{\displaystyle \operatorname {Unif} (-,0)\colon S\mapsto \operatorname {Unif} (S,0)}
Unif
(
−
,
0
)
∗
:
S
↦
Unif
(
S
,
0
)
∗
=
Unif
(
S
,
|
S
|
)
{\displaystyle \operatorname {Unif} (-,0)^{*}\colon S\mapsto \operatorname {Unif} (S,0)^{*}=\operatorname {Unif} (S,|S|)}
및
(
−
)
0
:
finMatr
→
finSet
{\displaystyle (-)_{0}\colon \operatorname {finMatr} \to \operatorname {finSet} }
(
−
)
0
:
E
↦
cl
E
(
∅
)
{\displaystyle (-)_{0}\colon E\mapsto \operatorname {cl} _{E}(\varnothing )}
(
−
)
0
:
(
E
→
f
E
′
)
↦
(
f
↾
(
cl
E
(
∅
)
)
)
{\displaystyle (-)_{0}\colon (E{\xrightarrow {f}}E')\mapsto \left(f\upharpoonright (\operatorname {cl} _{E}(\varnothing ))\right)}
를 정의할 수 있다. 이들은 다음과 같은 수반 함자 관계를 이룬다.[ 13] :Theorem 2.9
Unif
(
−
,
0
)
∗
⊣
|
−
|
⊣
Unif
(
−
,
0
)
⊣
(
−
)
0
{\displaystyle \operatorname {Unif} (-,0)^{*}\dashv |-|\dashv \operatorname {Unif} (-,0)\dashv (-)_{0}}
즉, 균등 매트로이드
Unif
(
S
,
0
)
∗
{\displaystyle \operatorname {Unif} (S,0)^{*}}
Unif
(
S
,
0
)
{\displaystyle \operatorname {Unif} (S,0)}
finMatr
{\displaystyle \operatorname {finMatr} }
쌍대곱 을 갖지만, 모든 유한 곱 을 갖지 못하며, 또한 유한 쌍대 극한 가운데 일부는 존재하지 못한다.,[ 13] :§3
임의의 집합
E
{\displaystyle E}
I
=
{
∅
}
{\displaystyle {\mathcal {I}}=\{\varnothing \}}
B
=
{
∅
}
{\displaystyle {\mathcal {B}}=\{\varnothing \}}
C
=
{
{
x
}
:
x
∈
E
}
{\displaystyle {\mathcal {C}}=\{\{x\}\colon x\in E\}}
rank
(
A
|
B
)
=
0
(
B
⊆
A
⊆
E
)
{\displaystyle \operatorname {rank} (A|B)=0\qquad (B\subseteq A\subseteq E)}
cl
(
A
)
=
E
(
A
⊆
E
)
{\displaystyle \operatorname {cl} (A)=E\qquad (A\subseteq E)}
를 부여하면, 이는 매트로이드를 이룬다. 이를
Unif
(
E
,
0
)
{\displaystyle \operatorname {Unif} (E,0)}
마찬가지로, 임의의 집합
E
{\displaystyle E}
I
=
Pow
(
E
)
{\displaystyle {\mathcal {I}}=\operatorname {Pow} (E)}
B
=
{
E
}
{\displaystyle {\mathcal {B}}=\{E\}}
rank
(
A
|
B
)
=
{
|
A
∖
B
|
|
A
∖
B
|
<
ℵ
0
∞
|
A
∖
B
|
≥
ℵ
0
(
B
⊆
A
⊆
E
)
{\displaystyle \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)}
cl
(
A
)
=
A
(
A
⊆
E
)
{\displaystyle \operatorname {cl} (A)=A\qquad (A\subseteq E)}
을 부여하면, 이는 매트로이드를 이룬다. 이는
Unif
(
E
,
0
)
{\displaystyle \operatorname {Unif} (E,0)}
Unif
(
E
,
0
)
∗
{\displaystyle \operatorname {Unif} (E,0)^{*}}
이들의 성질을 비교하면 다음과 같다.
성질
Unif
(
E
,
0
)
{\displaystyle \operatorname {Unif} (E,0)}
Unif
(
E
,
0
)
∗
{\displaystyle \operatorname {Unif} (E,0)^{*}}
독립 집합
공집합
모든 집합
기저
공집합
전체 집합
E
{\displaystyle E}
종속 집합
공집합이 아닌 집합
(없음)
회로
한원소 집합
(없음)
폐포 연산
전체 집합 값의 상수 함수
항등 함수
닫힌집합
전체 집합
E
{\displaystyle E}
모든 집합
상대 계수 함수
0 값의 상수 함수
차집합 의 크기
이와 같은 두 종류의 매트로이드의 직합으로 표현될 수 있는 매트로이드를 이산 매트로이드 (離散matroid, 영어 : discrete matroid )라고 한다.
보다 일반적으로, 임의의 집합
E
{\displaystyle E}
0
≤
k
{\displaystyle 0\leq k}
균등 매트로이드 (均等matroid, 영어 : uniform matroid )
Unif
(
E
,
k
)
{\displaystyle \operatorname {Unif} (E,k)}
E
{\displaystyle E}
I
=
{
S
⊆
E
:
|
S
|
≤
k
}
{\displaystyle {\mathcal {I}}=\{S\subseteq E\colon |S|\leq k\}}
B
=
{
S
⊆
E
:
|
S
|
=
k
}
{\displaystyle {\mathcal {B}}=\{S\subseteq E\colon |S|=k\}}
C
=
{
S
⊆
E
:
|
S
|
=
k
+
1
}
{\displaystyle {\mathcal {C}}=\{S\subseteq E\colon |S|=k+1\}}
이는 항상 유한형 매트로이드이다.
만약
E
{\displaystyle E}
유한 집합 일 때,
Unif
(
E
,
k
)
{\displaystyle \operatorname {Unif} (E,k)}
Unif
(
E
,
|
E
|
−
k
)
{\displaystyle \operatorname {Unif} (E,|E|-k)}
E
{\displaystyle E}
Unif
(
E
,
k
)
{\displaystyle \operatorname {Unif} (E,k)}
체
K
{\displaystyle K}
벡터 공간
V
{\displaystyle V}
중복집합
E
⊂
V
{\displaystyle E\subset V}
K
{\displaystyle K}
행렬 로 나타낼 수 있다.)
I
(
E
)
⊂
P
(
E
)
{\displaystyle {\mathcal {I}}(E)\subset {\mathcal {P}}(E)}
E
{\displaystyle E}
일차독립 부분 중복집합 들의 집합이라고 하면,
(
E
,
I
(
E
)
)
{\displaystyle (E,{\mathcal {I}}(E))}
선형 매트로이드 (영어 : linear matroid )라고 한다.
모든 그래프 에는 순환 매트로이드 접합 매트로이드 가 대응된다.
공집합 위에는 유일한 매트로이드 구조가 존재하며, 이는 균등 매트로이드
Unif
(
0
,
0
)
{\displaystyle \operatorname {Unif} (0,0)}
이는 무변 그래프 의 순환 매트로이드 이자, 임의의 벡터 공간 속의 공집합 으로부터 정의되는 선형 매트로이드이다.
크기 1의 매트로이드 동형류들은 다음 두 가지이다.
Unif
(
1
,
1
)
{\displaystyle \operatorname {Unif} (1,1)}
경로 그래프
P
2
{\displaystyle P_{2}}
순환 매트로이드 이다.
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (1,0)}
다중 그래프 의 순환 매트로이드 이다.크기 2의 매트로이드 동형류들은 다음 네 가지이다.
Unif
(
2
,
2
)
{\displaystyle \operatorname {Unif} (2,2)}
Unif
(
1
,
1
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (1,1)\oplus \operatorname {Unif} (1,0)}
Unif
(
2
,
1
)
{\displaystyle \operatorname {Unif} (2,1)}
Unif
(
2
,
0
)
{\displaystyle \operatorname {Unif} (2,0)}
이 가운데 단순 매트로이드인 것은 첫째 밖에 없다.
크기 3의 매트로이드 동형류들은 다음 여덟 가지이다.
Unif
(
3
,
3
)
{\displaystyle \operatorname {Unif} (3,3)}
Unif
(
3
,
2
)
{\displaystyle \operatorname {Unif} (3,2)}
Unif
(
2
,
2
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (2,2)\oplus \operatorname {Unif} (1,0)}
Unif
(
2
,
1
)
⊕
Unif
(
1
,
1
)
{\displaystyle \operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,1)}
Unif
(
3
,
1
)
{\displaystyle \operatorname {Unif} (3,1)}
Unif
(
2
,
1
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,0)}
Unif
(
2
,
0
)
⊕
Unif
(
1
,
1
)
{\displaystyle \operatorname {Unif} (2,0)\oplus \operatorname {Unif} (1,1)}
Unif
(
3
,
0
)
{\displaystyle \operatorname {Unif} (3,0)}
이 가운데 단순 매트로이드인 것은 처음 두 개이다.
크기 4의 매트로이드는 총 17개가 있으며, 하나를 제외하고는 나머지는 균등 매트로이드들의 직합으로 표현될 수 있다.
계수 0:
Unif
(
4
,
0
)
{\displaystyle \operatorname {Unif} (4,0)}
계수 1:
Unif
(
4
,
1
)
{\displaystyle \operatorname {Unif} (4,1)}
Unif
(
3
,
1
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (3,1)\oplus \operatorname {Unif} (1,0)}
Unif
(
2
,
1
)
⊕
Unif
(
2
,
0
)
{\displaystyle \operatorname {Unif} (2,1)\oplus \operatorname {Unif} (2,0)}
Unif
(
1
,
1
)
⊕
Unif
(
3
,
0
)
{\displaystyle \operatorname {Unif} (1,1)\oplus \operatorname {Unif} (3,0)}
계수 2:
Unif
(
4
,
2
)
{\displaystyle \operatorname {Unif} (4,2)}
Unif
(
3
,
1
)
⊕
Unif
(
1
,
1
)
{\displaystyle \operatorname {Unif} (3,1)\oplus \operatorname {Unif} (1,1)}
Unif
(
3
,
2
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (3,2)\oplus \operatorname {Unif} (1,0)}
Unif
(
2
,
1
)
⊕
Unif
(
2
,
1
)
{\displaystyle \operatorname {Unif} (2,1)\oplus \operatorname {Unif} (2,1)}
Unif
(
2
,
2
)
⊕
Unif
(
2
,
0
)
{\displaystyle \operatorname {Unif} (2,2)\oplus \operatorname {Unif} (2,0)}
Unif
(
2
,
1
)
⊕
Unif
(
1
,
1
)
⊕
Unif
(
1
,
0
)
{\displaystyle \operatorname {Unif} (2,1)\oplus \operatorname {Unif} (1,1)\oplus \operatorname {Unif} (1,0)}
균등 매트로이드의 직합이 아닌 매트로이드
X
{\displaystyle X}
계수 3 및 계수 4의, 크기 4의 매트로이드들은 각각 계수 1 및 계수 0의 것들의 쌍대 매트로이드로 얻어진다.
여기서, 매트로이드
X
{\displaystyle X}
E
=
{
a
,
b
,
c
,
d
}
{\displaystyle E=\{{\mathsf {a}},{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\}}
B
=
{
S
⊆
E
:
|
S
|
=
2
,
S
≠
{
a
,
b
}
}
{\displaystyle {\mathcal {B}}=\{S\subseteq E\colon |S|=2,\;S\neq \{{\mathsf {a}},{\mathsf {b}}\}\}}
C
=
{
{
a
,
b
}
,
{
b
,
c
,
d
}
,
{
a
,
c
,
d
}
}
{\displaystyle {\mathcal {C}}=\left\{\{{\mathsf {a}},{\mathsf {b}}\},\{{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\},\{{\mathsf {a}},{\mathsf {c}},{\mathsf {d}}\}\right\}}
이는 다음과 같은 다중 그래프 에 대응하는 순환 매트로이드 이다.
마찬가지로, 이는 (예를 들어) 다음과 같은 실수 벡터 공간
R
2
{\displaystyle \mathbb {R} ^{2}}
{
a
,
b
,
c
,
d
}
{\displaystyle \{{\mathsf {a}},{\mathsf {b}},{\mathsf {c}},{\mathsf {d}}\}}
a
=
(
1
,
0
)
{\displaystyle {\mathsf {a}}=(1,0)}
b
=
(
2
,
0
)
{\displaystyle {\mathsf {b}}=(2,0)}
c
=
(
0
,
1
)
{\displaystyle {\mathsf {c}}=(0,1)}
d
=
(
1
,
1
)
{\displaystyle {\mathsf {d}}=(1,1)}
매트로이드의 개념은 해슬러 휘트니 가 1935년에 도입하였다.[ 14] 나카자와 다케오 (일본어 : 中澤 武雄 , 1913~1946)가 동일한 개념을 독립적으로 발견하였으나,[ 15] [ 16] [ 17] [ 18]
이후 윌리엄 토머스 텃 이 매트로이드 이론을 발달시켰고, 텃 다항식 과 같은 중요한 개념들을 발견하였다.[ 19]
1970년에 잔카를로 로타 와 헨리 하울런드 크레이포(영어 : Henry Howland Crapo )는 매트로이드 이론에 대한 최초의 책을 출판하였다.[ 20] 영어 : combinatorial geometry )라는 용어가 사용되었다.) 이듬해에 윌리엄 토머스 텃은 매트로이드 이론에 대한 둘째 책을 출판하였다.[ 21]
무한 매트로이드의 올바른 정의는 오랫동안 미해결 문제였다. 1966년에 리하르트 라도 는 무한 매트로이드의 올바른 정의에 대한 문제를 제기하였다.[ 22] :263, §6(c), Problem P531 영어 : Denis A. Higgs , 1932~2011)는 1969년에 무한 매트로이드에 대한 다양한 정의를 제시하였으며, 그 가운데 하나는 “B-매트로이드”(영어 : B-matroid )라는 개념이었다.[ 23]
이후 1978년에 제임스 옥슬리(영어 : James G. Oxley )는 “B-매트로이드”의 모임이 쌍대성을 가지며 매트로이드 마이너 에 대하여 닫혀 있는 가장 큰 모임이라는 것을 증명하였다.[ 24] [ 7]
↑ Gordon, Gary; McNulty, Jennifer (2012년 9월). 《Matroids: a geometric introduction》 (영어). Cambridge University Press. doi :10.1017/CBO9781139049443 . ISBN 978-052176724-8 ↑ Oxley, James G. (1992). 《Matroid theory》 (영어). Oxford: Oxford University Press. ISBN 0-19-853563-5 MR 1207587 . Zbl 0784.05002 . ↑ Recski, András (1989). 《Matroid theory and its applications in electric network theory and in statics》 (영어). Springer-Verlag, Akademiai Kiado. ISBN 3-540-15285-7 MR 1027839 . ↑ Bryant, Victor; Perfect, Hazel (1980). 《Independence theory in combinatorics》 (영어). London and New York: Chapman and Hall. ISBN 0-412-22430-5 ↑ Welsh, Dominic James Anthony (1976). 《Matroid theory》. London Mathematical Society Monographs (영어) 8 . Academic Press. ISBN 0-12-744050-X Zbl 0343.05002 . ↑ Wilson, Robin James (1973년 5월). “An introduction to matroid theory”. 《The American Mathematical Monthly》 (영어) 80 (5): 500–525. doi :10.2307/2319608 . JSTOR 2319608 . Zbl 0275.05018 . ↑ 가 나 다 라 마 바 사 아 Bruhn, Henning; Diestel, Reinhard; Kriesell, Matthias; Pendavingh, Rudi A.; Wollan, Paul (2013년 6월 1일). “Axioms for infinite matroids”. 《Advances in Mathematics》 (영어) 239 : 18–46. arXiv :1003.3919 . Bibcode :2010arXiv1003.3919B . doi :10.1016/j.aim.2013.01.011 . Zbl 1279.05013 . ↑ Bowler, Nathan; Carmesin, Johannes (2014년 7월). “Matroids with an infinite circuit-cocircuit intersection”. 《Journal of Combinatorial Theory B》 (영어) 107 : 78–91. arXiv :1202.3406 . Bibcode :2012arXiv1202.3406C . doi :10.1016/j.jctb.2014.02.005 . ↑ Higgs, Denis A. (1969년 3월). “Equicardinality of bases in B-matroids”. 《Canadian Mathematical Bulletin》 (영어) 12 : 861–862. doi :10.4153/CMB-1969-112-6 . ISSN 0008-4395 . ↑ Bowler, Nathan; Geschke, Stefan (2016). “Self-dual uniform matroids on infinite sets” (PDF) . 《Proceedings of the American Mathematical Society》 (영어) 144 : 459–471. doi :10.1090/proc/12667 . ISSN 0002-9939 . MR 3430826 . ↑ Mayhew, Dillon; Royle, Gordon F. (2007). “Matroids with nine elements” (영어). arXiv :math/0702316 . Bibcode :2007math......2316M . ↑ Bansal, Nikhil; Pendavingh, Rudi A.; van der Pol, Jorn G. (2015년 4월). “On the number of matroids”. 《Combinatorica》 (영어) 35 (3): 253–277. arXiv :1206.6270 . Bibcode :2012arXiv1206.6270B . doi :10.1007/s00493-014-3029-z . ISSN 0209-9683 . ↑ 가 나 Heunen, Chris; Patta, Vaia (2017). “The category of matroids”. 《Applied Categorical Structures》 (영어) 25 . arXiv :1512.01390 . Bibcode :2015arXiv151201390H . doi :10.1007/s10485-017-9490-2 . ISSN 0927-2852 . ↑ Whitney, Hassler (1935). “On the abstract properties of linear dependence”. 《American Journal of Mathematics》 (영어) 57 (3): 509–533. doi :10.2307/2371182 . JFM 61.0073.03 . JSTOR 2371182 . MR 1507091 . Zbl 0012.00404 . ↑ Nakasawa, Takeo (1935). “Zur Axiomatik der linearen Abhängigkeit Ⅰ” . 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 2 : 235–255. JFM 61.1341.03 . Zbl 0012.22001 . ↑ Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit Ⅱ” . 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 3 : 45–69. JFM 62.0649.01 . Zbl 0013.31406 . ↑ Nakasawa, Takeo (1936). “Zur Axiomatik der linearen Abhängigkeit Ⅲ” . 《Science reports of the Tokyo Bunrika Daigaku A》 (독일어) (東京文理科大学) 3 : 123–136. JFM 62.1400.01 . Zbl 0016.03704 . ↑ Nishimura, Hirokazu; Kuroda, Susumu (2009). 《A lost mathematician, Takeo Nakasawa: the forgotten father of matroid theory》 (영어). Springer-Verlag. doi :10.1007/978-3-7643-8573-6 . ISBN 978-3-7643-8572-9 Zbl 1163.01001 . ↑ Tutte, William Thomas (1965). “Lectures on matroids”. 《Journal of Research of the National Bureau of Standards (U.S.A.) B》 (영어) 69 : 1–47. doi :10.6028/jres.069b.001 . Zbl 0151.33801 . ↑ Crapo, Henry Howland; Rota, Gian-Carlo (1970). 《On the Foundations of Combinatorial Theory Ⅱ. Combinatorial geometries》 (영어). Massachusetts Institute of Technology Press. ISBN 978-0-262-53016-3 MR 0290980 . ↑ Tutte, William Thomas (1971). 《Introduction to the theory of matroids》. Modern Analytic and Computational Methods in Science and Mathematics (영어) 37 . Elsevier. Zbl 0231.05027 . ↑ Rado, Richard (1966). “Abstract linear dependence” . 《Colloquim Mathematicae》 (영어) 14 (1): 257–264. ISSN 0010-1354 . Zbl 0136.26203 . ↑ Higgs, Denis A. (1969). “Matroids and duality” . 《Colloquium Mathematicae》 (영어) 20 (2): 215–20. ISSN 0010-1354 . Zbl 0192.33402 . ↑ Oxley, James G. (1978년 9월). “Infinite matroids”. 《Proceedings of the London Mathematical Society》 (영어) 37 (3): 259–272. doi :10.1112/plms/s3-37.2.259 . Zbl 0436.05017 .
“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” (영어).
![{\displaystyle {\mathcal {I}}\cap [A,B]=\{S\in {\mathcal {I}}\colon A\subseteq S\subset B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fe0b6fda3305557379a3ea53c6b5a48ab82dc43)
이 부분의 본문은 매트로이드 마이너입니다.
