Matroids-Duality

download Matroids-Duality

of 4

description

Matroid theory notes in japanese

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