[logic-ml] JAIST Logic Seminar Series

[Takako Nemoto]

皆様
インスブリア大学（イタリア）の Marco Benini 先生の講演のお知らせです。
どうぞふるってご参加ください。

問い合わせ先：
根元　多佳子
北陸先端科学技術大学院大学　情報科学系
email: t-nemoto at jaist.ac.jp
---------------------------------------------
*JAIST Logic Seminar Series*

Date: Tuesday, 6 June, 2017, 15:30-17:00

Place: JAIST, Collaboration room 7 (I-56)
(Access: http://www.jaist.ac.jp/english/location/access.html)

Speaker: Marco Benini (Università degli Studi dell'Insubria)

Title: The Graph Minor Theorem: a walk on the wild side of graphs

Abstract: The Graph Minor Theorem says that the collection of finite graphs
ordered by the minor relation is a well quasi order. This apparently
innocent statement hides a monstrous proof: the original result by
Robertson and Seymour is about 500 pages and twenty articles, in which a
new and deep branch of Graph Theory has been developed.

The theorem is famous and full of consequences both on the theoretical side
of Mathematics and in applications, e.g., to Computer Science. But there
is no concise proof available, although many attempts have been made.
In this talk, arising from one such failed attempts, an analysis of the
Graph Minor Theorem is presented. Why is it so hard?

Assuming to use the by-now standard Nash-Williams's approach to prove
it, we will
illustrate a number of methods which allow to solve or circumvent some
of the difficulties. Finally, we will show that the core of this line of
thought lies in a coherence question which is common to many parts of
Mathematics: elsewhere it has been solved, although we were unable to
adapt those solutions to the present framework. So, there is hope for a
short proof of the Graph Minor Theorem but it will not be elementary.