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

4/5(水): 大杉英史(阪大・理・数学)
「凸多面体の三角形分割とグレブナー基底」

有限個の格子点の集合が与えられたとき，その凸閉包の正則三角形分割の
Stanley-Reisner ideal と，対応するトーリックイデアルの initial ideal
の radical ideal が一対一に対応することが知られている．( [1, chapter 8] 参照)
（initial ideal はグレブナー基底を用いて計算される．）

本講演では，その対応について概説するとともに，ある種の凸多面体の三角形分割に
関する問題への応用について述べる．

参考文献：
[1] B. Sturmfels, ``Groebner Bases and Convex Polytopes,''
Amer. Math. Soc., Providence, RI, 1995.

4/12(水): 岡本吉央(東大・総合文化・広域システム)
「アンチマトロイドのマイナー」

アンチマトロイドは先行関係を組合せ論的に一般化した概念です．例えば，安
部さんや安藤さんの発表でも触れられた半順序集合のイデアル全体の集合はア
ンチマトロイドの1つの例です．他にも，道路を建設する問題や城郭を攻略す
る問題などにも現れて来ます．マトロイドとも関係はあるのですが，全く別の
ものです．

本発表では，アンチマトロイドとはどういうものなのか，という紹介と，その
マイナーに関連した話題をお話しようと思っています．特に，グラフの探索に
よって得られるアンチマトロイドの禁止マイナー型特徴付けに重点を置くつも
りです．

4/19(水): 竹内史比古(東大・理・情報科学)
「2次元の単体的複体のいくつかの再帰的な分解の関係--- shellability, extendable shellability, vertex decomposability」

森山園子さん（東大）との共同研究

[概要]

与えられた2次元の単体的複体、つまり3角形の集合を、分解／構成していくこ
とを考える。3角形の全順序、あるいは頂点の全順序で、「きれいに」単体的
複体を構成していく方法として shelling などがある。逆に、きれいな構成の
方法がある単体的複体は、きれいな／単純な形をしていると思ってもよい。

shellability, extendable shellability, vertex decomposability はいずれ
も、単体的複体の（再帰的な構成のしやすさから見た）きれいさを規定する性
質である。これらの性質の間の関係を考え、2次元の場合について、新しい結
果も紹介する。

これらの性質の関係する話題として、凸多面体の面の数の上限定理 
[McMullen]、凸包の効率的計算 [Seidel]、Hirsch 予想との関連 [Billera,
Provan] などがある。

1月17日の COMAセミでの八森さんの発表とも強い関連があります。

[ちょっと専門家向けのアブストラクト]

We give new examples of shellable but not extendably shellable two
dimensional simplicial complexes.  They include minimal examples,
which are smaller than those previously known.  We also give examples
of shellable but not vertex decomposable two dimensional simplicial
complexes.  Among them are extendably shellable ones.  This shows that
neither extendable shellability nor vertex decomposability implies the
other.  We found these examples by enumerating shellable two
dimensional simplicial complexes which are not pseudomanifolds.  A
rather efficient algorithm for this enumeration is also given.

[参考文献]

Anders Bj{\"o}rner,
Topological methods,
in Handbook of combinatorics, pp.1819--1872, Elsevier, Amsterdam, 1995. 

Richard P. Stanley,
Combinatorics and commutative algebra,
Birkh{\"a}user, Boston, 2nd ed., 1996.

G{\"u}nter M. Ziegler,
Lectures on polytopes,
Springer-Verlag, New York, 1995.

4/26(水): 徳永裕己(東大・理・情報科学)
「量子計算のアルゴリズム」

量子計算の基本的概念と有名なアルゴリズムについて紹介します．
（量子力学の知識はなくても大丈夫です．）
「ちょうど半分か？」「周期はいくつか？」など，古典的には効率的に
解くことが難しい問題を量子の特徴である重ね合わせと干渉効果を用いると
効率的に解くことができます．
Shor の素因数分解の多項式時間アルゴリズムについて詳細に紹介します．
量子計算による「周期発見」と，整数論の知識を組み合わせた証明は
他にも参考になることがあると思います．
また，N個の未整列の要素から欲しい要素を O(√N)で探索する
Grover のアルゴリズムについても紹介をしたいと思います．

参考文献
[1] P. W. Shor, "Algorithms for quantum computation: Discrete logarithms 
and factoring," FOCS, pp. 124--134 (1994); SIAM Journal on Computing, 
Vol. 26, No.5, pp. 1484--1509 (1997). 

[2] L. K. Grover, "A fast quantum mechanical algorithm for database search,"
STOC, pp. 212--219 (1996). 

5/10(水): Zhan Ping(江戸川大・環境情報)
「The monotonic diameter of bisubmodular polyhedra」

  (0,1)Hasse図を(0,1,-1)までに拡張した概念など
を利用して、 bisubmodular polyhedra の
monotonic diameter が tightly bounded ｂｙ $n^2$
であることを説明します。

5/17(水): (鈴木泰博・東京医科歯科大学・難治疾患研究所 生命情報学)
「マルチ集合書き換え系を用いた抽象化学系のふるまいについて」

抽象化学系とは複雑系、人工生命の研究領域に属する比較的新しい研究領域で
ある。我々は、マルチ集合書き換え系を用い，抽象化学反応系 (Abstract
Rewriting System on Multisets, ARMS)を定式化し、その性質等について研究
をすすめてきた。ARMSとは直観的には、化学溶液内での化学反応のモデルに相
当する。具体的には化学溶液はマルチセットに、化学反応式は語の書き換え規
則に、反応は語の書き換えによって表現される。また，我々は，「膜」をARMS
に導入することにより、細胞膜計算モデルを構築した。細胞膜は膜物質により
構築され、それらは細胞内での化学反応により生成される。具体的には膜物質
とは任意に定められた語に相当し、マルチセット内の膜物質の数がある一定量
を超えると、膜が生成される。このモデルは 1998 年に G.Paun (ルーマニア
科学アカデミー 数学研究所) が提案した形式言語モデル P Systems に密接に
関係しており現在，共同研究を行っている。講演では ARMS の紹介，計算機実
験の結果について述べる．

尚，講演者は数学者ありませんで，定理も証明も出てきません．ただただ計算
機実験の結果のみです．「万が一」興味を持った方がいらっしゃれば，いろい
ろとご教示いただければと存じます．

5/24(水): 塩浦昭義(上智大・工・機械工学)
「線形及び整数計画問題に対する主算法の計算量について」

線形及び整数計画問題に対する一般的な解法とのひとつとして, 
主算法が挙げられる．主算法の計算量は，解の更新の際に用いる
探索方向に依存する．本発表では, ある種の比を最小化する
探索方向を用いた主算法(最小比閉路消去法)に注目する．
本発表では, 最小比閉路消去法について説明するとともに, 
線形及び整数計画問題に対し，この算法が多項式回反復で終了
することを示す．また，主内点法との関係についても述べる．

5/31: 柏原賢二(東大・広域システム)
「凸幾何上の貪欲算法と多面体分割」

コマゼミにおける安藤さんの発表でも紹介されたように、Kr\"uger(2000)は与え
られた半順序集合のアンチチェーンの全体上に定義された関数がgreedy
algorithmで解けるためには、b-submodularという条件が必要十分条件である
ことを示した。今回の研究では、半順序集合のアンチチェーンを凸幾何一般に
拡張した枠組で議論する。そしてgreedy algorithmが通用するような関数の範
囲を特定する。最後に集合関数に付随する多面体の面構造と、greedy
algorithmがどのように関係するのか解説する。(岡本吉央氏との共同研究)

submodular関数の最適化問題について基本的なところからお話します。

6/7: 宮本裕一郎(東京商船大・流通情報工学)
「unit disk graphとチャネル割当問題」

本発表では，頂点彩色問題の問題例としてunit disk graphが
与えられた場合について説明し，頂点彩色問題の拡張である
チャネル割当問題とその解法の紹介をする．
unit disk graphの定義は下記のとおりである．
チャネル割当問題の定義については

を参照していただきたい．
前半は，unit disk graphの頂点彩色問題に対するいくつかの
（近似率保証付）近似解法を紹介する．近似保証の手法として
初等幾何学を用いたものから，ネットワークフローを用いたものまで
さまざまである．
後半は，チャネル割当問題に対して分枝限定法を適用した結果と
近似・発見的解法を適用した結果を報告する．

unit disk graph:2次元平面上に頂点集合が存在するとき，
全ての頂点対について，頂点対間の距離が1以下ならば辺で
結んで生成される図をunit disk diagramと呼ぶことにする．
頂点に2次元座標を与えることによってunit disk diagramに
なりえる単純グラフをunit disk graphと呼ぶ．

6/14: 岩田覚(東大・工・計数)
「劣モジュラ関数の最小化」

劣モジュラ関数の最小値を求めるアルゴリズムを解説する．
この問題は, 1981年に, Groetschel, Lovasz, Schrijver に
よって, 多項式時間で解けることが示された．しかし，彼らの
方法は，楕円体法を用いているため，実際には，効率的な
アルゴリズムとは言えない．昨年の夏に，我々のグループ 
(Iwata, Fleischer, Fujishige)と Schrijver とが，独立に
組合せ的な強多項式時間アルゴリズムを開発した．本発表では，
劣モジュラ関数に関する基礎から出発して，両者のアルゴリズムを
解説する．

6/21: 萩田真理子(慶応大・理工・数理科学)
「差集合の存在性について」

TeXファイル

差集合とは有限群 $G$ の 部分集合 $D$ で
群環 $ZG$ 上で $DD^{(-1)}=n \cdot 1+\lambda G$ 
（$D=\sum_{d \in D} d$, $D^{(-1)}
=\sum_{d \in D} d^{-1}$, 
$G=\sum_{g \in G} g$ とおいた）をみたすもので, 
群上のブロックデザインとなっていて
代数と組み合わせ論の
交わる分野にあり, 古くからその存在条件についての
研究が進められている. 
通常具体的な 差集合 を表わす時は
群のサイズ $v$, 部分集合の大きさ $k$, と上記の
$\lambda$ を添えて, $(v,k,\lambda)$-差集合 
と書く. また上定義にある $n$ はその差集合 
の位数と呼ばれる. 空集合, 1点集合, 
及びそれらの補集合は必ず差集合となるが
これらは自明な差集合とし区別する. 

現在多くの未解決予想が提示されているが, 
その最も重要な問題の一つに, Ryser予想として知られる
「巡回群 $Z_v$ に自明でない差集合 
が存在するなら位数 $n$ と 
$v$ は互いに素」というものがある. 
また, この一部である
「サイズが $4$ をこえる Circulant Hadamard 
Matrix は存在しない」, 
「二面体群 $D_{2l}$ に自明でない差集合は存在しない」, 
という予想も最近の話題の中心となっている. 
これらの予想を解決することを目標に, 
群 $G$ とパラメータを決めた時に 
$G$ の正規部分群 $N$ について, 
$Z(G/N)$ での 差集合 の像が
みたさなくてはいけない組み合わせ論的条件と 
指標の上での整数論から導かれる条件とを合わせて
存在条件をせばめていく, という方針で
研究を進めてきた. 
この方針は上記予想の $Z_l$ や $D_{2l}$ 
についても有効で, 
「差集合の位数 $n$ を割るどの素数 $p$ 
も $Z[\xi_l]$ で複素共役不変な素イデアルにしか
わかれないための条件：
$p^i \equiv -1$ (mod $l'$) をみたす $i$ がある
（ここで $l'$ は $l$ の $p$-free part）」
という整数論的特殊性を仮定すれば
予想も示せている. 

アーベル群の場合については, Jungnickel(1992) が
 差集合 の order $ｎ$ が $30$ 以下の
場合についてのこの問題の答えのリストを与えている. 
ここには３つの群, 
$Z_4\times Z_8 \times Z_3$ と 
$Z_2\times Z_2 \times Z_8 \times Z_3$,  
$Z_2\times Z_4\times Z_4 \times Z_3$ の 
$(96,20,4)$-差集合 の存在性
だけが未解決問題として残されていた. 
これらは既に,  Arasu, Davis, Jedwab, Ma, McFarland  
により解決されているが,  
円分体の整数論を用いた別の手法で
同じ結果を含み,  非可換群を含む
より広い群について利用できる 
差集合 が存在するための 
群の指数の上限を導いた. 

次に, この指数の上限を用いて, 
二面体群と類似する 
generalized quaternion groups 
$Q_{2^l}:=$ 
の 差集合 
をすべて決定した: generalized quaternion group の 
nontrivial 差集合 は, 
$Q_{16}$ の $(16,6,2)$-差集合のみである.  

ここで得られた群の指数の上限と 
Jungnickel のリストでは, 
アーベル群の 差集合 は
指数が低く階数の高い群にほど存在しやすい
傾向がみられる. 
そこで同じ位数のアーベル群で $p$-シロー群の形だけが
違う群をいくつか用意し, 差集合を
すべて見つけてみると, 多くのパラメーターで 
指数が低く階数が高い群ほど
たくさんの解をもち, また異なる群での
解たちの間に構造の似たものが現れる
ことがわかったので, 
実際に指数の高い群 $G=Z_{p^m} \times K$ 
から同じ大きさで指数が低い群 $G'=Z_{p^{r_1}} 
\times Z_{p^{r_2}} \times \dots \times 
Z_{p^{r_s}} \times K$ への, 群準同型ではないが
代数的構造を大きくは崩さない
辞書式順序による折り畳み写像と名づけた写像をつくり, 
いくつかの条件をみたす差集合は
同じパラメーターの差集合
に移ることを示し, この傾向を裏付けた. 
また, この折り畳み写像は差集合
だけでなく, 群環上のいくつかの条件をみたす
元の指標の値を保つことを示し, 
relative difference sets, building sets,  
group invariant weighing matrices 
等の組み合わせ論の対象も保つことも示した. 

6/28 宮川幹平(電通大・情報工学)
「進化系統樹最節約復元問題の数理的研究」

解析されたDNAや蛋白質の配列データ等から生物の系統進化を研究する進化
生物学、分子系統学、分類学などの分野において、生物の進化系統樹を推定
するという問題が議論されている。推定する手法のひとつとして最節約法が
挙げられるが、この「系統樹の長さが最小となるように」系統樹を推定する
という問題を数理的に定式化した最節約復元問題(MPR問題)について述べる。
この「系統樹の長さが最小となるように」という基準は最節約原理と呼ばれ
ている。
MPR問題は大きく2種類に分類され、一つは系統樹と、そのもとで観察可能な
種(=頂点)の形質値が既知な状態で、形質値が未知な種について最節約原理の

もとで最適な形質値を求めるという問題。もう一つは観察可能な種の形質値
のみが既知で、樹形と未知な中間種の最適な形質値を求めるという問題である。
今回は主に前者について、その最適解の性質やアルゴリズムをこれまでの研究
の流れを踏まえて紹介する。