多面体的複体の組合せ構造を表す性質にシェラビリティーという性質がある．多面体的複体のファセットの全順序集合の中に，再帰的条件を満たすシェリングという全順序が少なくとも1つ存在するとき，その多面体的複体はシェラブルであるという．多面体的複体のシェラビリティーは，Brugesser と Mani が凸多面体の複体は常にシェラブルであると示したことで，更に注目を集め，以後多くの研究者により研究されてきた．シェラビリティーの最も有名な応用は多面体の上限定理である．「n頂点のd次元多面体のk次元面の最大数はいくつか」という問題に対して，様々な研究が行われてきたが，1970年に McMullen が多面体のシェラビリティーを用いることで，同問題の完全な答えを与える上限定理を示した．また，シェラビリティーの概念は，複体そのもののみならず，複体をモデルとする他分野にも応用されている．例えば，Ball と Provan は，単体的複体と正ブール関数が自然な一対一対応をなすことに着目し，単体的複体において研究されてきたシェラビリティーとの関連から正ブール関数にシェラビリティーを導入した．信頼性理論の根源的問題のひとつに，各変数が独立かつランダムに $0$ または $1$ をとるとき，ブール関数 $f$ が $1$ をとる確率，つまりあるシステムの信頼度予測がある．Ball と Provan はこの計算が一般的に NP-困難となることを示した一方で，多項式時間で信頼度計算が可能な部分クラスが存在することを示した．この部分クラスがまさにシェラビリティーを満たすクラスとなっている．

本論文では，多面体的複体のシェラビリティーを，シェリング向き付けと名付けた多面体的複体の双対構造の向き付けとして表現し，シェリング向き付けの立場から多面体的複体のシェラビリティーを解析することで，多面体的複体のシェラビリティーに対して新しい3つの方向性を与える．

第1の方向性は，シェリング向き付けにより多面体的複体のシェリング集合のアンチマトロイド族への分解である．多面体的複体がシェラブルのとき，同じシェリング向き付けを構成するシェリングは複数存在するが，任意のシェリングから構成されるシェリング向き付けは一意に定まる．つまり，同じシェリング向き付けを構成するシェリングどうしに同値関係を与えることにより，多面体的複体のシェリング集合を同値類分解することができる．このとき，任意の同値類に属するシェリング集合がアンチマトロイド構造を有することを示す．

第2の方向性は，多面体的複体の部分クラスである単体的複体における新しい概念h-assignment の導入と，このh$-assignmentを用いて単体的複体のシェラビリティー判定する新しい2つの方法の提案である．単体的複体のシェラビリティーと単体的複体の性質を表す $h$-ベクトルには密接な関連がある．この関連に基づいて単体的複体のファセット集合にh-assignmentという新しい概念を導入し，h-assignment により単体的複体のシェリング向き付けを特徴付ける．更に，h-assignment を用いた単体的複体のシェラビリティー判定する2つの方法，hash-DFS法とRS法を提案する．

Hash-DFS法とは，長井のハッシュを用いて再探索を回避するための情報を保存しつつ，探索木を深さ優先的に探索する方法である．しかし，探索空間が大きいため，全ての情報をハッシュに保持することができない．つまり，hash-DFS法では再探索という無駄足を免れない．そこで，理論的に再探索を完全に回避する方法として，逆探索に基づいたRS法を提案する．実際，探索空間全体を探索する単体的複体の非シェラビリティー判定においては，RS法が hash-DFS 法より機能的であることを計算機実験により確かめることができる．また，RS法はシェリング向き付けの列挙に応用できることを示す．

第3の方向性は，数理計画問題の組合せ的性質と多面体的複体の部分クラスである凸多面体の複体のシェリング向き付けの関係である．1988年に Hoke により，単純多面体のグラフ上の非巡回なユニークシンク向き付け（USO）とその双対多面体である単体的多面体のシェリングが一対一対応であることが示された．USO とは，多面体の任意の面においてソースとシンクを1つずつ持つ向き付けである．特に単純多面体が超立方体のとき，そのグラフ上のUSOは数理計画問題の組合せ性質と深い関連がある．P-行列上の線形相補性問題をピボッティングで解く場合も，2次計画問題のひとつである最小包含球問題を解く場合も，

アルゴリズムの挙動（PLCP-cube と SEB-cube）は常に超立方体のグラフ上の USO となる．同様に，許容領域が超立方体に組合せ同値である線形計画問題と有向マトロイド計画の場合も，ピボッティングで解く場合のアルゴリズムの挙動（LP-cube と OMP-cube）は超立方体のグラフ上の USO となる．これまでに，2つの包含関係LP-cube⊆PLCP-cubeとLP-cube⊆OMP-cubeが理論的に示されたが，両者の違いは未だはっきりしない．そこで，本論文では，LP-cubeとPLCP-cube の違いとLP-cubeとOMP-cube の違いに関する予見を得るべく，2つの実験を行う．

1つ目は，非巡回な4次元 PLCP-cubeの個数の上限および非巡回な5次元 PLCP-cube における偶数出次数予想の成立である．2つ目は，LP-cube とOMP-cube の違いを有向マトロイドの実現不可能性の立場から言及する．実現不可能性を与える有向マトロイドの新しい性質non-HK 性とnon-HK* 性を導入し，その有用性を理論的かつ実験的に示す．

本論文は、多面体的複体の組合せ構造を表すシェラビリティーと呼ばれる性質に関する研究成果をまとめたものである。多面体的複体のファセットの間に再帰的条件を満たすシェリングという全順序が少なくとも1つ存在するとき,その多面体的複体はシェラブルであるという.特に本論文では、シェラビリティーがシェリング向き付けと名付けられた多面体的複体の双対構造の向き付けとして表現され,シェリング向き付けの立場からシェラビリティーに対する新しい方向性が与えられている.

本論文は7章から成る。第1章は本研究の背景と貢献についてまとめている。第2章は、本論文の内容を理解するための基礎知識を簡潔に解説している。

第3章において、同じシェリング向き付けを構成するシェリングの間に同値関係を与えることにより,多面体的複体のシェリング集合を同値類分解することができることが示されている.このとき,任意の同値類に属するシェリング集合がアンチマトロイド構造を有することがわかる.

第4章において、多面体的複体の部分クラスである単体的複体に対してh-assignmentと呼ばれる概念が導入され,h-assignmentにより単体的複体のシェリング向き付けが特徴付けられている.そして、h-assignmentを用いて単体的複体のシェラビリティーを判定する新しい2つの方法,hash-DFS法とRS法が提案されている。Hash-DFS法とは,長井のハッシュを用いて再探索を回避するための情報を保存しつつ,探索木を深さ優先的に探索する方法である.しかし,探索空間が大きいため,全ての情報をハッシュに保持することができず再探索が必要になる.そこで,理論的に再探索を完全に回避する方法として,逆探索に基づいたRS法が提案された.実際に,探索空間全体を探索する単体的複体の非シェラビリティー判定においては,RS法がhash-DFS法より機能的であることが計算機実験により確かめられた.また,RS法はシェリング向き付けの列挙に応用できることが示されている.

第5章と第6章においては、数理計画問題の組合せ的性質と多面体的複体の部分クラスである凸多面体の複体のシェリング向き付けの関係が述べられている.ユニークシンク向き付け（USO）とは,多面体の任意の面においてソースとシンクを1つずつ持つ向き付けであり、特に単純多面体が超立方体のとき,そのグラフ上のUSOは数理計画問題の組合せ性質と深い関連がある.P-行列上の線形相補性問題をピボッティングで解く場合も,2次計画問題のひとつである最小包含球問題を解く場合も,アルゴリズムの挙動（PLCP-cubeとSEB-cube）は常に超立方体のグラフ上のUSOとなる.同様に,許容領域が超立方体に組合せ同値である線形計画問題と有向マトロイド計画の場合も,ピボッティングで解く場合のアルゴリズムの挙動（LP-cubeとOMP-cube）は超立方体のグラフ上のUSOとなる.これまでに,2つの包含関係LP-cube⊆PLCP-cubeとLP-cube⊆OMP-cubeが理論的に示されたが,両者の違いは未だはっきりしていない.本論文の第5章においては,非巡回な4次元PLCP-cubeの個数の上限および非巡回な5次元PLCP-cubeにおける偶数出次数予想の成立について述べられている.第6章においては,LP-cubeとOMP-cubeの違いが有向マトロイドの実現不可能性の立場から言及されている.実現不可能性を与える有向マトロイドの新しい性質non-HK性とnon-HK*性が導入され,その有用性が理論的かつ実験的に示された.

以上に述べたように、本研究の結果は、シェリング向き付けの立場から多面体的複体のシェラビリティーに対する新しい方向性を与えており、本論文は博士（情報理工学）の学位請求論文として合格と認められる。