組合せ理論における極値的問題の確率的証明手法、及びそのアルゴリズム的側面の研究

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

ランダムグラフ上のラムゼ-理論を主に研究した。この分野に多いに貢献したB.Bollobas著Random Graphs(1985)は、ランダムグラフ上でのラムゼ-理論にはほとんど触れていない。が、最近の研究によってこの著書もすでに古くなった感があり、ラムゼ-理論の発展と確率的手法,ランダムグラフの研究の進展とともに,近年、ランダムグラフ上でのラムゼ-理論が技術的に可能になってきた。一方で、辺着色されたグラフの全頂点を単色の木で被覆する研究は強く注目をあびているものの古典的ラムゼ-理論の例にもれず,もっとも単純な完全グラフ上においてしかなされていない。今回は,これらの状況をふまえ、この単色木被覆の研究はランダムグラフを融合させる試みを行なった。それによると、2着色の場合、完全グラフにおける(単色木による)被覆数は1、辺を一本除去したグラフは2まであがるが、その後、辺をランダムに除去し続けた場合、かなり辺が減ってしまった場合においても2のままでありつづけ,ある段階で突然無限にとんでしまう。(例えば、ほぼ全てのグラフの被覆数が2である。)また、着色数が3以上の場合、2着色の場合ほど突然ではなく、被覆数がもっと早い段階から増加していることがわかった。完全グラフの場合,2着色と3着色以上でも性質が似ているのに対し、ランダムグラフの場合でははっきりとした差が確認された。この意味でも興味深い。ランダムグラフ上で議論可能なラムゼ-的性質はまだあまり多くはないが、なかでも本研究における単色木被覆の研究は新たにわかった基礎的なラムゼ-的性質であり,本研究が、古典的な完全グラフ上での研究の単なる拡張ではなく、ランダムグラフとラムゼ-の融合による独特の課題であるという点でも意義が認められる。