有向マトロイドとは、ユークリッド空間における超平面配置、点配置、多面体、線形計画問題、線形相補性問題、グラスマン多様体の分割などを組合せ的に抽象化したものであり、そのようなさまざまな対象に共通して現れる組合せ構造をうまくとらえるものとして広く研究されている。本論文は、それらさまざまな対象の組合せ構造の分類・構成に関する研究を通じて、それら組合せ構造の理解へ貢献することを目的とする。

まず、本論文の前半では、有向マトロイドの実現可能性問題に対し、2 つのアルゴリズムを提案し、実現可能性分類を通じて、さまざまな組合せ構造の分類を行う。有向マトロイドの実現可能性問題とは、与えられた有向マトロイドが実際の超平面配置や点配置として表現できる(実現可能) かを問う問題であり、一般の整数係数の等式・不等式系の可解性を判定する問題と同程度に難しい、すなわちNP 困難な問題であることが知られている。そのため、計算量的に非常に難しい問題であるが、一方で、十分条件から実現可能であることや実現不可能であることが示すというアプローチにより、多くの有向マトロイドの実現可能性の決定が行われてきた。そして、2001 年にFinschi とFukuda により、退化したものも含んだ有向マトロイドの大規模列挙が達成されて以来、そのようなアプローチで、要素数8・ランク4、要素数9・ランク3 の有向マトロイドの実現可能性の分類を行うことを目指した研究が多数なされた。その一方、分類は完全でなく、新たな分類手法が求められていた。

本論文では、まず、実現可能性を十分条件から示す手法として、Bokowski とSturmfels により提案されたsolvability sequence を拡張した手法を提案し、これまで実現可能性が分類されていなかった要素数8・ランク4、要素数9・ランク3、要素数9・ランク6 の有向マトロイドの実現可能性の完全な分類を行う。また、今まで実現可能性がすでにわかっていたものについてもこの手法により再計算を行い、実際に実現を証拠として公開することで、分類結果は非常に信頼できるものになっている。また、その結果から、点数8の3 次元点配置、点数9 の2 次元点配置、点数9 の5 次元点配置、頂点数9 の5 次元多面体の組合せ構造を完全に分類する。この結果は退化を含んだ分類、次元の高いものも含んだ分類として、初めての大規模分類として位置づけられるものである。さらに実現不可能性を十分条件から示す手法として、半正定値計画問題(SDP) 緩和に基づく手法を提案する。これは数値計算的手法であるが、SDP の双対性などを用いることで厳密に実現不可能性判定として用いることができる。それを要素数8・ランク4、要素数9・ランク3の有向マトロイドに適用し、実際に有向マトロイドを実現不可能と決定できることを示す。

次に、提案した有向マトロイドの実現可能性判定の手法を用いて、P 行列で定義される線形相補性問題による4 次元超立方体の向き付けの分類を行う。線形相補性問題(LCP) とは、線形計画問題や凸2 次計画問題などの問題に対する統一的な枠組みを与える重要な問題である。一般に、LCP はNP 完全な問題であるが、係数行列がP 行列である場合(PLCP) は、多項式時間可解であると考えられている。一方、PLCP に対する多項式時間アルゴリズムは未だに与えられておらず、多項式時間アルゴリズムへ向けさまざまなピボットアルゴリズムが研究されている。それらピボットアルゴリズムは向きをつけられた超立方体グラフ上でシンクを探す問題として定式化でき、そのような向き付けをPLCP 向き付けと呼ぶ。係数行列がd × d 行列のPLCP はd 次元超立方体のシンクを探す問題に対応し、3 次元の場合は、1978 年にStickney とWatsonにより、PLCP 向き付けの分類がなされている。本研究では、有向マトロイドの部分列挙と実現可能性分類により、PLCP 向き付けの列挙を行うことを提案し、4 次元の超立方体上のPLCP 向き付けを列挙する。これは要素数9・ランク4 の有向マトロイドの一部の実現可能性分類を通じて行われ、実現可能性分類の提案手法がそのサイズでも有効に働くことがわかる。

さらに、有向マトロイドの実現を与える手法を変形し、組合せ球面に多面体的実現を与える手法を与え、2-simple, 2-simplicial な4 次元多面体の持ちうる頂点数の分類を完結する。多面体の複雑さを示す一つの指標として、面の数が挙げられるが、各次元の面の数を並べたものをf-vector といい、多面体の複雑を理解するために盛んに研究されてきた。2-simple, 2-simplicial な4 次元多面体とは「極端」なf-vector を持つ多面体であり、4 次元多面体のf-vector の理解という観点から、2-simple, 2-simplicial な4 次元多面体の頂点数を分類する研究がなされてきたが、その分類は完全でなかった。本研究では、Werner によって構成された12 頂点からなる2-simple, 2-simplicial な3 次元組合せ球面に多面体実現を与え、分類を完結する。

本論文の後半では、ある特殊な性質をもつ組合せ構造の構成法、およびそれを用いた性質解明の研究を行う。まず、マトロイド、有向マトロイドの自己同型群の構造解析を目標として、実際の点配置の幾何的な対称性と点配置から定義されるマトロイドや有向マトロイドとしての対称性を比較する。まず、非自明な回転対称性を持つ任意の2 次元点配置に対し、ある操作を行うことで、マトロイドとしては同様の対称性を持つがそれを決して幾何的に実現できないような対称性を持つ3 次元点配置を構成する手法を与える。これは、点配置に対し、マトロイドとしての対称性と実際の幾何的対称性には大きな差があることを示唆する。これは、2 次元ユークリッド平面における回転の不動点の存在・一意性などを活用して証明される。一方、点配置から定義される有向マトロイドの対称性は幾何的な対称性をある程度うまくとらえていることを示す。

具体的には組合せ的回転対称性を持つランク3 の凸な有向マトロイドに対し、幾何的回転対称性の顕著な性質である不動点の存在・一意性といった性質が自然に拡張されることを示す。

最後に、多面体グラフのLP 向き付けに関連する組合せ構造の性質および構成法を研究する。今日、線形計画問題(LP) の強多項式時間アルゴリズムの設計は一大未解決問題であり、特にうまいピボット規則のもと、単体法が強多項式時間アルゴリズムとなりうるのかが大きく注目されている。線形計画グラフ(LP グラフ) とは、実行可能領域の多面体のグラフに対し、枝を目的関数が改善する方向に向きをつけたものであり、LP の可能なピボットを全て表現するグラフと考えられる。このグラフの組合せ的性質を解明することは、ピボット規則を設計・解析する上で大きな役割を果たすと考えられるが、現在は、Shelling 性、Holt-Klee性、唯一シンク性、非閉路性の4 つの性質が知られている。本論文では、特に2009 年にAvis とMoriyamaにより提案されたShelling 性を考察する。まず、Shelling 性に対し、一見もっと強い条件に見える新たな定義を与え、実際には元の定義と等価であることを示す。この等価性は、Shelling 性の扱いを簡単にする。具体的にこの等価性を用いて、Shelling 性を満たさないがHolt-Klee 性、唯一シンク性、非閉路性を満たす多

面体有向グラフ(X 型グラフ) の無限族を構成するための多面体グラフに関する一般的な操作を提案する。これはAvis, Miyata, Moriyama によって2009 年に与えられた構成を一般化して得られるものである。この結果は、Shelling 性を満たさないがHolt-Klee 性、唯一シンク性、非閉路性を満たす多面体有向グラフが豊富であることを示唆し、LP グラフの組合せ的性質としてのShelling 性の有用性を示すものである。次に、Develin によって提案されたgood pair sequence による十字多面体の線形計画向き付けの特徴づけの結果が、十字多面体の線形計画向き付けがShelling 性で完全に特徴づけられることを示唆していることを指摘する。さらに、その結果を用いて、十字多面体上でX グラフを与える向き付けの数を具体的に評価する。

論文の概略

ベクトル配置,超平面配置,点配置,多面体,線形計画問題,線形相補性問題等,さまざまな問題の組合せ論的抽象化である有向マトロイドについて,計算科学・数学の2つの観点から研究を行った.

第一の貢献は,有向マトロイドに関するデータベースの拡張である.定められた要素数 n とランク r のそれぞれに対して数え上げた有向マトロイド(有限個)のうち,幾何学的に実現可能であるものの個数のデータベースがある(たとえば 「n=7 で r=4 のとき206個の異なる有向マトロイド(正確に言うと,ある同値関係による同値類)が存在し,そのすべてが幾何学的実現可能である」というように).このデータベースの構築は,実現可能性・不可能性それぞれの十分条件をいくつか用いて,計算機による総当りで行われる.それゆえ,ある程度以上大きな n と r については数え上げがなされていない.候補者は既存の計算手法を拡張し,その計算論的実効性を高めることにより,新たに (n,r)=(4,8),(3,9),(6,9)の場合に対して,実現可能マトロイドの個数を確定させた.

第二の貢献は,このようにして拡張したデータベースを基にした種々の理論的貢献である.その応用領域は線形相補性問題,線形計画問題,点列配置など多岐にわたるが,その一つに「点の幾何学的配置における対称性」と「(有向)マトロイドが内包する対称性」の比較がある.データベース中の例により前者と後者のギャップの存在が明らかになったが(マトロイドの対称性であって,幾何学的対称性として実現できないものが存在する),候補者はこの例を注意深く観察することにより,一般のマトロイド上の置換に対する不動点の概念を得るに至り,それに付随する数学的結果をいくつか証明した.この結果は,点配置の対称性(直感的に理解できる)の組合せ論的抽象化として,非自明であり高く評価できる.

総合評価

候補者は博士課程在籍中に3本の論文を出版し,また別の3本を投稿準備中である.提出された論文中の学術的成果は,学位取得のために十分なものである.特に,データベースとして得られた計算科学的成果をさまざまな目的に活用する上での,候補者の視野の広さと数学的洞察力は特筆に値すると考える.

論文中の成果によって導かれる,さらなる理論的発展について,候補者は既に複数の方向性を見出し,それらに邁進しつつある.このことは,「一人前の研究者」としての準備ができていることを示し,候補者の今後の研究に期待がかかる.

提出された論文は,時折生硬さが見えるものの,数学的厳密さや,英語による表現の適切さの面で標準以上である.特に,非専門家向けに分野の概観を行う Preliminaries の章に注力したことは,単なる出版論文の集合体ではなく,それ自身で完結した学位論文を目指す野心的な試みとして,高く評価したい.また,論文審査会の口頭試問においては,学術的成果の解説の巧みさ,また,質問に対する受け答えにおける科学的・批判的姿勢など,大いに好印象であった.

以上の理由により,本論文を博士(情報理工学)の学位請求論文として合格と認める.