The Speakers

The conference features 10 keynote lectures by Robin Thomas.  Thomas' insightful work in the area of structural graph theory has enabled the discipline to enjoy its present reputation as a field with deep results, intricate connections to other areas in the mathematical and computer sciences and the potential  for profound advances in the years to come..  Neil Robertson and Paul Seymour revolutionized  the study of graph structure theory  with the development of  Graph Minors.  James Geelen, Bojan Mohar, Bruce Reed, and Dominic Welsh have all made significant contributions to the further development of the theory of graph structures. These six  world renown graph theorist will join Robin Thomas as auxiliary lecturers for this conference.

 

The 10 -Keynote Lectures

  1. Graph Planarity:  Graph planarity is a concept of fundamental importance. Not only do planar graphs form an important class of graphs from an applications point of view, but graph planarity also arises naturally in graph structure theory as an obstruction to various properties of interest (such as, for example, the two paths problem). In this talk, we will survey classical results, generalizations to surfaces of higher genus, as well as new directions such as the emerging field of Graph Drawing, Colin de Verdiere's parameter, and the role of graph embeddings in the graph minors project. This lecture will also serve as a preview of the rest of the series.
  2. Linear Planarity Algorithm: The two classical linear-time planarity algorithms are too complicated to be presented in a textbook. A recent algorithm of Shih and Hsu, independently discovered by Boyer and Myrvold, seems to be somewhat simpler. The lecturer will present this algorithm, based on his class notes.
  3. Tree-decompositions of Graphs I:  A graph has small tree-width if it has a tree-decomposition into small parts. Tree-width has become an important graph parameter during the last fifteen years. It forms the cornerstone of the Graph Minors project, but it has also found applications elsewhere in Graph Theory, in the design of efficient algorithms, and it has also been successfully used in practical computations. More generally, tree-decompositions into parts that are not necessarily small, but are controlled in terms of embeddings, are also important. These talk will give a comprehensive survey.
  4. Tree-decompositions of Graphs II:
  5. The Graph Minors Project: This lecture will explain the fundamental concepts and results from the Graph Minors project, including the Graph Minor theorem. The proof of the latter is still too long to be presented in a short lecture series, but several steps in the proof have been simplified by several researchers. We will present these simplified arguments, leading up to a proof of a conjecture of Erdos that the obstruction set for embedding into any fixed surface is finite. Use will be made of the theory of tree-decompositions developed in the previous two lectures.
  6. Excluded minor theorems and extremal problems: This lecture will survey excluded minor theorems and techniques to prove them. In the second part we will discuss how many edges are needed to guarantee a minor isomorphic to a specified graph.
  7. Spatial embeddings of graphs: This talk will focus on linkless embeddings of graphs; their characterization in terms of the fundamental group; uniqueness; a characterization in terms of excluded minors; and the recent characterization in terms of Colin de Verdiere's parameter. This will lead to open problems about knotlessly embeddable graphs, and the idea of relating higher values of the Colin de Verdiere parameter to suitable higher-dimensional embeddings.
  8. Pfaffian orientations: Given an n x n 0-1 matrix A, when can some of the 1's be changed to - 1's in such a way that the permanent of A equals the determinant of the modified matrix? When does a real n x n matrix A have the property that every real matrix B with the same sign pattern (that is, the corresponding entries either have the same sign, or are both zero) is non-singular? When is a hypergraph with n vertices and n hyperedges minimally non-bipartite? When does a bipartite graph have a "Pfaffian orientation"? Given a digraph, does it have no directed circuit of even length? Given a digraph, does it have a subdivision with no even directed circuit?  All those problems are equivalent. Their solution was obtained by means of a structural characterization of bipartite graphs that admit a Pfaffian orientation. A characterization of general graphs that admit a Pfaffian orientation remains open.
  9. The structure of directed graphs: Various isolated results about directed graphs have suggested the possibility of extending the graph minors project to directed graphs. This talk will introduce the recently developed notion of tree-width for directed graphs, and will discuss the prospects for extending other parts of the theory.
  10. The perfect graph conjecture: This talk will introduce the recent work of Chudnovsky, Robertson, Seymour and the lecturer on decompositions of Berge graphs. It will be followed by a more detailed exposition by Paul Seymour.

 

A Tentative Schedule

Monday (Thursday)

  1. 9:00 - 10:00 Lecture 1 (7).
  2. 11:00-12:00 Lecture 2 (8)
  3. 1:30-2:30 Auxiliary Lecture
  4. 4:15-5:15 Auxiliary Lecture

Tuesday

  1. 9:00 - 10:00 Lecture 3
  2. 11:00 - 12:00 Lecture 4
  3. 1:30 - 2:30 Auxiliary Lecture
  4. 7:15-8:15 Auxiliary Lecture

Wednesday

  1. 9:00- 10:00 Lecture 5
  2. 11-:00-12:00 Lecture 6

Friday

  1. 9:00 - 10:00 Lecture 9
  2. 12:00-1:00 Lecture 10