談話会


2017/11/20(Mon)

16:30--17:30 数学教室 大セミナー室 (E404)

太田 克弘

慶應義塾大学

極値グラフ理論の話題から

極値グラフ理論の典型的な問題は,与えられたグラフ H に対し,頂点数 n の グラフ G がどのくらい多くの辺を持てば(あるいは,最小次数がどのくらい 大きければ)必ず H を部分グラフとして含むか,その最善の値を n の関数と して与えるものである。H が完全グラフのときは,Turanの定理(1941)として よく知られている。また H の染色数が 3 以上の場合も,漸近的に最善の値が わかっている。一方,H が二部グラフのケースは「退化した場合」と呼ばれ, 未解決な問題も多く残されている。本講演では,とくに最も退化した場合であ る H が森グラフのときに着目し,知られている結果や予想などについて述べる。