【研究分野】代数学

【研究領域課題番号】26400003 (KAKENデータベースで見る）

【研究キーワード】

球デザイン / グラフ / 整数格子 / 有限群 / 線形符号 / 代数的組合せ論 / 組合せデザイン / グラフ理論 / 有限体

【研究成果の概要】

球デザインの構成のヒントとなる、グラフのスペクトルや有限置換群について、様々な角度から研究した。グラフのスペクトルによる特徴付けの反例の構成法として知られるスイッチングの手法を、極めて非自明な適用法を見出すことによって、グラスマングラフのスペクトラルメイトとして有名な例を全く別の方法で構成することに成功した。また、アソシエーション・スキームから得られる球面の有限部分集合の様々な性質について、研究分担者はこれまで得られている結果を拡張した。

【研究種目】基盤研究(C)

【研究期間】2014-04-01 - 2017-03-31

【配分額】4,810千円 (直接経費: 3,700千円、間接経費: 1,110千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】20340023 (KAKENデータベースで見る）

【研究キーワード】

組合せ論 / グラフ / マイナー / 禁止マイナー / 禁止部分グラフ / 完全マッチング / クローフリーグラフ / タフネス / グラフ理論 / グラフマイナー / 閉曲面上への埋め込み / 全域木

【研究成果の概要】

与えられたグラフの部分グラフから,辺の縮約を繰り返して得られるグラフを,元のグラフのマイナーと呼ぶ.平面グラフなど重要なグラフの族はマイナーに関して閉じており,禁止マイナーによって特徴づけされる.これまでに知られていた平面グラフなどにおける閉路,全域木,因子に関する問題を,禁止マイナーの観点から拡張することを行った.とくに完全2部グラフをマイナーとして含まないグラフのタフネス,全域木に関する性質で顕著な成果が上がった.加えて,禁止部分グラフによる同種の問題にも成果があった。

【研究種目】基盤研究(B)

【研究期間】2008 - 2011

【配分額】6,240千円 (直接経費: 4,800千円、間接経費: 1,440千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】11640135 (KAKENデータベースで見る）

【研究キーワード】

位相幾何学的グラフ理論 / 三角形分割 / 四角形分割 / 染色数 / representativity / ハミルトン性 / 閉曲面 / グラフ理論 / 本型空間 / 対角変形 / 向き付け不可能曲面 / グラフ / 埋め込み

【研究成果の概要】

幾何学的対象に埋め込まれたグラフの研究としては,まず閉曲面の三角形分割や四角形分割についての研究を行った.三角形分割に対しては,対角変形と呼ばれる基本変形による推移可能性に関しての研究を引き続き進め,次数制約のついた問題や,外平面グラフの拡張である外三角形分割について結果を得た.また,平面上の三角形分割であって,他の閉曲面の四角形分割としても埋め込むことのできるグラフについて,曲面が向き付け可能かどうかに依存して,グラフの組合せ的性質が重要な役割を果たしているという,興味深い結果を得た.
この結果に見られるような,向き付け不可能な曲面特有の性質として,向き付け可能曲面に切り開ける奇閉路が存在するような四角形分割は,染色数が4以上になることを示した.ここで用いられた議論をトーラスとクラインの壺に適用することによって,それらの曲面の四角形分割の染色数は,ある位相幾何学的性質によって特徴付けられることを示した.さらに,一般の閉曲面の四角形分割においては,閉路の偶奇性に関連した閉曲面の代数的不変量が,染色数に影響を及ぼすことがわかった.
本研究の目的のひとつに,平面において知られていた事実を一般の閉曲面へ拡張するための一般的道具立ての開発を挙げていたが,閉曲面上の3連結グラフで,representativityの高いものに対して,それを切り開き,元の構造をあまり破壊せずに全域部分グラフとなる平面グラフを得る手法を開発した.この手法により,そのような3連結グラフがどの程度ハミルトン性に近い性質を持つか,という問いに対する答えとして,最大次数4以下の全域木に関するもの,最大次数8以下の全域2連結部分グラフの存在,次数和の小さい連結部分グラフに関する漸近的に最善の結果を証明した.

【研究種目】基盤研究(C)

【研究期間】1999 - 2000

【配分額】3,500千円 (直接経費: 3,500千円)

【研究分野】数学一般(含確率論・統計数学)

【研究領域課題番号】10304008 (KAKENデータベースで見る）

【研究キーワード】

離散幾何 / 組合せ論 / 三角形分割 / 四角形分割 / グラフ理論 / 木 / 直線描画 / ネットワークフロー / サイクル / グラフ / ハミルトン性 / Johnsonスキーム / 閉包 / 因子 / 分割問題 / 組み合せ論 / 照明問題 / 刑務所問題 / ハミルトングラフ / 単位距離グラフ

【研究成果の概要】

本研究は、3年という研究期間において離散幾何の諸問題の持つ組合せ論的な側面を抽出、分類し、そこから離散幾何における一般的な方法論を構築することを目的としていた。その研究成果のうち、主要なものをいくつか挙げる。
・平面内の有限個の頂点を線分で結び、できるだけ交差する線分が少ないハミルトンサイクルを描画する問題は、見かけ上幾何学的な問題であるが、実はこれが本質的に組合せ論的特性として記述できることを明らかにし、こうした問題を解決する方法論を構築した。
・幾何学的独立木の問題をグラフの独立木の問題の発展形として捉えることで、その組合せ論的特性を明らかにし、幾何学的独立木の問題を扱う方法論を構築した。
・ユークリッド空間内に置かれた有限個の幾何的対象に対し、その両側にほぼ同数が分布するような超平面の存在を問う問題は多数存在するが、これらの問題の組合せ論的特性を明らかにし、それを用いて、特に対象が球面である場合に問題を解決した。
・濃淡画像を白黒2値画像として表現する問題を、グラフ理論におけるネットワークフロー問題に還元する方法論を構築し、それを用いて従来のものとは全く異なるアルゴリズムを得た。
・離散幾何の問題にはグラフの分割問題に帰着させられるものが多数存在することを明らかにし、特に完全グラフ、完全2部グラフの場合における様々な分割問題を解決した。これらは本研究成果のごく一部であり、その全容は研究成果報告書に詳しい。得られた成果の多さと深さを考えれば、本研究は大きな成功を収めたと考えられる。

【研究種目】基盤研究(A)

【研究期間】1998 - 2000

【配分額】26,600千円 (直接経費: 26,600千円)