マトロイド表現論の情報・計算理論への展開

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

本年度は、前年度に得られたマトロイド表現論に関する理論研究の成果をさらに進展させると同時に、他分野への展開として、マトロイドを一般化したポリマトロイドに関する高次元多面体表現（拡張定式化）に関する研究を行った。さらに今後、マトロイド表現論をネットワーク理論に展開させるための前段階として、ネットワーク解析に関する諸結果を得た。まず前者に関して、体上表現可能性や向き付け可能性に関する特徴づけに関して、前年度の研究結果を進展させ、より詳細な解析を行った。マトロイドは、離散数学や計算機科学に登場する様々な離散構造の疎構造として表れることが知られている一方で、各部分構造に簡潔な特徴づけが存在するかについては、未だ解明されていない部分が多い。本研究では、特にベクトル空間・射影空間との対応が存在する体上表現可能マトロイドや向き付け可能マトロイドと呼ばれる部分構造に関して、特徴づけに関する困難性を解明する研究を行った。特に、体上表現可能なマトロイドに関して、代数拡大を用いた特徴づけに関する詳細な解析を行った。後者に関しては、マトロイドの拡張・一般化であるポリマトロイドの中で、特に足切り横断ポリマトロイドに着目し、高次元多面体による簡潔な表現（拡張定式化）の可能性について研究を行った。これにより、足きり横断ポリマトロイドが表現できる組合せ的問題に関し、多面体的組合せ論による統一的アプローチを適応するための土台を整備した。また今後、マトロイド表現論をネットワーク理論に展開する前段階として、故障に頑強なネットワーク構成に関する研究も行った。また、これらの研究成果に関して、前者の研究成果に関してはび国際学会において発表を行い、後者の研究成果に関しては論文誌および国際学会において発表を行った。