# Connectivity of Bichromatic Matchings

## Greg Aloupis, New York University

## March 6, 2018

Given a set $S$ of $n$ red points and $n$ blue points in the
plane, a (non-crossing geometric bichromatic perfect) matching
consists of $n$ pairwise-disjoint straight-line segments, each of
which has a red endpoint and a blue endpoint. Two such matchings are
considered to be *neighbors* if their union does not strictly
intersect. We consider a graph $G$ in which every vertex corresponds
to a matching of $S$. If two matchings are neighbors, then
they share an edge in $G$. We show that for every set $S$ its
corresponding graph $G$ is connected.

Time permitting, we will
discuss bounds on the diameter of $G$, and will mention similar
results about matching of non-colorful point sets.

Joint work with Luis Barba, Stefan Langerman, and Diane Souvaine.