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 twenty-two centuries later by Moritz Pasch: http://www-groups.dcs.st-and.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 Sylvester-Gallai theorem http://mathworld.wolfram.com/SylvestersLineProblem.html and the de Bruijn-Erdos 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/2003-32.html that the Sylvester-Gallai 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 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. 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).