組合せ数学セミナー
発表内容の概要
初回10/10と10/17と2回連続で
「Grinsteadの予想とStrong Perfect Graph Conjecture」
という題で話させて頂きます。
Strong Perfect Graph Conjecture(SPGC)は、グラフ論における有名な未解決
問題で、1960年にBergeが予想して以来、多くの人が取り組みましたが、未だ
に解決していません。回転対称性をもったcircular graphといわれるクラスで
すら、成り立つのかどうかわかっていません。しかし、このクラスに関しては、
Grinsteadの予想(84年)を肯定的に解いたならば、成り立つことが分かってい
ます。
本発表は従来はクリークの大きさが5までしか解決してなかったGrinsteadの予
想を、うまい方法を思い付くことにより、クリークの大きさが15程度まで計算
で予想の正しさを確かめることが出来たというお話です。
最初にSPGCの紹介をちょっとしたあとは、グラフ論的な話からすこし離れて、
話の中心は線形の方程式系に01解があるかどうか、それからほんのちょっ
と、巡回群など簡単な代数の話が絡んできます。
今後はGrinsteadの予想を一般に証明することを目標としているので、いろん
な人のアドバイスを聞いてみたいです。沢山の方の御参加をお待ちしておりま
す。
なお、この研究は東京大学佐久間雅氏との共同研究です。
10/10($\omega=6$の場合の証明)
Strong Perfect Graph Conjecture(SPGC)の紹介
Circular partitionable graphとGrinstead Conjecture
$\omega=6$の場合(第1世代)
$\omega=6$の場合(第2世代)
10/17(一般の場合の計算)
復習をすこし
一般の場合の計算法(第1世代)
一般の場合の計算法(第2世代)
01整数計画solverをつかって
一般の場合の予想の証明にむけての見通し
議会においては, 各党が保有する議席数, 法案決定に必要な賛成の票数によって,
各党の発言力は変化する. その発言力を数理的なモデルを用いて
表現したものが投票力指数である. いくつかのモデルが提案されており,
それぞれについて, その指数を計算するアルゴリズムが研究されている.
本稿では, これらのアルゴリズムの改良方法を示し, 1つの党の指数計算と
同じ計算量で, すべての党の指数を計算するアルゴリズムを提案する.
自由リー代数は（有限）alphabet 上生成される次数付無限次元リー代数で,
その斉 n 次空間は n 枚の leaf を持つ (labelled) binary tree で記述される.
今回の話は, この自由リー代数（の multilinear part）上での対称群の
表現を考え, 特に巡回表現の指標の characteristic がこの文脈から
いかに導出されるかを解説する. 対称群の表現論に関する基本的な事実の解説も
適宜行いながら話を進めていく予定である.
suppot vector machine(ＳＶＭ)は，Vapnikにより開発された、
パターン認識における学習手法のひとつであり，入力データを
kernel関数を用いて非常に高次なfeature spaceに写像し，
厚みを持つ超平面でそれらを分類する．
今日では，その応用は画像解析，時系列データ解析，DNA解析，
文章構造解析などに及び ，また，その判別の誤判別率の推定の
精度を上げるための研究も続けられている．
今回はＳＶＭの原理と，その長所，現時点での問題点などに
ついての一般的な説明を行なう．
1993年にBerrou らによってシャノン限界に極めて近い特性を
与える符号として Turbo code が提案された．
そこで今回は，Turbo code の基礎となる畳み込み符号を定義し，
Turbo code の符号化，復号化について説明する．
また，Turbo code において問題とされている反復復号による，
復号時間，復号遅延の増大が問題とされている．そこで，並列
復号法を用いたときにその特性を生かした復号停止規範について
説明する．
集団遺伝学の基礎原則として知られる Hardy-Weinberg 則（平衡仮説）は，
任意結婚と遺伝子頻度に関わる重要な理論である．Hardy-Weinberg 則の検
定には古典的な適合度検定が用いられることが多いが，サンプル数が小さい場
合やいくつかのアレル頻度が小さい場合には，漸近カイ二乗性の当てはまりの
悪さが指摘されており，漸近論を用いない正確検定が必要とされる．
Louis and Dempster (1987) は，アレル頻度を固定した上でのすべての遺伝子
型頻度の数え上げによる正確検定のアルゴリズムを提案し，アレルの数が 3
または 4 の場合の小さいサイズのデータに対して p 値の計算を行なった
が，よりサイズの大きなデータに対しては，計算量の問題が生じる．本研究で
は，正確検定の p 値をより効率的に計算するアルゴリズムを提案し，Guo and
Thompson (1992) の提案した MCMC 法との比較を行なう．
整数計画問題に対して toric ideal を用いた計算代数的アプローチとして，
・グレブナ基底を用いたもの
・standard pair を用いたもの
がある．ここでは，特に後者に着目し，強多項式時間で解けることの示されてい
る有向グラフの最小費用流問題を題材にして有効性を考える．
本発表では，standard pair について説明し，もっとも基本的な無閉路トーナメ
ントグラフの場合においても，関連する計算量(standard pair の数)が定数の場
合と指数オーダになる場合があることを示す．
HITS: Webの部分グラフを表す接続行列から、
あるトピックに関するauthority(そのトピックで多くの人が
権威があると思っている)サイトとhub(多くのauthoritiesに
リンクを持つ、すなわち良いリンク集)サイトを見つける
アルゴリズム。(Kleinberg '98)
Small-World: 昔から社会学の民間伝承とされてきたsmall-world
現象="我々は皆短い「知り合いの鎖」でつながっている"について。
small-world現象は一般の社会だけでなくWebグラフの世界でも
成り立つのではないかと考えられている。
社会学者Milgramはアメリカで手紙による大規模な実験
(住所を知っている知り合いでない人に手紙を送るのだが、
その際、知り合いからその知り合いへと手渡してゆく)
をおこない、任意の2人が5-6人の「知り合いの鎖」で
つながっていることを見つけた。
この「短い知り合いの鎖」が存在し、しかも上の実験で用いたような
アルゴリズムがうまくいくようなグラフとはどのような
グラフなのか示す (Kleinberg '00)
大きさnの二分木について、rotationと呼ばれる操作で生成されるグラフは、
n+2角形のdiagonal flipにより生成されるグラフと同型になります。Sleator,
Tarjan, Thurstonは、n>12のとき、このグラフの直径が上から2n-6で押さえ
られることを示しました。さらに彼らは、このグラフでの適当な二点を繋ぐ
pathと、B^3上の三角形分割との対応を利用し、nが十分大きいときには直径
が真に2n-6に決まることも示しました。
一方実際の計算により、このグラフの直径はn>12においては全て2n-6に一致
することが予想されていました。
今回は上記の結果を紹介するとともに、予想解決へのアプローチについてお
話したいと思っています。
各項の値が漸化式を用いて比較的簡単に計算できるような数列の
クラスとしてP-recursive sequenceというクラスがあります。また、
ある数列がP-recursiveなことと、その母関数がD-finiteという性質を
持つことが同値ということが知られています。今回の発表では、
R.P.Stanley, L.Lipshitzらの理論に基づいて、一見複雑な
漸化式・一般項を持つ数列の比較的簡単な漸化式を求める
具体的なアルゴリズムを紹介したいと思います。
なお予備知識としては、線型代数の基本的な知識があれば
理解できるような内容にする予定です。
生命科学の重要な課題のひとつに進化に対する知見を深めることがある。
進化については、ダーウィンに始まりたくさんの研究がなされたが、近年の
コンピューター技術の発展に伴って、進化そのものをコンピュータシミュレ
ーションによって表現可能になりつつある。
そのような表現の始まりともいえるのが、Tierra である。Tierra とは、
人工生命の分野で研究が進んでいる進化シミュレーションであり、仮想マシ
ン語で記述された自己複製プログラムを進化させることが出来る。
本発表では、Tierra においてプログラムがどのようにして自己複製する
か、またどのように進化するかを示し、その考えを植物系のシミュレーショ
ンに応用した場合を考える。
植物系のシミュレーションにおいては、ある程度のパラメータによって、
進化によって意図した環境を得られるかどうか、また進化によって得られる
環境は、その設定の時点で推測可能であるかを考察する。
d次元の純な単体的複体に対して、d次元の面(ファセット)とd-1次元の面(リッ
ジ)の接続関係のみの情報では一般には複体全体の情報は完全には得られず、
トポロジーを特定することすらできない。しかし今回は、これに加えて面の総
数が分かれば複体がshellableであるかどうかを判定できるという、少し直感
に反した結果を紹介する。この結果はshellabilityをグラフの非巡回的向きづ
け上での最適化問題として特徴づけることによって得られるのであるが、余裕
があれば、関連するグラフの非巡回的向きづけに関連する問題にも触れたい。
この話は東大・情報科学の森山園子さんとの共同研究に基づきます。
本発表では, {0,1}^m ×{1,2,...,n}分割表をランダムに生成する
Markov chainを提案する. 提案するMarkov chainは,path coupling法
[Bubley and Dyer 1997]を用いて, mixing timeを 分割表の列数,
分割表中の数値の総和,精度の逆数の多項式でおさえている.この
Markov chainは,2000年に,Dyer and Greenhill によって提案されたも
のの拡張である.
本研究は,松井知己氏(東大・計数)と小野陽子氏(東京理科大・経営工学)との
共同研究である.
トップに戻る