Maria Chudnovsky (Columbia), Vertex-disjoint paths in tournaments

The question of linking pairs of terminals by disjoint paths is a standard and well-studied question in graph theory. The setup is: given vertices s1,..,sk and t1,..,tk, is there a set of disjoint path P1,..,Pk such that Pi is a path from si to ti? This question makes sense in both directed and undirected graphs, and the paths may be required to be edge- or vertex-disjoint.

For undirected graphs, a polynomial-time algorithm for solving both the edge-disjoint and the vertex-disjoint version of the problem (where the number k of terminals is fixed) was first found by Robertson and Seymour, and is a part of their well-known Graph Minors project. For directed graphs, both problems are NP-complete, even when k=2 (by a result of Fortune, Hopcroft and Wyllie). However, if we restrict our attention to tournaments (these are directed graphs with exactly one arc between every two vertices), the situation improves. Polynomial time algorithms for solving the edge-disjoint and the vertex-disjoint paths problems when k=2 have been known for a while (these are results of Bang-Jensen, and Bang-Jensen and Thomassen, respectively).
 

Last year, Fradkin and Seymour were able to design a polynomial-time algorithm to solve the edge-disjoint paths problem in tournaments for general (fixed) k, using a new parameter for tournaments, developed by Seymour and the speaker, called "cut-width". However, the vertex-disjoint paths problem seemed to be resistant to similar methods. This talk will
focus on a polynomial-time algorithm to solve the vertex-disjoint paths problem in tournaments for general (fixed) k, that we have recently obtained in joint work with Scott and Seymour.

Leslie Goldberg (Liverpool), Estimating the partition function of the ferromagnetic Ising model on a regular matroid 

We investigate the computational difficulty of approximating the partition function of the ferromagnetic Ising model on a regular matroid. Jerrum and Sinclair have shown that there is a fully polynomial randomised approximation scheme (FPRAS) for the class of graphic matroids. On the other hand, the authors have previously shown, subject to a complexity-theoretic assumption, that there is no FPRAS for the class of binary matroids, which is a proper superset of the class of graphic matroids. In order to map out the region where approximation is feasible, we focus on the class of regular matroids, an important class of matroids which properly includes the class of graphic matroids, and is properly included in the class of binary matroids. Using Seymour's decomposition theorem, we give an FPRAS for the class of regular matroids. (Joint work with Mark Jerrum, paper available at http://arxiv.org/abs/1010.6231)

Francisco Santos (Cantabria), Counter-examples to the Hirsch conjecture

The Hirsch conjecture, stated in 1957, said that if a polyhedron is defined by n linear inequalities in d variables then its combinatorial diameter should be at most n-d. That is, it should be possible to travel from any vertex to any other vertex in at most n-d steps (traversing an edge at each step). The unbounded case was disproved by Klee and Walkup in 1967. In this talk I describe my construction of the first counter-examples to the bounded case (polytopes).

The conjecture was posed and is relevant in connection to linear programming since the simplex method, one of the ‘mathematical algorithms with the greatest impact in science and engineering in the 20th century’, solves linear programming problems by traversing the graph of the feasibility polyhedron.