5ECM Minisymposium on Graphs and Matroids
Friday July 18, 2008, 10.30-12 am + 1.30-3 pm

Many real-world problems can be modeled by networks (graphs) and matrices. Algorithms for such problems often rely on an insightful visualization of the model, on an embedding in a space we understand, like a particular topological or linear space. Typical examples are planarity of graphs and total unimodularity of matrices. The search for understanding such structural properties often leads to new challenging research directions. A concrete example is the famous and deep Robertson Seymour Graph Minor Project. One of its major outcomes is that, under reasonable conditions on how you wish to visualize graphs, there is an efficient algorithm that creates such visualization if it exists and otherwise certifies that it cannot be done. This required a deep understanding of the structure of so called minor-closed classes of graphs. The minisymposium is devoted to these issues for graphs and for matroids. Matroids abstract the in this context relevant combinatorial properties of matrices.

Program: 10.30-11.15: Paul Seymour Princeton University, Princeton, NJ, USA Perfect matchings in planar cubic graphs. A well-known conjecture of Lovász and Plummer from the 1970's asserts that for every 2-edge-connected cubic graph G with n vertices, the number of perfect matchings in G is exponential in n. This seems to be wide open still, and as far as we know the best lower bound is n/2 + 1. In this talk we sketch a proof of the Lovász-Plummer conjecture for PLANAR cubic graphs. In this case the problem is more tractable, because we can use the four-colour theorem as a source of 3-edge-colourings and hence of perfect matchings. This is joint work with Maria Chudnovsky, Columbia University. 11.15-12.00: Jim Geelen University of Waterloo, Waterloo, Ontario, Canada Matroid minors. In joint work with Bert Gerards and Geoff Whittle, we hope to extend the Graph Minors Project of Neil Robertson and Paul Seymour to matroids representable over a fixed finite field. In this talk we discuss the motivation for the project and report on our progress. 13.30-14.15: Robin Thomas Georgia Institute of Technology, Atlanta, GA, USA Kt minors in large t-connected graphs. A graph G has a Kt minor if a graph isomorphic to Kt, the complete graph on t vertices, can be obtained from a subgraph of G by contracting edges. Jorgensen conjectured that every 6-connected graph with no K6 minor has a vertex whose deletion makes the graph planar. This is of interest, because it implies Hadwiger's conjecture for graphs with no K6 minor (which is known to be true, but Jorgensen's conjecture would give more structural information). I conjecture that for every integer t there exists an integer N such that every t-connected graph on at least N vertices with no Kt minor has a set of at most t-5 vertices whose deletion makes the graph planar. If true, this would be best possible in the sense that neither t-connectivity nor the size of the deleted set can be lowered, and for t>7 some lower bound on the number of vertices is needed. Furthermore, no graph satisfying the conclusion of the conjecture has a Kt minor. A couple of years ago we proved the conjecture for t=6 in joint work with Matt DeVos, Rajneesh Hegde, Kenichi Kawarabayashi, Sergey Norin and Paul Wollan. Thus Jorgensen's conjecture holds for sufficiently big graphs. In the talk I will report on recent progress for t>6 obtained in joint work with Sergey Norin. 14.15-15.00: Carsten Thomassen Danmarks Tekniske Universitet, Lyngby, Denmark Graph decomposition. János Barát and I made the following conjecture: For every tree T, there is a natural number kT such that every kT-edge-connected graph of size divisible by |E(T)| has an edge-decomposition into subgraphs each isomorphic to T. The conjecture is trivial when T has at most two edges. When we made the conjecture we could not prove it for one single tree with three or more edges. However, we showed that the conjecture holds for the claw (the star with three edges) provided Tutte's 3-flow conjecture is true. A year ago I verified the conjecture for one tree. Recently, I have verified it for a second tree.

Organizers:	Sponsors:
Bert Gerards, Centrum Wiskunde & Informatica and Technische Universiteit Eindhoven Hein van der Holst, Technische Universiteit Eindhoven Rudi Pendavingh, Technische Universiteit Eindhoven

This minisymposium is organized in conjunction with
The Netherlands Workshop on Graphs and Matroids, 2008
Sittard, July 19-22, 2008