マトロイド共通基分割に関する反例

この記事は「反例」アドベントカレンダー 4 日目の記事です.本ブログは別のアドベントカレンダー用に昨日誕生したものですが,せっかくなのでもう 1 つぐらい記事を書いてみようと思います.

準備

色々言葉を準備しますが,そういうものかと適当に読み飛ばしていただいても大丈夫です.

  • G = (V, E)グラフであるとは,V が有限集合であり,E が「各要素が『要素数 2V の部分集合』であるような集合」であることをいう.ここで,V の各要素を頂点E の各要素をと呼ぶ.
  • グラフ G = (V, E)2 部グラフであるとは,頂点集合 V2 つの部分集合 UW に分割でき (\, U \cup W = V~~\text{and}~~U \cap W = \emptyset \,),各辺 e \in EU, W それぞれと非空な交わりを持つ (\, e \cap U \neq \emptyset \neq e \cap W \,) ことをいう.2 部グラフ G の頂点集合の分割を明示する場合,G = (U, W; E) と書く.
  • 辺部分集合 M \subseteq EGマッチングであるとは,「任意の頂点 v \in V に対して,v を含む M の辺が高々 1 本しかない」ことをいう.さらに |M| = |V|/2 が成り立つとき,M完全マッチングであるという.
  • 有限集合 E とその部分集合族 \mathcal{I} \subseteq 2^E = \{\, X \mid X \subseteq E \,\} の組 \mathbf{M} = (E, \mathcal{I})マトロイドであるとは,以下の 3 つの性質が成り立つことをいう.(本記事内では定義自体は特に重要ではなく,下の 2 つの例だけが必要になります.)
      (I0)  \emptyset \in \mathcal{I}.
      (I1)  X \subseteq Y \in \mathcal{I} \implies X \in \mathcal{I}.
      (I2)  [\, X, Y \in \mathcal{I}~~\text{and}~~|X| \lt |Y| \,] \implies \exists e \in Y \setminus X~~\text{s.t.}~~X \cup \{e\} \in \mathcal{I}.
    ここで,EM台集合\mathcal{I} の各要素を M独立集合と呼ぶ.さらに,包含関係に関して極大な独立集合をと呼び,マトロイド \mathbf{M} の基族を \mathcal{B}(\mathbf{M}) と書く.(I2) の性質から,X, Y \in \mathcal{B}(\mathbf{M}) \implies |X| = |Y| が導ける.
  • \mathbf{M} = (E, \mathcal{I})分割マトロイドであるとは,台集合 E の分割 E_1, \dots, E_r が存在して,独立集合族 \mathcal{I} が以下のように書けることをいう.
    \displaystyle\mathcal{I} = \{\, X \subseteq E \mid |X \cap E_i| \leq 1~(\forall i) \,\}.
  • \mathbf{M} = (E, \mathcal{I})グラフ的マトロイドであるとは,台集合 E を辺集合とするグラフ G = (V, E) が存在して,独立集合族 \mathcal{I} が以下のように書けることをいう.
    \displaystyle\mathcal{I} = \{\, X \subseteq E \mid X~は~G~中で閉路を形成しない \,\}.
    ここで,辺部分集合 X \subseteq E閉路を形成するとは,X の非空な部分集合 C であって,「各頂点 v \in V に対して,v を含む C の辺がちょうど 0 本または 2 本となる」ようなもの(閉路)が存在することをいう.

さて,ここから本題に入ります.以下の定理は 100 年以上前に示されたものですが,「自明な必要条件がそのまま十分条件にもなっている」というなかなか綺麗な結果です.

定理 (Kőnig)*1  任意の 2 部グラフ G = (U, W; E) と任意の正の整数 k に対して,以下は同値.

  • 辺集合 Ek 個の完全マッチングに分割できる.(\, \exists M_1, \ldots, M_k \colon G の完全マッチング~~\text{s.t.}~~\bigcup_{i = 1}^k M_i = E~~\text{and}~~[\, i \neq j \implies M_i \cap M_j = \emptyset \,] \,)
  • すべての頂点の次数が k である.(\, \forall v \in U \cup W,~d_G(v) := |\{\, e \in E \mid v \in e \,\}| = k \,)

そして,この定理をマトロイドの言葉で言い換えると以下のようになります.

  台集合 E が共通である任意の 2 つの分割マトロイド \mathbf{M}_1, \mathbf{M}_2 と任意の正の整数 k に対して,以下は同値.

  • 台集合 Ek 個の共通基に分割できる.(\, \exists X_1, \ldots, X_k \in \mathcal{B}(\mathbf{M}_1) \cap \mathcal{B}(\mathbf{M}_2)~~\text{s.t.}~~\bigcup_{i = 1}^k X_i = E~~\text{and}~~[\, i \neq j \implies X_i \cap X_j = \emptyset \,] \,)
  • \mathbf{M}_1, \mathbf{M}_2 それぞれに関して,台集合 Ek 個の基に分割できる.(\, \forall p \in \{1, 2\},~\exists X_1, \ldots, X_k \in \mathcal{B}(\mathbf{M}_p) ~~\text{s.t.}~~\bigcup_{i = 1}^k X_i = E~~\text{and}~~[\, i \neq j \implies X_i \cap X_j = \emptyset \,] \,)

というわけで,自然な疑問として,「上の系の分割マトロイドの部分を一般のマトロイドに置き換えるとどうなるのか?」ということが気になります.以下の反例は,k = 2 で,一方が分割マトロイド,他方がグラフ的マトロイドであるような場合でも,上の系が(そのままの形では)拡張できないということを示しています.

反例*2  K_4 = (V, E)4 頂点完全グラフ,すなわち,|V| = 4E = \binom{V}{2} = \{\, X \subseteq V \mid |X| = 2 \,\} であるグラフとし,M_1, M_2, M_3 \subseteq EK_4 の完全マッチングで互いに素なものとする.(必然的に M_1, M_2, M_3E の分割となる.)\mathbf{M}_1 = (E, \mathcal{I}_1)M_1, M_2, M_3 が誘導する分割マトロイド,すなわち,

\displaystyle\mathcal{I}_1 = \{\, X \subseteq E \mid |X \cap M_i| \leq 1~(\forall i) \,\}

とし,\mathbf{M}_2 = (E, \mathcal{I}_2)K_4 が誘導するグラフ的マトロイド,すなわち,

\displaystyle\mathcal{I}_2 = \{\, X \subseteq E \mid X~は~K_4~中で閉路を形成しない \,\}

とする.今 k = 2 とすると,\mathbf{M}_1, \mathbf{M}_2 それぞれに関して,台集合 E2 個の基に分割できることは簡単に確認できる.一方,共通基は必ずどこか 1 頂点を含む辺 3 本すべてを取る必要があり,そのような辺部分集合の補集合は閉路となるため,E2 個の共通基に分割できないことがわかる.

*1:D. Kőnig: Graphok és Alkalmazásuk a Determinánsok és a Halmazok Elméletére. Mathematikai és Természettudományi Értesitő, 34 (1916), pp. 104–119. (Link: http://real-j.mtak.hu/4450/)

*2:cf. A. Schrijver: Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003. (ISBN: 9783540443896)