マトロイド共通基分割に関する反例
この記事は「反例」アドベントカレンダー 日目の記事です.本ブログは別のアドベントカレンダー用に昨日誕生したものですが,せっかくなのでもう つぐらい記事を書いてみようと思います.
準備
色々言葉を準備しますが,そういうものかと適当に読み飛ばしていただいても大丈夫です.
- がグラフであるとは, が有限集合であり, が「各要素が『要素数 の の部分集合』であるような集合」であることをいう.ここで, の各要素を頂点, の各要素を辺と呼ぶ.
- グラフ が 部グラフであるとは,頂点集合 が つの部分集合 と に分割でき ,各辺 が それぞれと非空な交わりを持つ ことをいう. 部グラフ の頂点集合の分割を明示する場合, と書く.
- 辺部分集合 が のマッチングであるとは,「任意の頂点 に対して, を含む の辺が高々 本しかない」ことをいう.さらに が成り立つとき, は完全マッチングであるという.
- 有限集合 とその部分集合族 の組 がマトロイドであるとは,以下の つの性質が成り立つことをいう.(本記事内では定義自体は特に重要ではなく,下の つの例だけが必要になります.)
(I0)
(I1)
(I2)
ここで, を の台集合, の各要素を の独立集合と呼ぶ.さらに,包含関係に関して極大な独立集合を基と呼び,マトロイド の基族を と書く.(I2) の性質から, が導ける. - が分割マトロイドであるとは,台集合 の分割 が存在して,独立集合族 が以下のように書けることをいう.
- がグラフ的マトロイドであるとは,台集合 を辺集合とするグラフ が存在して,独立集合族 が以下のように書けることをいう.
ここで,辺部分集合 が閉路を形成するとは, の非空な部分集合 であって,「各頂点 に対して, を含む の辺がちょうど 本または 本となる」ようなもの(閉路)が存在することをいう.
さて,ここから本題に入ります.以下の定理は 年以上前に示されたものですが,「自明な必要条件がそのまま十分条件にもなっている」というなかなか綺麗な結果です.
定理 (Kőnig)*1 任意の 部グラフ と任意の正の整数 に対して,以下は同値.
- 辺集合 が 個の完全マッチングに分割できる.
- すべての頂点の次数が である.
そして,この定理をマトロイドの言葉で言い換えると以下のようになります.
系 台集合 が共通である任意の つの分割マトロイド と任意の正の整数 に対して,以下は同値.
- 台集合 が 個の共通基に分割できる.
- それぞれに関して,台集合 が 個の基に分割できる.
というわけで,自然な疑問として,「上の系の分割マトロイドの部分を一般のマトロイドに置き換えるとどうなるのか?」ということが気になります.以下の反例は, で,一方が分割マトロイド,他方がグラフ的マトロイドであるような場合でも,上の系が(そのままの形では)拡張できないということを示しています.
反例*2 を 頂点完全グラフ,すなわち, で であるグラフとし, を の完全マッチングで互いに素なものとする.(必然的に は の分割となる.) を が誘導する分割マトロイド,すなわち,
とし, を が誘導するグラフ的マトロイド,すなわち,
とする.今 とすると, それぞれに関して,台集合 が 個の基に分割できることは簡単に確認できる.一方,共通基は必ずどこか 頂点を含む辺 本すべてを取る必要があり,そのような辺部分集合の補集合は閉路となるため, を 個の共通基に分割できないことがわかる.
*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)