§E16.16マトロイドの回路と階数

最終更新

前の記事では、マトロイドを独立集合の族として定め、基底の族からも同じ対象が定まることを証明した。独立集合と基底は、いずれも独立な部分集合によってマトロイドの構造を記述する概念である。本記事では、包含に関して極小な従属集合と、各部分集合に含まれる独立集合の最大濃度によって、同じ構造を記述する。

極小な従属集合を回路といい、部分集合に含まれる独立集合の最大濃度を階数という。回路の族は消去公理条件 (C1)–条件 (C3)を満たし、階数関数は条件 (R1)–条件 (R3)を満たす。逆に、これらの条件だけを仮定した族または関数から、独立集合族を復元することができる。独立集合公理系、基底公理系、回路公理系、階数公理系のいずれによっても、同じマトロイドが定められる。本記事では復元の各方向を省略せずに証明する。

以下、M=(E,I)M=(E,\mathcal I)を§E16.15 定義 1.1の意味でのマトロイドとし、B\mathcal Bをその基底全体とする。

1 回路

定義 1.1. マトロイドM=(E,I)M=(E,\mathcal I)において、包含に関して極小な従属集合を回路 (circuit) という。すなわちC⊆EC\subseteq Eが回路であるとは、C∉IC\notin\mathcal Iであり、かつC′⊊CC'\subsetneq Cを満たす任意のC′C'についてC′∈IC'\in\mathcal Iが成り立つことをいう。回路の全体をC\mathcal Cと書く。

極小と最小は別の条件である。回路は包含に関して極小な従属集合であって、濃度が最小の従属集合ではない。実際、例 6.2のとおり、M(K4)M(K_4)では三角形の辺集合（濃度33）と長さ44の閉路の辺集合（濃度44）がともに回路である。

命題 1.2.A⊆EA\subseteq Eが従属集合ならば、C⊆AC\subseteq Aを満たす回路CCが存在する。

証明.D={D⊆A: D∉I}\mathcal D=\{D\subseteq A:\ D\notin\mathcal I\}と置く。A∈DA\in\mathcal DであるからD≠∅\mathcal D\ne\emptysetであり、EEが有限集合であるからD\mathcal Dも有限集合である。ゆえにD\mathcal Dの元の濃度の集合は空でない有限な非負整数の集合であり、最小値をとる元C∈DC\in\mathcal Dが存在する。

CCが回路であることを示す。CCは従属集合である。C′⊊CC'\subsetneq CかつC′∉IC'\notin\mathcal Iを満たすC′C'が存在したとすると、C′⊆AC'\subseteq AよりC′∈DC'\in\mathcal Dであり∣C′∣<∣C∣\lvert C'\rvert<\lvert C\rvertとなってCCの最小性に反する。ゆえにCCの真部分集合はすべて独立であり、CCは極小な従属集合、すなわち回路である。▨

命題 1.3.A⊆EA\subseteq Eに対し、A∈IA\in\mathcal Iであることと、C⊆AC\subseteq Aを満たす回路CCが存在しないことは同値である。すなわちI={A⊆E: ∀C∈C, C⊈A}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}が成り立つ。

証明.A∈IA\in\mathcal Iとし、C⊆AC\subseteq Aを満たす回路CCが存在したとする。回路は従属集合であるが、§E16.15 定義 1.1 条件 (I2)よりC⊆A∈IC\subseteq A\in\mathcal IからC∈IC\in\mathcal Iが従い、矛盾する。ゆえにAAに含まれる回路は存在しない。

逆にA∉IA\notin\mathcal Iとすると、命題 1.2よりC⊆AC\subseteq Aを満たす回路CCが存在する。対偶を取ると、AAに含まれる回路が存在しないならばA∈IA\in\mathcal Iである。▨

2 回路消去公理

定義 2.1. 有限集合EEとC⊆2E\mathcal C\subseteq 2^{E}について、C\mathcal Cが回路公理系 (circuit axiom system) を満たすとは、次の三条件を満たすことをいう。

  1. ∅∉C\emptyset\notin\mathcal C。
  2. C1,C2∈CC_1,C_2\in\mathcal CかつC1⊆C2C_1\subseteq C_2ならばC1=C2C_1=C_2。
  3. 相異なるC1,C2∈CC_1,C_2\in\mathcal Cとx∈C1∩C2x\in C_1\cap C_2に対し、(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}に含まれる回路、すなわちC3⊆(C1∪C2)∖{x}C_3\subseteq(C_1\cup C_2)\setminus\{x\}を満たすC3∈CC_3\in\mathcal Cが存在する。

条件 (C3)の集合は(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}であり、C1C_1とC2C_2の合併からxxを取り除いたものである。括弧を落としてC1∪(C2∖{x})C_1\cup(C_2\setminus\{x\})と読むと、その集合はC1C_1を含むので、C3=C1C_3=C_1が条件を満たす。そのため、そう読んだ主張は自明になる。xxはC1C_1からもC2C_2からも取り除かれる。

3 基本回路

次の補題は、回路公理系だけを仮定した設定で述べる。マトロイドに対する形は系として得られる。

補題 3.1. 有限集合EEとC⊆2E\mathcal C\subseteq 2^{E}が条件 (C1)、条件 (C2)、条件 (C3)を満たすとし、I={A⊆E: ∀C∈C, C⊈A}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}と置く。A∈IA\in\mathcal I、x∈E∖Ax\in E\setminus Aとし、A∪{x}∉IA\cup\{x\}\notin\mathcal Iとする。このときA∪{x}A\cup\{x\}に含まれるC\mathcal Cの元はただ一つであり、その元はxxを含む。

証明.A∪{x}∉IA\cup\{x\}\notin\mathcal Iであるから、I\mathcal Iの定義よりC⊆A∪{x}C\subseteq A\cup\{x\}を満たすC∈CC\in\mathcal Cが存在する。A∈IA\in\mathcal IよりC⊈AC\not\subseteq Aであるからx∈Cx\in Cである。したがってA∪{x}A\cup\{x\}に含まれるC\mathcal Cの元はすべてxxを含む。

一意性を示す。C1,C2⊆A∪{x}C_1,C_2\subseteq A\cup\{x\}をC\mathcal Cの相異なる元とすると、いずれもxxを含むのでx∈C1∩C2x\in C_1\cap C_2である。条件 (C3)よりC3⊆(C1∪C2)∖{x}C_3\subseteq(C_1\cup C_2)\setminus\{x\}を満たすC3∈CC_3\in\mathcal Cが存在する。C1∪C2⊆A∪{x}C_1\cup C_2\subseteq A\cup\{x\}であるから(C1∪C2)∖{x}⊆A(C_1\cup C_2)\setminus\{x\}\subseteq Aであり、C3⊆AC_3\subseteq Aとなる。これはA∈IA\in\mathcal Iに反する。ゆえにA∪{x}A\cup\{x\}に含まれるC\mathcal Cの元はただ一つである。▨

4 階数

定義 4.1. マトロイドM=(E,I)M=(E,\mathcal I)とA⊆EA\subseteq Eに対しr(A)=max⁡{∣I∣: I⊆A, I∈I}r(A)=\max\{\lvert I\rvert:\ I\subseteq A,\ I\in\mathcal I\}をAAの階数 (rank) という。§E16.15 定義 1.1 条件 (I1)より∅\emptysetはAAに含まれる独立集合であり、AAの部分集合は有限個であるから、この最大値は定まる。r(E)r(E)をMMの階数という。

命題 4.2.A⊆EA\subseteq Eとし、IA={I∈I: I⊆A}\mathcal I_A=\{I\in\mathcal I:\ I\subseteq A\}と置く。IA\mathcal I_Aの包含に関して極大な元はすべて濃度r(A)r(A)をもつ。またIA\mathcal I_Aの任意の元はIA\mathcal I_Aの極大な元に含まれる。

証明. 極大な元への延長.I∈IAI\in\mathcal I_Aとする。{J∈IA: I⊆J}\{J\in\mathcal I_A:\ I\subseteq J\}は空でない有限族であるから、濃度が最大の元JJを取ることができる。J⊊J′J\subsetneq J'かつJ′∈IAJ'\in\mathcal I_AならばI⊆J′I\subseteq J'となってJJの最大性に反するから、JJはIA\mathcal I_Aの極大な元である。

極大な元の等濃度性.I,JI,JをIA\mathcal I_Aの極大な元とし、∣I∣<∣J∣\lvert I\rvert<\lvert J\rvertと仮定する。I,J∈II,J\in\mathcal Iであるから§E16.15 定義 1.1 条件 (I3)よりx∈J∖Ix\in J\setminus Iが存在してI∪{x}∈II\cup\{x\}\in\mathcal Iとなる。x∈J⊆Ax\in J\subseteq AであるからI∪{x}⊆AI\cup\{x\}\subseteq Aであり、I∪{x}∈IAI\cup\{x\}\in\mathcal I_AとなってIIの極大性に反する。ゆえに∣I∣<∣J∣\lvert I\rvert<\lvert J\rvertは成り立たず、役割を入れ替えて∣I∣=∣J∣\lvert I\rvert=\lvert J\rvertを得る。

共通の濃度がr(A)r(A)であること.r(A)r(A)を与えるIA\mathcal I_Aの元I0I_0、すなわち∣I0∣=r(A)\lvert I_0\rvert=r(A)を満たすI0∈IAI_0\in\mathcal I_Aを取る。I0I_0はIA\mathcal I_Aの極大な元である。実際I0⊊JI_0\subsetneq JかつJ∈IAJ\in\mathcal I_Aならば∣J∣>r(A)\lvert J\rvert>r(A)となって階数の定義に反する。ゆえに極大な元の共通の濃度はr(A)r(A)である。▨

グラフ的マトロイドについては、階数を連結成分の個数によって書き下すことができる。§E16.15 補題 6.2は閉路を含まない辺集合についての辺数の勘定であり、閉路を含む一般の辺集合に対する階数の式ではないから、両者を結ぶ段を明示して証明する。

命題 4.3.G=(V,E)G=(V,E)を有限単純無向グラフとし、M(G)M(G)を§E16.15 定義 6.1のグラフ的マトロイドとする。F⊆EF\subseteq Eに対し、部分グラフ(V,F)(V,F)の連結成分の個数をc(F)c(F)と書くと、M(G)M(G)の階数関数rrはr(F)=∣V∣−c(F)r(F)=\lvert V\rvert-c(F)を満たす。

証明.(V,F)(V,F)の連結成分をH1,…,Hc(F)H_1,\dots,H_{c(F)}とし、HiH_iの頂点集合をViV_i、辺集合をFiF_iと書く。FFの各辺は両端点が同一の連結成分に属するから、F=F1⊔⋯⊔Fc(F)F=F_1\sqcup\dots\sqcup F_{c(F)}であり、V=V1⊔⋯⊔Vc(F)V=V_1\sqcup\dots\sqcup V_{c(F)}である。

  1. 極大な独立集合の構成. 各HiH_iは連結であるから、§D2.7 命題 3.9よりViV_iを頂点集合とするHiH_iの全域木が存在する。その辺集合をTi⊆FiT_i\subseteq F_iと書き、T=T1∪⋯∪Tc(F)T=T_1\cup\dots\cup T_{c(F)}と置く。

    TTがFFに含まれるM(G)M(G)の独立集合であることを示す。(V,T)(V,T)が閉路をもつとする。T⊆FT\subseteq Fであるから、閉路の頂点は(V,F)(V,F)において互いに到達可能であり、§D2.7 定義 2.3より同一の連結成分に属する。その頂点集合をViV_iとすると、閉路の各辺は両端点がViV_iに属するTTの辺である。Tj⊆FjT_j\subseteq F_jの辺は両端点がVjV_jに属し、相異なる添字のVjV_jは互いに素であるから、閉路の各辺はTiT_iに属する。(Vi,Ti)(V_i,T_i)はHiH_iの全域木であって§D2.7 定義 3.1の意味で木であるから閉路をもたず、矛盾する。ゆえに(V,T)(V,T)は閉路をもたずT∈IT\in\mathcal Iである。

    TTが{I∈I: I⊆F}\{I\in\mathcal I:\ I\subseteq F\}の包含に関して極大な元であることを示す。e∈F∖Te\in F\setminus Tを取り、e={u,v}e=\{u,v\}と書く。e∈Fie\in F_iを満たす添字iiを取ると、uuとvvはともにViV_iに属する。TiT_iはHiH_iの全域木の辺集合であるから、§D2.7 定理 3.6 (1)⇒\Rightarrow(4)によりuuとvvを結ぶ(Vi,Ti)(V_i,T_i)の道PPが存在する。e∉Tie\notin T_iであるからPPはeeを用いず、PPにeeを加えると閉路が得られる。ゆえにT∪{e}∉IT\cup\{e\}\notin\mathcal Iであり、TTは極大である。

  2. 極大性から階数へ.命題 4.2をA=FA=Fに対して適用すると、{I∈I: I⊆F}\{I\in\mathcal I:\ I\subseteq F\}の極大な元の濃度はすべてr(F)r(F)に等しい。(1)よりTTはその極大な元であるから∣T∣=r(F)\lvert T\rvert=r(F)である。

  3. 辺数の勘定.(V,T)(V,T)は閉路をもたないから、§E16.15 補題 6.2をTTへ適用することができる。(V,T)(V,T)の連結成分はHiH_iの全域木(Vi,Ti)(V_i,T_i)そのものであり、その個数はc(F)c(F)である。実際、TiT_iはViV_iを頂点集合とする木の辺集合であるから(Vi,Ti)(V_i,T_i)は連結であり、相異なる添字のViV_iの間にはTTの辺が存在しない。ゆえにr(F)=∣T∣=∣V∣−c(T)=∣V∣−c(F)r(F)=\lvert T\rvert=\lvert V\rvert-c(T)=\lvert V\rvert-c(F)である。

▨

定義 4.4. 有限集合EEと関数r:2E→Z≥0r:2^{E}\to\Z_{\ge0}について、rrが階数公理系 (rank axiom system) を満たすとは、次の三条件を満たすことをいう。

  1. 任意のA⊆EA\subseteq Eに対し0≤r(A)≤∣A∣0\le r(A)\le\lvert A\rvert。
  2. A⊆B⊆EA\subseteq B\subseteq Eならばr(A)≤r(B)r(A)\le r(B)。
  3. 任意のA,B⊆EA,B\subseteq Eに対しr(A∪B)+r(A∩B)≤r(A)+r(B)r(A\cup B)+r(A\cap B)\le r(A)+r(B)。

条件 (R2)を単調性、条件 (R3)を劣モジュラ性という。

補題 4.5.r:2E→Z≥0r:2^{E}\to\Z_{\ge0}が条件 (R1)、条件 (R2)、条件 (R3)を満たすならば、任意のA⊆EA\subseteq Eとx∈Ex\in Eに対しr(A)≤r(A∪{x})≤r(A)+1r(A)\le r(A\cup\{x\})\le r(A)+1が成り立つ。さらに、A⊆EA\subseteq EとAAと交わらない有限集合T⊆ET\subseteq Eに対しr(A∪T)≤r(A)+∣T∣r(A\cup T)\le r(A)+\lvert T\rvertが成り立つ。

証明. 左側の不等式はA⊆A∪{x}A\subseteq A\cup\{x\}と条件 (R2)による。

右側の不等式を示す。x∈Ax\in AならばA∪{x}=AA\cup\{x\}=Aであるから明らかである。x∉Ax\notin Aとする。条件 (R3)をAAと{x}\{x\}へ適用するとA∪{x}A\cup\{x\}とA∩{x}=∅A\cap\{x\}=\emptysetについてr(A∪{x})+r(∅)≤r(A)+r({x})r(A\cup\{x\})+r(\emptyset)\le r(A)+r(\{x\})となる。条件 (R1)よりr(∅)≥0r(\emptyset)\ge0かつr({x})≤∣{x}∣=1r(\{x\})\le\lvert\{x\}\rvert=1であるからr(A∪{x})≤r(A)+1r(A\cup\{x\})\le r(A)+1である。

最後の主張を示す。t=∣T∣t=\lvert T\rvertと置き、T={x1,…,xt}T=\{x_1,\dots,x_t\}と書き、A0=AA_0=A、Aj=Aj−1∪{xj}A_j=A_{j-1}\cup\{x_j\}（1≤j≤t1\le j\le t）と置く。非負整数jjについての述語P(j)P(j)を、0≤j≤t0\le j\le tのときは「r(Aj)≤r(A)+jr(A_j)\le r(A)+jが成り立つ」、j>tj>tのときは恒に真であると定める。

P(0)P(0)はA0=AA_0=Aより等号として成り立つ。0≤j<t0\le j<tを満たすjjについてP(j)P(j)を仮定すると、上で示した不等式よりr(Aj+1)≤r(Aj)+1≤r(A)+j+1r(A_{j+1})\le r(A_j)+1\le r(A)+j+1であるからP(j+1)P(j+1)が成り立つ。j≥tj\ge tのときはP(j+1)P(j+1)が定義により真である。ゆえに§D2.1 命題 1.2の単純帰納法によりすべての非負整数jjについてP(j)P(j)が成り立つ。とくにj=tj=tとしてr(A∪T)=r(At)≤r(A)+t=r(A)+∣T∣r(A\cup T)=r(A_t)\le r(A)+t=r(A)+\lvert T\rvertを得る。▨

5 各公理系からの独立集合族の復元

5.1 証明方針

回路の族からの復元と階数関数からの復元を、それぞれ独立に示す。

回路からの復元では、I={A: ∀C∈C, C⊈A}\mathcal I=\{A:\ \forall C\in\mathcal C,\ C\not\subseteq A\}と定めたときに§E16.15 定義 1.1 条件 (I1)と§E16.15 定義 1.1 条件 (I2)が定義から直ちに従う一方、増大公理§E16.15 定義 1.1 条件 (I3)だけが手間を要する。そこで§E16.15 定義 1.1 条件 (I3)を、各X⊆EX\subseteq Eについて「XXに含まれるI\mathcal Iの極大な元がすべて同じ濃度をもつ」という形へ言い換える。言い換えたうえで、濃度の異なる二つの極大元I,JI,Jの対のうち∣I∖J∣\lvert I\setminus J\rvertが最小のものを取り、e∈I∖Je\in I\setminus Jに対する基本回路補題 3.1を用いてJJの元をeeで置き換えた集合を作る。置き換えによって∣I∖J∣\lvert I\setminus J\rvertが真に減るので最小性に反する。回路の一意性が、置き換えた集合がふたたびI\mathcal Iに属することを保証する一手である。

階数関数からの復元では、I={A: r(A)=∣A∣}\mathcal I=\{A:\ r(A)=\lvert A\rvert\}と定める。§E16.15 定義 1.1 条件 (I2)は劣モジュラ性から導いた一元追加の評価補題 4.5を繰り返して示す。§E16.15 定義 1.1 条件 (I3)では、増やす候補がすべて階数を上げないと仮定したうえで、劣モジュラ性を二つの集合A∪{x1,…,xj}A\cup\{x_1,\dots,x_j\}とA∪{xj+1}A\cup\{x_{j+1}\}へ適用して、候補を一つずつ付け加えても階数が変わらないことを帰納的に示す。最後にr(A∪B)≥r(B)=∣B∣>∣A∣=r(A∪B)r(A\cup B)\ge r(B)=\lvert B\rvert>\lvert A\rvert=r(A\cup B)という矛盾を作る。

補題 5.1. 有限集合EEとI⊆2E\mathcal I\subseteq 2^{E}が§E16.15 定義 1.1 条件 (I1)と§E16.15 定義 1.1 条件 (I2)を満たすとする。このとき次の二条件は同値である。

  1. I\mathcal Iは§E16.15 定義 1.1 条件 (I3)を満たす。
  2. 任意のX⊆EX\subseteq Eについて、{I∈I: I⊆X}\{I\in\mathcal I:\ I\subseteq X\}の包含に関して極大な元はすべて同じ濃度をもつ。

証明.(1)⇒\Rightarrow(2)を示す。命題 4.2の証明のうち「極大な元の等濃度性」の段は§E16.15 定義 1.1 条件 (I1)、§E16.15 定義 1.1 条件 (I2)、§E16.15 定義 1.1 条件 (I3)だけを用いているから、そのまま適用することができる。

(2)⇒\Rightarrow(1)を示す。A,B∈IA,B\in\mathcal Iかつ∣A∣<∣B∣\lvert A\rvert<\lvert B\rvertとし、すべてのx∈B∖Ax\in B\setminus AについてA∪{x}∉IA\cup\{x\}\notin\mathcal Iと仮定する。X=A∪BX=A\cup Bと置き、IX={I∈I: I⊆X}\mathcal I_X=\{I\in\mathcal I:\ I\subseteq X\}と置く。

AAはIX\mathcal I_Xの極大な元である。実際、A⊊JA\subsetneq JかつJ∈IXJ\in\mathcal I_Xとすると、x∈J∖A⊆X∖A=B∖Ax\in J\setminus A\subseteq X\setminus A=B\setminus Aを取ることができ、§E16.15 定義 1.1 条件 (I2)よりA∪{x}⊆JA\cup\{x\}\subseteq JからA∪{x}∈IA\cup\{x\}\in\mathcal Iが従って仮定に反する。

一方B∈IXB\in\mathcal I_Xであるから、{J∈IX: B⊆J}\{J\in\mathcal I_X:\ B\subseteq J\}の中で濃度が最大の元B′B'を取ると、B′B'はIX\mathcal I_Xの極大な元であり∣B′∣≥∣B∣>∣A∣\lvert B'\rvert\ge\lvert B\rvert>\lvert A\rvertである。これは(2)に反する。ゆえに仮定は誤りであり、§E16.15 定義 1.1 条件 (I3)が成り立つ。▨

定理 5.2. 有限集合EEについて次が成り立つ。

  1. C⊆2E\mathcal C\subseteq 2^{E}がEE上のあるマトロイドの回路全体であるための必要十分条件は、C\mathcal Cが条件 (C1)、条件 (C2)、条件 (C3)を満たすことである。C\mathcal Cが条件 (C1)、条件 (C2)、条件 (C3)を満たすとし、I={A⊆E: ∀C∈C, C⊈A}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}と置く。このとき(E,I)(E,\mathcal I)はマトロイドであり、その回路全体はC\mathcal Cに一致する。
  2. r:2E→Z≥0r:2^{E}\to\Z_{\ge0}がEE上のあるマトロイドの階数関数であるための必要十分条件は、rrが条件 (R1)、条件 (R2)、条件 (R3)を満たすことである。rrが条件 (R1)、条件 (R2)、条件 (R3)を満たすとし、I={A⊆E: r(A)=∣A∣}\mathcal I=\{A\subseteq E:\ r(A)=\lvert A\rvert\}と置く。このとき(E,I)(E,\mathcal I)はマトロイドであり、その階数関数はrrに一致する。

逆に、マトロイドM=(E,I)M=(E,\mathcal I)の回路全体C\mathcal Cと階数関数rrについてI={A⊆E: ∀C∈C, C⊈A},I={A⊆E: r(A)=∣A∣}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\},\qquad \mathcal I=\{A\subseteq E:\ r(A)=\lvert A\rvert\}が成り立つ。したがって独立集合公理系、基底公理系、回路公理系、階数公理系によりいずれも同じマトロイドが定められる。

さらにこのrrについて、任意のA⊆EA\subseteq Eとx∈Ex\in Eに対し

r(A)≤r(A∪{x})≤r(A)+1r(A)\le r(A\cup\{x\})\le r(A)+1

が成り立つ。この一元追加についての性質は、条件 (R1)と条件 (R2)と条件 (R3)だけから従う。

証明. 主張 (1)の§E16.15 定義 1.1 条件 (I1).条件 (C1)より∅∉C\emptyset\notin\mathcal Cである。C⊆∅C\subseteq\emptysetを満たす集合は∅\emptysetだけであるから、∅\emptysetに含まれるC\mathcal Cの元は存在せず∅∈I\emptyset\in\mathcal Iである。

主張 (1)の§E16.15 定義 1.1 条件 (I2).A∈IA\in\mathcal IかつA′⊆AA'\subseteq Aとする。C⊆A′C\subseteq A'を満たすC∈CC\in\mathcal CがあればC⊆AC\subseteq AとなってA∈IA\in\mathcal Iに反する。ゆえにA′∈IA'\in\mathcal Iである。

主張 (1)の§E16.15 定義 1.1 条件 (I3).補題 5.1により、任意のX⊆EX\subseteq EについてIX={I∈I: I⊆X}\mathcal I_X=\{I\in\mathcal I:\ I\subseteq X\}の極大な元がすべて同じ濃度をもつことを示せばよい。

X⊆EX\subseteq Eを固定する。∣I∣<∣J∣\lvert I\rvert<\lvert J\rvertを満たすIX\mathcal I_Xの極大な元の対(I,J)(I,J)が存在したとする。IX\mathcal I_Xは有限族であるから、そのような対のうち∣I∖J∣\lvert I\setminus J\rvertが最小のものを一つ取り、あらためて(I,J)(I,J)と書く。

I∖J=∅I\setminus J=\emptysetとするとI⊆JI\subseteq Jであり、J∈IXJ\in\mathcal I_XとIIの極大性からI=JI=Jとなって∣I∣<∣J∣\lvert I\rvert<\lvert J\rvertに反する。ゆえにe∈I∖Je\in I\setminus Jを取ることができる。

e∈I⊆Xe\in I\subseteq Xかつe∉Je\notin Jであり、JJはIX\mathcal I_Xの極大な元であるからJ∪{e}∉IJ\cup\{e\}\notin\mathcal Iである。補題 3.1より、J∪{e}J\cup\{e\}に含まれるC\mathcal Cの元はただ一つであり、それをCCと書くとe∈Ce\in Cである。

I∈II\in\mathcal IであるからC⊈IC\not\subseteq Iであり、f∈C∖If\in C\setminus Iが存在する。e∈Ie\in Iであるからf≠ef\ne eであり、C⊆J∪{e}C\subseteq J\cup\{e\}よりf∈J∖If\in J\setminus Iである。

J′=(J∪{e})∖{f}J'=(J\cup\{e\})\setminus\{f\}と置く。J′∈IJ'\in\mathcal Iを示す。D⊆J′D\subseteq J'を満たすD∈CD\in\mathcal Cが存在したとする。D⊆J∪{e}D\subseteq J\cup\{e\}であり、J∪{e}J\cup\{e\}に含まれるC\mathcal Cの元はCCだけであるからD=CD=Cである。しかしf∈Cf\in Cかつf∉J′f\notin J'であるからC⊈J′C\not\subseteq J'となって矛盾する。ゆえにJ′∈IJ'\in\mathcal Iである。

e∈Xe\in XかつJ⊆XJ\subseteq XよりJ′⊆XJ'\subseteq XであるからJ′∈IXJ'\in\mathcal I_Xであり、f∈Jf\in Jかつe∉Je\notin Jより∣J′∣=∣J∣\lvert J'\rvert=\lvert J\rvertである。J′J'を含むIX\mathcal I_Xの極大な元J′′J''を取ると（命題 4.2の延長の議論は§E16.15 定義 1.1 条件 (I1)と§E16.15 定義 1.1 条件 (I2)と有限性だけを用いるので、ここで用いることができる）、∣J′′∣≥∣J′∣=∣J∣>∣I∣\lvert J''\rvert\ge\lvert J'\rvert=\lvert J\rvert>\lvert I\rvertである。

f∉If\notin IであるからI∖J′=I∖((J∪{e})∖{f})=I∖(J∪{e})=(I∖J)∖{e}I\setminus J'=I\setminus\bigl((J\cup\{e\})\setminus\{f\}\bigr)=I\setminus(J\cup\{e\})=(I\setminus J)\setminus\{e\}であり、e∈I∖Je\in I\setminus Jより∣I∖J′∣=∣I∖J∣−1\lvert I\setminus J'\rvert=\lvert I\setminus J\rvert-1である。J′⊆J′′J'\subseteq J''よりI∖J′′⊆I∖J′I\setminus J''\subseteq I\setminus J'であるから∣I∖J′′∣≤∣I∖J∣−1\lvert I\setminus J''\rvert\le\lvert I\setminus J\rvert-1である。したがって対(I,J′′)(I,J'')は∣I∣<∣J′′∣\lvert I\rvert<\lvert J''\rvertを満たし、∣I∖J′′∣<∣I∖J∣\lvert I\setminus J''\rvert<\lvert I\setminus J\rvertとなって最小性に反する。

ゆえにIX\mathcal I_Xの極大な元はすべて同じ濃度をもち、§E16.15 定義 1.1 条件 (I3)が成り立つ。

主張 (1)の回路の一致.(E,I)(E,\mathcal I)の回路全体をC′\mathcal C'と書く。C∈CC\in\mathcal CとするとC⊆CC\subseteq CよりC∉IC\notin\mathcal Iであり、CCは従属集合である。D⊊CD\subsetneq CかつD∉ID\notin\mathcal Iとすると、C′⊆DC'\subseteq Dを満たすC′∈CC'\in\mathcal Cが存在し、C′⊆D⊊CC'\subseteq D\subsetneq Cとなって条件 (C2)よりC′=CC'=Cが従い、C⊆D⊊CC\subseteq D\subsetneq Cという矛盾を得る。ゆえにCCの真部分集合はすべて独立でありC∈C′C\in\mathcal C'である。

逆にC′∈C′C'\in\mathcal C'とするとC′∉IC'\notin\mathcal Iであるから、C⊆C′C\subseteq C'を満たすC∈CC\in\mathcal Cが存在する。いま示したとおりCCは従属集合であり、C′C'が極小な従属集合であることからC=C′C=C'である。ゆえにC=C′\mathcal C=\mathcal C'である。

主張 (1)の必要性.C\mathcal CをマトロイドM=(E,I)M=(E,\mathcal I)の回路全体とする。条件 (C1)を示す。§E16.15 定義 1.1 条件 (I1)より∅∈I\emptyset\in\mathcal Iであるから∅\emptysetは従属集合ではなく、回路ではない。

条件 (C2)を示す。C1,C2∈CC_1,C_2\in\mathcal CかつC1⊆C2C_1\subseteq C_2とする。C1⊊C2C_1\subsetneq C_2と仮定すると、C2C_2が極小な従属集合であることからC1∈IC_1\in\mathcal Iとなるが、C1C_1は回路であり従属集合であるから矛盾する。ゆえにC1=C2C_1=C_2である。

条件 (C3)を示す。 相異なるC1,C2∈CC_1,C_2\in\mathcal Cとx∈C1∩C2x\in C_1\cap C_2を取り、X=C1∪C2X=C_1\cup C_2と置く。命題 1.3により、X∖{x}X\setminus\{x\}に含まれる回路が存在しないこととX∖{x}∈IX\setminus\{x\}\in\mathcal Iは同値であるから、X∖{x}∈IX\setminus\{x\}\in\mathcal Iと仮定して矛盾を導けばよい。

まずC2∖C1≠∅C_2\setminus C_1\ne\emptysetである。実際C2⊆C1C_2\subseteq C_1とすると条件 (C2)よりC1=C2C_1=C_2となって仮定に反する。y∈C2∖C1y\in C_2\setminus C_1を一つ取る。C2C_2は極小な従属集合であるからC2∖{y}∈IC_2\setminus\{y\}\in\mathcal Iであり、C2∖{y}⊆XC_2\setminus\{y\}\subseteq Xである。

{I∈I: C2∖{y}⊆I⊆X}\{I\in\mathcal I:\ C_2\setminus\{y\}\subseteq I\subseteq X\}はC2∖{y}C_2\setminus\{y\}を含む空でない有限族であるから、包含に関して極大な元IIを取ることができる。IIは{J∈I: J⊆X}\{J\in\mathcal I:\ J\subseteq X\}においても極大である。実際、I⊊J⊆XI\subsetneq J\subseteq XかつJ∈IJ\in\mathcal IならばC2∖{y}⊆I⊆JC_2\setminus\{y\}\subseteq I\subseteq JであるからJJは上の族に属し、IIの極大性に反する。

y∉Iy\notin Iである。実際y∈Iy\in IとするとC2=(C2∖{y})∪{y}⊆IC_2=(C_2\setminus\{y\})\cup\{y\}\subseteq Iとなり、§E16.15 定義 1.1 条件 (I2)よりC2∈IC_2\in\mathcal Iが従ってC2C_2が従属であることに反する。

C1⊈IC_1\not\subseteq Iである。実際C1⊆IC_1\subseteq Iとすると同様にC1∈IC_1\in\mathcal Iとなって矛盾する。ゆえにz∈C1∖Iz\in C_1\setminus Iが存在する。y∈C2∖C1y\in C_2\setminus C_1よりy∉C1y\notin C_1であるからz≠yz\ne yである。y,z∈Xy,z\in Xかつy,z∉Iy,z\notin Iであるから∣I∣≤∣X∣−2\lvert I\rvert\le\lvert X\rvert-2が成り立つ。

一方、仮定よりX∖{x}∈IX\setminus\{x\}\in\mathcal Iであり、X∖{x}⊆XX\setminus\{x\}\subseteq Xかつ∣X∖{x}∣=∣X∣−1>∣I∣\lvert X\setminus\{x\}\rvert=\lvert X\rvert-1>\lvert I\rvertである。IIとX∖{x}X\setminus\{x\}はともにXXに含まれる独立集合であるから、§E16.15 定義 1.1 条件 (I3)を対(I, X∖{x})(I,\ X\setminus\{x\})へ適用すると、w∈(X∖{x})∖Iw\in(X\setminus\{x\})\setminus Iが存在してI∪{w}∈II\cup\{w\}\in\mathcal Iとなる。w∈Xw\in XであるからI∪{w}⊆XI\cup\{w\}\subseteq Xであり、IIが{J∈I: J⊆X}\{J\in\mathcal I:\ J\subseteq X\}の極大元であることに反する。

ゆえにX∖{x}∉IX\setminus\{x\}\notin\mathcal Iであり、命題 1.2より(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}に含まれる回路が存在する。

主張 (2)の準備.rrは条件 (R1)、条件 (R2)、条件 (R3)を満たすから補題 4.5を用いることができる。

主張 (2)の§E16.15 定義 1.1 条件 (I1).条件 (R1)より0≤r(∅)≤∣∅∣=00\le r(\emptyset)\le\lvert\emptyset\rvert=0であるからr(∅)=0=∣∅∣r(\emptyset)=0=\lvert\emptyset\rvertであり∅∈I\emptyset\in\mathcal Iである。

主張 (2)の§E16.15 定義 1.1 条件 (I2).A∈IA\in\mathcal IかつB⊆AB\subseteq Aとする。補題 4.5をBBとT=A∖BT=A\setminus Bへ適用すると∣A∣=r(A)=r(B∪T)≤r(B)+∣A∣−∣B∣\lvert A\rvert=r(A)=r(B\cup T)\le r(B)+\lvert A\rvert-\lvert B\rvertであり、r(B)≥∣B∣r(B)\ge\lvert B\rvertを得る。条件 (R1)よりr(B)≤∣B∣r(B)\le\lvert B\rvertであるからr(B)=∣B∣r(B)=\lvert B\rvert、すなわちB∈IB\in\mathcal Iである。

主張 (2)の§E16.15 定義 1.1 条件 (I3).A,B∈IA,B\in\mathcal Iかつ∣A∣<∣B∣\lvert A\rvert<\lvert B\rvertとし、すべてのx∈B∖Ax\in B\setminus AについてA∪{x}∉IA\cup\{x\}\notin\mathcal Iと仮定する。x∈B∖Ax\in B\setminus Aに対しr(A∪{x})≤∣A∣+1r(A\cup\{x\})\le\lvert A\rvert+1が条件 (R1)から従い、r(A∪{x})=∣A∪{x}∣=∣A∣+1r(A\cup\{x\})=\lvert A\cup\{x\}\rvert=\lvert A\rvert+1は仮定により成り立たないからr(A∪{x})≤∣A∣=r(A)r(A\cup\{x\})\le\lvert A\rvert=r(A)である。条件 (R2)よりr(A∪{x})≥r(A)r(A\cup\{x\})\ge r(A)であるからr(A∪{x})=r(A)(x∈B∖A)r(A\cup\{x\})=r(A)\qquad(x\in B\setminus A)が成り立つ。

m=∣B∖A∣m=\lvert B\setminus A\rvertと置き、B∖A={x1,…,xm}B\setminus A=\{x_1,\dots,x_m\}と書き、A0=AA_0=A、Aj=Aj−1∪{xj}A_j=A_{j-1}\cup\{x_j\}（1≤j≤m1\le j\le m）と置く。非負整数jjについての述語P(j)P(j)を、0≤j≤m0\le j\le mのときは「r(Aj)=r(A)r(A_j)=r(A)が成り立つ」、j>mj>mのときは恒に真であると定める。

P(0)P(0)はA0=AA_0=Aより成り立つ。0≤j<m0\le j<mを満たすjjについてP(j)P(j)を仮定する。xj+1∉Ajx_{j+1}\notin A_jであるからAj∩(A∪{xj+1})=AA_j\cap(A\cup\{x_{j+1}\})=AかつAj∪(A∪{xj+1})=Aj+1A_j\cup(A\cup\{x_{j+1}\})=A_{j+1}であり、条件 (R3)をAjA_jとA∪{xj+1}A\cup\{x_{j+1}\}へ適用してr(Aj+1)+r(A)≤r(Aj)+r(A∪{xj+1})=r(A)+r(A)r(A_{j+1})+r(A)\le r(A_j)+r(A\cup\{x_{j+1}\})=r(A)+r(A)すなわちr(Aj+1)≤r(A)r(A_{j+1})\le r(A)を得る。条件 (R2)よりr(Aj+1)≥r(A)r(A_{j+1})\ge r(A)であるからr(Aj+1)=r(A)r(A_{j+1})=r(A)であり、P(j+1)P(j+1)が成り立つ。j≥mj\ge mのときはP(j+1)P(j+1)が定義により真である。ゆえに§D2.1 命題 1.2の単純帰納法によりすべての非負整数jjについてP(j)P(j)が成り立つ。

とくにj=mj=mとしてr(A∪B)=r(Am)=r(A)=∣A∣r(A\cup B)=r(A_m)=r(A)=\lvert A\rvertを得る。一方B⊆A∪BB\subseteq A\cup Bと条件 (R2)よりr(A∪B)≥r(B)=∣B∣>∣A∣r(A\cup B)\ge r(B)=\lvert B\rvert>\lvert A\rvertであり、矛盾する。ゆえに§E16.15 定義 1.1 条件 (I3)が成り立つ。

主張 (2)の階数関数の一致.(E,I)(E,\mathcal I)の階数関数をrIr_{\mathcal I}と書く。A⊆EA\subseteq Eとする。I⊆AI\subseteq AかつI∈II\in\mathcal Iならば条件 (R2)より∣I∣=r(I)≤r(A)\lvert I\rvert=r(I)\le r(A)であるからrI(A)≤r(A)r_{\mathcal I}(A)\le r(A)である。

逆向きを示す。命題 4.2より{I∈I: I⊆A}\{I\in\mathcal I:\ I\subseteq A\}の極大な元IIを取ることができ、∣I∣=rI(A)\lvert I\rvert=r_{\mathcal I}(A)である。x∈A∖Ix\in A\setminus Iに対しI∪{x}∉II\cup\{x\}\notin\mathcal Iであるから、上の§E16.15 定義 1.1 条件 (I3)の証明と同じ計算によりr(I∪{x})=r(I)r(I\cup\{x\})=r(I)である。

そこでA∖IA\setminus Iの元を一つずつ加える帰納法を、上の議論でAAが果たした役割をIIに、B∖AB\setminus Aが果たした役割をA∖IA\setminus Iに取り替えて実行する。p=∣A∖I∣p=\lvert A\setminus I\rvertと置き、A∖I={x1,…,xp}A\setminus I=\{x_1,\dots,x_p\}と書き、I0=II_0=I、Ij=Ij−1∪{xj}I_j=I_{j-1}\cup\{x_j\}（1≤j≤p1\le j\le p）と置く。0≤j<p0\le j<pのときxj+1∉Ijx_{j+1}\notin I_jであるからIj∩(I∪{xj+1})=II_j\cap(I\cup\{x_{j+1}\})=IかつIj∪(I∪{xj+1})=Ij+1I_j\cup(I\cup\{x_{j+1}\})=I_{j+1}であり、条件 (R3)をIjI_jとI∪{xj+1}I\cup\{x_{j+1}\}へ適用してr(Ij+1)+r(I)≤r(Ij)+r(I∪{xj+1})r(I_{j+1})+r(I)\le r(I_j)+r(I\cup\{x_{j+1}\})を得る。r(Ij)=r(I)r(I_j)=r(I)とr(I∪{xj+1})=r(I)r(I\cup\{x_{j+1}\})=r(I)からr(Ij+1)≤r(I)r(I_{j+1})\le r(I)が従い、条件 (R2)と合わせてr(Ij+1)=r(I)r(I_{j+1})=r(I)である。上と同じ形の帰納法（§D2.1 命題 1.2）により0≤j≤p0\le j\le pを満たすすべてのjjについてr(Ij)=r(I)r(I_j)=r(I)が成り立つ。j=pj=pとしてr(A)=r(I∪(A∖I))=r(Ip)=r(I)=∣I∣=rI(A)r(A)=r\bigl(I\cup(A\setminus I)\bigr)=r(I_p)=r(I)=\lvert I\rvert=r_{\mathcal I}(A)を得る。ゆえにr=rIr=r_{\mathcal I}である。

主張 (2)の必要性.rrをマトロイドM=(E,I)M=(E,\mathcal I)の階数関数とする。条件 (R1)を示す。∅⊆A\emptyset\subseteq Aかつ∅∈I\emptyset\in\mathcal Iであるからr(A)≥0r(A)\ge0である。AAに含まれる独立集合IIはI⊆AI\subseteq Aを満たすから∣I∣≤∣A∣\lvert I\rvert\le\lvert A\rvertであり、r(A)≤∣A∣r(A)\le\lvert A\rvertである。

条件 (R2)を示す。A⊆BA\subseteq Bとする。AAに含まれる独立集合はBBに含まれる独立集合でもあるから、最大値をとる範囲が広がりr(A)≤r(B)r(A)\le r(B)である。

条件 (R3)を示す。A,B⊆EA,B\subseteq Eとする。命題 4.2より、A∩BA\cap Bに含まれる独立集合のうち極大なものIIを取ることができ、∣I∣=r(A∩B)\lvert I\rvert=r(A\cap B)である。I⊆A∪BI\subseteq A\cup BかつI∈II\in\mathcal Iであるから、同じ命題によりI⊆JI\subseteq Jを満たす{J′∈I: J′⊆A∪B}\{J'\in\mathcal I:\ J'\subseteq A\cup B\}の極大な元JJが存在し、∣J∣=r(A∪B)\lvert J\rvert=r(A\cup B)である。

J∩(A∩B)=IJ\cap(A\cap B)=Iを示す。I⊆JI\subseteq JかつI⊆A∩BI\subseteq A\cap BよりI⊆J∩(A∩B)I\subseteq J\cap(A\cap B)である。逆にJ∩(A∩B)J\cap(A\cap B)はA∩BA\cap Bに含まれる独立集合でありIIを含むから、IIがA∩BA\cap Bに含まれる独立集合の中で極大であることよりJ∩(A∩B)=IJ\cap(A\cap B)=Iである。

J∩AJ\cap AはAAに含まれる独立集合であるから∣J∩A∣≤r(A)\lvert J\cap A\rvert\le r(A)であり、同様に∣J∩B∣≤r(B)\lvert J\cap B\rvert\le r(B)である。J⊆A∪BJ\subseteq A\cup Bであるから包除原理（§D2.3 定理 1.2）により∣J∣=∣J∩(A∪B)∣=∣J∩A∣+∣J∩B∣−∣J∩A∩B∣≤r(A)+r(B)−r(A∩B)\lvert J\rvert=\lvert J\cap(A\cup B)\rvert=\lvert J\cap A\rvert+\lvert J\cap B\rvert-\lvert J\cap A\cap B\rvert\le r(A)+r(B)-r(A\cap B)となる。左辺はr(A∪B)r(A\cup B)であるから条件 (R3)を得る。

一元追加についての性質. いま示した条件 (R1)、条件 (R2)、条件 (R3)へ補題 4.5を適用すればよい。

逆向きの二つの等式. 第一の等式は命題 1.3である。第二の等式を示す。A∈IA\in\mathcal IならばAA自身がAAに含まれる独立集合であるからr(A)≥∣A∣r(A)\ge\lvert A\rvertであり、条件 (R1)と合わせてr(A)=∣A∣r(A)=\lvert A\rvertである。逆にr(A)=∣A∣r(A)=\lvert A\rvertならば、I⊆AI\subseteq A、I∈II\in\mathcal I、∣I∣=∣A∣\lvert I\rvert=\lvert A\rvertを満たすIIが存在し、有限集合であるからI=AI=AとなってA∈IA\in\mathcal Iである。▨

系 5.3. マトロイドM=(E,I)M=(E,\mathcal I)、A∈IA\in\mathcal I、x∈E∖Ax\in E\setminus Aとし、A∪{x}∉IA\cup\{x\}\notin\mathcal Iとする。このときA∪{x}A\cup\{x\}に含まれる回路はただ一つであり、その回路はxxを含む。この回路をAAとxxの基本回路 (fundamental circuit) という。

証明.定理 5.2 (1)よりMMの回路全体C\mathcal Cは条件 (C1)、条件 (C2)、条件 (C3)を満たす。また命題 1.3よりI={A⊆E: ∀C∈C, C⊈A}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}が成り立つ。ゆえに補題 3.1を適用することができ、主張を得る。▨

6 具体例

例 6.1.Uk,nU_{k,n}の台集合をEEとする。A⊆EA\subseteq Eが従属であることは∣A∣≥k+1\lvert A\rvert\ge k+1と同値であるから、極小な従属集合は(k+1)(k+1)元部分集合であり、k<nk<nのとき回路は(k+1)(k+1)元部分集合の全体、k=nk=nのとき回路は存在しない。階数はr(A)=min⁡{∣A∣, k}r(A)=\min\{\lvert A\rvert,\ k\}である。実際、AAに含まれる独立集合は濃度kk以下の部分集合であり、その最大濃度は∣A∣\lvert A\rvertとkkの小さい方である。

U2,4U_{2,4}について劣モジュラ性を検算する。A={1,2}A=\{1,2\}、B={2,3}B=\{2,3\}とするとA∪B={1,2,3}A\cup B=\{1,2,3\}、A∩B={2}A\cap B=\{2\}でありr(A∪B)+r(A∩B)=2+1=3,r(A)+r(B)=2+2=4r(A\cup B)+r(A\cap B)=2+1=3,\qquad r(A)+r(B)=2+2=4であるから3≤43\le4が成り立つ。A={1,2}A=\{1,2\}、B={3,4}B=\{3,4\}とするとA∪B=EA\cup B=E、A∩B=∅A\cap B=\emptysetであり2+0=2≤2+2=42+0=2\le2+2=4である。

U2,4U_{2,4}について条件 (C3)を検算する。C1={1,2,3}C_1=\{1,2,3\}、C2={1,2,4}C_2=\{1,2,4\}、x=1x=1とすると(C1∪C2)∖{1}={2,3,4}(C_1\cup C_2)\setminus\{1\}=\{2,3,4\}であり、これは三元集合であるから回路そのものである。x=3x=3はC1∩C2={1,2}C_1\cap C_2=\{1,2\}に属さないので条件 (C3)の対象にならない。

例 6.2.G=(V,E)G=(V,E)を有限単純無向グラフとし、M(G)M(G)を§E16.15 定義 6.1のグラフ的マトロイドとする。F⊆EF\subseteq Eが従属であることは(V,F)(V,F)が閉路をもつことであるから、極小な従属集合は閉路の辺集合にほかならない。ゆえにM(G)M(G)の回路はGGの閉路の辺集合の全体である。階数は命題 4.3により得られる。

K4K_4で条件 (C3)を検算する。頂点を1,2,3,41,2,3,4とし、辺をa={1,2}a=\{1,2\}、b={1,3}b=\{1,3\}、c={1,4}c=\{1,4\}、d={2,3}d=\{2,3\}、e={2,4}e=\{2,4\}、f={3,4}f=\{3,4\}と書く。C1={a,b,d}C_1=\{a,b,d\}は三角形1,2,31,2,3の辺集合、C2={a,c,e}C_2=\{a,c,e\}は三角形1,2,41,2,4の辺集合であり、C1∩C2={a}C_1\cap C_2=\{a\}である。x=ax=aとすると(C1∪C2)∖{a}={b,c,d,e}(C_1\cup C_2)\setminus\{a\}=\{b,c,d,e\}であり、これは辺{1,3}\{1,3\}、{1,4}\{1,4\}、{2,3}\{2,3\}、{2,4}\{2,4\}からなる。頂点を1,3,2,4,11,3,2,4,1の順にたどると{1,3},{3,2},{2,4},{4,1}\{1,3\},\{3,2\},\{2,4\},\{4,1\}という長さ44の閉路が得られるから、{b,c,d,e}\{b,c,d,e\}自身が回路である。同じM(K4)M(K_4)の中に、濃度33の回路{a,b,d}\{a,b,d\}と濃度44の回路{b,c,d,e}\{b,c,d,e\}がともに存在する。

C1∪C2={a,b,c,d,e}C_1\cup C_2=\{a,b,c,d,e\}の階数は、(V,C1∪C2)(V,C_1\cup C_2)が連結であるから命題 4.3より4−1=34-1=3であり、∣C1∪C2∣=5\lvert C_1\cup C_2\rvert=5であるから確かに従属である。

7 演習

問題 7.1.

  1. マトロイドM=(E,I)M=(E,\mathcal I)の相異なる回路C1,C2C_1,C_2とx∈C1∩C2x\in C_1\cap C_2、y∈C1∖C2y\in C_1\setminus C_2に対し、y∈C3⊆(C1∪C2)∖{x}y\in C_3\subseteq(C_1\cup C_2)\setminus\{x\}を満たす回路C3C_3が存在することを示せ。
  2. マトロイドM=(E,I)M=(E,\mathcal I)の階数関数をrrとする。回路CCについてr(C)=∣C∣−1r(C)=\lvert C\rvert-1であることを示し、相異なる回路C1,C2C_1,C_2について条件 (R3)を用いてr(C1∪C2)≤∣C1∪C2∣−2r(C_1\cup C_2)\le\lvert C_1\cup C_2\rvert-2を示せ。この不等式から、MMの回路全体が条件 (C3)を満たすことを導け。また、C1∩C2≠∅C_1\cap C_2\ne\emptysetかつr(C1∪C2)<∣C1∪C2∣−2r(C_1\cup C_2)<\lvert C_1\cup C_2\rvert-2となる例を一様マトロイドの中に作れ。
  3. 有限集合EEとC⊆2E\mathcal C\subseteq 2^{E}が条件 (C1)と条件 (C2)を満たすとし、I={A⊆E: ∀C∈C, C⊈A}\mathcal I=\{A\subseteq E:\ \forall C\in\mathcal C,\ C\not\subseteq A\}と置く。C\mathcal Cが条件 (C3)を満たすことと、「A∈IA\in\mathcal Iとx∈E∖Ax\in E\setminus Aに対し、A∪{x}A\cup\{x\}に含まれるC\mathcal Cの元は高々一つである」という条件が成り立つことは同値であることを示せ。さらに、条件 (C1)と条件 (C2)を満たすが条件 (C3)を満たさないC\mathcal Cの例を作り、その例のI\mathcal Iが§E16.15 定義 1.1 条件 (I3)を満たさないことを確かめよ。
  4. 有限集合EE上の関数r:2E→Z≥0r:2^{E}\to\Z_{\ge0}について、条件 (R3)が成り立つことと、「A⊆B⊆EA\subseteq B\subseteq Eとx∈E∖Bx\in E\setminus Bに対しr(B∪{x})−r(B)≤r(A∪{x})−r(A)r(B\cup\{x\})-r(B)\le r(A\cup\{x\})-r(A)」という条件が成り立つことは同値であることを示せ。
  5. 有限集合EE上の関数r:2E→Z≥0r:2^{E}\to\Z_{\ge0}が条件 (R3)を満たすとする。rrが条件 (R1)を満たすことと、r(∅)=0r(\emptyset)=0かつすべてのx∈Ex\in Eについてr({x})≤1r(\{x\})\le1が成り立つことは同値であることを示せ。さらにE≠∅E\ne\emptysetとし、条件 (R2)と条件 (R3)を満たすが条件 (R1)を満たさない関数で、r(∅)=0r(\emptyset)=0を満たすものと、すべてのx∈Ex\in Eについてr({x})≤1r(\{x\})\le1を満たすものをそれぞれ作れ。
  6. マトロイドM=(E,I)M=(E,\mathcal I)の基底BBとx∈E∖Bx\in E\setminus Bをとる。B∪{x}B\cup\{x\}が従属であり、BBとxxの基本回路CC（系 5.3）が定まることを示せ。さらに、y∈By\in Bについて、(B∖{y})∪{x}(B\setminus\{y\})\cup\{x\}が基底であることとy∈Cy\in Cであることが同値であることを示せ。例 6.2の記号でM(K4)M(K_4)、B={a,b,c}B=\{a,b,c\}、x=fx=fとするとき、CCと、(B∖{y})∪{f}(B\setminus\{y\})\cup\{f\}が基底となるy∈By\in Bをすべて求めよ。
  7. マトロイドM=(E,I)M=(E,\mathcal I)の階数関数をrrとし、kkを非負整数とする。A⊆EA\subseteq Eに対してrk(A)=min⁡{r(A),k}r_k(A)=\min\{r(A),k\}と置く。rkr_kが条件 (R1)、条件 (R2)、条件 (R3)を満たすことを示し、定理 5.2 (2)によりrkr_kから定まるマトロイドの独立集合の全体が{A∈I: ∣A∣≤k}\{A\in\mathcal I:\ \lvert A\rvert\le k\}であることを示せ。
  8. 有限単純無向グラフG=(V,E)G=(V,E)とF⊆EF\subseteq Eをとり、(V,F)(V,F)の連結成分の個数をc(F)c(F)と書く。(V,F∖D)(V,F\setminus D)が閉路をもたないようなD⊆FD\subseteq Fの濃度の最小値が∣F∣−∣V∣+c(F)\lvert F\rvert-\lvert V\rvert+c(F)であることを示せ。K4K_4の辺集合全体についてこの値を求め、最小値を与えるDDを一つ挙げよ。
  9. 命題 4.3をK4K_4の辺集合全体と、三角形1,2,31,2,3の辺集合に対して適用し、それぞれの階数を求めよ。得た値が定義 4.1の最大濃度としての定義と一致することを、独立集合を具体的に挙げて確かめよ。
  10. U2,4U_{2,4}の階数関数r(A)=min⁡{∣A∣,2}r(A)=\min\{\lvert A\rvert,2\}が条件 (R3)を満たすことを、∣A∣\lvert A\rvertと∣B∣\lvert B\rvertの場合分けによって直接証明せよ。
解答.

(1)を示す。MMの回路全体をC\mathcal Cと書く。定理 5.2 (1)より、C\mathcal Cは条件 (C2)と条件 (C3)を満たす。相異なるC1,C2∈CC_1,C_2\in\mathcal C、x∈C1∩C2x\in C_1\cap C_2、y∈C1∖C2y\in C_1\setminus C_2の組(C1,C2,x,y)(C_1,C_2,x,y)で、y∈C3⊆(C1∪C2)∖{x}y\in C_3\subseteq(C_1\cup C_2)\setminus\{x\}を満たすC3∈CC_3\in\mathcal Cが存在しないものを反例と呼ぶ。反例が存在すると仮定する。EEは有限集合であるから、反例のうち∣C1∪C2∣\lvert C_1\cup C_2\rvertが最小のものを一つ取り、あらためて(C1,C2,x,y)(C_1,C_2,x,y)と書く。

条件 (C3)より、C3⊆(C1∪C2)∖{x}C_3\subseteq(C_1\cup C_2)\setminus\{x\}を満たすC3∈CC_3\in\mathcal Cが存在する。(C1,C2,x,y)(C_1,C_2,x,y)は反例であるからy∉C3y\notin C_3である。C3⊆C1C_3\subseteq C_1と仮定すると、条件 (C2)よりC3=C1C_3=C_1であるが、x∈C1x\in C_1かつx∉C3x\notin C_3であるから矛盾する。ゆえにz∈C3∖C1z\in C_3\setminus C_1が存在し、C3⊆C1∪C2C_3\subseteq C_1\cup C_2よりz∈C2∖C1z\in C_2\setminus C_1である。

組(C2,C3,z,x)(C_2,C_3,z,x)を考える。x∈C2x\in C_2かつx∉C3x\notin C_3であるからC2≠C3C_2\ne C_3であり、z∈C2∩C3z\in C_2\cap C_3、x∈C2∖C3x\in C_2\setminus C_3である。C2∪C3⊆C1∪C2C_2\cup C_3\subseteq C_1\cup C_2であり、C1∪C2C_1\cup C_2の元yyはy∉C2y\notin C_2かつy∉C3y\notin C_3を満たすから、∣C2∪C3∣<∣C1∪C2∣\lvert C_2\cup C_3\rvert<\lvert C_1\cup C_2\rvertである。∣C1∪C2∣\lvert C_1\cup C_2\rvertの最小性により(C2,C3,z,x)(C_2,C_3,z,x)は反例でないから、x∈C4⊆(C2∪C3)∖{z}x\in C_4\subseteq(C_2\cup C_3)\setminus\{z\}を満たすC4∈CC_4\in\mathcal Cが存在する。

組(C1,C4,x,y)(C_1,C_4,x,y)を考える。x∈C1∩C4x\in C_1\cap C_4である。C4⊆C2∪C3C_4\subseteq C_2\cup C_3かつy∉C2∪C3y\notin C_2\cup C_3であるからy∉C4y\notin C_4であり、y∈C1∖C4y\in C_1\setminus C_4、とくにC1≠C4C_1\ne C_4である。C3⊆C1∪C2C_3\subseteq C_1\cup C_2であるからC1∪C4⊆C1∪C2∪C3=C1∪C2C_1\cup C_4\subseteq C_1\cup C_2\cup C_3=C_1\cup C_2であり、C1∪C2C_1\cup C_2の元zzはz∉C1z\notin C_1かつz∉C4z\notin C_4を満たすから、∣C1∪C4∣<∣C1∪C2∣\lvert C_1\cup C_4\rvert<\lvert C_1\cup C_2\rvertである。最小性により(C1,C4,x,y)(C_1,C_4,x,y)は反例でないから、y∈C5⊆(C1∪C4)∖{x}y\in C_5\subseteq(C_1\cup C_4)\setminus\{x\}を満たすC5∈CC_5\in\mathcal Cが存在する。(C1∪C4)∖{x}⊆(C1∪C2)∖{x}(C_1\cup C_4)\setminus\{x\}\subseteq(C_1\cup C_2)\setminus\{x\}であるから、C5C_5はy∈C5⊆(C1∪C2)∖{x}y\in C_5\subseteq(C_1\cup C_2)\setminus\{x\}を満たし、(C1,C2,x,y)(C_1,C_2,x,y)が反例であることに反する。ゆえに反例は存在せず、主張が成り立つ。

(2)を示す。CCを回路とする。§E16.15 定義 1.1 条件 (I1)より∅\emptysetは独立であるからC≠∅C\ne\emptysetであり、y∈Cy\in Cをとることができる。回路の定義よりC∖{y}C\setminus\{y\}はCCに含まれる独立集合であるから、r(C)≥∣C∣−1r(C)\ge\lvert C\rvert-1である。CCに含まれる独立集合の濃度は∣C∣\lvert C\rvert以下であり、濃度が∣C∣\lvert C\rvertであるCCの部分集合は従属集合CC自身だけであるから、r(C)≤∣C∣−1r(C)\le\lvert C\rvert-1である。ゆえにr(C)=∣C∣−1r(C)=\lvert C\rvert-1である。

C1,C2C_1,C_2を相異なる回路とする。C1∩C2=C1C_1\cap C_2=C_1と仮定するとC1⊆C2C_1\subseteq C_2であり、定理 5.2 (1)よりMMの回路全体は条件 (C2)を満たすから、C1=C2C_1=C_2となって矛盾する。ゆえにC1∩C2⊊C1C_1\cap C_2\subsetneq C_1であり、回路の定義よりC1∩C2C_1\cap C_2は独立である。定理 5.2の等式I={A⊆E: r(A)=∣A∣}\mathcal I=\{A\subseteq E:\ r(A)=\lvert A\rvert\}よりr(C1∩C2)=∣C1∩C2∣r(C_1\cap C_2)=\lvert C_1\cap C_2\rvertである。定理 5.2 (2)よりrrは条件 (R3)を満たすから、

r(C1∪C2)+∣C1∩C2∣≤r(C1)+r(C2)=∣C1∣+∣C2∣−2r(C_1\cup C_2)+\lvert C_1\cap C_2\rvert\le r(C_1)+r(C_2)=\lvert C_1\rvert+\lvert C_2\rvert-2

である。包除原理（§D2.3 定理 1.2）より∣C1∣+∣C2∣−∣C1∩C2∣=∣C1∪C2∣\lvert C_1\rvert+\lvert C_2\rvert-\lvert C_1\cap C_2\rvert=\lvert C_1\cup C_2\rvertであるから、r(C1∪C2)≤∣C1∪C2∣−2r(C_1\cup C_2)\le\lvert C_1\cup C_2\rvert-2である。

条件 (C3)を導く。x∈C1∩C2x\in C_1\cap C_2とし、(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}が独立であると仮定する。条件 (R2)よりr(C1∪C2)≥r((C1∪C2)∖{x})=∣C1∪C2∣−1r(C_1\cup C_2)\ge r\bigl((C_1\cup C_2)\setminus\{x\}\bigr)=\lvert C_1\cup C_2\rvert-1となり、上の不等式に反する。ゆえに(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}は従属であり、命題 1.2より(C1∪C2)∖{x}(C_1\cup C_2)\setminus\{x\}に含まれる回路が存在する。この導出で用いた条件 (R3)の証明は回路の性質を用いないので、この導出は条件 (C3)の別証を与える。

例を作る。U2,5U_{2,5}の台集合をE={1,2,3,4,5}E=\{1,2,3,4,5\}とする。例 6.1より、回路は三元部分集合の全体であり、階数はr(A)=min⁡{∣A∣,2}r(A)=\min\{\lvert A\rvert,2\}である。C1={1,2,3}C_1=\{1,2,3\}、C2={1,4,5}C_2=\{1,4,5\}とするとC1∩C2={1}≠∅C_1\cap C_2=\{1\}\ne\emptysetであり、C1∪C2=EC_1\cup C_2=Eであるからr(C1∪C2)=2<3=∣C1∪C2∣−2r(C_1\cup C_2)=2<3=\lvert C_1\cup C_2\rvert-2である。

(3)を示す。「A∈IA\in\mathcal Iとx∈E∖Ax\in E\setminus Aに対し、A∪{x}A\cup\{x\}に含まれるC\mathcal Cの元は高々一つである」という条件を一意性の条件と呼ぶ。C\mathcal Cが条件 (C3)を満たすとし、A∈IA\in\mathcal I、x∈E∖Ax\in E\setminus Aとする。A∪{x}∈IA\cup\{x\}\in\mathcal Iならば、I\mathcal Iの定義よりA∪{x}A\cup\{x\}に含まれるC\mathcal Cの元は存在しない。A∪{x}∉IA\cup\{x\}\notin\mathcal Iならば、補題 3.1よりA∪{x}A\cup\{x\}に含まれるC\mathcal Cの元はただ一つである。ゆえに一意性の条件が成り立つ。

逆に、一意性の条件を仮定し、相異なるC1,C2∈CC_1,C_2\in\mathcal Cとx∈C1∩C2x\in C_1\cap C_2をとる。A=(C1∪C2)∖{x}A=(C_1\cup C_2)\setminus\{x\}と置き、AAがC\mathcal Cのどの元も含まないと仮定する。このときA∈IA\in\mathcal Iかつx∉Ax\notin Aであり、A∪{x}=C1∪C2A\cup\{x\}=C_1\cup C_2はC\mathcal Cの相異なる二つの元C1,C2C_1,C_2を含む。これは一意性の条件に反する。ゆえにAAはC\mathcal Cのある元C3C_3を含み、C\mathcal Cは条件 (C3)を満たす。

例を作る。E={1,2,3}E=\{1,2,3\}、C={{1,2},{1,3}}\mathcal C=\bigl\{\{1,2\},\{1,3\}\bigr\}とする。∅∉C\emptyset\notin\mathcal Cであり、{1,2}\{1,2\}と{1,3}\{1,3\}はどちらも他方に含まれないから、条件 (C1)と条件 (C2)が成り立つ。C1={1,2}C_1=\{1,2\}、C2={1,3}C_2=\{1,3\}、x=1x=1について(C1∪C2)∖{1}={2,3}(C_1\cup C_2)\setminus\{1\}=\{2,3\}はC\mathcal Cの元を含まないから、条件 (C3)は成り立たない。I\mathcal Iは{1,2}\{1,2\}と{1,3}\{1,3\}のどちらも含まない部分集合の全体であるから

I={∅,{1},{2},{3},{2,3}}\mathcal I=\bigl\{\emptyset,\{1\},\{2\},\{3\},\{2,3\}\bigr\}

である。A={1}A=\{1\}とB={2,3}B=\{2,3\}は∣A∣<∣B∣\lvert A\rvert<\lvert B\rvertを満たすI\mathcal Iの元であるが、A∪{2}={1,2}A\cup\{2\}=\{1,2\}とA∪{3}={1,3}A\cup\{3\}=\{1,3\}はどちらもI\mathcal Iに属さない。ゆえにI\mathcal Iは§E16.15 定義 1.1 条件 (I3)を満たさない。この例では、{2,3}∈I\{2,3\}\in\mathcal Iとx=1x=1について{2,3}∪{1}=E\{2,3\}\cup\{1\}=EがC\mathcal Cの二つの元を含み、一意性の条件も成り立たない。

(4)を示す。問題の条件を局所劣モジュラ性と呼ぶ。

条件 (R3)から局所劣モジュラ性を導く。A⊆B⊆EA\subseteq B\subseteq E、x∈E∖Bx\in E\setminus Bとする。A⊆BA\subseteq Bとx∉Bx\notin Bより(A∪{x})∪B=B∪{x}(A\cup\{x\})\cup B=B\cup\{x\}、(A∪{x})∩B=A(A\cup\{x\})\cap B=Aである。条件 (R3)をA∪{x}A\cup\{x\}とBBへ適用すると

r(B∪{x})+r(A)≤r(A∪{x})+r(B)r(B\cup\{x\})+r(A)\le r(A\cup\{x\})+r(B)

であり、移項すると局所劣モジュラ性の不等式を得る。

局所劣モジュラ性から条件 (R3)を導く。A,B⊆EA,B\subseteq Eとし、D=A∩BD=A\cap B、m=∣B∖A∣m=\lvert B\setminus A\rvertと置き、B∖AB\setminus Aの相異なる元をy1,…,ymy_1,\dots,y_mと並べる。j=0,1,…,mj=0,1,\dots,mについてYj={y1,…,yj}Y_j=\{y_1,\dots,y_j\}と置く（Y0=∅Y_0=\emptyset）。1≤j≤m1\le j\le mとする。D⊆AD\subseteq AであるからD∪Yj−1⊆A∪Yj−1D\cup Y_{j-1}\subseteq A\cup Y_{j-1}であり、yj∉Ay_j\notin Aかつyj∉Yj−1y_j\notin Y_{j-1}であるからyj∉A∪Yj−1y_j\notin A\cup Y_{j-1}である。局所劣モジュラ性をD∪Yj−1⊆A∪Yj−1D\cup Y_{j-1}\subseteq A\cup Y_{j-1}とyjy_jへ適用すると

r(A∪Yj)−r(A∪Yj−1)≤r(D∪Yj)−r(D∪Yj−1)r(A\cup Y_j)-r(A\cup Y_{j-1})\le r(D\cup Y_j)-r(D\cup Y_{j-1})

である。この不等式をj=1,…,mj=1,\dots,mについて辺々加えると、各辺の和は隣り合う項が打ち消し合って

r(A∪Ym)−r(A)≤r(D∪Ym)−r(D)r(A\cup Y_m)-r(A)\le r(D\cup Y_m)-r(D)

となる（m=0m=0のときは両辺とも00である）。Ym=B∖AY_m=B\setminus AであるからA∪Ym=A∪BA\cup Y_m=A\cup B、D∪Ym=(A∩B)∪(B∖A)=BD\cup Y_m=(A\cap B)\cup(B\setminus A)=Bである。ゆえにr(A∪B)−r(A)≤r(B)−r(A∩B)r(A\cup B)-r(A)\le r(B)-r(A\cap B)であり、移項すると条件 (R3)を得る。

(5)を示す。rrが条件 (R1)を満たすならば、0≤r(∅)≤∣∅∣=00\le r(\emptyset)\le\lvert\emptyset\rvert=0よりr(∅)=0r(\emptyset)=0であり、各x∈Ex\in Eについてr({x})≤∣{x}∣=1r(\{x\})\le\lvert\{x\}\rvert=1である。

逆に、r(∅)=0r(\emptyset)=0かつすべてのx∈Ex\in Eについてr({x})≤1r(\{x\})\le1が成り立つとする。rrの値は非負整数であるからr(A)≥0r(A)\ge0である。A⊆EA\subseteq Eとx∈E∖Ax\in E\setminus Aに対し、条件 (R3)をAAと{x}\{x\}へ適用すると、A∩{x}=∅A\cap\{x\}=\emptysetより

r(A∪{x})+r(∅)≤r(A)+r({x})r(A\cup\{x\})+r(\emptyset)\le r(A)+r(\{x\})

であり、r(∅)=0r(\emptyset)=0とr({x})≤1r(\{x\})\le1からr(A∪{x})≤r(A)+1r(A\cup\{x\})\le r(A)+1である。r(A)≤∣A∣r(A)\le\lvert A\rvertを∣A∣\lvert A\rvertについての帰納法で示す。∣A∣=0\lvert A\rvert=0のときA=∅A=\emptysetでありr(∅)=0r(\emptyset)=0である。k≥1k\ge1とし、濃度k−1k-1のすべての部分集合について主張が成り立つと仮定する。∣A∣=k\lvert A\rvert=kのとき、x∈Ax\in AをとってA′=A∖{x}A'=A\setminus\{x\}と置くと、x∉A′x\notin A'であるからr(A)=r(A′∪{x})≤r(A′)+1≤(k−1)+1=kr(A)=r(A'\cup\{x\})\le r(A')+1\le(k-1)+1=kである。ゆえにrrは条件 (R1)を満たす。この向きでは条件 (R2)を用いていない。

例を作る。第一に、すべてのA⊆EA\subseteq Eについてr(A)=2∣A∣r(A)=2\lvert A\rvertと定める。A⊆BA\subseteq Bならば2∣A∣≤2∣B∣2\lvert A\rvert\le2\lvert B\rvertであるから条件 (R2)が成り立ち、包除原理（§D2.3 定理 1.2）より2∣A∪B∣+2∣A∩B∣=2∣A∣+2∣B∣2\lvert A\cup B\rvert+2\lvert A\cap B\rvert=2\lvert A\rvert+2\lvert B\rvertであるから条件 (R3)が等号で成り立つ。r(∅)=0r(\emptyset)=0であるが、x∈Ex\in Eについてr({x})=2>1=∣{x}∣r(\{x\})=2>1=\lvert\{x\}\rvertであるから条件 (R1)は成り立たない。第二に、すべてのA⊆EA\subseteq Eについてr(A)=1r(A)=1と定める。rrは定数であるから条件 (R2)が成り立ち、r(A∪B)+r(A∩B)=2=r(A)+r(B)r(A\cup B)+r(A\cap B)=2=r(A)+r(B)であるから条件 (R3)が成り立つ。すべてのx∈Ex\in Eについてr({x})=1r(\{x\})=1であるが、r(∅)=1>0=∣∅∣r(\emptyset)=1>0=\lvert\emptyset\rvertであるから条件 (R1)は成り立たない。ゆえに、二つの条件のどちらも省くことはできない。

(6)を示す。B⊊B∪{x}B\subsetneq B\cup\{x\}であり、BBは包含に関して極大な独立集合であるから、B∪{x}∉IB\cup\{x\}\notin\mathcal Iである。B∈IB\in\mathcal Iかつx∈E∖Bx\in E\setminus Bであるから、系 5.3よりB∪{x}B\cup\{x\}に含まれる回路はただ一つであり、それをCCと書くとx∈Cx\in Cである。

y∈By\in Bとし、B′=(B∖{y})∪{x}B'=(B\setminus\{y\})\cup\{x\}と置く。x∉Bx\notin Bであるからx≠yx\ne yであり、x∉B∖{y}x\notin B\setminus\{y\}であるから∣B′∣=∣B∣\lvert B'\rvert=\lvert B\rvertである。

y∈Cy\in Cと仮定する。B′B'が従属であるとすると、命題 1.2よりB′B'に含まれる回路DDが存在する。B′⊆B∪{x}B'\subseteq B\cup\{x\}であるからD⊆B∪{x}D\subseteq B\cup\{x\}であり、基本回路の一意性よりD=CD=Cである。しかしy∈Cy\in Cかつy∉B′y\notin B'であるからC⊈B′C\not\subseteq B'となり、矛盾する。ゆえにB′∈IB'\in\mathcal Iであり、∣B′∣=∣B∣\lvert B'\rvert=\lvert B\rvertであるから、§E16.15 系 2.4よりB′B'は基底である。

y∉Cy\notin Cと仮定する。C⊆B∪{x}C\subseteq B\cup\{x\}とy∉Cy\notin CよりC⊆(B∪{x})∖{y}=B′C\subseteq(B\cup\{x\})\setminus\{y\}=B'である。回路CCを含むB′B'は命題 1.3より従属であり、基底でない。以上より、B′B'が基底であることとy∈Cy\in Cであることは同値である。

M(K4)M(K_4)の場合を求める。B={a,b,c}B=\{a,b,c\}は頂点11と残りの三頂点を結ぶ三辺であるから(V,B)(V,B)は連結である。閉路の各頂点は次数が22以上であり、閉路は33個以上の頂点をもつが、(V,B)(V,B)で次数が22以上の頂点は頂点11だけであるから、(V,B)(V,B)は閉路をもたない。ゆえにBBは全域木の辺集合であり、§E16.15 命題 6.3より基底である。B∪{f}B\cup\{f\}には、頂点を1,3,4,11,3,4,1の順にたどる閉路の辺集合{b,f,c}\{b,f,c\}が含まれ、例 6.2よりこれは回路である。基本回路の一意性よりC={b,c,f}C=\{b,c,f\}である。ゆえに(B∖{y})∪{f}(B\setminus\{y\})\cup\{f\}が基底となるy∈By\in Bはy=by=bとy=cy=cであり、得られる基底は{a,c,f}\{a,c,f\}と{a,b,f}\{a,b,f\}である。y=ay=aのときの{b,c,f}\{b,c,f\}は回路であり、基底でない。

(7)を示す。定理 5.2 (2)より、rrは条件 (R1)、条件 (R2)、条件 (R3)を満たす。

条件 (R1)を示す。r(A)≥0r(A)\ge0かつk≥0k\ge0であるからrk(A)≥0r_k(A)\ge0であり、rk(A)≤r(A)≤∣A∣r_k(A)\le r(A)\le\lvert A\rvertである。

条件 (R2)を示す。A⊆BA\subseteq Bならばr(A)≤r(B)r(A)\le r(B)であるから、rk(A)=min⁡{r(A),k}≤min⁡{r(B),k}=rk(B)r_k(A)=\min\{r(A),k\}\le\min\{r(B),k\}=r_k(B)である。

条件 (R3)を示す。A,B⊆EA,B\subseteq Eとし、a=r(A)a=r(A)、b=r(B)b=r(B)、u=r(A∪B)u=r(A\cup B)、i=r(A∩B)i=r(A\cap B)と置く。条件 (R3)よりu+i≤a+bu+i\le a+bであり、条件 (R2)よりi≤ai\le aかつi≤bi\le bである。示すべき不等式はmin⁡{u,k}+min⁡{i,k}≤min⁡{a,k}+min⁡{b,k}\min\{u,k\}+\min\{i,k\}\le\min\{a,k\}+\min\{b,k\}である。a≥ka\ge kかつb≥kb\ge kのとき、右辺は2k2kであり、左辺の各項はkk以下であるから不等式が成り立つ。a<ka<kのとき、i≤a<ki\le a<kであるからmin⁡{i,k}=i\min\{i,k\}=iかつmin⁡{a,k}=a\min\{a,k\}=aである。さらにb≥kb\ge kならば、左辺はmin⁡{u,k}+i≤k+a\min\{u,k\}+i\le k+aであり、右辺はa+ka+kである。b<kb<kならば、左辺はmin⁡{u,k}+i≤u+i≤a+b\min\{u,k\}+i\le u+i\le a+bであり、右辺はa+ba+bである。a≥ka\ge kかつb<kb<kのときは、示すべき不等式がAAとBBの入れ替えで変わらないので、a<ka<kの場合の議論をAAとBBの役割を入れ替えて適用すればよい。以上で、すべての場合に不等式が成り立つ。

独立集合を求める。定理 5.2 (2)により、rkr_kから定まるマトロイドの独立集合の全体はIk={A⊆E: rk(A)=∣A∣}\mathcal I_k=\{A\subseteq E:\ r_k(A)=\lvert A\rvert\}である。定理 5.2の等式より、A∈IA\in\mathcal Iであることとr(A)=∣A∣r(A)=\lvert A\rvertであることは同値である。A∈IA\in\mathcal Iかつ∣A∣≤k\lvert A\rvert\le kならば、r(A)=∣A∣≤kr(A)=\lvert A\rvert\le kであるからrk(A)=∣A∣r_k(A)=\lvert A\rvertであり、A∈IkA\in\mathcal I_kである。逆にA∈IkA\in\mathcal I_kとする。r(A)>kr(A)>kと仮定するとrk(A)=kr_k(A)=kであるから∣A∣=k<r(A)\lvert A\rvert=k<r(A)となって条件 (R1)に反する。ゆえにr(A)≤kr(A)\le kであり、r(A)=rk(A)=∣A∣≤kr(A)=r_k(A)=\lvert A\rvert\le kであるから、A∈IA\in\mathcal Iかつ∣A∣≤k\lvert A\rvert\le kである。以上よりIk={A∈I: ∣A∣≤k}\mathcal I_k=\{A\in\mathcal I:\ \lvert A\rvert\le k\}である。とくに、n=∣E∣n=\lvert E\rvertとし、すべての部分集合を独立とするマトロイドUn,nU_{n,n}にk≤nk\le nを適用すると、Uk,nU_{k,n}が得られる。

(8)を示す。M(G)M(G)の階数関数をrrと書く。命題 4.3よりr(F)=∣V∣−c(F)r(F)=\lvert V\rvert-c(F)である。D⊆FD\subseteq Fについて(V,F∖D)(V,F\setminus D)が閉路をもたないとする。このときF∖DF\setminus DはFFに含まれるM(G)M(G)の独立集合であるから、∣F∖D∣≤r(F)\lvert F\setminus D\rvert\le r(F)であり、D⊆FD\subseteq Fより

∣D∣=∣F∣−∣F∖D∣≥∣F∣−r(F)=∣F∣−∣V∣+c(F)\lvert D\rvert=\lvert F\rvert-\lvert F\setminus D\rvert\ge\lvert F\rvert-r(F)=\lvert F\rvert-\lvert V\rvert+c(F)

である。逆に、定義 4.1より、T⊆FT\subseteq F、T∈IT\in\mathcal I、∣T∣=r(F)\lvert T\rvert=r(F)を満たすTTが存在する。D=F∖TD=F\setminus Tと置くとF∖D=TF\setminus D=Tであるから(V,F∖D)(V,F\setminus D)は閉路をもたず、∣D∣=∣F∣−r(F)=∣F∣−∣V∣+c(F)\lvert D\rvert=\lvert F\rvert-r(F)=\lvert F\rvert-\lvert V\rvert+c(F)である。ゆえに最小値は∣F∣−∣V∣+c(F)\lvert F\rvert-\lvert V\rvert+c(F)である。

K4K_4の辺集合全体E={a,b,c,d,e,f}E=\{a,b,c,d,e,f\}では∣E∣=6\lvert E\rvert=6、∣V∣=4\lvert V\rvert=4であり、(V,E)(V,E)は連結であるからc(E)=1c(E)=1である。ゆえに最小値は6−4+1=36-4+1=3である。D={d,e,f}D=\{d,e,f\}とすると、E∖D={a,b,c}E\setminus D=\{a,b,c\}は頂点11と残りの三頂点を結ぶ三辺であり、次数が22以上の頂点は頂点11だけである。閉路の各頂点は次数が22以上であり、閉路は33個以上の頂点をもつから、(V,{a,b,c})(V,\{a,b,c\})は閉路をもたない。したがってD={d,e,f}D=\{d,e,f\}は最小値を与える。

(9)では、K4K_4の頂点集合をV={1,2,3,4}V=\{1,2,3,4\}とし、例 6.2の辺の記号を用いる。辺集合全体E={a,b,c,d,e,f}E=\{a,b,c,d,e,f\}については、(V,E)(V,E)は連結であるからc(E)=1c(E)=1であり、命題 4.3よりr(E)=4−1=3r(E)=4-1=3である。定義との一致を確かめる。{a,b,c}\{a,b,c\}は頂点11と残りの三頂点を結ぶ三辺であり、次数が22以上の頂点は頂点11だけである。閉路の各頂点は次数が22以上であり、閉路は33個以上の頂点をもつから、(V,{a,b,c})(V,\{a,b,c\})は閉路をもたず、{a,b,c}\{a,b,c\}は濃度33の独立集合である。一方、EEに含まれる任意の独立集合IIについて、§E16.15 補題 6.2より∣I∣=4−c(I)≤3\lvert I\rvert=4-c(I)\le3である。ゆえに最大濃度は33であり、公式の値と一致する。

三角形1,2,31,2,3の辺集合F={a,b,d}F=\{a,b,d\}については、(V,F)(V,F)の連結成分は頂点集合{1,2,3}\{1,2,3\}の成分と孤立点44の成分の二つであるからc(F)=2c(F)=2であり、命題 4.3よりr(F)=4−2=2r(F)=4-2=2である。公式の∣V∣\lvert V\rvertはK4K_4の頂点数44であり、c(F)c(F)は孤立点44も一つの連結成分として数える。定義との一致を確かめる。{a,b}\{a,b\}は頂点11と頂点2,32,3を結ぶ二辺であり、次数が22以上の頂点は頂点11だけであるから閉路をもたず、濃度22の独立集合である。FFに含まれる濃度33の部分集合はFF自身だけであり、FFは閉路1,2,3,11,2,3,1の辺集合であるから従属である。ゆえに最大濃度は22であり、公式の値と一致する。

(10)を示す。A,B⊆EA,B\subseteq Eとし、a=∣A∣a=\lvert A\rvert、b=∣B∣b=\lvert B\rvert、i=∣A∩B∣i=\lvert A\cap B\rvertと置く。包除原理（§D2.3 定理 1.2）より∣A∪B∣=a+b−i\lvert A\cup B\rvert=a+b-iであり、A∩B⊆AA\cap B\subseteq A、A∩B⊆BA\cap B\subseteq Bよりi≤ai\le aかつi≤bi\le bである。示すべき不等式は

min⁡{a+b−i, 2}+min⁡{i, 2}≤min⁡{a, 2}+min⁡{b, 2}\min\{a+b-i,\,2\}+\min\{i,\,2\}\le\min\{a,\,2\}+\min\{b,\,2\}

である。

a≥2a\ge2かつb≥2b\ge2の場合、右辺は2+2=42+2=4であり、左辺の各項は22以下であるから左辺は44以下である。

a≤1a\le1の場合、i≤a≤1i\le a\le1であるからmin⁡{i,2}=i\min\{i,2\}=i、min⁡{a,2}=a\min\{a,2\}=aである。さらにb≥2b\ge2ならば、右辺はa+2a+2であり、左辺はmin⁡{a+b−i,2}+i≤2+i≤2+a\min\{a+b-i,2\}+i\le2+i\le2+aであるから、不等式が成り立つ。b≤1b\le1ならば、右辺はa+ba+bであり、左辺はmin⁡{a+b−i,2}+i≤(a+b−i)+i=a+b\min\{a+b-i,2\}+i\le(a+b-i)+i=a+bであるから、不等式が成り立つ。

b≤1b\le1の場合は、不等式の両辺がAAとBBの入れ替えで変わらないので、a≤1a\le1の場合の議論でAAとBBの役割を入れ替えればよい。以上の場合は、a≥2a\ge2かつb≥2b\ge2であるか、a≤1a\le1またはb≤1b\le1であるかのいずれかであるから、すべてのA,BA,Bを尽くしている。ゆえにrrは条件 (R3)を満たす。▨

注意 7.2. 閉包作用素による公理化、超平面による公理化、および実数値の劣モジュラ関数の一般論は、本記事では扱っていない。

参考文献

  1. James Oxley, Matroid Theory, 2nd ed., Oxford University Press, 2011.回路公理系と階数公理系の定式化、および各公理系から独立集合族を復元する構成を参考にした。
  2. Bernhard Korte and Jens Vygen, Combinatorial Optimization: Theory and Algorithms, 6th ed., Algorithms and Combinatorics, Springer, 2018.階数関数の劣モジュラ性の証明と、独立集合系に対する各種公理の同値性の並べ方を参考にした。

前提記事