組合せ論の極値的問題における確率的方法の研究

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

ランダムハイパーグラフ上のラムゼ-理論を主に研究した。この分野に多いに貢献した著者B.Bollobas著Random Graphs(1985)は、ランダムグラフ上でのラムゼ-理論にはほとんど触れていない。が、最近の研究によってこの著書もすでに古くなった感があり、ラムゼ-理論の発展と確率的手法,ランダムグラフの研究の進展とともに,近年、ランダムグラフでのラムゼ-理論が技術的に可能になってきた。ランダムハイパーグラフ上のラムゼ-理論となると、まだあまり研究されていない。Luczak氏らのランダムグラフにおけるRamsey的性質の研究をうけつぎ、最近、Kreuter氏がさらに広い場合について成果を拡張した。今回は,これらの状況をふまえ、さらにランダムハイパーグラフにおいて、これらの研究結果のいくつかを拡張した。ここでいうランダムハイパーグラフとは、もっとも標準的な確率モデルであるランダムk-ユニフォームハイパーグラフを採用した。つまり、n頂点完全k-ユニフォームハイパーグラフの各辺を一定の確率p(0<p<1)でとりだして作ったハイパーグラフを、ランダムハイパーグラフとして考える。ランダムハイパーグラフ上で議論可能なラムゼ-的性質はあまり多くはないが、本研究において新たにわかった成果は基礎的なラムゼ-的性質であり,ランダムハイパーグラフとラムゼ-の融合による独特の課題であるという点でも意義が認められる。