§E16.24マトロイドの双対

(1)を示す。$B$は包含に関して極大な独立集合であり$x\notin B$であるから$B\cup\{x\}\notin\mathcal I$であり、§E16.16 系 5.3により$B$と$x$の基本回路$C$が定まる。$y\in B$とし、$D=(B\cup\{x\})\setminus\{y\}$と置く。$x\notin B$かつ$y\in B$であるから$\lvert D\rvert=\lvert B\rvert$である。

$y\in C$とする。$D\notin\mathcal I$と仮定すると、§E16.16 命題 1.2より$C'\subseteq D$を満たす回路$C'$が存在する。$C'\subseteq D\subseteq B\cup\{x\}$であり、$B\cup\{x\}$に含まれる回路は$C$だけであるから$C'=C$である。ところが$y\in C$かつ$y\notin D$であるから$C\not\subseteq D$であり、$C'\subseteq D$に反する。ゆえに$D\in\mathcal I$であり、$\lvert D\rvert=\lvert B\rvert$と§E16.15 系 2.4より$D\in\mathcal B$である。

$y\notin C$とする。$C\subseteq B\cup\{x\}$であるから$C\subseteq(B\cup\{x\})\setminus\{y\}=D$である。$C\notin\mathcal I$であるから、§E16.15 定義 1.1 条件 (I2)の対偶により$D\notin\mathcal I$であり、$D$は基底でない。以上で前半の同値が示された。

後半を示す。$B_1,B_2\in\mathcal B$、$x\in B_2\setminus B_1$とし、$C$を$B_1$と$x$の基本回路とする。前半を$B=B_1$へ適用すると、$y\in B_1\setminus B_2$について$(B_1\cup\{x\})\setminus\{y\}\in\mathcal B$であることは$y\in C$と同値である。したがって求める集合は$C\cap(B_1\setminus B_2)$である。$C\cap(B_1\setminus B_2)\subseteq C\setminus B_2$である。逆に$z\in C\setminus B_2$とすると、$x\in B_2$より$z\ne x$であり、$C\subseteq B_1\cup\{x\}$より$z\in B_1$であるから、$z\in C\cap(B_1\setminus B_2)$である。ゆえに求める集合は$C\setminus B_2$に一致する。$C\notin\mathcal I$かつ$B_2\in\mathcal I$であるから、§E16.15 定義 1.1 条件 (I2)より$C\not\subseteq B_2$であり、この集合は空でない。

(2)を示す。定理 1.3より$M^{*}$はマトロイドであり、その基底全体は$\mathcal B^{*}$である。$B^{*}=E\setminus B$と置くと、$B^{*}$は$M^{*}$の基底、すなわち$M^{*}$の包含に関して極大な独立集合である。$y\in B$より$y\notin B^{*}$であるから$B^{*}\subsetneq B^{*}\cup\{y\}$であり、$B^{*}\cup\{y\}\notin\mathcal I^{*}$である。§E16.16 系 5.3を$M^{*}$、その独立集合$B^{*}$、および$y\in E\setminus B^{*}$へ適用すると、$B^{*}\cup\{y\}=(E\setminus B)\cup\{y\}$に含まれる$M^{*}$の回路はただ一つであり、その回路は$y$を含む。定義 3.1により$M^{*}$の回路は$M$の余回路であるから、前半の主張を得る。この基本余回路を$C^{*}$と書く。$C^{*}$は、$M^{*}$における$B^{*}$と$y$の基本回路である。

$x\in E\setminus B=B^{*}$とする。(1)の前半を、マトロイド$M^{*}$、その基底$B^{*}$、$y\in E\setminus B^{*}$、および$x\in B^{*}$へ適用すると、$(B^{*}\cup\{y\})\setminus\{x\}\in\mathcal B^{*}$であることと$x\in C^{*}$であることは同値である。$y\in B$かつ$x\notin B$であるから$x\ne y$であり、

である。実際、$z\in E$が左辺に属することは「$z\ne x$であり、かつ$z\notin B$または$z=y$である」ことと同値であり、これは「$z=x$であるか、または$z\in B$かつ$z\ne y$である」ことの否定、すなわち$z\notin(B\setminus\{y\})\cup\{x\}$と同値である。$\mathcal B^{*}$の元は$\mathcal B$の元の補集合であり、$E$の部分集合$D_1,D_2$について$E\setminus D_1=E\setminus D_2$ならば$D_1=D_2$であるから、$(B^{*}\cup\{y\})\setminus\{x\}\in\mathcal B^{*}$であることと$(B\setminus\{y\})\cup\{x\}\in\mathcal B$であることは同値である。ゆえに第一の条件と第二の条件は同値である。さらに$x\ne y$より$(B\setminus\{y\})\cup\{x\}=(B\cup\{x\})\setminus\{y\}$であるから、(1)の前半を$M$、$B$、$x$、$y$へ適用すると、第二の条件は$y$が$B$と$x$の基本回路に属することと同値である。

(3)を示す。$C\cap C^{*}=\{e\}$を満たす$e$が存在すると仮定する。$C^{*}\setminus\{e\}\subsetneq C^{*}$であるから、定理 3.2 (2)より、$(C^{*}\setminus\{e\})\cap B_0=\emptyset$を満たす$B_0\in\mathcal B$が存在する。同じ条件より$C^{*}\cap B_0\ne\emptyset$であるから$C^{*}\cap B_0=\{e\}$であり、$e\in B_0$である。$X=E\setminus C^{*}$、$I=C\setminus\{e\}$と置く。$C$は回路であるから$I\in\mathcal I$であり、$C\cap C^{*}=\{e\}$より$I\subseteq X$である。§E16.16 命題 4.2より、$X$に含まれる独立集合のうち包含に関して極大なもの$J$であって$I\subseteq J$を満たすものが存在する。$J$が基底であるとすると、$J\subseteq X$より$J\cap C^{*}=\emptyset$となり、$C^{*}$がすべての基底と交わることに反する。ゆえに$J$は基底でなく、§E16.15 系 2.4より$\lvert J\rvert<\lvert B_0\rvert$である。§E16.15 定義 1.1 条件 (I3)を$J$と$B_0$へ適用すると、$b\in B_0\setminus J$が存在して$J\cup\{b\}\in\mathcal I$となる。$b\in X$であるとすると、$J\cup\{b\}$は$X$に含まれる独立集合であって$J$を真に含むので、$J$の極大性に反する。ゆえに$b\in C^{*}\cap B_0=\{e\}$であり、$b=e$である。すると$C=I\cup\{e\}\subseteq J\cup\{e\}\in\mathcal I$であるから、§E16.15 定義 1.1 条件 (I2)より$C\in\mathcal I$となり、$C$が回路であることに反する。ゆえに$\lvert C\cap C^{*}\rvert\ne1$である。

後半を示す。$B_1,B_2\in\mathcal B$、$x\in B_1\setminus B_2$とする。(2)により$B_1$と$x$の基本余回路$C^{*}$が定まり、$x\in C^{*}\subseteq(E\setminus B_1)\cup\{x\}$である。$B_2$は包含に関して極大な独立集合であり$x\notin B_2$であるから、§E16.16 系 5.3により$B_2$と$x$の基本回路$C$が定まり、$x\in C\subseteq B_2\cup\{x\}$である。$x\in C\cap C^{*}$であり、前半より$\lvert C\cap C^{*}\rvert\ne1$であるから、$x$と異なる$y\in C\cap C^{*}$が存在する。$y\in C\setminus\{x\}\subseteq B_2$であり、$y\in C^{*}\setminus\{x\}\subseteq E\setminus B_1$であるから、$y\in B_2\setminus B_1$である。$y\in E\setminus B_1$は$B_1$と$x$の基本余回路に属するので、(2)の第一の条件と第二の条件の同値により$(B_1\setminus\{x\})\cup\{y\}\in\mathcal B$である。$y\in B_2$は$B_2$と$x$の基本回路に属するので、(1)の前半により$(B_2\cup\{x\})\setminus\{y\}\in\mathcal B$であり、$x\ne y$よりこの集合は$(B_2\setminus\{y\})\cup\{x\}$に等しい。

(4)を示す。$V=\{\lvert A\cap B\rvert:\ B\in\mathcal B\}$と置く。補題 2.1より$\max V=r(A)$である。補題 2.1を$M^{*}$へ適用すると、$\lvert A\cap(E\setminus B)\rvert=\lvert A\rvert-\lvert A\cap B\rvert$であるから

である。これと定理 2.2より$\min V=\lvert A\rvert-r^{*}(A)=r(E)-r(E\setminus A)$である。ゆえに$V$は$r(E)-r(E\setminus A)$以上$r(A)$以下の整数からなり、両端の値は$V$に属する。

$\lvert A\cap B_0\rvert=\min V$、$\lvert A\cap B_1\rvert=\max V$を満たす$B_0,B_1\in\mathcal B$を取る。基底の列$D_0,D_1,\dots$を次のように定める。$D_0=B_0$とする。$D_i\in\mathcal B$が定まり$D_i\ne B_1$であるとする。§E16.15 命題 2.3より$\lvert D_i\rvert=\lvert B_1\rvert$であるから、$D_i\subseteq B_1$ならば$D_i=B_1$となる。したがって$D_i\setminus B_1\ne\emptyset$であり、$x_i\in D_i\setminus B_1$を取ることができる。§E16.15 定理 4.3 (1)より$\mathcal B$は§E16.15 定義 3.1 条件 (B2)を満たすから、$y_i\in B_1\setminus D_i$が存在して$D_{i+1}=(D_i\setminus\{x_i\})\cup\{y_i\}\in\mathcal B$となる。$x_i\notin B_1$かつ$y_i\in B_1$であるから$\lvert D_{i+1}\setminus B_1\rvert=\lvert D_i\setminus B_1\rvert-1$である。ゆえに、$k=\lvert B_0\setminus B_1\rvert$と置くと、この操作は$k$回で$D_k\setminus B_1=\emptyset$、すなわち$D_k=B_1$に至る。