第5回組合せ論若手研究集会

招待講演アブストラクト

平成 21 年 2 月 3 日 (火) ∼ 2 月 5 日 (木) 慶應義塾大学矢上キャンパス 12 棟 1 階 103 番教室

2 月 3 日 (火) 斎藤明氏 （日本大学）

「グラフの因子と禁止部分グラフ」

Sumner (1976) は連結な偶位数の K_{1,3}-フリーグラフは 1-因子を持つことを証明した。なぜ Sumner は 1-因子の存在を保証する禁止する部分グラフとして K_{1,3} を選んだのであろうか。この疑問を出発点として、本講演では様々な連結グラフを禁止することにより、その結果として 1-因子の存在が導かれるのか、また導かれない場合には最大マッチングの位数についてどの程度の情報が得られるのかを論じる。また１つではなく、複数のグラフを禁止した場合、連結度の高いグラフに制限した場合に状況がどのように変化するのかについても考察する。

2 月 3 日 (火) 小沢誠氏 （駒澤大学）

「Hierarchy of graphs by spatial embeddings」

グラフの空間埋め込みによる階層構造について解説します。現在まで、 S^{1}- linkless、 outer-linkless、 linkless embedding についての obstruction set が決定されており、それらの間には綺麗な階層構造があります。しかし、 knotless embedding についての obstruction set は未決定であり、どのようなグラフの集合なのか予想も挙げられておりません。この問題について、分かっていること、分かっていないことをご紹介します。

2 月 4 日 (水) Robert Morris 氏 （University of Cambridge）

「An introduction to bootstrap percolation」

Bootstrap percolation is a deterministic cellular automaton defined on a graph G. Given a (normally randomly chosen) set A ⊂ V (G) of ’initially infected’ vertices, and a parameter r ∈ ℕ, healthy vertices are infected, at each time step, if they have at least r already infected neighbours. The set A is said to ’percolate’ if eventually every vertex is infected. The main question is to determine the ’critical threshold’ p_{c} at which percolation becomes likely. In this talk I shall discuss the motivation and history of bootstrap percolation on the graph [n]^{d}, including its links with the Ising model and some very recent progress on the major questions. I shall also discuss a number of open problems.

2 月 5 日 (木) 岡本吉央氏 （東京工業大学）

「フロベニウス数のはなし」

互いに素な正整数がいくつか与えられたとき，それらの非負整数結合として書けない最大の整数が存在する．そのような数を与えられた数のフロベニウス数と呼ぶ．今回はフロベニウス数について知られていることのいくつかを主に幾何的な側面から紹介する．