組合せ数学セミナー
発表内容の概要
あるグラフGにおいて、各辺が独立に確率pで存在、確率(1-p)で非存在という
状況を考え、グラフの不変量fの期待値f(G;p)を考える。
例えば、fとして、グラフが連結なときに1、非連結なときに0、というもの
を考えると、f(G;p)は全端点信頼度になるなど、特にネットワークの性能の評
価において有用となる考え方である。
今回は、この不変量をp∈[0,1]で一様ランダムに選んだ場合の期待値u-f(G)を
考える。これは、Bailey, Gordon, Patton, Scancellaがある不変量に対して
提案したものを、上記の枠組で一般化したものにあたる。このu-f(G)を計算する
方法やその性質を紹介したい。
無向グラフとその頂点上のいくつかの始点・終点ペアーが与えられたとき，
始点から終点への有向路が短くなるように無向枝を向きづけする問題を扱う．
向き付けの目的としては，始点・終点間有向最短路長の和の最小化と
始点・終点間有向最短路長の最大値の最小化を扱う．
また，無向グラフの枝に長さが与えられた場合も扱う．
本研究では，この問題の難しさ（計算困難性）を，
与えられた無向グラフのクラスごとに場合分けして論じる．
例えば，平面グラフならばNP-困難，サイクルならばクラスPである．
当日の発表では，問題設定と全体の概要を述べた後で，
（リクエストに応じて）いくつかの場合を詳しく述べる予定です．
本論文では以下のように定義される劣モジュラ集合被覆制約を持つ劣モジュラ
関数最小化問題を考える．入力としては，台集合 N，非負劣モジュラ関数 f と
単調非負劣モジュラ関数 g が与えられる．求めるべきものは g(X) = g(N) を満
たす N の部分集合 X のうち f(X) を最小化するものである．
この問題は Iwata & Nagano (FOCS'09) によって考えられた劣モジュラ費用関
数を持つ集合被覆問題の一般化となっている．本論文では，この劣モジュラ集
合被覆制約を持つ劣モジュラ関数最小化問題に対しても，Iwata & Nagano に
よって提案された，劣モジュラ費用関数を持つ集合被覆問題に対する主双対
近似アルゴリズムが素直に拡張できることを示す．
積分を含んだ関数の最適化問題を考える. 勾配法などの反復解法によりこれを
解こうとすると, 反復ごとに数値積分が必要となり, 特に多次元の積分の場合は
計算量が大きくなる. 本講演では, 数値積分の回数を減らすための方法として
ホロノミック勾配法 (holonomic gradient descent) を提案する. ここで, 被積分
関数にはホロノミック性という条件を仮定する. ホロノミック性を利用して, 最適解へ
収束する常微分方程式を構成し, これを数値的に解くというのがアイデアである.
必要な数値積分は常微分方程式の初期値計算のみとなる. 常微分方程式の
導出には, 微分作用素環における代数的なアルゴリズムが使われる.
応用例として, 統計学における Fisher-Bingham 分布族の最尤法について述べる.
本研究は, 高山信毅, 竹村彰通, 中山洋将, 西山絢太, 野呂正行, 小原功任各氏との
共同研究である (講演者の貢献は主に統計学への応用の部分).
本発表は八森正泰氏・松井泰子氏との共同研究に基づいています．
有限単純グラフGのindependece complexとは，Gの補グラフの
flag complexとして定まる単体的複体です．この複体のトポロジーは
グラフの組み合わせ構造に強く依存することが知られています．
ここでは既知の結果を簡単に紹介した後で，graded poset や
intersection propertyを持つ正則胞複体に対して，そのindependence complexを
考えて見たいと思います．そして具体例を通して，independence complexのトポロジーと
正則胞複体の組合せ構造の関係を考察したいと思います．
2項関係PがQより強いとは、「x P y ならば、x Q yが成り立つ」ということである。
ある半順序を固定したとき、同じ台集合で、より弱い関係となる半順序の全体は、
強弱関係で束になる。つまり、それぞれの半順序が束の各要素になる。その束は
凸幾何である。
半順序は、x>yの関係があるときに、xからyへの有向辺を引いて作ったtransitively
closed acyclic digraph と同一視できる。半順序全体の凸幾何は、この有向辺を
transitivityを崩さないように一つづつ除くことによって作る凸幾何と同じである。
この凸幾何は、アフィン空間内の点配置で表すことができる。今回は、台集合の点
を単体の中の面の重心に対応させて、2つの凸幾何が一致することを示す。
transitively closed acyclic digraph ⊂ acyclic digraph
⊂ アフィン点配置 ⊂ acyclic oriented matroid
という包含関係があるが、それぞれ対応する凸幾何のクラスを考えることができる。
半順序の強弱関係の定義する凸幾何は、この対応におけるtransitively closed
acyclic digraph に対応する凸幾何と同じである。この意味で、半順序とは、アフィ
ン点配置の特殊なものと考えることもできる。
本研究は、東京大学の中村政隆先生との共同研究である。
(0,1) 正方行列Xがレーマン行列であるとは、XY=J+dI を満たす
正方行列Y および自然数d が存在することをいう。ただしJはすべての成
分が1 の行列、Iは単位行列とする。レーマン行列は「集合被覆問題を線型
計画法で解くことのできない行列は何か」という問題において重要な役割を
果たすことが知られている。一方、XY =J-Iの解は分解可能グラフの
クリーク行列および安定集合行列であり、理想グラフの理論で重要な役割を
果たす。
1979 年にChvatal らは分解可能グラフを構成するために有限群のnear-factorと呼ば
れる概念を定義した。本講演ではまずレーマン行列を得るため
に有用な有限群の1-overlapped factor という概念を定義する。さらにこの2
種類の分解を中心にレーマン行列と分解可能グラフに関する多くの非自明な
類似点を紹介する。
この発表の一部は山形大学の佐久間雅先生との共同研究によるものです。
群およびその生成元により定まるケーリーグラフをΓとし，Γ上で原点を中心とした
半径nの円板をΓ_nとする．適当なラベル付き部分グラフSについて，Γ_nへの埋め込
みの個数をc(S, n)とし，級数Σc(S, n)z^nを増大度関数と呼ぶことにする．
この増大度関数の計算はK.SaitoによるIsing模型の研究に端を発する．Epsteinらは
双曲群について，群のオートマティック構造の性質を用いることで，増大度関数Σc(S, n)z^n
は有理関数になり，その分母は部分グラフの取り方に依らずに定まることを示した．
今回は双曲群，オートマティック群についての基本事項を整理した後で，Epsteinら
の結果の有限生成アーベル群への拡張について話をする予定である。
トップに戻る