グラフ・ネットワークにおける理論と最適化グループセミナー
日時
2013年1月30日 (水) 17:00 ～
場所
国立情報学研究所 2208号室
講演者
Sang-il Oum 先生(KAIST)
タイトル
Well-quasi-ordering conjecture for pivot-minors
アブストラクト
The graph minor theorem of Robertson and Seymour, one of the deepest theorems in graph theory, states that every infinite set of graphs contains a pair G, H of graphs such that G is isomorphic to a minor of H. I will talk about a similar conjecture on pivot-minors of graphs and related result.
Surprisingly, this conjecture, if true, would imply the graph minor theorem as well as the theorem by Geelen, Gerards,
and Whittle on the well-quasi-ordering of binary matroids. This conjecture is equivalent to the statement that every pivot-minor-closed class C of graphs has finitely many forbidden obstructions; I proved that if C has bounded rank-width, then this conjecture is true.
On the other hand, the number of obstructions could be very big; a recent theorem by Jisu Jeong, O-joung Kwon and myself states that the number of pivot-minor obstructions for graphs of linear rank-width k grows double exponential in k.
