値最適化による有向マトロイドの構造解析とその実代数幾アルゴリズムへの展開

点击翻译按钮获取中文摘要

まず、研究計画にも挙げた有向マトロイドの自己同型群の研究を進めた。昨年度、マトロイドとしての対称性を幾何的に実現できないような点配置を複数発見し、マトロイドの自己同型群とアフィン対称性で定義される幾何的対称性で定義される自己同型群には大きな差がありそうであることを発見したが、本年度はそれをさらに拡張し、任意の非自明な回転対称性を持つ2次元点配置からそのような性質を持つ3次元点配置を構成する手法を提案し、マトロイドの自己同型群と幾何的対称性の間に大きな差があることを明確にした。また、その原因がマトロイドに対し、非自明2次元回転の不動点は唯一存在するという性質に対応する性質がないことを特定し、有向マトロイドに対し、そのような性質に対応する性質を証明した。これは、有向マトロイドの自己同型群が幾何的に定義される自己同型群と似た構造を持つことを示唆するとともに、これから不動点定理を元に自己同型群の解析を行うという方針を与える結果である。次に、前年度に引き続き、線形計画グラフの組合せ的性質を研究した。前年度までは、線形計画グラフの組合せ的性質としてのシェリング性の有用性を示すため、他の3つの知られている性質(非閉路性、唯一シンク性、Holt-Klee性)を満たすがシェリング性を満たさない多面体グラフの無限族の構成法を研究したが、本年度は、別の角度から有用性を示した。具体的には、十字多面体上の線形計画グラフがシェリング性で完全に特徴づけられることを示した。また、他の3つの性質では特徴づけが不可能なことも示し、さらに、他の3つの性質を満たすがシェリング性を満たさない向き付けの数を十字多面体上で具体的に評価した。この結果により、シェリング性を用いた線形計画の研究がより促進されることが期待できる。