要素同士の相互関係を符号に抽象化することで得られる有向マトロイドが,対応する幾何的配置を持つかという実現可能性判定問題(ROM)は,組合せ的モデルと幾何的モデル間のギャップを端的に表すものであり,有向マトロイドの分野における重要な問題である.本論文では,この問題に対し,以下の貢献を行なった.まず第一に,非一様な有向マトロイドの中で特に複雑な構造を持つと考えられる有向マトロイドについて,その実現を得るための新しい方法を提案したこと,第二にはその提案した方法を用いて,特徴のある有向マトロイドの例を構築したこと,そして第三には有向マトロイドの属するクラス間の新たな関係を示したことである.

　有向マトロイドが非一様であるとは,部分的に退化した構造を持つことと言える.従来は非一様な場合については有向マトロイドの全体像も明らかにはされていなかったが,Finschiにより提案された列挙アルゴリズムにより,非一様な場合も含む全ての有向マトロイドのデータベースが与えられたことで,各々の例に対して計算機実験を行ない,解析するというアプローチが可能になった.

まず我々は,非一様な有向マトロイドに対し,既知の性質solvability sequence,双二次最終多項式(BFP)を用いることにより,可能なものに対してはその実現可能性および不可能性を決定する.このどちらの手法によっても実現可能性を判定できない有向マトロイドは,「難しい構造を持つ」有向マトロイドと位置付けることが出来る.

　本論文ではこの「難しい構造を持つ」有向マトロイドの実現を与えるための枠組みとして,ROMを極小reduced systemから得られる多項式制約により定義される多項式最適化問題(POP)とみて解く手法と,既に解決した有向マトロイドの実現を用いることで類似した構造を持つ有向マトロイドの実現を与えるための一般化mutationグラフを提案する.

　近年,POPはSDP緩和を用いることにより現実的に解くことが出来るようになった最適化問題として注目されているが,良い解を求めるために緩和次数を上げた場合,問題のサイズが急激に増加してしまう.我々はこの困難を解決するために,実現行列中の変数を正規化することで変数の数および制約の次数を減らし,また等式制約に注目して,一方の辺を他方で置き換えることにより等式制約を除去することで問題のサイズを縮小し,同時に数値計算の誤差を克服する

　戦略を提案する.我々はこの戦略に基づき,「難しい構造を持つ」有向マトロイドに対して実現を与える.

　次に,我々は有向マトロイドの操作であるmutationに注目する.このmutationとは,互いに1箇所だけ異なる構造を持つ有向マトロイドに対し,互いに移り合う操作であると言うことが出来る.Mutationは元々は一様な場合についてのみ定義されていたが,我々はこれを拡張し,非一様な場合に対応した一般化mutationおよび一般化mutationグラフを提案する.一般化mutationグラフにより隣り合う有向マトロイドは互いに1箇所だけ異なる構造を持つため,一般化mutationの一方が既に実現を与えられている場合,それを用いることにより他方の実現を容易に与えることが出来ると考えられる.本論文では,solvability sequenceおよびPOPにより与えられた実現を始点として,一般化mutationグラフの辺に沿って逐次的に実現を与える.

　以上で提案した手法を,非一様な有向マトロイドの中で実現不可能なものが存在することが知られている,ランクr,要素数nが(4,8)および(3,9)の非一様な有向マトロイド全体に対して適用する.その結果,(r,n)=(4,8)の場合については,非一様な有向マトロイド178844個のうち「難しい構造を持つ」8802個について,POPを用いた手法により1857個,さらに一般化mutationグラフを用いた手法により2093個について実現を与えた.

　また我々は,有向マトロイドの新しいサブクラスとして,一様な有向マトロイドを始点として一般化mutationグラフの辺を辿ることで到達可能な,「根本的な」有向マトロイドの集合を提案する.この集合について,(r,n)=(4,8)の場合については双二次最終多項式により既知である実現不可能な有向マトロイドがすべてこの根本的なクラスに含まれることを示す。また,Richter-Gebertの定理の対偶を用い,一般化mutationグラフの辺に沿って実現不可能な有向マトロイドの列挙を行なう.その結果,(r,n)=(4,8)の場合については,この手法によって列挙された実現不可能な有向マトロイドは全て双二次最終多項式をもつことが分かり,これは双二次最終多項式が(r,n)=(4,8)の場合に置いて十分強力な手法であることの裏付けと捉えることが出来る.

　本論文では次に,特徴のある有向マトロイドの紹介を行なう.ランクが3,要素数が9の場合の特徴のある有向マトロイドの例として知られている,Pappusの有向マトロイドや,有理数表現を持たないGP(9)などの例が,ランク4,要素数が8の場合についても存在することを示す.これらの有向マトロイドは我々の提案した一般化mutationグラフ,およびPOPの多項式制約のサイズ縮小戦略により得られたものである.

　我々は最後に,有向マトロイドの既知なクラスに対する新たな関係を示す.有向マトロイドの実現不可能性を保証する性質であるBFPと非ユークリッド性について,有向マトロイドが一様である場合については,非ユークリッド性を満たせば必ずBFPを持つという包含関係が存在することが知られていたが,我々はこの証明を拡張することで,非一様な有向マトロイドに対しても同様に成り立つことを示す.また,ランクが3の場合については,有向マトロイドの実現可能性を保証する性質であるsolvability sequenceを持つ有向マトロイドは必ずnot-isolatedな要素を持つことが知られているが,我々はランクが4の場合について,solvability sequenceを持ち,かつ全ての要素が互いにisolatedである有向マトロイドが存在することを示す.

　有向マトロイドは,要素同士の相互関係を符号として抽象的に表すものであるが,それが対応する幾何学的な構造を実際にもつかどうかの実現可能性判定問題は,組み合わせ的モデルと幾何学的モデルのギャップを明快に示すという点で,有向マトロイドの非常に重要な問題と認識されてきている.本研究は,従来の一様な有向マトロイドの実現可能性判定問題に関する知見を拡張し,非一様な有向マトロイドの実現可能性問題について,その退化の程度に着目して判定を行う様々な手法を構築している.本研究の貢献は,主に(1)複雑な非一様有向マトロイドうち実現可能なものを,多項式計画問題を解くことで得る方法を示したこと,(2)有向マトロイドの属するクラス間の新たな関係を示したこと,(3)以上の提案した知見を用いて特徴のある有向マトロイドの例を実際に構築したことの3つにまとめることができる.

　本論文は7章で構成され,各章の内容は以下のようにまとめることができる.

　第1章では,有向マトロイドの周辺に存在する問題を実現可能性判定問題の観点から整理し,最適化問題等の周辺分野との関係付けを明らかにしている.その上で,非一様有向マトロイドの実現可能性判定問題に関する本論文の貢献についてまとめている.

　第2章では,非一様な有向マトロイドの実現可能性判定問題を理解するために必要な公理等を含む予備知識を,本論文で重要な役割を果たす有向マトロイドの退化の概念とともに,具体例をまじえて紹介している.さらに,従来知られている有向マトロイドのデータベースに関しても言及している.

　第3章は,まずsolvability sequenceと双二次最終多項式などの既存の手法を用いて,非一様有向マトロイド全体の実現可能性および不可能性をそれぞれ判定している.そして,ここで実現性が判定できない非一様な有向マトロイドのクラスを「難しい構造をもつ」有向マトロイドと定義し,本研究の主な解析対象と位置づけている.また,有向マトロイドの退化の度合いに基づいた非一様有向マトロイドの階層的な表現方法についても紹介している.本論文では,ランク数4,要素数8とランク数3,要素数9の非一様有向マトロイドOM(4,8),OM(3,9)について実現可能性判定問題を解いており,この時点でOM(4,8)には全体で178,844個中8,753個,OM(3,9)では全体で456,671個中14,030個の有向マトロイドが,実現性が判定できない「難しい構造をもつ」有向マトロイドと判定される.

　第4章から第6章が,本研究の新しい貢献の部分に対応する,「難しい構造をもつ」有向マトロイドの実現可能性判定問題に関する,新しい知見を紹介している.

　第4章では,実現可能性判定問題を,極小reduced systemから得られる多項式制約で定まる多項式最適化問題としてとらえ,個々の有向マトロイドの実現を得る手法について述べている.多項式最適化問題は,半正定値緩和を用いることで現実的に解くことが可能となったが,よい解を得るために緩和次数をあげると,緩和問題のサイズが急激に増加するという問題があった.本論文では,この問題を一部の変数を正規化することで,変数の個数および制約の次元を減らし,また等式制約を取り除くことで制約のサイズを縮小し,同時に数値誤差を回避する手法について示している.加えて,ひとつの制約のみが満たされない場合には,小さいサイズの多項式最適化問題を新たに解きなおすことで有向マトロイドの実現を得る,partial assignmentという手法を新たに提案している.この段階で,実現可能性が判定できない非一様有向マトロイドの個数は,OM(4,8)については8,753から6,779へ,OM(3,9)については14,030から10,881に個数を減らすことに成功した.

　第5章では,有向マトロイドの構造を変更する操作であるmutationを,非一様有向マトロイドに拡張することで,一般化mutation graphという概念を導入している.一般化mutationグラフにおいては,稜線で接続される有向マトロイド同士は互いに1箇所だけ構造が異なるため,仮に一方の有向マトロイドが実現可能であれば,先のpartial assignment手法を用いて容易に他方の実現を得ることができる.そこで本論文では,多項式最適化問題およびsolvability sequenceにより実現が与えられた有向マトロイドをシードとし,一般化mutation graphを追跡することにより,逐次的に有向マトロイドの実現を与える手法を提案している.この段階で,実現可能性が判定できない非一様有向マトロイドの個数は,OM(4,8)については6,779から4,803へ,OM(3,9)については10,881から8,548にさらに個数を減らすことに成功した.

　第6章では,有向マトロイドの既知のクラスに対する新たな関係を示している.まず,実現不可能性を保証する性質である双二次最終多項式と非ユークリッド性に関し,非ユークリッド性を満たせば必ず双二次最終多項式をもつという包含関係が,一様な有向マトロイドに対して成り立つことが知られていたが,これを非一様な場合でも成り立つことを証明した.また,ランク3のときに,実現可能性を保証する性質であるsolvability sequenceをもつ有向マトロイドは,必ずreduction sequenceをもち,従ってnon-isolatedな要素をもつことが知られていたが,これがランク4の場合でも成り立つことを示している.さらに,ランク3要素数9の有向マトロイドで知られている特徴のあるマトロイドが,ランク4要素数8の場合にも存在することを示した.

　最後に第7章で論文を総括し,今後の課題について言及している.

　以上のように,本論文は有向マトロイドの実現可能性問題に関し多大な貢献を示し,既存の最適化問題に関しても新しい知見をもたらしている点において,非常に独創的かつ重要な研究となっている.審査委員会は,有向マトロイドの分野における本論文の特筆すべき貢献を評価し,博士号に十分値するものと判断した.

　よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。