
Discrete Mathematics and Optimization Seminar

Tuesday, Jan. 11th, 2010
Betweenness
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 twentytwo
centuries later by Moritz Pasch:
http://wwwgroups.dcs.stand.ac.uk/~history/Biographies/Pasch.html
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
SylvesterGallai theorem
http://mathworld.wolfram.com/SylvestersLineProblem.html
and the de BruijnErdos theorem. I conjectured in 1998
http://users.encs.concordia.ca/~chvatal/newsg.pdf
and Xiaomin Chen proved in 2003
http://dimacs.rutgers.edu/TechnicalReports/abstracts/2003/200332.html
that the SylvesterGallai theorem generalizes to metric spaces when
lines in these spaces are defined right; together, we conjectured
http://arxiv.org/abs/math.CO/0610036
that the de BruijnErdos 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 MinkowskiKreinMilman
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 fivepoint condition, a class of
betweennesses generating a class of convex geometries that subsumes
the two examples.
http://users.encs.concordia.ca/~chvatal/abc.pdf
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
http://en.wikipedia.org/wiki/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.
http://arxiv.org/abs/0902.1763
A nice connection with a 1979 theorem of Jarda Opatrny
http://dx.doi.org/10.1137/0208008
appears here.
The joint work with Laurent Beaudou, Ehsan Chiniforooshan, and
Baoyindureng Wu was done in our research group ConCoCO
http://users.encs.concordia.ca/~concoco/
(Concordia Computational Combinatorial Optimization).



