|
|
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.
|
|
|
|