単体的複体のトポロジー的組合せ論とグラフの非巡回的向き付け上の最適化問題の研究

今年度は、昨年度の単体的複体および正則セル複体の「非巡回的符号付け可能性」(acyclic signability)および「再帰的非巡回的符号付け可能性」(recursive acyclic signability)という概念に関する研究を引続き行なった。これらは本研究課題である「グラフの非巡回的向き付け上の最適化問題」で中心的に扱っている最適化問題における最適解にあたる非巡回的向き付けと等価であり、その性質を詳しく研究することが重要な課題の一つとなっている。今年度この成果を論文の形にまとめるまでには至らなかったが、引続き今後の成果につながることを期待する。また,「非巡回的」という条件をはずした場合にどのようなことが起こるのか、ということにも研究の範囲を広げ、対応する概念となる、単体的複体の分割可能性に関しても研究を行なった。分割可能性に関しては、これまでに知られている分割可能でない例の構成法としては、1次元の場合の自明な構成法、リンクが分割可能性を保存することを利用して高次元に持ち上げる構成法、h-列が負であれば分割可能でないという性質を利用する方法、の3種しかしられていないが、これらに該当しない構成法により、2次元の分割可能でない単体的複体の例を構成した。これは今年度この成果を論文の形にまとめるまでには至っていないが、RIMS短期共同研究『グラフの変形とその数量的評価』(2005.9.26-30)にて口頭で発表を行なっている。

今年度は、昨年度の単体的複体および正則セル複体の「非巡回的符号付け可能性」(acyclic signability)および「再帰的非巡回的符号付け可能性」(recursive acyclic signability)という概念に関する研究を引続き行なった。これらは本研究課題である「グラフの非巡回的向き付け上の最適化問題」で中心的に扱っている最適化問題における最適解にあたる非巡回的向き付けと等価であり、その性質を詳しく研究することが重要な課題の一つとなっている。今年度この成果を論文の形にまとめるまでには至らなかったが、引続き今後の成果につながることを期待する。また,「非巡回的」という条件をはずした場合にどのようなことが起こるのか、ということにも研究の範囲を広げ、対応する概念となる、単体的複体の分割可能性に関しても研究を行なった。分割可能性に関しては、これまでに知られている分割可能でない例の構成法としては、1次元の場合の自明な構成法、リンクが分割可能性を保存することを利用して高次元に持ち上げる構成法、h-列が負であれば分割可能でないという性質を利用する方法、の3種しかしられていないが、これらに該当しない構成法により、2次元の分割可能でない単体的複体の例を構成した。これは今年度この成果を論文の形にまとめるまでには至っていないが、RIMS短期共同研究『グラフの変形とその数量的評価』(2005.9.26-30)にて口頭で発表を行なっている。