
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.



