マトロイドの削除・縮約とマイナー | 離散数学 II

1 削除

定義 1.1. $T\subseteq E$ とする。台集合 $E\setminus T$ の上の集合族 $\mathcal I(M\setminus T)=\{I\in\mathcal I:\ I\subseteq E\setminus T\}$ を独立集合族とする組を $M\setminus T$ と書き、 $M$ から $T$ を削除 (deletion) して得られる構造という。 $T=\{x\}$ のときは $M\setminus x$ とも書く。

命題 1.2. $T\subseteq E$ とする。 $M\setminus T$ は台集合 $E\setminus T$ 上のマトロイドであり、その階数関数 $r_{M\setminus T}$ は $r_{M\setminus T}(A)=r(A)\qquad(A\subseteq E\setminus T)$ を満たす。また $M\setminus T$ の基底は、 $E\setminus T$ に含まれる $M$ の独立集合のうち包含に関して極大なものの全体であり、その共通の濃度は $r(E\setminus T)$ である。

証明. マトロイドであること.§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)$ である。▨

2 縮約

縮約は、取り除く元をすでに使ったものとして扱う操作である。階数関数によって定義すると、選び方に依存しない形で書くことができる。

定義 2.1. $T\subseteq E$ とする。関数 $r_{M/T}:2^{E\setminus T}\to\mathbb Z_{\ge0}$ を $r_{M/T}(A)=r(A\cup T)-r(T)\qquad(A\subseteq E\setminus T)$ と定める。 $r_{M/T}$ を階数関数とする台集合 $E\setminus T$ 上のマトロイドを $M/T$ と書き、 $M$ から $T$ を縮約 (contraction) して得られるマトロイドという。 $M/T$ がマトロイドとして定まることは命題 2.2が示す。 $T=\{x\}$ のときは $M/x$ とも書く。

命題 2.2. $T\subseteq E$ とする。 $r_{M/T}$ は台集合 $E\setminus T$ 上で§E13.16 定義 4.4の§E13.16 定義 4.4 条件 (a)、§E13.16 定義 4.4 条件 (b)、§E13.16 定義 4.4 条件 (c)を満たす。したがって§E13.16 定理 5.2により、 $r_{M/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による。▨

命題 2.3. $T\subseteq E$ とし、 $B_T$ を $T$ に含まれる $M$ の独立集合のうち包含に関して極大なものとする（ $\lvert B_T\rvert=r(T)$ である）。 $I\subseteq E\setminus T$ に対し次が成り立つ。

$I$ が $M/T$ の独立集合であることと、 $I\cup B_T\in\mathcal I$ であることは同値である。とくにこの条件は $B_T$ の選び方に依存しない。
$I$ が $M/T$ の基底であることと、 $I\cup B_T$ が $M$ の基底であることは同値である。したがって $M/T$ の基底全体は $\{B\setminus B_T:\ B\in\mathcal B,\ B_T\subseteq B\}$ である。

証明.§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$ である。▨

3 loop 元と coloop 元における削除と縮約

削除と縮約は一般には異なるマトロイドを与える。一致するのは、取り除く元が loop 元または coloop 元である場合に限る。

命題 3.1. $x\in E$ とする。

$x$ が§E13.24 定義 4.1の意味で $M$ の loop 元ならば、任意の $A\subseteq E\setminus\{x\}$ に対し $r(A\cup\{x\})=r(A)$ が成り立ち、 $M/x=M\setminus x$ である。
$x$ が $M$ の coloop 元ならば、任意の $A\subseteq E\setminus\{x\}$ に対し $r(A\cup\{x\})=r(A)+1$ が成り立ち、 $M/x=M\setminus x$ である。
$x$ が loop 元でも coloop 元でもないならば、 $r_{M/x}(E\setminus\{x\})=r(E)-1$ かつ $r_{M\setminus x}(E\setminus\{x\})=r(E)$ であり、 $M/x\ne M\setminus x$ である。

証明.(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\}$ の階数が異なるから相異なる。▨

注意 3.2 (縮約は新たな loop 元を作る). $T\subseteq E$ と $x\in E\setminus T$ について、 $r(T\cup\{x\})=r(T)$ が成り立つならば $r_{M/T}(\{x\})=0$ であり、 $x$ は $M/T$ の loop 元である。もとのマトロイド $M$ が loop 元をもたない場合でも、縮約によって loop 元が現れることがある。同様に、縮約は相異なる二元 $x,y$ について $\{x,y\}$ を回路にすることがある。例 6.2にその例を示す。

4 双対は削除と縮約を交換する

定理 4.1. $T\subseteq E$ とする。台集合 $E\setminus T$ 上のマトロイドとして $(M\setminus T)^{*}=M^{*}/T,\qquad (M/T)^{*}=M^{*}\setminus T$ が成り立つ。

証明. 第一の等式. 両辺の階数関数を $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)^{*}$ を得る。▨

5 マイナー

命題 5.1. $T_1,T_2\subseteq E$ が互いに交わらないとする。

$(M\setminus T_1)\setminus T_2=M\setminus(T_1\cup T_2)$ 。
$(M/T_1)/T_2=M/(T_1\cup T_2)$ 。
$(M\setminus T_1)/T_2=(M/T_2)\setminus T_1$ 。

証明. いずれも台集合は $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)$ である。二つは一致する。▨

定義 5.2. マトロイド $N$ が $M$ のマイナー (minor) であるとは、 $M$ から削除と縮約を有限回反復して $N$ が得られること、すなわち $M_0=M$ から始めて、各段で $M_{i}=M_{i-1}\setminus T_i$ または $M_{i}=M_{i-1}/T_i$ （ $T_i$ は $M_{i-1}$ の台集合の部分集合）と定める有限列 $M_0,M_1,\dots,M_k$ が存在して $M_k=N$ となることをいう。

定理 5.3. $N$ が $M$ のマイナーであることと、互いに交わらない $X,Y\subseteq E$ が存在して $N=(M\setminus X)/Y$ となることは同値である。

証明. 十分性. $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)$ が成り立ち、有限回の反復で得られるマトロイドはすべてこの形に書くことができる。▨

系 5.4. 互いに交わらない $X,Y\subseteq E$ に対し $\bigl((M\setminus X)/Y\bigr)^{*}=(M^{*}/X)\setminus Y$ が成り立つ。とくに $M$ のマイナーの双対は $M^{*}$ のマイナーである。

証明.定理 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^{*}$ のマイナーである。▨

6 具体例

例 6.1 (一様マトロイドの削除・縮約とマイナー). $M=U_{2,4}$ を台集合 $E=\{1,2,3,4\}$ の上で取る。階数関数は $r(A)=\min\{\lvert A\rvert,2\}$ 、 $r(E)=2$ である。

削除. $T=\{4\}$ とすると、 $M\setminus4$ の階数関数は $A\subseteq\{1,2,3\}$ に対し $\min\{\lvert A\rvert,2\}$ であるから $M\setminus4=U_{2,3}$ である。

縮約. $M/4$ の階数関数は $A\subseteq\{1,2,3\}$ に対し $r_{M/4}(A)=r(A\cup\{4\})-r(\{4\})=\min\{\lvert A\rvert+1,\ 2\}-1=\min\{\lvert A\rvert,\ 1\}$ であるから $M/4=U_{1,3}$ である。 $4$ は loop 元でも coloop 元でもないから、命題 3.1 (3)のとおり $M\setminus4\ne M/4$ である。実際、台集合 $\{1,2,3\}$ の階数は前者が $2$ 、後者が $1$ である。

双対との交換の検算. $U_{2,4}^{*}=U_{2,4}$ である（§E13.24 例 2.3）。第一の等式 $(M\setminus4)^{*}=M^{*}/4$ を確かめる。左辺は $U_{2,3}^{*}=U_{1,3}$ である。右辺は $U_{2,4}/4=U_{1,3}$ である。両者は一致する。第二の等式 $(M/4)^{*}=M^{*}\setminus4$ を確かめる。左辺は $U_{1,3}^{*}=U_{2,3}$ である。右辺は $U_{2,4}\setminus4=U_{2,3}$ である。両者は一致する。

マイナー. $(M\setminus\{4\})/\{3\}$ を計算する。 $M\setminus4=U_{2,3}$ の階数関数は $\min\{\lvert A\rvert,2\}$ であるから、 $A\subseteq\{1,2\}$ に対し $r_{(M\setminus4)/3}(A)=\min\{\lvert A\rvert+1,\ 2\}-1=\min\{\lvert A\rvert,\ 1\}$ であり、 $(M\setminus4)/3=U_{1,2}$ である。

例 6.2 (グラフ的マトロイドの縮約は平行な元を生む). 頂点 $1,2,3,4$ と六本の辺 $a=\{1,2\},\quad b=\{1,3\},\quad c=\{1,4\},\quad d=\{2,3\},\quad e=\{2,4\},\quad f=\{3,4\}$ からなる完全グラフ $K_4$ を取り、 $M=M(K_4)$ とする。§E13.16 命題 4.3より $r(F)=4-c(F)$ である（ $c(F)$ は $(V,F)$ の連結成分の個数）。

削除. $M\setminus f$ は、辺 $f$ を除いたグラフ $K_4-f$ のグラフ的マトロイドである。実際、 $F\subseteq E\setminus\{f\}$ が閉路をもたないことは $(V,F)$ が閉路をもたないことにほかならない。

縮約. $M/a$ を調べる。 $r(\{a\})=1$ であるから $r_{M/a}(A)=r(A\cup\{a\})-1$ である。

$r_{M/a}(\{b\})=r(\{a,b\})-1$ を計算する。 $(V,\{a,b\})$ の辺は $\{1,2\}$ と $\{1,3\}$ であり、連結成分は $\{1,2,3\}$ と $\{4\}$ の二つであるから $r(\{a,b\})=4-2=2$ であり $r_{M/a}(\{b\})=1$ である。ゆえに $\{b\}$ は $M/a$ の独立集合である。
同様に $r_{M/a}(\{d\})=r(\{a,d\})-1$ であり、 $(V,\{a,d\})$ の辺は $\{1,2\}$ と $\{2,3\}$ 、連結成分は $\{1,2,3\}$ と $\{4\}$ であるから $r(\{a,d\})=2$ 、 $r_{M/a}(\{d\})=1$ である。
$r_{M/a}(\{b,d\})=r(\{a,b,d\})-1$ を計算する。 $(V,\{a,b,d\})$ の辺は $\{1,2\}$ 、 $\{1,3\}$ 、 $\{2,3\}$ であり、連結成分は $\{1,2,3\}$ と $\{4\}$ の二つであるから $r(\{a,b,d\})=4-2=2$ であり $r_{M/a}(\{b,d\})=1$ である。 $\lvert\{b,d\}\rvert=2>1$ であるから $\{b,d\}$ は $M/a$ の従属集合である。

$\{b\}$ と $\{d\}$ が独立で $\{b,d\}$ が従属であるから、 $\{b,d\}$ は $M/a$ の回路である。すなわち $M/a$ は濃度 $2$ の回路をもつ。§D2.7 定義 1.1の単純グラフのグラフ的マトロイドは、一本の辺だけからなる集合が独立であり二本の辺だけからなる集合も独立であるから、濃度 $2$ の回路をもたない。ゆえに $M/a$ は単純グラフのグラフ的マトロイドではない。縮約は、もとのマトロイドがもたなかった小さな回路を作ることがある。

7 演習

問題 7.1.

命題 2.2の§E13.16 定義 4.4 条件 (c)の証明で用いた二つの等式 $(A\cup T)\cup(B\cup T)=(A\cup B)\cup T$ と $(A\cup T)\cap(B\cup T)=(A\cap B)\cup T$ のうち、後者が $A,B\subseteq E\setminus T$ という条件を要することを、条件を外した反例によって示せ。
命題 2.3 (1)の必要性の証明では、 $\lvert J\cap T\rvert\le r(T)$ と $\lvert J\setminus T\rvert\le\lvert I\rvert$ の二つの不等式がともに等号になることを導いた。この段を参照せずに再現し、どちらの等号から $I\subseteq J$ が従うかを述べよ。
命題 2.3 (1)が $B_T$ の選び方に依存しないことを、二つの極大独立集合 $B_T$ と $B_T'$ を取って直接比較する形で証明し直せ。
命題 3.1 (2)の証明で、 $I$ を含む基底 $B$ を取り $x\in B$ を用いた。 $x$ が coloop 元であるという仮定をどこで用いたかを明示し、仮定を落とすと $r(A\cup\{x\})\ge r(A)+1$ が成り立たなくなる例を $U_{1,2}$ で構成せよ。
定理 4.1の第一の等式の証明を、参照せずに再現せよ。 $\lvert A\cup T\rvert=\lvert A\rvert+\lvert T\rvert$ をどこで用いたか、その等式が $A\cap T=\emptyset$ を要することを明示せよ。
定理 4.1の第二の等式を、第一の等式へ帰着させる方法ではなく、両辺の階数関数を直接計算する方法で証明せよ。
定理 5.3の帰納段階のうち、削除の場合の書き換えを、用いた命題 5.1の項目を明示しながら再現せよ。縮約の場合と削除の場合で、 $X$ と $Y$ のどちらが増えるかを述べよ。
例 6.2にならい、 $M(K_4)/\{a,f\}$ の階数関数を計算し、台集合 $\{b,c,d,e\}$ の上でどのようなマトロイドになるかを決定せよ。

8 つまずいたら

削除は独立集合を制限する操作であり、縮約は階数の基準点をずらす操作である。二つは一般に異なるマトロイドを与え、一致するのは取り除く元が loop 元または coloop 元である場合に限る（命題 3.1）。
縮約の定義を $\mathcal I(M/T)=\{I:\ I\cup B_T\in\mathcal I\}$ とする流儀では、 $B_T$ の選び方に依存しないことを別に示す必要がある。本記事は階数関数によって定義したので（定義 2.1）、非依存性は命題 2.3の帰結として得られる。
双対階数公式には台集合全体の階数が現れる。削除や縮約の後で双対を取るときは、その台集合が $E$ ではなく $E\setminus T$ であることに注意する（定理 4.1の計算）。
縮約は新たな loop 元や濃度 $2$ の回路を作ることがある（注意 3.2、例 6.2）。単純グラフのグラフ的マトロイドを縮約した結果が、ふたたび単純グラフのグラフ的マトロイドになるとは限らない。
マイナーの正規形は「削除してから縮約する」形である（定理 5.3）。順序を逆にした「縮約してから削除する」形も同じ族を与えるが、それは命題 5.1 (3)による帰結であって、定義から明らかなことではない。

9 扱った範囲と次の記事

本記事は、削除を独立集合の制限として、縮約を階数関数のずらしとして定義し、いずれもマトロイドであることを証明した。縮約については、 $T$ に含まれる極大独立集合 $B_T$ を用いた独立集合と基底による記述を証明し、その記述が $B_T$ の選び方に依存しないことも示した。loop 元と coloop 元については削除と縮約が一致し、それ以外の元については一致しないことを階数の比較によって証明した。双対が削除と縮約を交換する二つの等式を階数関数の計算によって証明し、削除と縮約の反復が「一度の削除と一度の縮約」へ整理されることを示してマイナーを定義した。禁止マイナーによるマトロイドの類の特徴づけ、正則マトロイドと表現可能性、およびマイナーに関する整列性は扱っていない。次の記事では、各辺を独立に同じ確率で選ぶ有限ランダムグラフを定義し、部分構造の個数の期待値と、性質の閾値を扱う。

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