**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

**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