Speaker: | David Rappaport |
School of Computing | |
Queen's University |
Title: Compatible Matchings
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.