매트로이드의 기초

Basis of a matroid

수학에서 매트로이드기본은 매트로이드의 최대 독립 집합, 즉 다른 독립 집합에 포함되지 않는 독립 집합이다.

예를 들어, 다음과 같은 독립된 세트를 사용하여 지면 세트 R2(이차원 유클리드 평면의 벡터) 위에 있는 매트로이드(matroid)를 고려하십시오.

{ {}, {(0,1)}, {(2,0)}, {(0,1),(2,0)}, {(0,3)}, {(0,3),(2,0)} }.

두 개의 베이스를 가지고 있는데, 그 베이스는 {(0,1)}, {0,3},(2,0)이다.이것들은 포함시 최대치인 유일한 독립형 세트들이다.

이 기반은 다음과 같은 몇 가지 전문화된 종류의 매트로이드에 특화된 이름을 가지고 있다.[1]

  • 독립된 집합이 숲인 그래픽 매트로이드에서는 그 기초를 그래프의 스패닝 포리스트라고 부른다.
  • 독립 집합이 주어진 초당적 그래프에서 일치의 끝점인 횡단 매트로이드에서, 베이스를 횡단이라고 한다.
  • 독립된 집합이 주어진 벡터 공간에서 선형적으로 독립된 벡터 집합인 선형 매트로이드에서는 베이스를 벡터 공간의 베이스라고 부른다.따라서, 매트로이드의 기본 개념은 선형 대수로부터 기본 개념을 일반화한다.
  • 독립된 세트가 모두 최대 k(일부 정수 k)에서 카디널리티로 설정된 경우, 베이스는 카디널리티 정확히 k로 설정된 모든 세트다.
  • 요소들이 범주로 분할되고 독립된 집합이 각 범주 c의 최대 kc 요소를 포함하는 파티션 매트로이드에서, 베이스는 모두 범주 c의 정확히 k 요소c 포함하는 집합이다.
  • 지반 집합 E의 모든 하위 집합이 독립적인 자유 매트로이드에서, 고유한 근거는 E이다.

특성.

교환

모든 매트로이드는 두 개의 고유한 A 에 대해 다음 속성을 만족한다[2][3]

  • Basis-exchange property: if , then there exists an element such that is a basis.
  • Symmetric basis-exchange property: if , then there exists an element such that both and are bases. 브루알디는[4] 그것이 사실상 염기교환 재산과 동등하다는 것을 보여주었다.
  • Multiple symmetric basis-exchange property: if , then there exists a subset such that both and are bases.브라이레츠키, 그린, 우달 등은 (독립적으로) 사실상 염기교환 재산에 해당한다는 것을 보여주었다.
  • 바이어시브 베이시스 교환 특성:There is a bijection from to , such that for every , is a basis.브루알디는[4] 그것이 기본 교환 재산과 맞먹는다는 것을 보여주었다.
  • 파티션 기준 교환 속성:For each partition of into m parts, there exists a partition of into m parts, such that for every ( i ) B 가 기본이다.[5]

그러나 대칭적이고 비주사적인 기본 교환 특성은 모든 매트로이드에 의해 충족되지 않는다. 즉, 기본 주문 가능한 매트로이드에 의해서만 충족된다.

일반적으로 대칭 기준 교환 속성에서 b A{\B\이(가) 고유할 필요는 없다.일반 매트로이드교환 특성을 가지고 있는데, 이는 A B 의 경우 해당 b가 고유하다는 것을 의미한다[6]

카디널리티

의 멤버가 다른 멤버의 적절한 하위 집합이 될 수 없다는 것은 기본 교환 속성에서 따온 것이다.

또한 주어진 모형의 모든 염기들은 동일한 카디널리티를 가진다.선형 매트로이드에서는 모든 베이스의 카디널리티를 벡터 공간의 치수라고 부른다.

닐 화이트의 추측

모든 모종이 다음과 같은 성질을 만족한다고 추측된다.[2]모든 정수 t ≥ 1에 대해, 만약 BB'가 동일한 멀티셋 유니언을 가진 베이스의 두 t-t-tule이라면, B를 B'로 변환하는 대칭 교환의 순서가 있다.

특성화

매트로이드의 기초는 매트로이드의 특성을 완전히 나타낸다. 집합은 기준의 부분 집합인 경우에만 독립적이다.Moreover, one may define a matroid to be a pair , where is the ground-set and is a collection of subsets of , called "bases", with the following properties:[7][8]

(B1) 베이스가 하나 이상 있음 - (가) 비어 있지 않음;
(B2) If and are distinct bases, and , then there exists an element such that is a basis (this is the basis-exchange재산의

(B2)는 AB의 어떤 두 베이스가 주어진다면, 우리는 단일 원소의 일련의 교환에 의해 AB로 변형시킬 수 있다는 것을 암시한다.특히 이는 모든 베이스가 같은 카디널리티를 가져야 한다는 것을 암시한다.

이중성

If is a finite matroid, we can define the orthogonal or dual matroid by calling a set a basis in if and only if its complement is in ( 실로 매트로이드임을 확인할 수 있다.이 정의는 ( 의 이중은(E {\ {B}}) , 임을 즉시 암시한다[9]: 32 [10]

이중성을 이용하여 재산(B2)을 다음과 같이 대체할 수 있음을 증명할 수 있다.

(B2*) If and are distinct bases, and , then there exists an element such that is a basis.

회로

기초에 대한 이중 개념은 회로다.매트로이드의 회로는 최소 종속 집합, 즉 적절한 하위 집합이 모두 독립적인 종속 집합이다.이 용어는 그래픽 매트로이드의 회로가 해당 그래프의 사이클이기 때문에 발생한다.

one may define a matroid to be a pair , where is the ground-set and is a collection of subsets of , called "circuits", with the following properties:[8]

(C1) 빈 세트는 회로가 아니다.
(C2) 회로의 서브셋은 회로가 아니다.
(C3) C와1 C가2 회로이고 x가 교차로에 있는 요소라면 C {x 는 회로를 포함한다.

Another property of circuits is that, if a set is independent, and the set is dependent (i.e., adding the element makes it dependent), then contains a unique circuit , 그리고 을(를) 포함하고 있다이 회로를 w.r.t.{\ J기본 회로라고 한다 독립 벡터 J 벡터 를 추가하면 의 원소들의 고유한 선형 조합이 있다는 선형 대수학 사실과 유사하다. (와) 같은 {\ J[10]

참고 항목

  • Matroid polytope - Rn(여기서 n은 matroid에 있는 원소의 수)의 폴리토프로서, 정점은 matroid의 기저부의 지시 벡터다.

참조

  1. ^ Ardila, Federico (2007). "Matroids, lecture 3". youtube. Archived from the original on 2020-02-14.
  2. ^ a b Bonin, Joseph E.; Savitsky, Thomas J. (2016-01-01). "An infinite family of excluded minors for strong base-orderability". Linear Algebra and Its Applications. 488: 396–429. arXiv:1507.05521. doi:10.1016/j.laa.2015.09.055. ISSN 0024-3795. S2CID 119161534. Lay summary (PDF). {{cite journal}}:Cite는 사용되지 않는 매개 변수를 사용한다. lay-url=(도움말)
  3. ^ https://www.youtube.com/watch?v=pipoFmeDWIs
  4. ^ a b Brualdi, Richard A. (1969-08-01). "Comments on bases in dependence structures". Bulletin of the Australian Mathematical Society. 1 (2): 161–167. doi:10.1017/S000497270004140X. ISSN 1755-1633.
  5. ^ Greene, Curtis; Magnanti, Thomas L. (1975-11-01). "Some Abstract Pivot Algorithms". SIAM Journal on Applied Mathematics. 29 (3): 530–539. doi:10.1137/0129045. hdl:1721.1/5113. ISSN 0036-1399.
  6. ^ McGuinness, Sean (2014-07-01). "A base exchange property for regular matroids". Journal of Combinatorial Theory, Series B. 107: 42–77. doi:10.1016/j.jctb.2014.02.004. ISSN 0095-8956.
  7. ^ Welsh, D. J. A. (1976), Matroid Theory, L.M.S. Monographs, vol. 8, Academic Press, ISBN 978-0-12-744050-7, Zbl 0343.05002. 섹션 1.2, "매트로이드에 대한 축계", 페이지 7–9.
  8. ^ a b Federico, Ardila (2012). "Matroids: Lecture 6". Youtube.
  9. ^ White, Neil, ed. (1986), Theory of Matroids, Encyclopedia of Mathematics and its Applications, vol. 26, Cambridge: Cambridge University Press, ISBN 978-0-521-30937-0, Zbl 0579.00001
  10. ^ a b Ardila, Federico (2012). "Matroids lecture 7". Youtube.