グラフのラムゼー的性質と構造
数学科 教授 善本 潔
点の集合Ｖとその間を結ぶ辺の集合Ｅからなる図形をグラフと呼び、Ｇ=(Ｖ,Ｅ)と書きます。任意の集合Ｓに対する写像ｃ : Ｅ → ＳをＧの辺着色、ｃ(ｅ)の値を辺ｅの色と呼びます．特に任意の隣接する２辺ｅ,ｆの色が異なる時、つまりｃ(ｅ)≠ｃ(ｆ)の時、写像ｃをグラフGの辺彩色と呼びます。
有名な四色定理とは「すべての地図は隣接する国が同色にならないように四色でそれぞれの国の領土を塗り分けることが出来る」ことです。四色定理は、平面に交差無く埋込み可能な３正則グラフ（すべての点に丁度３本の辺が接続しているグラフ）は、３色からなる辺彩色を持つ」と同値となります。このため辺彩色や辺着色は重要な研究課題として、これまで多くの研究が行われてきました。
辺着色を研究する理論の一つにラムゼー理論があります。ラムゼー理論の出発点となったラムゼーの定理は、任意の自然数ｓに対して適当な自然数Ｎが存在し、任意の２色で辺着色された点数Ｎ以上の完全グラフは単色（全ての辺が同色）の点数ｓの完全グラフを含むという主張です。このように、ある状況（２色で辺着色された完全グラフの点数が十分大きい）が、ある構造（単色の完全グラフの存在）を強制する現象の研究は、グラフ理論や組合せ論においてもっとも重要な研究課題の一つです。私の研究の主なテーマの一つは、辺着色されたグラフのラムゼー的な性質とその構造を解明することです。
有名な四色定理とは「すべての地図は隣接する国が同色にならないように四色でそれぞれの国の領土を塗り分けることが出来る」ことです。四色定理は、平面に交差無く埋込み可能な３正則グラフ（すべての点に丁度３本の辺が接続しているグラフ）は、３色からなる辺彩色を持つ」と同値となります。このため辺彩色や辺着色は重要な研究課題として、これまで多くの研究が行われてきました。
辺着色を研究する理論の一つにラムゼー理論があります。ラムゼー理論の出発点となったラムゼーの定理は、任意の自然数ｓに対して適当な自然数Ｎが存在し、任意の２色で辺着色された点数Ｎ以上の完全グラフは単色（全ての辺が同色）の点数ｓの完全グラフを含むという主張です。このように、ある状況（２色で辺着色された完全グラフの点数が十分大きい）が、ある構造（単色の完全グラフの存在）を強制する現象の研究は、グラフ理論や組合せ論においてもっとも重要な研究課題の一つです。私の研究の主なテーマの一つは、辺着色されたグラフのラムゼー的な性質とその構造を解明することです。
この先生・教授に出会えるのは・・・
日本大学 理工学部 数学科
現代数学の最先端にチャレンジ。数理科学者、コンピュータ関係の情報技術者を目指します
基本情報
学校の魅力
入試情報
その他
