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

10/18(金): 八森正泰 (筑波大・社工)
3-球面の三角形分割と結び目
― Simon Kingの「polytopality」 ―

Simon Kingは2000年に3次元球面の三角形分割に対してpolytopalityと
いう概念を導入した．これは双対セル分割の1次元骨格に対する結び目
の橋指数のようなものである．これはある意味で三角形分割のきれいさ
を示す指標に使う事が出来，(単体的)凸多面体(の境界)⊂シェラブルな
分割⊂一般の分割，に従って上界値が大きくなっていく現象が示されて
いる．また，三角形分割を局所変形で凸多面体に変形するために必要な
操作の下界値を評価することもできる．また，三角形分割の1次元骨格に
含まれる結び目の橋指数や交点数の評価にも使える．本発表ではこの
polytopalityという概念をSimon Kingによるこれら一連の仕事とともに
紹介したい．

11/1(金): 青木 敏 (東大・情報理工学)
2次元周辺度数を固定した3x3xK分割表上の既約なマルコフ基底の構成

マルコフ連鎖・モンテカルロ法を用いて3元分割表に対する各種の条件
付検定を行うために、2次元周辺度数を固定した3元分割表上に既約なマルコフ
連鎖を構成する方法について述べる。特に、3x3xK分割表に対して、基底の最
小集合の具体形を求めたので報告する。

11/15(金): 亀井聡 (東大・数理)
Cones over the boundaries of nonshellable but constructible 3-balls

単体的複体の組合せ的性質として、shellability、constructibilityというものが知
られている。Constructibilityは、shellabilityを真に弱めた概念であることがわか
っており、実際、$3$-ballにおいて、shellabilityを満たさず、かつconstructibility
を満たすような例がZiegler, Rudin, Gr\"{u}nbaumらによって提示されている。一方、
$3$-sphereにおいて、二つの性質の「間」に位置するような例は今のところ知られて
いない。今回は、先の$3$-ballの例において、それらの境界におけるconeをとって得
られる$3$-sphereについて、そのshellabilityを調べることにより、$3$-sphereでの
二つの性質の「差」について考察したい。

11/29(金): 高畑貴志 (阪大・基礎工)
多品種フロー問題の組合せ的解法に関して

多品種フロー問題は, LPで定式化できるが組合せ的な多項式時間アルゴリズムが
知られていない代表的な問題である. 無向ネットワーク上の多品種フローで
さらに制限を加えると, 組合せ的なアルゴリズムで解ける場合がある. 今回は,
そのような論文のいくつかを紹介する. また, 有向ネットワーク上の多品種
フロー問題に対する近似解法の論文も紹介する予定である.

12/13(金): 中村政隆 (東大・広域システム)
アラインメントと系統樹構築のアルゴリズム ― バイオインフォマティクス入門

  アラインメントと系統樹作成の課題を中心にして、バイ
オインフォマティクスの入門的な話しをしたい。
  系統樹の構築アルゴリズムには、距離行列による方法と
樹形探索による方法がある。前者の代表的なものとして、
近隣接合法 (Neighbour Joining Method) があり、後者の
代表例として最大節約法 (Maximum Parsimony) と最尤法
(Maximum Likelihood Method) がある。
最後に最大節約法、最尤法などの樹形探索へのメタヒュー
リスティックアルゴリズムの応用を考えたい。

1/10(金): 柏原賢二 (東大・広域システム)
凸幾何の幾何学的表現定理

凸幾何は、組み合わせ的な凸性を抽象化したものといえる。
いろいろな組み合わせ構造が凸幾何をあらわすことが知られている。
ユークリッド空間内に点配置から定義される凸シェリングも
その一つである。今回の研究では、
取り除けない点をもうけた凸シェリングが作る
凸幾何を考える。そして、それが凸幾何全体のクラスと
一致することを示した。これにより、任意の凸幾何は、
ユークリッド空間内の点集合で表現できることが分かった。

1/31(金): 宇野毅明 (国立情報学研究所)
集合族の要素を差分定数の移動で全て訪れる

集合族の集合族（例えば任意のグラフに対する全張木の集合）
に対して、その要素である任意の集合族 F を
ハミング距離定数の移動で全て訪れることができるかどうかを、
列挙アルゴリズムを使って証明できることを紹介する。
平たく言えば、例えば、
「任意のグラフに対して、その全張木を頂点とし、ハミング距離定数の2点に
枝を張ったグラフがハミルトンパス（あるいは閉路）を持つか」
という質問に対し、列挙アルゴリズムを用いて証明が作れることを示す。

2/7(金): 井床利生 (東大・情報理工学)
六面体メッシュの生成法から

六面体メッシュ生成法の一つに、M. M{\"u}ller-Hannemann氏によって提案された
サイクル消去法がある。これは、あらかじめ対象立体の表面に四角形メッシュが
与えられた時、その表面メッシュに矛盾しない“組合せ的な”内部の六面体分割を
求める手法である。ただし、表面の四角形メッシュの構造によっては六面体分割が
求まらないことがある。実用的でない応用（個人的興味）として、「サイクル消去法
によって六面体分割可能な表面四角形メッシュのクラスを特定できないか」という
問題がある。本発表では、サイクル消去法について詳しく紹介した後、上記の問題に
ついて、単体的複体のVertex decomposabilityとの関連に着目して、考察したい。
（組合せ的:=六面体同士の隣接関係だけ定まり、各六面体の幾何学的形状は定まらないこと）

2/14(金): 来嶋秀治 (東大・情報理工学)
2×n 分割表のPerfect Sampling

本報告では、与えられた周辺和を満たす2行分割表の一様生成方法を提案する。
この方法では定常分布として一様分布をもつマルコフ連鎖を推移させて標本を生成する。
この方法はCFTP(Coupling From the Past)理論に基づいたアルゴリズムで、
標本は厳密に一様分布に従って生成される。
CFTP理論では全状態からの推移を追跡する必要があるが、
本報告では特定の2つの分割表からのcoalescenceが
全状態のcoalescenceの十分条件となっていることを示す。