組合せ数学セミナー
発表内容の概要
スポーツのスケジューリングを考える際、
試合がどちらのチームの本拠地で行われるかは非常に重要な要素である。
本発表では、試合の開催場所が指定されているという条件の下で、
そこから矛盾の無いスケジュールを作成可能かどうか判定する問題と、
この問題に対するいくつかの結果を紹介する。
今回は新しい結果を紹介します。
立方的複体とは、多面体的複体で各面が(超)立方体と同型である
もののことで、ファセットはその極大な面、リッジはそれを含む
1次元高い面が必ずファセットであるような面のことを指すことに
する。ここで、立方的複体のファセットとリッジの接続グラフ上
の非巡回的向き付けで、各リッジの入次数が1以上であるものを考
え、その中で、ある目的関数を最小化する。このときに、ある条件
下で、立方的複体のトポロジーに関する情報が得られることを示す。
また、この枠組におけるいくつかの興味深い定理も合わせて紹介
したい。
与えられたトーリックイデアルに対して，ある単項式順序が存在して，
その順序に関する被約グレブナー基底が次数２の２項式からなる場合，
対応する semigroup ring は代数的に良い性質を持つ事が知られており，
このような性質を持つトーリックイデアルのクラスを発見する事は重要である。
発表では，更に良い性質を持つ例として，ある単項式順序が存在して，
被約グレブナー基底が次数２の２項式からなるだけではなく，
その Rees 代数のトーリックイデアルまで同じ性質を持つようなクラスについて解説する。
また，このクラスに属する例として，pure poset に付随するものを挙げ，
あるSagbi 基底（Subalgebra Analogue to Groebner Bases for Ideals）の
計算に対する応用を紹介する。
単純無向グラフが与えられたとき、隣り合う点同士の色が異なるように
点に色を塗ることを (vertex) coloring という。
coloring で使われる色の最小数を、
グラフの coloring {chromatic} number という。
単純無向グラフに加えて点に非負整数重みが与えられたとき、
隣り合う点同士で使われる色に重なりがないように
各点に重みの数だけ色を塗ることを (vertex) multicoloring という。
multicoloringで使われる色の最小数を、
グラフの multicoloring number という。
簡単に（多項式時間で）coloring number を求められる、
そして簡単に coloring number で塗れるグラフであっても、
与えられた点重みに対して multicoloring number を簡単に求められる
とは限らないことが知られている。
本発表ではそのようなグラフの例として Lattice Graphs with Diagonals
を取り上げ、かなりタイトな近似解法を提案する。
また、その周辺の話題を簡単に報告する。
クラッターの研究で中心的な予想としてクラッターがpacking propertyをみた
すならばMFMCであるという予想があり、またそれを導くような、より強い予想
として、ブロッキング数が3以上のideal minimally non-packing clutterは存
在しないという予想がある。今回の発表は、後者の予想と関連した結果を発表
するものである。
minimally non-packing clutterには、minimally non-idealと、ideal
minimally non-packing clutterの2種類に分けられることが知られている。
minimally non-idealについては、coreという概念を通じていろいろなことが
調べられているが、上の予想により関係が深い、ideal minimally
non-packing clutter のほうに関してはブロッキング数が2のideal minimally
non-packing clutter がどういうものがあるかが調べられているくらいで、あ
とは大したことが分かっていない。
われわれの研究では、台集合E上のクラッターに対して次のような多面体を考えれば
いいことを提案している。
\tau(C)をクラッターCのブロッキング数として、
(1) 任意のa\in Eに対して、0 \leq x(a) \leq 1
(2) 任意のブロッカーBに対して、1 \leq \sum_{a\in B} x(a) \leq |B|-\tau(C)+1
を満たすxからなる多面体である。
この多面体は必ず非空になり、minimally non-packing clutterに対してはこ
の多面体の頂点がすべて非整数頂点であることが示される。そして、J_kとい
うタイプ以外のminimally non-idealに対しては多面体は1点になりcoreに一致
する。ideal minimally non-packing clutterに対してはこの多面体は1点にな
ることはないことが示される。そして、ブロッキング数が2のideal minimally
non-packing clutterに対応する多面体は八面体になることを証明する。他に
も、この多面体を研究していくことで、ideal minimally non-packing
clutterに関していろいろなことがわかることが示される。
なおこの研究は東京大学の佐久間雅氏との共同研究である。
コマゼミに出席できないけれども、研究に興味があるかたはお知らせ下さい。
ゼミの終了後になると思いますが、メールでレジュメを送ります。
matroid と基点との対は pointed matroid と呼ばれ、
圏をなすことが知られている。
pointed matroid と同値な qusai-matroid を定義すると
matroid のある種の一般化になることを示します。
そして、既存の matroid にはいろいろな構成法:
single-element extension, moduler cut, quotient, lift.. など
が知られているが、
それらの関係を matroid の triple を通して整理する。
さらに、グラフ理論から考えられている Steiner complex の概念と
qusai-matroid は同等であることとその位相的な性質を紹介したい。
また、qusai-matroid の Orlik-Solomon (O-S)代数が、
超平面配置の理論同様に定義される。
qusai-matroid の O-S 代数と matroid の O-S 代数との
関係を紹介したい。
2部グラフの辺彩色問題に対する O( m log d + m/d log m/d )
時間のアルゴリズムを紹介します．(ただし, 辺数 m 最大次数 d)
この結果は，Makino−Takabatake−Fujishige の正則2部グラフに
対する完全マッチングアルゴリズムを応用して得られます．この
辺彩色問題の解法としては，Cole−Ost−Schirra によるスプレー
木を用いた O( m log d )時間の組合せ的解法よりも遅いのですが，
スプレー木などの複雑なデータ構造を必要としないという利点が
あります．
複雑なデータ構造を用いないでできる既存の組合せ的アルゴリズム
としては，Rizzi および Makino−Takabatake−Fujishige による
O( m log d + m/d log m/d log d ) 時間や Schrijver による
O( m d ) 時間のものが知られていました．
今回のコマゼミでは，関連するアルゴリズムの簡単な説明も加え
self-cotained になるよう努めます．アルゴリズムの動作が，互除
法やオイラーの小定理に対応して，少し整数論っぽくなってます．
トップに戻る