매트로이드

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

조합론에서, 매트로이드(영어: matroid 메이트로이드[*])는 선형독립성을 공리화한 조합론적인 대상이다.

정의[편집]

매트로이드 (E,\mathcal I)집합 E와 그 부분집합들의 집합 \mathcal I\subset\mathcal P(E)로 구성된다. 여기서 \mathcal I의 원소들을 독립 집합(獨立集合, 영어: independent set)이라고 한다. 이 데이터는 다음 공리들을 만족시켜야 한다.[1]

  • (공집합의 독립성) 공집합은 독립 집합이다. 즉, \varnothing\in\mathcal I이다.
  • (독립성의 유전 영어: hereditary property) 독립 집합의 부분집합은 독립이다. 즉, 만약 B\subset 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 Ia\in A\setminus B가 존재한다.
  • (극대 독립 집합의 존재) 만약 \mathcal I\ni A\subset B\subset E라면, 닫힌 구간 \mathcal I\cap [A,B]=\{S\in\mathcal I\colon A\subset S\subset B\}는 극대 원소를 갖는다.

만약 E가 유한 집합이라면, 마지막 조건은 자동적으로 성립된다. 독립 집합이 아닌 집합을 종속 집합(영어: dependent set)이라고 한다.

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

  • 만약 E유한 집합이라면, (E,\mathcal I)유한 매트로이드(영어: finite matroid)라고 한다.
  • 만약 임의의 A\subset E에 대하여 A의 모든 유한 부분 집합이 독립 집합인 경우 A 또한 독립 집합이라면, (E,\mathcal I)유한형 매트로이드(영어: finitary matroid)라고 한다.[1]

매트로이드 E기저(영어: basis)는 E의 극대 독립 집합이다. 즉, 만약 독립 집합 B의 모든 진포함집합이 종속 집합이라면, B는 기저를 이룬다. 매트로이드의 서로 다른 기저들의 크기는 서로 같으며, 기저의 크기를 매트로이드의 계수(영어: rank) r(E)라고 한다. 매트로이드의 쌍대계수(영어: corank)는 기저의 여집합크기이다.

매트로이드 E회로(영어: circuit)는 E의 최소 종속 집합이다. 즉, 모든 부분집합이 독립 집합인 종속 집합이다.

부분 매트로이드[편집]

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

폐포[편집]

매트로이드 (E,\mathcal I)의 부분집합 S폐포 (영어: closure) \operatorname{cl}(S)는 다음과 같다.

\operatorname{cl}(S)=\{e\in E\colon r(S)=r(S\cup\{x\})\}\supset S

즉, S의 폐포는 S에 추가해도 계수가 바뀌지 않는 모든 원소들을 추가한 S의 포함집합이다. \operatorname{cl}(S)=S인 집합 S평탄면(영어: flat 플랫[*])이라고 한다. 유한 매트로이드 E 속에서, 계수가 |E|-1인 평탄면을 초평면(영어: hyperplane 하이퍼플레인[*])이라고 한다.

쌍대 매트로이드[편집]

매트로이드 (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,\mathcal I)텃 다항식(영어: Tutte polynomial)은 다음과 같은 2변수 다항식 T_E(x,y)이다.

T_E(x,y)=\sum_{S\subset E}(1-x)^{r(E)-r(S)}(y-1)^{|S|-r(S)}

여기서 r(E)는 매트로이드 E의 계수이다.

[편집]

균등 매트로이드[편집]

균등 매트로이드(영어: uniform matroid) U_{n,k}는 다음과 같다.

  • 집합으로서, U_{n,k}n개의 원소를 갖는다.
  • U_{n,k}의 독립 집합은 크기가 k 이하인 집합이다.

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

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

그래프의 매트로이드[편집]

그래프 G의 변들의 집합 E(G)이 주어지면, \mathcal I(G)\subset\mathcal P(E(G))G들의 집합이라고 하자. 그렇다면 (E(G),\mathcal I(G))는 매트로이드를 이루며, 이를 G순환 매트로이드(영어: cycle matroid) M(G)라고 한다. 순환 매트로이드의 회로는 그래프의 순환들이다.

그래프에서, 접합(영어: bond) B\subset E(G)는 제거하면 연결 성분의 수가 증가하는 변의 극소 집합이다. G의 접합을 회로로 갖는 매트로이드를 G접합 매트로이드(영어: bond matroid) M^*(G)라고 한다. 접합 매트로이드는 순환 매트로이드의 쌍대 매트로이드이다.

작은 매트로이드의 수[편집]

크기가 n인 서로 동형이 아닌 매트로이드의 수는 다음과 같다 (n=0,1,2,\dots).

1, 2, 4, 8, 17, 38, 98, 306, 1724, 383172, … (OEIS의 수열 A55545)

이를 m_n이라고 하면, 다음이 성립한다.[2]

n-\frac32\log_2n-O(1)\le \log_2\log_2m_n\le n-\frac32\log_2n+\frac12\log_2\sqrt{8/\pi}+o(1)

크기가 n인 서로 동형이 아닌 단순 매트로이드의 수는 다음과 같다 (n=0,1,2,\dots).

1, 1, 1, 2, 4, 9, 26, 101, 950, 376467, … (OEIS의 수열 A2773)

역사[편집]

해슬러 휘트니가 1935년 도입하였다.[3] 1938년에 일본의 나카자와 다케오(일본어: 中澤 武雄 (なかざわ たけお))가 동일한 개념을 독립적으로 발견하였으나,[4][5][6][7] 크게 알려지지 못했다. 이후 윌리엄 토머스 텃이 매트로이드 이론을 발달시켰고, 텃 다항식과 같은 중요한 개념들을 발견하였다.

참고 문헌[편집]

  1. (영어) Bruhn, Henning, Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, Paul Wollan (2013년 6월 1일). Axioms for infinite matroids. 《Advances in Mathematics》 239: 18–46. arXiv:1003.3919. doi:10.1016/j.aim.2013.01.011. Bibcode2010arXiv1003.3919B. Zbl 1279.05013.
  2. (영어) . arXiv:1206.6270.
  3. (영어) Whitney, Hassler (1935년). On the abstract properties of linear dependence. 《American Journal of Mathematics》 57 (3): 509–533. doi:10.2307/2371182. JSTOR 2371182. MR1507091. Zbl 0012.00404. JFM 61.0073.03.
  4. (독일어) Nakasawa, Takeo (1935년). Zur Axiomatik der linearen Abhängigkeit I. 《Science reports of the Tokyo Bunrika Daigaku A》 2: 235–255. Zbl 0012.22001. JFM 61.1341.03.
  5. (독일어) Nakasawa, Takeo (1936년). Zur Axiomatik der linearen Abhängigkeit II. 《Science reports of the Tokyo Bunrika Daigaku A》 3: 45–69. Zbl 0013.31406. JFM 62.0649.01.
  6. (독일어) Nakasawa, Takeo (1936년). Zur Axiomatik der linearen Abhängigkeit III. 《Science reports of the Tokyo Bunrika Daigaku A》 3: 123–136. Zbl 0016.03704. JFM 62.1400.01.
  7. (영어) Nishimura, Hirokazu, Susumu Kuroda. 《A Lost Mathematician, Takeo Nakasawa: The Forgotten Father of Matroid Theory》. Springer. doi:10.1007/978-3-7643-8573-6. ISBN 978-3-7643-8572-9

바깥 고리[편집]