組合せ数学セミナー
発表内容の概要

5/10(金): 中村政隆(東大・広域システム)
「マトロイドとアンチマトロイドのサーキット、コサーキット族とそのパッキング」

マトロイドの根付きサーキットと根付きコサーキットは互いにブロッカーになるが、
グラフの場合は常にパックすることは Menger の定理としてよく知られている。
ただし、一般のマトロイドではこれは成立しない。バイナリマトロイドのクラスの中で
パックするような良い性質を持つマトロイドであるための必要十分条件は、それが
Fano マトロイドの dual をマイナーとして含まないことであるということが Seymour
によって示されている。

アンチマトロイドでも根付きサーキット、根付きパスという概念が知られていて、
これも互いにブロッカーになる。これらのマトロイドとアンチマトロイドでのブロッカー対
のあいだにどれだけアナロジーが成立するか考えてみたい。

(1) マトロイド、アンチマトロイドを形の上で部分として含む閉集合族という概念を
    考えると、閉集合族で根付きサーキット、根付きコサーキットという概念が
    定義できて、マトロイド、アンチマトロイドの場合はそれの特別な場合になっている。
    その意味でマトロイドとアンチマトロイドのサーキット、コサーキットの概念を
    対比させて考えるのは、あながちまとはずれでもない。

(2) マトロイドにおける Seymour の定理に対応するアンチマトロイドの定理を確立したいが
    未解決である。Seymour がバイナリマトロイドのクラスに限って考えたことに対応して、
    realizable acyclic oriented matroid の定める凸幾何・アンチマトロイドのクラスの
    に限って考えるのが順当であると思われる。

5/24(金): 大杉英史(立教・理・数学)
「root system に付随する配置のグレブナー基底」

根系 $A_{n-1}$ の正根に付随するGKZ-超幾何方程式系の解空間の次元を計算するために，
Gelfand-Graev-Postnikov は根系 $A_{n-1}$ の正根に原点を加えた配置の正則単模
三角形分割を具体的に構成し，その配置の正規化体積がカタラン数${2n - 2 \choose n - 1} / n$
に一致することを示した．彼等の結果の本質はその配置のトーリックイデアルの２次 squarefree
単項式から成るイニシャルイデアル（をスタンレーライスナーイデアルとする正則単模三角形分割）
を発見した点にある．

Gelfand-Graev-Postnikov の結果に刺激され，根系$B_{n}，C_{n}， D_{n}，BC_{n}$ の各々について，
その根系のすべての正根に原点を加えた配置（あるいは原点を加えない配置や，その部分配置）の
トーリックイデアルのグレブナー基底を解析してこれまでに得られた結果について報告する．

6/7(金): (高畑貴志・基礎工学)
「 一般化最小独立フロー問題とその多項式時間アルゴリズム 」(江口, 藤重との共同研究)

  独立フロー問題は, 古典的なネットワークフローモデルの入口と出口のそれ
ぞれに, 劣モジュラ関数で表される流入/流出ベクトルに関する制約を加えた
問題です. 従来のネットワークフローに加え, マトロイド・インターセクション
等を記述できる離散最適化のモデルになっています.
  今回の研究では, 枝にゲインを考慮した最小費用独立フロー問題を提案しま
す. 各枝 a に与えるゲイン γ(a) は, 枝 a への流入量が γ(a) 倍されて枝
の出口へ届くことを意味します. 
  この問題に対して, 劣モジュラ関数が定める基多面体の交換容量をオラクル
とした, 多項式時間アルゴリズムを提案します. このアルゴリズムは, Wayne 
による一般化最小費用フロー問題 (ゲインのみを考慮し, 流入/流出ベクトルの
制限は設けない問題) に対する最小比率サーキットキャンセルによる多項式時間
アルゴリズムをベースに, 劣モジュラ関数の制約を扱うための工夫を加えたもの
になっています.
  今回は, この内容をできるだけ self-contained に話そうと思います.

6/21(金): 藤江哲也(神戸商大・商経・管理)
「安定集合問題，彩色問題に対する定式化とその緩和」

　Meurdesoifは``半正定値計画(SDP)＋整数制約''として彩色問題
を定式化し，その問題の緩和とLov\'aszの$\theta$-numberとの関
係を示した．$\theta$-numberは最大安定集合問題に対するSDP緩和
問題の最適値として特徴付けられる．
　本発表では，まず最大安定集合問題にSDP緩和についてまとめをし，
Meurdesoifの結果を紹介する．そして彩色問題に対する緩和がさらに
強化できるか検討する．

7/5(金): 河原林健一(Princeton Univ. & 慶應・理工)
「Hadwiger's Conjecture and the Four Color Theorem」

There are many conjectures and problems motivated by The Four Color Theorem.
Hadwiger's conjecture is one of them. In 1943, Hadwiger made the conjecture
that every $k$-chromatic graph has a $K_k$-minor. This conjecture is, perhaps,
the most interesting conjecture of all graph theory. It is well known that
the case $k=5$ is equivalent to the Four Colour Theorem, as proved by Wagner
in 1937. About 60 years later, Robertson, Seymour and Thomas proved that the
case $k=6$ is also equivalent to the Four Colour Theorem. So far, the cases
$k \geq 7$ are still open and we have little hope to verify even the case
$k=7$ up to now. In this talk, we will focus on recent progress on case $k=7$.
Also, we will discuss some recent progress due to Diestel, Robertson, Seymour
and myself, Reed and Seymour, and Toft and myself.