FULL PAPER SUBMISSION

CIMPA School on Combinatorics and Algorithms

Speakers

Adrian Bondy
Université Claude Bernard Lyon 1, France

Vašek Chvátal
Rutgers University, USA

Gérard Cornuéjols
Carnegie Mellon University, USA

Luc Devroye
McGill University, Canada

László Lovász
Microsoft Corporation, USA

Bruce Reed
University Paris VI and CNRS, France

William Tutte
University of Waterloo, Canada

Talks

Title of the talk: Triangles in Graphs and Directed Graphs
Speaker: Adrian Bondy

Title of the talk: The Sylvester-Gallai Theorem and Metric Spaces
Speaker: Vasek Chvátal
Abstract: Sylvester conjectured in 1890 and Gallai proved in 1930 that every finite set S of points in the plane includes two points such that the line passing through them includes either no other point of S or all other points of S. I have conjectured that, with a suitable definition of a line, this theorem generalizes from finite subsets of the plane to arbitrary finite metric spaces. I will present first the suitable definition and then meagre evidence in support of the arrogant conjecture. In addition, I will rant about the ternary relation of betweenness in metric spaces.

Title of the talk: Square-Free Perfect Graphs
Speaker: Gérard Cornuéjols
Abstract: In joint work with Michele Conforti and Kristina Vuskovic, we prove that square-free perfect graphs are bipartite graphs or line graphs of bipartite graphs or have a 2-join or a star cutset. Since minimal imperfect graphs cannot contain a 2-join (Cornuejols-Cunningham 1985) nor a star cutset (Chvatal 1985), it follows that the Strong Perfect Graph Conjecture holds for square-free graphs.

Title of the talk: Tries and concentration
Speaker: Luc Devroye
Abstract: Tries are trees used for storing strings. We will survey recent results on the complexity of various algorithms that operate on random tries and show interesting new applications of concentration inequalities.

Title of the talk: Shortest paths, resistance, and the energy of convex sets
Speaker: Dr. L. Lovász
Abstract: Let us assign independent, exponentially distributed random edge lengths to the edges of an undirected graph. Lyons, Pemantle and Peres proved that the expected length of the shortest path between two given nodes is bounded from below by the resistance between these nodes, where the resistance of an edge is the expectation of its length. They remarked that instead of exponentially distributed variables, one could consider random variables with a log-concave tail. We generalize this result in two directions. First, we note that the variables don't have to be independent: it suffices to assume that their joint distribution is log-concave. Second, the inequality can be formulated as follows: the expected length of a shortest path between two given nodes is the expected optimum of a stochastic linear program over a flow polytope, while the resistance is the minimum of a convex quadratic function over this polytope. We show that the inequality between these quantities holds true for an arbitrary polytope provided its blocker has integral vertices.

Title of the talk: List Colouring Via the Probabilisitc Method
Speaker: Bruce Reed
Abstract: We discuss partial solutions to two recent conjectures on list colouring. The techniques used are probabilistic, one goal of the talk is to provide a gentle introduction to such techniques.

Title of the talk: The FISH Machine at Bletchley Park
Speaker: William Tutte