§E16.15マトロイドの独立集合と基底

証明.$\mathcal F=\{I\in\mathcal I:\ A\subseteq I\}$と置く。$A\in\mathcal F$であるから$\mathcal F\ne\emptyset$であり、$E$が有限集合であるから$\mathcal F$も有限集合である。したがって$\mathcal F$の元の濃度の集合は空でない有限な非負整数の集合であり、最大値をとる元$B\in\mathcal F$が存在する。

$B$が基底であることを示す。$B\subsetneq I$かつ$I\in\mathcal I$を満たす$I$が存在したとする。$A\subseteq B\subseteq I$であるから$I\in\mathcal F$であり、$\lvert I\rvert>\lvert B\rvert$となって$B$の最大性に反する。ゆえにそのような$I$は存在せず、$B$は包含に関して極大な独立集合、すなわち基底である。

最後に、条件 (I1)より$\emptyset\in\mathcal I$であるから、$A=\emptyset$に対して上の議論を適用すると基底が存在する。▨

証明.$B_1,B_2$を基底とし、$\lvert B_1\rvert<\lvert B_2\rvert$と仮定する。$B_1,B_2\in\mathcal I$であるから条件 (I3)を適用すると、$x\in B_2\setminus B_1$が存在して$B_1\cup\{x\}\in\mathcal I$となる。$x\notin B_1$であるから$B_1\subsetneq B_1\cup\{x\}$であり、$B_1$が包含に関して極大であることに反する。

ゆえに$\lvert B_1\rvert<\lvert B_2\rvert$は成り立たない。$B_1$と$B_2$の役割を入れ替えると$\lvert B_2\rvert<\lvert B_1\rvert$も成り立たない。したがって$\lvert B_1\rvert=\lvert B_2\rvert$である。▨

証明.$A\in\mathcal I$とする。命題 2.2より$A\subseteq B$を満たす基底$B$が存在し、命題 2.3より$\lvert B\rvert=b$である。したがって$\lvert A\rvert\le\lvert B\rvert=b$である。

さらに$\lvert A\rvert=b$ならば$A\subseteq B$かつ$\lvert A\rvert=\lvert B\rvert$であり、両者は有限集合であるから$A=B$となる。ゆえに$A$は基底である。▨

証明.$\lvert B_1\rvert>\lvert B_2\rvert$を満たす対$(B_1,B_2)\in\mathcal B\times\mathcal B$が存在したとする。$\mathcal B$は有限集合であるから、そのような対のうち$\lvert B_1\setminus B_2\rvert$が最小のものを一つ取り、あらためて$(B_1,B_2)$と書く。

$\lvert B_1\rvert>\lvert B_2\rvert$より$B_1\setminus B_2\ne\emptyset$であるから、$x\in B_1\setminus B_2$を取ることができる。条件 (B2)より$y\in B_2\setminus B_1$が存在して$B_3=(B_1\setminus\{x\})\cup\{y\}\in\mathcal B$となる。

$y\notin B_1$であるから$\lvert B_3\rvert=\lvert B_1\rvert-1+1=\lvert B_1\rvert>\lvert B_2\rvert$である。また$y\in B_2$であるから$B_3\setminus B_2=\bigl((B_1\setminus\{x\})\cup\{y\}\bigr)\setminus B_2=(B_1\setminus B_2)\setminus\{x\}$であり、$x\in B_1\setminus B_2$より$\lvert B_3\setminus B_2\rvert=\lvert B_1\setminus B_2\rvert-1$である。したがって対$(B_3,B_2)$は$\lvert B_3\rvert>\lvert B_2\rvert$を満たし、かつ$\lvert B_3\setminus B_2\rvert<\lvert B_1\setminus B_2\rvert$となって、$(B_1,B_2)$の最小性に反する。

ゆえに$\lvert B_1\rvert>\lvert B_2\rvert$を満たす対は存在せず、$\mathcal B$のすべての元は同じ濃度をもつ。▨

証明.$\mathcal G=\{B'\in\mathcal B:\ A\subseteq B'\}$と置く。$A\in\mathcal I$であるから$\mathcal G\ne\emptyset$である。$\mathcal G$は有限集合であるから、$\lvert B'\setminus B\rvert$を最小にする$B'\in\mathcal G$を一つ取ることができる。

$B'\subseteq A\cup B$を示す。$x\in B'\setminus(A\cup B)$が存在したとする。とくに$x\in B'\setminus B$である。条件 (B2)を$B',B\in\mathcal B$と$x\in B'\setminus B$へ適用すると、$y\in B\setminus B'$が存在して$B''=(B'\setminus\{x\})\cup\{y\}\in\mathcal B$となる。

$x\notin A$であるから$A\subseteq B'\setminus\{x\}\subseteq B''$であり、$B''\in\mathcal G$である。さらに$y\in B$であるから$B''\setminus B=\bigl((B'\setminus\{x\})\cup\{y\}\bigr)\setminus B=(B'\setminus B)\setminus\{x\}$であり、$x\in B'\setminus B$より$\lvert B''\setminus B\rvert=\lvert B'\setminus B\rvert-1$となって$B'$の最小性に反する。

ゆえに$B'\setminus(A\cup B)=\emptyset$、すなわち$B'\subseteq A\cup B$である。$A\subseteq B'$は$B'\in\mathcal G$による。▨

証明. 主張 (1)の条件 (I1).条件 (B1)より$B\in\mathcal B$を取ることができ、$\emptyset\subseteq B$であるから$\emptyset\in\mathcal I$である。

主張 (1)の条件 (I2).$A\in\mathcal I$とし$A'\subseteq A$とする。$A\subseteq B$を満たす$B\in\mathcal B$を取ると$A'\subseteq A\subseteq B$であるから$A'\in\mathcal I$である。

主張 (1)の条件 (I3).$A_1,A_2\in\mathcal I$とし$\lvert A_1\rvert<\lvert A_2\rvert$とする。$A_2\subseteq B_2$を満たす$B_2\in\mathcal B$を取る。補題 4.2を$A_1$と$B_2$へ適用すると、$A_1\subseteq B_1\subseteq A_1\cup B_2$を満たす$B_1\in\mathcal B$が存在する。補題 4.1より$\lvert B_1\rvert=\lvert B_2\rvert$であり、この共通の値を$b$と書く。

$B_1\cap(A_2\setminus A_1)\ne\emptyset$を示す。$B_1\cap(A_2\setminus A_1)=\emptyset$と仮定する。$B_1\subseteq A_1\cup B_2$であるから$B_1\setminus A_1\subseteq B_2\setminus A_1=(A_2\setminus A_1)\,\cup\,\bigl(B_2\setminus(A_1\cup A_2)\bigr)$であり、仮定より$B_1\setminus A_1$は$A_2\setminus A_1$と交わらないから$B_1\setminus A_1\subseteq B_2\setminus(A_1\cup A_2)$である。ゆえに$\lvert B_1\setminus A_1\rvert\le\bigl\lvert B_2\setminus(A_1\cup A_2)\bigr\rvert\le\lvert B_2\setminus A_2\rvert.$$A_1\subseteq B_1$かつ$A_2\subseteq B_2$であるから$\lvert B_1\setminus A_1\rvert=b-\lvert A_1\rvert$かつ$\lvert B_2\setminus A_2\rvert=b-\lvert A_2\rvert$であり、上の不等式から$b-\lvert A_1\rvert\le b-\lvert A_2\rvert$、すなわち$\lvert A_2\rvert\le\lvert A_1\rvert$が得られる。これは$\lvert A_1\rvert<\lvert A_2\rvert$に反する。

ゆえに$x\in B_1\cap(A_2\setminus A_1)$が存在する。$A_1\subseteq B_1$かつ$x\in B_1$であるから$A_1\cup\{x\}\subseteq B_1$であり、$\mathcal I$の定義より$A_1\cup\{x\}\in\mathcal I$である。$x\in A_2\setminus A_1$であるから条件 (I3)が成り立つ。

主張 (1)の基底の一致. まず$B\in\mathcal B$が$(E,\mathcal I)$の基底であることを示す。$B\in\mathcal I$である。$B\subseteq A$かつ$A\in\mathcal I$とすると、$A\subseteq B'$を満たす$B'\in\mathcal B$が存在し、$B\subseteq A\subseteq B'$となる。補題 4.1より$\lvert B\rvert=\lvert B'\rvert$であり、有限集合であるから$B=A=B'$である。ゆえに$B$は包含に関して極大であり、基底である。

逆に$A$を$(E,\mathcal I)$の基底とする。$A\in\mathcal I$であるから$A\subseteq B$を満たす$B\in\mathcal B$が存在し、いま示したとおり$B\in\mathcal I$である。$A$の極大性より$A=B\in\mathcal B$である。以上より$(E,\mathcal I)$の基底全体は$\mathcal B$に一致する。

主張 (1)の必要性.$\mathcal B$をマトロイド$M=(E,\mathcal I)$の基底全体とする。条件 (B1)を示す。命題 2.2より$\mathcal B\ne\emptyset$である。

条件 (B2)を示す。$B_1,B_2\in\mathcal B$とし、$x\in B_1\setminus B_2$とする。基底の共通の濃度を$b$と書く。$B_1\setminus\{x\}\subseteq B_1\in\mathcal I$であるから条件 (I2)より$B_1\setminus\{x\}\in\mathcal I$であり、$x\in B_1$より$\lvert B_1\setminus\{x\}\rvert=b-1<b=\lvert B_2\rvert$である。

条件 (I3)を独立集合の対$(B_1\setminus\{x\},\,B_2)$へ適用すると、$y\in B_2\setminus(B_1\setminus\{x\})$が存在して$(B_1\setminus\{x\})\cup\{y\}\in\mathcal I$となる。$x\notin B_2$であるから$y\ne x$であり、したがって$y\notin B_1$、すなわち$y\in B_2\setminus B_1$である。

$y\notin B_1\setminus\{x\}$であるから$\lvert(B_1\setminus\{x\})\cup\{y\}\rvert=(b-1)+1=b$である。系 2.4より$(B_1\setminus\{x\})\cup\{y\}$は基底である。

主張 (2)を示す。$\mathcal J=\{A\subseteq E:\ \exists B\in\mathcal B,\ A\subseteq B\}$と置く。$A\in\mathcal J$ならば$A\subseteq B$かつ$B\in\mathcal B\subseteq\mathcal I$であるから、条件 (I2)より$A\in\mathcal I$である。逆に$A\in\mathcal I$ならば命題 2.2より$A\subseteq B$を満たす基底$B$が存在するので$A\in\mathcal J$である。ゆえに$\mathcal J=\mathcal I$である。

互いに逆であること.主張 (2)では、マトロイドから基底族を作り、基底族から独立集合族を作ると、もとの独立集合族に戻ることが述べられている。主張 (1)では、条件 (B1)と条件 (B2)を満たす族から独立集合族を作り、その基底族を取ると、もとの族に戻ることが述べられている。したがって二つの対応は互いに逆であり、二つの公理系により同じ対象が定められる。▨

証明.条件 (I1)を示す。$\lvert\emptyset\rvert=0\le k$である。

条件 (I2)を示す。$B\subseteq A$ならば$\lvert B\rvert\le\lvert A\rvert\le k$である。

条件 (I3)を示す。$A,B\in\mathcal I$かつ$\lvert A\rvert<\lvert B\rvert$とする。$\lvert B\rvert\le k$より$\lvert A\rvert\le k-1$である。$\lvert A\rvert<\lvert B\rvert$より$B\setminus A\ne\emptyset$であるから$x\in B\setminus A$を取ることができ、$\lvert A\cup\{x\}\rvert=\lvert A\rvert+1\le k$であるから$A\cup\{x\}\in\mathcal I$である。

基底.$\lvert A\rvert=k$ならば、$A\subsetneq A'$かつ$A'\in\mathcal I$を満たす$A'$は$\lvert A'\rvert\ge k+1$となって存在しないから$A$は基底である。逆に$\lvert A\rvert<k$ならば、$\lvert E\rvert=n\ge k>\lvert A\rvert$より$x\in E\setminus A$が存在し、$\lvert A\cup\{x\}\rvert\le k$であるから$A$は極大でない。ゆえに基底は$k$元部分集合に限る。▨

証明.$(V,F)$の連結成分を$H_1,\dots,H_{c(F)}$とし、$H_i$の頂点数を$n_i$、辺数を$m_i$と書く。各$H_i$は連結であり、$(V,F)$の部分グラフであるから閉路をもたない。ゆえに§D2.7 定義 3.1より$H_i$は木であり、§D2.7 定理 3.6の定理 4.3 (1)から定理 4.3 (2)への含意により$m_i=n_i-1$である。

§D2.7 定義 2.3より、連結成分は到達可能性の同値類が定める部分グラフであり、$F$の各辺の両端点は互いに到達可能であるからちょうど一つの連結成分に属する。また各頂点もちょうど一つの連結成分に属する。したがって$\lvert F\rvert=\sum_{i=1}^{c(F)}m_i$かつ$\lvert V\rvert=\sum_{i=1}^{c(F)}n_i$であり、$\lvert F\rvert=\sum_{i=1}^{c(F)}(n_i-1)=\lvert V\rvert-c(F)$が成り立つ。▨

証明.条件 (I1)を示す。$(V,\emptyset)$は辺をもたないから閉路をもたない。

条件 (I2)を示す。$F'\subseteq F$とし$(V,F)$が閉路をもたないとする。$(V,F')$の閉路は$F'\subseteq F$より$(V,F)$の閉路でもあるから、$(V,F')$は閉路をもたない。

条件 (I3)を示す。$F_1,F_2\in\mathcal I$とし$\lvert F_1\rvert<\lvert F_2\rvert$とする。補題 6.2より$\lvert V\rvert-c(F_1)<\lvert V\rvert-c(F_2)$、すなわち$c(F_1)>c(F_2)$である。

$F_2\setminus F_1$の辺のうち、両端点が$(V,F_1)$の相異なる連結成分に属するものが存在することを示す。存在しないと仮定する。$F_1\cap F_2$の辺については、両端点が$(V,F_1)$の同一の連結成分に属することが§D2.7 定義 2.3から従う。ゆえに仮定のもとでは、$F_2$のすべての辺について両端点が$(V,F_1)$の同一の連結成分に属する。$(V,F_2)$において$u$から$v$への歩道が存在するとき、その歩道の各辺の両端点は$(V,F_1)$の同一の連結成分に属するから、歩道に沿って順に見ることにより$u$と$v$は$(V,F_1)$の同一の連結成分に属する。したがって$(V,F_2)$の各連結成分の頂点集合は$(V,F_1)$のある連結成分の頂点集合に含まれる。この対応によって$(V,F_2)$の連結成分から$(V,F_1)$の連結成分への写像$\varphi$が定まる。$(V,F_1)$の連結成分$H$を任意に取り、$H$の頂点$u$を一つ取ると、$u$を含む$(V,F_2)$の連結成分$H'$が存在し、$\varphi(H')$は$u$を含む$(V,F_1)$の連結成分であるから$\varphi(H')=H$である。ゆえに$\varphi$は全射であり、$c(F_2)\ge c(F_1)$となる。これは$c(F_1)>c(F_2)$に反する。

ゆえに$e=\{u,v\}\in F_2\setminus F_1$であって、$u$と$v$が$(V,F_1)$の相異なる連結成分に属するものが存在する。$(V,F_1\cup\{e\})$が閉路をもたないことを示す。閉路$C$が存在したとする。$(V,F_1)$は閉路をもたないから$C$は辺$e$を用いる。$C$から$e$を取り除くと$u$から$v$への$(V,F_1)$における歩道が残り、$u$と$v$が$(V,F_1)$の同一の連結成分に属することになって矛盾する。ゆえに$F_1\cup\{e\}\in\mathcal I$であり、$e\in F_2\setminus F_1$であるから条件 (I3)が成り立つ。

基底.$G$が連結であるとする。$F$が基底であることと$c(F)=1$であることが同値であることを示す。$c(F)\ge2$ならば$G$が連結であるから、相異なる二つの連結成分の頂点を結ぶ辺$e\in E\setminus F$が存在し、上と同じ議論で$F\cup\{e\}\in\mathcal I$となって$F$は極大でない。逆に$c(F)=1$ならば補題 6.2より$\lvert F\rvert=\lvert V\rvert-1$であり、$F\subsetneq F'$かつ$F'\in\mathcal I$を満たす$F'$があれば$\lvert F'\rvert\ge\lvert V\rvert$となって補題 6.2の等式$\lvert F'\rvert=\lvert V\rvert-c(F')\le\lvert V\rvert-1$に反する。

$c(F)=1$かつ$(V,F)$が閉路をもたないことは、$(V,F)$が木であること、すなわち$F$が$G$の全域木の辺集合であることにほかならない。このとき$\lvert F\rvert=\lvert V\rvert-1$である。▨

証明.条件 (I1)を示す。 空の族は一次独立であるから$\emptyset\in\mathcal I$である。

条件 (I2)を示す。$A\in\mathcal I$かつ$B\subseteq A$とする。$\sum_{i\in B}c_iv_i=0$とし、$i\in A\setminus B$に対し$c_i=0$と定めると$\sum_{i\in A}c_iv_i=0$となる。$A\in\mathcal I$より$c_i=0$がすべての$i\in A$について成り立ち、とくに$i\in B$について成り立つ。ゆえに$B\in\mathcal I$である。

条件 (I3)を示す。$A,B\in\mathcal I$かつ$\lvert A\rvert<\lvert B\rvert$とする。$U=\operatorname{span}\{v_i:\ i\in A\}$と置く。$U$は$W$の部分空間であり、$\lvert A\rvert$個のベクトル$(v_i)_{i\in A}$によって生成される。

すべての$j\in B$について$v_j\in U$であると仮定する。このとき$(v_j)_{j\in B}$は$U$に属する一次独立な$\lvert B\rvert$個のベクトルの族であり、$U$は$\lvert A\rvert$個のベクトルで生成されるから、§D3.8 補題 3.1を生成系$(v_i)_{i\in A}$と一次独立な族$(v_j)_{j\in B}$へ適用して$\lvert B\rvert\le\lvert A\rvert$を得る。これは$\lvert A\rvert<\lvert B\rvert$に反する。

ゆえに$j\in B$であって$v_j\notin U$を満たすものが存在する。$i\in A$に対しては$v_i\in U$であるから$j\notin A$、すなわち$j\in B\setminus A$である。$A\cup\{j\}\in\mathcal I$を示す。$\sum_{i\in A}c_iv_i+c_jv_j=0$とする。$c_j\ne0$とすると$v_j=-c_j^{-1}\sum_{i\in A}c_iv_i\in U$となって$v_j\notin U$に反する。ゆえに$c_j=0$であり、$\sum_{i\in A}c_iv_i=0$から$A\in\mathcal I$より$c_i=0$がすべての$i\in A$について成り立つ。したがって$A\cup\{j\}\in\mathcal I$である。▨