幾何的実現を与える組合せ構造の性質の探求と解析

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

平成19年度は,昨年度の研究成果の更なる発展を目指すと共に,研究目的として掲げた全ての目標を完遂することを目指し,以下4つの共同研究を遂行した.第1に,中山裕貴氏(慶應義塾大学)と福田公明教授(ETH Zurich)との昨年度の共同研究である有向マトロイドの列挙結果を解析し,3つの特徴的な有向マトロイドの存在を発見した.本結果を,International Workshop on Combinatorics 2007において発表した.第2に,宮田洋行氏と今井浩教授(2名とも東京大学)との昨年度の共同研究で提案した半正定値計画緩和を用いた実現不可能性に関する十分条件を更に発展させ,同じく半正定値計画緩和を用いた実現可能性に関する十分条件の提案を目指す研究を行った.昨年度の研究結果に本年度の研究結果を加えた内容でKyotoCGGT2007において発表した他,本年度の研究結果について1CCOPT II & MOPT 07(McMaster大学,カナダ)で発表した.第3に,有向マトロイドに続き,マトロイドに関する研究を開始した.その第一歩として,本年度は逆探索に基づくマトロイドの列挙アルゴリズムを開発し,以前の列挙アルゴリズムではできなかった規模の列挙を達成した。本研究は,松本宜丈氏,今井浩教授(2名とも東京大学),David Bremner准教授(UCB)との共同研究である.本結果については,KyotoCGGT2007で発表した.第4に,David Avis教授との共同研究により.有向マトロイドの実現可能性を与える十分条件を組合せ論で有用なツールの1つであるシェリングの立場から提案した.本結果は雑誌論文として投稿中である.