組合せ論の総合的研究
【研究分野】数学一般
【研究キーワード】
組合せ論 / グラフ / 曲面への埋込み / 計算幾何 / アルゴリズム / アソシエーションスキーム / スピンモデル / 組合せ理論 / 分割問題 / 閉路 / 次数 / 埋め込み / 連結度 / 双対グラフ / 指標表
【研究成果の概要】
グラフ理論の基礎的な分野において研究が活発に行われた。特に、k-因子や連結[2,k]-因子、ハミルトン閉路などが存在するために、点連結度、辺連結度、強度、結合数などグラフの連結性を表す不変量が満たすべき条件について色々な結果が得られた。たとえば、独立した3頂点の次数の和がグラフの位数以上ならば、いくつかの例外を除き、最長閉路の長さは最長通過の点数-1以上であることが示された。これは、今までに知られていたこの種の結果を統一的に記述した形で拡張しており、最長閉路の性質に関する基本的な結果になると思われる。3-連結グラフには可縮な辺が存在するという結果は有名であるが、その分布に関する研究や3点以上の可縮な部分グラフの存在に関する条件が得られた。たとえば、グラフを任意の大きさの孤立点を持たない部分集合に分割できるための最小次数に関する最善の条件が求まった。曲面の幾何学的性質と、そこに埋め込まれたグラフの性質の間には深い関係がある。平面に埋め込まれたグラフ、すなわち、平面グラフには双対グラフが定義できるが、その他の曲面の場合には双対グラフの定義は成功していない。射影平面への異なる埋め込みに対応する双対グラフの性質を調べることにより、双対概念の見直しが行われた。また、各種の曲面上の三角形分割や四角形分割の性質が調べられた。代数的組合せ論においては、距離正則グラフやアソシエーションスキームの分類問題や、スピンモデル、アダマ-ル行列の研究が進展し、興味ある実例が色々構成された。とくに、代数的グラフ理論の中心的研究対象である距離正則グラフの研究では、対応するアソシエーションスキームの表現を研究することが重要であることがわかってきた。とくに、有限群の場合と同じような指標表が定義できることがわかり、代表的なアソシエーションスキームであるハミングスキーム等の指標表の性質が調べられた。さらに、有限幾何や各種組み合わせ問題に関する各種アルゴリズムの解析と開発が行われた。
【研究代表者】