Discrete Mathematics and Optimization Seminar
Tuesday, Jan. 11th, 2010
Vasek Chvatal (Canada Research Chair in Combinatorial Optimization)
Concordia University
A point in the plane is said to lie between points A and C if it is the interior point of the line segment joining A and C. In his development of geometry, Euclid neglected to give the notion of betweenness the same axiomatic treatment that he gave, for instance, to the notion of equality. This omission was rectified twenty-two centuries later by Moritz Pasch:


During the twentieth century, geometric betweenness was generalized in diverse branches of mathematics to ternary relations of metric betweennes, lattice betweenness, and algebraic betweenness. I will talk about three settings where such abstract betweennesses show up.

The first of these settings is ordered geometry; there, primitive notions of points and lines are linked by the relation of incidence and by axioms of betweenness; two classic theorems here are the Sylvester-Gallai theorem


and the de Bruijn-Erdos theorem. I conjectured in 1998


and Xiaomin Chen proved in 2003


that the Sylvester-Gallai theorem generalizes to metric spaces when lines in these spaces are defined right; together, we conjectured


that the de Bruijn-Erdos theorem also generalizes to metric spaces when lines in these spaces are defined right (with "right" having a different sense in each of the two instances); the two of us and Ehsan Chiniforooshan have partial results on this conjecture.

The second of the three settings is abstract convexity; there, families of sets called "convex" obey certain axioms. Such finite structures are called convex geometries when they have the Minkowski-Krein-Milman property: every set is the convex hull of its extreme points. Two classical examples of convex geometries come from shelling of partially ordered sets and simplicial shelling of triangulated graphs. Last June I characterized, by a five-point condition, a class of betweennesses generating a class of convex geometries that subsumes the two examples.


Laurent Beaudou, Ehsan Chiniforooshan, and I have additional results on such betweennesses.

The last setting lies between physics and philosophy: in his effort to develop a causal theory of time, Hans Reichenbach


introduced the notion of causal betweenness, which is a ternary relation defined on events in probability spaces. This January, Baoyindureng Wu and I characterized, by easily verifiable properties, abstract ternary relations isomorphic to Reichenbach's causal betweenness.


A nice connection with a 1979 theorem of Jarda Opatrny


appears here.

The joint work with Laurent Beaudou, Ehsan Chiniforooshan, and Baoyindureng Wu was done in our research group ConCoCO

(Concordia Computational Combinatorial Optimization).