Discrete Mathematics and Optimization Seminar
May. 29, 2009
MC 320, 11:20AM
Compatible Matchings
David Rappaport
Queen's University
A set of disjoint planar line segments represents a plane perfect matching of the endpoints of the segments, and two plane matchings on the same vertex set are compatible if no two edges cross.

The compatible matchings conjecture is: Given a set of 4n points and a plane perfect matching there is a disjoint compatible matching.

I will present several partial results that suggest that the compatible matchings conjecture is true. I will also show how some techniques that have been attempted to prove this conjecture are doomed to failure.