Matroids-Duality
description
Transcript of Matroids-Duality
-
1 M = (E; I)M = (E; I)
I := fI EjclM (E n I) = Eg
M ()M M
2.1 M
M (I1)(I3)(I1)clM (E) = E (rM (E))(I2)I 0 := EnI; J 0 := EnJ I 0 J 0 clM (J 0) = E (CL2) clM (I 0) E clM (I
0) = E (I3)I 0 := E n I; J 0 := E n J BI I 0; BJ J 0 M (B2) BJ n I BI j 2 J n I I + j 2= I i 2 I 0 n J 0 rM (I 0 i) < rM (I 0)J n I = I 0 n J 0 BI BJ \ J = ;
jBJ j = jBJ n Ij+ jBJ \ Ij jBJ n Ij+ jI n J j < jBJ n Ij+ jJ n Ij jBI j
jBI j = jBJ j(I3)(q:e:d:)
1M BI ; BJ (BIBJ)
1
-
2 2.1
2.2 M BM M M B fE nBjB 2 Bg MMB = fEnBjB 2BgM B 2 B I 1E nB 2 I BM8e 2 E nB; clM (E nBe) 6= EE nBM EM B 2 B ) E nB 2 BMB 2 B 1EnB 2 IB clM (X) = EX E 18b 2 B; E nB + b 2= I E nB M B 2 B ) E nB 2 BB = fE n BjB 2 BgM M
BB 6= ;B 6= ;
(B1)B1 ; B2 2 B; i 2 B1 nB2 B1 = E nB1 ; B2 = E nB2 M i 2 B2 nB1 B 2.39j 2 B1 nB2 s:t: B1 + i j 2 BB1 i+ j = E n (B1 + i j) 2 B (B2)
2.3 M B
(B2)' B1; B2 2 B; i 2 B2 nB1 ) 9j 2 B1 nB2 s:t: B1 + i j 2 B
B1 + i 1B1 + i B1 i 2(C3) i B1 + i C1 B2 9j 2 C1 n B2 (
B2 C1 B2 ) C1 B1 + i; i 2 B2 C1 nB2 B1 nB2 B1 + i j B1 + i C1 jB1j(q:e:d:)
B(I2) I = fIjI 9B 2 Bg8I 2 I; 9B 2 B s:t: I E nBs:t:B E n I I fI EjclM (E n I) = Eg I 2 fI EjclM (E n I) = Eg E n I M B
I E nB 2 B II fI EjclM (E n I) = Eg I(q:e:d:)
2.4 M = (E; I)M = (E; I) B;BI 2 I; I 2 I; I \ I = ; ) 9B 2 B; 9B 2 B s:t: I B; I B; B \B = ;
2
-
I 2 I clM (E n I) = E E n I M B0 2 B I B0 (I3)I B E n I B 2 B MM 2.2 E n B 2 B B B = E nB E n (E n I) = I (q:e:d:)
2.2
2 1
2.5 M (M) = M
2.2(M)M (I2)(q:e:d:)
2.3
2.6 M = (E; I)M = (E; I)M CM C C 2 C; C 2 C ) jC \ Cj 6= 1 C \C = fegI := C e 2 I; I := C e 2 I; I \ I = ; 2.4I B 2 B; I B 2 B; B \ B = ; B;B 2.2B [B = EeI + e 2 B I + e 2 B (q:e:d:)
2.4
2.7 M = (E; I)M = (E; I)M rM r X E
r(X) = r(E nX) + jXj r(M) (1)
I X I 2 I I E nX I 2 I 1r(X) = jIj; r(E nX) = jIjM;M B;B 2.4I B 2 B; I B 2 B; B \B = ; B;B I; I B \ (E nX) = I; B \X = I B = E n B
B \X = X n I B = I [ (X n I); I \ (X n I) = ;
jBj = jIj+ jX n Ij = jIj+ jXj jIj
r(M) = jBj 2 (1)(q:e:d:)
3
-
EI
I
B
X
2 2.7
3 dual property complement relation
2012 7 6com_math_arith
4