- Supervisor
- Marco Benini - Università dell'Insubria
- Date and time
- Monday, April 3, 2017 at 4:00 PM - Rinfresco 15.45, inizio seminario 16.00.
- Place
- Ca' Vignal - Piramide, Floor 0, Hall Verde
- Programme Director
- Peter Michael Schuster
- External reference
- Publication date
- March 18, 2017
- Department
- Computer Science

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.

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.

© 2002 - 2021
Verona University

Via dell'Artigliere 8, 37129 Verona |
P. I.V.A. 01541040232 |
C. FISCALE 93009870234