§E13.25マトロイドの削除・縮約とマイナー

証明. マトロイドであること.§E13.15 定義 1.1 条件 (a)は$\emptyset\in\mathcal I$かつ$\emptyset\subseteq E\setminus T$による。§E13.15 定義 1.1 条件 (b)は、$A\in\mathcal I(M\setminus T)$かつ$B\subseteq A$ならば$B\in\mathcal I$かつ$B\subseteq E\setminus T$であることによる。§E13.15 定義 1.1 条件 (c)は、$A,B\in\mathcal I(M\setminus T)$かつ$\lvert A\rvert<\lvert B\rvert$のとき$M$の§E13.15 定義 1.1 条件 (c)により$x\in B\setminus A$が存在して$A\cup\{x\}\in\mathcal I$となり、$x\in B\subseteq E\setminus T$より$A\cup\{x\}\subseteq E\setminus T$であることによる。

階数.$A\subseteq E\setminus T$とする。$M\setminus T$において$A$に含まれる独立集合とは、$A$に含まれる$M$の独立集合にほかならない。実際、$I\subseteq A\subseteq E\setminus T$であれば$I\in\mathcal I$と$I\in\mathcal I(M\setminus T)$は同値である。ゆえに最大濃度も等しく$r_{M\setminus T}(A)=r(A)$である。

基底.$M\setminus T$の基底は$\mathcal I(M\setminus T)$の包含に関して極大な元であり、これは$\{I\in\mathcal I:\ I\subseteq E\setminus T\}$の極大な元にほかならない。§E13.16 命題 4.2を$M$と$A=E\setminus T$に対して適用すると、その共通の濃度は$r(E\setminus T)$である。▨

証明.§E13.16 定義 4.4 条件 (a)を示す。$T\subseteq A\cup T$と$M$の§E13.16 定義 4.4 条件 (b)より$r(A\cup T)\ge r(T)$であるから$r_{M/T}(A)\ge0$である。$A$と$T$は交わらないから、§E13.16 補題 4.5の最後の主張を$T$と$A$へ適用して$r(A\cup T)\le r(T)+\lvert A\rvert$を得る。ゆえに$r_{M/T}(A)\le\lvert A\rvert$である。

§E13.16 定義 4.4 条件 (b)を示す。$A\subseteq B\subseteq E\setminus T$ならば$A\cup T\subseteq B\cup T$であり、$M$の§E13.16 定義 4.4 条件 (b)より$r(A\cup T)\le r(B\cup T)$であるから$r_{M/T}(A)\le r_{M/T}(B)$である。

§E13.16 定義 4.4 条件 (c)を示す。$A,B\subseteq E\setminus T$とする。$A$と$B$はいずれも$T$と交わらないから$(A\cup T)\cup(B\cup T)=(A\cup B)\cup T,\qquad (A\cup T)\cap(B\cup T)=(A\cap B)\cup T$が成り立つ。$M$の§E13.16 定義 4.4 条件 (c)を$A\cup T$と$B\cup T$へ適用すると$r\bigl((A\cup B)\cup T\bigr)+r\bigl((A\cap B)\cup T\bigr)\le r(A\cup T)+r(B\cup T)$であり、両辺から$2r(T)$を引くと$r_{M/T}(A\cup B)+r_{M/T}(A\cap B)\le r_{M/T}(A)+r_{M/T}(B)$を得る。

$M$の階数関数が§E13.16 定義 4.4 条件 (a)、§E13.16 定義 4.4 条件 (b)、§E13.16 定義 4.4 条件 (c)を満たすことは§E13.16 定理 4.6による。▨

証明.§E13.16 命題 4.2より$B_T$は存在し$\lvert B_T\rvert=r(T)$である。また§E13.16 定理 5.2より、$I$が$M/T$の独立集合であることは$r_{M/T}(I)=\lvert I\rvert$、すなわち$r(I\cup T)=r(T)+\lvert I\rvert$と同値である。

(1)の十分性.$I\cup B_T\in\mathcal I$とする。$I$と$B_T$は交わらないから$\lvert I\cup B_T\rvert=\lvert I\rvert+r(T)$であり、$I\cup B_T\subseteq I\cup T$であるから$r(I\cup T)\ge\lvert I\cup B_T\rvert=r(T)+\lvert I\rvert$である。一方§E13.16 補題 4.5より$r(I\cup T)\le r(T)+\lvert I\rvert$であるから等号が成り立ち、$I$は$M/T$の独立集合である。

(1)の必要性.$r(I\cup T)=r(T)+\lvert I\rvert$とする。$B_T$は$I\cup T$に含まれる$M$の独立集合であるから、§E13.16 命題 4.2より$B_T\subseteq J$を満たす$\{J'\in\mathcal I:\ J'\subseteq I\cup T\}$の極大な元$J$が存在し、$\lvert J\rvert=r(I\cup T)=r(T)+\lvert I\rvert$である。

$J\cap T$は$T$に含まれる独立集合であるから$\lvert J\cap T\rvert\le r(T)$であり、$J\setminus T\subseteq(I\cup T)\setminus T=I$であるから$\lvert J\setminus T\rvert\le\lvert I\rvert$である。二つを加えると$r(T)+\lvert I\rvert=\lvert J\rvert=\lvert J\cap T\rvert+\lvert J\setminus T\rvert\le r(T)+\lvert I\rvert$であるから、両方の不等式が等号でなければならない。とくに$\lvert J\setminus T\rvert=\lvert I\rvert$であり、$J\setminus T\subseteq I$と有限性から$J\setminus T=I$、すなわち$I\subseteq J$である。$B_T\subseteq J$でもあるから$I\cup B_T\subseteq J\in\mathcal I$であり、§E13.15 定義 1.1 条件 (b)より$I\cup B_T\in\mathcal I$である。

選び方への非依存.(1)の左辺の条件$r_{M/T}(I)=\lvert I\rvert$は$B_T$を含まないから、右辺の条件も$B_T$の選び方に依存しない。

(2)を示す。$M/T$の階数は$r_{M/T}(E\setminus T)=r(E)-r(T)$であるから、$M/T$の基底の濃度は$r(E)-r(T)$である。

$I$を$M/T$の基底とすると(1)より$I\cup B_T\in\mathcal I$であり、$\lvert I\cup B_T\rvert=(r(E)-r(T))+r(T)=r(E)$である。§E13.15 系 2.4より$I\cup B_T$は$M$の基底である。

逆に$I\subseteq E\setminus T$かつ$I\cup B_T\in\mathcal B$とすると、(1)より$I$は$M/T$の独立集合であり、$\lvert I\rvert=r(E)-r(T)$であるから、§E13.15 系 2.4を$M/T$へ適用して$I$は$M/T$の基底である。

基底全体の表示.$B\in\mathcal B$が$B_T\subseteq B$を満たすとする。$B\cap T$は$T$に含まれる独立集合であって$B_T$を含むから、$B_T$の極大性より$B\cap T=B_T$である。ゆえに$B\setminus B_T=B\setminus T\subseteq E\setminus T$であり、$(B\setminus B_T)\cup B_T=B\in\mathcal B$であるから、いま示したことより$B\setminus B_T$は$M/T$の基底である。逆に$M/T$の基底$I$に対し$B=I\cup B_T\in\mathcal B$は$B_T\subseteq B$を満たし$I=B\setminus B_T$である。▨

証明.(1)を示す。$x$が loop 元であるとは$r(\{x\})=0$が成り立つことである。$A\subseteq E\setminus\{x\}$に対し$A\cap\{x\}=\emptyset$であるから、§E13.16 定理 4.6の§E13.16 定義 4.4 条件 (c)を$A$と$\{x\}$へ適用して$r(A\cup\{x\})+r(\emptyset)\le r(A)+r(\{x\})=r(A)$を得る。$r(\emptyset)=0$であるから$r(A\cup\{x\})\le r(A)$であり、§E13.16 定義 4.4 条件 (b)より$r(A\cup\{x\})=r(A)$である。ゆえに$r_{M/x}(A)=r(A\cup\{x\})-r(\{x\})=r(A)-0=r(A)=r_{M\setminus x}(A)$であり、二つのマトロイドは同じ台集合と同じ階数関数をもつから、§E13.16 定理 5.2より$M/x=M\setminus x$である。

(2)を示す。$x$が coloop 元であるとは§E13.24 命題 4.2により$x$がすべての基底に属することである。$A\subseteq E\setminus\{x\}$を取り、$A$に含まれる独立集合のうち極大なもの$I$を取ると$\lvert I\rvert=r(A)$である（§E13.16 命題 4.2）。§E13.15 命題 2.2より$I\subseteq B$を満たす基底$B$が存在し、仮定より$x\in B$である。$I\cup\{x\}\subseteq B$であるから§E13.15 定義 1.1 条件 (b)より$I\cup\{x\}\in\mathcal I$であり、$x\notin A$より$x\notin I$であるから$\lvert I\cup\{x\}\rvert=r(A)+1$である。$I\cup\{x\}\subseteq A\cup\{x\}$であるから$r(A\cup\{x\})\ge r(A)+1$である。§E13.16 補題 4.5より$r(A\cup\{x\})\le r(A)+1$であるから等号が成り立つ。

とくに$A=\emptyset$として$r(\{x\})=r(\emptyset)+1=1$である。ゆえに$r_{M/x}(A)=r(A\cup\{x\})-r(\{x\})=\bigl(r(A)+1\bigr)-1=r(A)=r_{M\setminus x}(A)$であり、(1)と同じ理由で$M/x=M\setminus x$である。

(3)を示す。$x$が coloop 元でないとする。§E13.24 命題 4.2より$x\notin B$を満たす基底$B$が存在する。$B\subseteq E\setminus\{x\}$かつ$\lvert B\rvert=r(E)$であるから$r(E\setminus\{x\})\ge r(E)$であり、§E13.16 定義 4.4 条件 (b)と合わせて$r_{M\setminus x}(E\setminus\{x\})=r(E\setminus\{x\})=r(E)$である。

$x$が loop 元でないとすると$r(\{x\})\ge1$であり、§E13.16 定義 4.4 条件 (a)より$r(\{x\})\le1$であるから$r(\{x\})=1$である。ゆえに$r_{M/x}(E\setminus\{x\})=r(E)-r(\{x\})=r(E)-1$である。二つのマトロイドは台集合$E\setminus\{x\}$の階数が異なるから相異なる。▨

証明. 第一の等式. 両辺の階数関数を$A\subseteq E\setminus T$について計算し、一致することを示す。§E13.16 定理 5.2により、台集合と階数関数が一致すればマトロイドは一致する。

左辺について、§E13.24 定理 2.2を台集合$E\setminus T$上のマトロイド$M\setminus T$へ適用すると$r_{(M\setminus T)^{*}}(A)=\lvert A\rvert-r_{M\setminus T}(E\setminus T)+r_{M\setminus T}\bigl((E\setminus T)\setminus A\bigr)$であり、命題 1.2より$r_{M\setminus T}$は$r$の制限であるから$r_{(M\setminus T)^{*}}(A)=\lvert A\rvert-r(E\setminus T)+r\bigl(E\setminus(T\cup A)\bigr)$である。ここで$(E\setminus T)\setminus A=E\setminus(T\cup A)$を用いた。

右辺について、定義 2.1より$r_{M^{*}/T}(A)=r^{*}(A\cup T)-r^{*}(T)$である。§E13.24 定理 2.2を$M$へ適用すると$r^{*}(A\cup T)=\lvert A\cup T\rvert-r(E)+r\bigl(E\setminus(A\cup T)\bigr),\qquad r^{*}(T)=\lvert T\rvert-r(E)+r(E\setminus T)$である。$A$と$T$は交わらないから$\lvert A\cup T\rvert=\lvert A\rvert+\lvert T\rvert$であり、差を取ると$r_{M^{*}/T}(A)=\lvert A\rvert+r\bigl(E\setminus(A\cup T)\bigr)-r(E\setminus T)$である。二つの式は一致するから$(M\setminus T)^{*}=M^{*}/T$である。

第二の等式. 第一の等式を$M$の代わりに$M^{*}$へ適用すると$(M^{*}\setminus T)^{*}=(M^{*})^{*}/T=M/T$である。ここで§E13.24 定理 1.3の$(M^{*})^{*}=M$を用いた。両辺の双対を取り、ふたたび$(N^{*})^{*}=N$を用いると$M^{*}\setminus T=\bigl((M^{*}\setminus T)^{*}\bigr)^{*}=(M/T)^{*}$を得る。▨

証明. いずれも台集合は$E\setminus(T_1\cup T_2)$である。

(1)を示す。$I\subseteq E\setminus(T_1\cup T_2)$について、$I$が左辺の独立集合であることは$I\in\mathcal I$かつ$I\subseteq E\setminus T_1$かつ$I\subseteq(E\setminus T_1)\setminus T_2$であることであり、これは$I\in\mathcal I$かつ$I\subseteq E\setminus(T_1\cup T_2)$と同値である。ゆえに独立集合族が一致する。

(2)を示す。$A\subseteq E\setminus(T_1\cup T_2)$とする。定義 2.1を二度用いると$r_{(M/T_1)/T_2}(A)=r_{M/T_1}(A\cup T_2)-r_{M/T_1}(T_2)=\bigl(r(A\cup T_2\cup T_1)-r(T_1)\bigr)-\bigl(r(T_2\cup T_1)-r(T_1)\bigr)$であり、右辺は$r\bigl(A\cup(T_1\cup T_2)\bigr)-r(T_1\cup T_2)=r_{M/(T_1\cup T_2)}(A)$に等しい。階数関数が一致するから§E13.16 定理 5.2より二つのマトロイドは一致する。

(3)を示す。$A\subseteq E\setminus(T_1\cup T_2)$とする。左辺について、命題 1.2より$r_{M\setminus T_1}$は$r$の制限であるから$r_{(M\setminus T_1)/T_2}(A)=r_{M\setminus T_1}(A\cup T_2)-r_{M\setminus T_1}(T_2)=r(A\cup T_2)-r(T_2)$である。右辺について、$r_{M/T_2}$の$E\setminus(T_1\cup T_2)$への制限であるから$r_{(M/T_2)\setminus T_1}(A)=r_{M/T_2}(A)=r(A\cup T_2)-r(T_2)$である。二つは一致する。▨

証明. 十分性.$X$を削除し$Y$を縮約する二段の操作は定義 5.2の反復であるから、$(M\setminus X)/Y$は$M$のマイナーである。

必要性. 反復の長さについての帰納法で示す。非負整数$k$についての述語$P(k)$を「長さ$k$の反復で得られるマトロイドは、互いに交わらない$X,Y\subseteq E$によって$(M\setminus X)/Y$の形に書くことができる」と定める。

$P(0)$、すなわち長さ$0$の場合は$M=(M\setminus\emptyset)/\emptyset$である。

$P(k)$を仮定する。長さ$k+1$の反復で得られるマトロイドを$M_{k+1}$とすると、その直前の$M_k$は長さ$k$の反復で得られるから、$M_k=(M\setminus X)/Y$（$X\cap Y=\emptyset$）と書くことができ、$M_k$の台集合は$E\setminus(X\cup Y)$である。$M_{k+1}$は$M_k$から一段の削除または縮約で得られるから、$T\subseteq E\setminus(X\cup Y)$を取って次の二つの場合に分ける。

削除の場合は、命題 5.1 (3)を$M\setminus X$の上で$T$と$Y$について適用して$M_{k+1}=\bigl((M\setminus X)/Y\bigr)\setminus T=\bigl((M\setminus X)\setminus T\bigr)/Y=\bigl(M\setminus(X\cup T)\bigr)/Y$となる。最後の等号は命題 5.1 (1)による。$T$は$Y$と交わらないから$(X\cup T)\cap Y=\emptyset$である。

縮約の場合は、命題 5.1 (2)を$M\setminus X$の上で適用して$M_{k+1}=\bigl((M\setminus X)/Y\bigr)/T=(M\setminus X)/(Y\cup T)$となる。$T$は$X$と交わらないから$X\cap(Y\cup T)=\emptyset$である。

いずれの場合も$M_{k+1}$は互いに交わらない二つの部分集合による$(M\setminus X')/Y'$の形に書くことができ、$P(k+1)$が成り立つ。ゆえに§D2.1 命題 1.2の単純帰納法によりすべての非負整数$k$について$P(k)$が成り立ち、有限回の反復で得られるマトロイドはすべてこの形に書くことができる。▨

証明.定理 4.1を$M\setminus X$と$Y$へ適用すると$\bigl((M\setminus X)/Y\bigr)^{*}=(M\setminus X)^{*}\setminus Y$である。同じ定理を$M$と$X$へ適用すると$(M\setminus X)^{*}=M^{*}/X$であるから、$\bigl((M\setminus X)/Y\bigr)^{*}=(M^{*}/X)\setminus Y$を得る。右辺は定理 5.3の形であるから$M^{*}$のマイナーである。▨