組合せ数学セミナー
発表内容の概要
平面上に半径が同じディスクが散らばっているときに，重なりがあるディスクの中心を
結んでできるグラフをunit disk graphという．
unit disk graphに対する様々な組合せ最適化問題はNP-困難であることが知られている．
本発表では頂点集合が格子点に限定されるunit disk graphを扱い，
それがパーフェクトとなる条件を探る．
そしてその条件を利用して重み付き安定集合問題やマルチカラーリングの
近似アルゴリズムを構築できることを解説する．
関連する話題としてfractional coloring numberやimperfection ratioにもふれる．
ＤＮＡあるいいはＲＮＡの塩基列もしくはアミノ酸列から
系統樹を推定するアルゴリズムは、大別して、距離行列法、
樹形探索によるものに分けられる。今回は、距離行列法の中の
最大節約法、樹形探索による方法のうち Bayesian method に
ついて概説を示す。
tropical geometry (algebra) とは通常の加算・乗算をそれぞれmin・加算として再定義した
世界で考えるものであり，応用の例としては，例えばtropicalな意味での凸包を考えること
で，通常の多面体におけるFarkasの補題・カラテオドリの定理などの定理がそのまま成り立つ．
一方で，行列のランクは，通常の線形代数では互いに同値なランクの定義が，tropicalな
世界の行列では双方の間にギャップが生じることが知られている．
本発表では，tropical geometryおよびtropical algebraを題材とした論文から，いくつかの
トピックを選び，内容を紹介する．
凸幾何は，ある種の離散的な凸性を表現した集合族である．凸幾何のFree複体は，可縮である
ことが知られている．さらにどういう単体的複体がFree複体となりうるかに対して，Edelman &
Reinerによる予想が提出されたが，その予想を肯定的に解決したというのが，本研究の成果で
ある．
凸幾何は，有限集合の部分集合のいくつかを集めてきたもの，すなわち集合族で表現される．
凸幾何は，ある種の離散的な凸性を表現した集合族といえる．いろいろな離散的な対象物から，
凸幾何を考えることができる．大雑把にいうと，点集合が与えられたときに，どんどんと「外
側」から元をひとつずつとっていくような状況を考えて，どのように元をとることができるか
を表したものが凸幾何である．それぞれの段階でとれる元ととれない元があるわけであるが，
1度とれる状態になった元は，その先の段階でもとれるとする．
すべての元がとれるようになった集合をFree集合と呼ぶ．Freeな集合全体は単体的複体をなし，
それをFree複体と呼ぶ．凸幾何のFree複体のトポロジーは可縮であることが知られている．
しかし任意の可縮な単体的複体が，ある凸幾何のFree複体になるわけではない．Edelman &
Reinerは，凸幾何のFree複体になるための必要条件に関する予想を提出した．この本研究は，
その予想を証明したというものである．
この研究は筑波大の八森氏との共同研究である．
Coxeterグラフとは、Coxeter群と呼ばれる特別な群（対称群、二面体群、
実鏡映群、有限初等可換2-群、等々）を記述するのに用いられる、
辺重み付き単純無向グラフのことである。 Coxeterグラフを与えることで、
対応するCoxeter群の生成元とその間の関係式を特定でき、従って群の構造が
（同型を除いて）一意に定まる。また、有限位数を持つものや
アフィン型と呼ばれるものなど、様々なCoxeter群のクラスが
Coxeterグラフを用いて特徴付けられている。それらの意味で、
CoxeterグラフはCoxeter群の構造を非常に良く記述していると考えられている。
その一方で、「それらの定める群が互いに同型か否か」によって
Coxeterグラフの間に同値関係を定めることは自然であるが、
その同値類の分類については未だに部分的な結果しか得られていない
（例えば、与えられたCoxeterグラフについて、それを含む同値類を
決定する問題も限られた場合にしか解決されていない）。
今回は、上記のCoxeterグラフの分類問題に関する既存の結果と、
話者（縫田）による最新の結果について具体例を交えながら紹介する。
（Coxeter群に関する予備知識は仮定せず、self-containedに話を進める予定です。）
並列計算機でシミュレーションをするときに、各計算機で擬似乱数を発生
させて用いることがあります。（例： 核分裂の様子を調べるとき、空間を
小さな区域に分割して、それぞれの領域での確率現象を、各計算機で生成し
た擬似乱数を用いて計算させる。）しかし、近くの現象を扱う計算機が全く
同じ擬似乱数列を生成していたら、それによる偏りがおきてしまいます。相
関が大きい場所では、なるべく違う関数で生成された擬似乱数を用いた方が
正しい結果を得られます。何種類かの関数しかないときに、どのように割り
振れば良いでしょうか？ この問題はグラフの分散彩色問題として書き表す
ことができます。
本講演では、４色定理やラムゼー理論など、古くから行われてきたグラフ
の彩色に関わるグラフ理論の解説と、シミュレーションのためのグラフの分
散彩色の研究の紹介をします。
超平面配置とはアファインもしくは射影空間内の超平面たちの有限集合のことで
ある。超平面配置の補集合は開空間であり、幾何学的に興味深い対象で多くの応
用をもつ。補集合上の(ド・ラーム)コホモロジーは超平面配置の組合せから決ま
ってしまう(Orlik and Solomon 1980)。そこで、このコホモロジーを組合せのみ
で書き下したものをOrlik-Solomon 代数という。超平面配置の組合せ的な拡張と
してマトロイドが考えられ、自然にマトロイドの Orlik-Solomon 代数を定義す
ることができる。Orlik-Solomon 代数はマトロイドの組合せを反映させた性質を
持っている。ここでは、入門的な内容で基本的な性質や結果を紹介したい。
また、超幾何関数の一般化には局所系係数のコホモロジーが登場する。これは
Orlik-Solomon 代数のコホモロジーとして組合せ的に調べることができる。この
コホモロジーの消滅定理や非消滅についての最近の結果を紹介したい。
有向グラフが与えられたときに出来る頂点集合上の安定な分割について
研究します．有向グラフにa<-bという枝があることを頂点集合上の
2項関係のように思うことにします．a->bに対して，aはbの親といい，
bはaの子供と表現することにします．
安定な分割とは，任意の同値類A,Bに対して
B\subset {a|b<-a,b\in A}か，{a|b<-a,b\in A}\cap B=\emptysetか，
のどちらかが成り立つものと定義します．
安定な分割の全体は細分の関係で束になります．
この束について研究します．
束なのでもっとも粗い安定な分割が一つ存在することが重要です．
また，グラフの頂点に対して，次数付きランクというものを考え，
それと上の安定分割との関係も論じます．頂点の0次のランクを，
末端の頂点(子供のない頂点)からの最短の有向パスの長さと定義します．
頂点に対し，そこにたどりつけるような末端の
頂点がない場合はランクを無限大と定義します．
k次のランクをその頂点の子供の頂点
たちのk-1次のランクを集めてきた集合とします．
このようにしてランクを定義すると，十分大きくすると，
同じランクを同値として定義した同値類は，
もっとも粗い安定な分割と一致するということを示します．
この研究はもともとは，非有基的集合論(non-well-founded set theory)
というものがもとになっています．
これは，大雑把にいうと，通常のZF集合論から，
基礎の公理を除いたものです．a<-bという有向枝は，集合論の世界では
a\in bということになります．非有基的集合論においては，通常の
集合論と異なり，a\in bと，b\in aが同時に成り立つことが許されます．
このようなものは有向グラフの世界では
サイクルとして表現されることになります．
なお，われわれのグループ
(この研究は，山口和紀氏，堀江郁美氏との共同研究です．)
では，さらにウェブのハイパーリンクの構造の分析に
この有向グラフによる表現を用いています．
ウェブページ間にハイパーリンクがあるときに
a->bという有向グラフで表現します．有向グラフに対して，
最も粗い分割に対応するグラフの簡単化を
行ったときにグラフが簡単になることと，
分かりやすいウェブ構造との関連を調べています．
tight span とは距離空間に対して定義される幾何学的対象であり、
1964年に J. Isbellによって最初発見され、1984年に A. Dressに再発見された。
Dressは、84年の論文において
「距離空間がtreeであることと、その tight spanが tree であることが同値である」
ことを示し、系統樹の問題に対する tight span の重要性が認識された。
その後、tight spanの理論は「スプリット分解法」と呼ばれる
系統ネットワーク構築法を産み(Bandelt & Dress 92),
また、近年流行の兆しを見せている tropical geometry
の多くの概念が tight span と関連している。
本講演では、Dressのtight spanの研究を振り返りながら、
tropical geometryを概観したいと思う。
あるクラスのトーリックイデアルの生成系は，
多元分割表の正確検定に用いられる
“マルコフ基底”に対応することが知られている。
講演では，分割表に付随するトーリックイデアルの
基本的な性質について述べるとともに，
対応する配置の単模性や，対応するトーリック環の
正規性について紹介する。
トップに戻る