Flips in Odd Matchings
<|reference_start|>Flips in Odd Matchings: Let $\mathcal{P}$ be a set of $n=2m+1$ points in the plane in general position. We define the graph $GM_\mathcal{P}$ whose vertex set is the set of all plane matchings on $\mathcal{P}$ with exactly $m$ edges. Two vertices in $GM_\mathcal{P}$ are connected if the two corresponding matchings have $m-1$ edges in common. In this work we show that $GM_\mathcal{P}$ is connected and give an upper bound of $O(n^2)$ on its diameter. Moreover, we present a tight bound of $\Theta(n)$ for the diameter of the flip graph of points in convex position.<|reference_end|>
@article{aichholzer2024flips,
    title={Flips in Odd Matchings},
    author={Oswin Aichholzer, Anna Br"otzner, Daniel Perz, Patrick Schnider},
    journal={arXiv preprint arXiv:2410.06139},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.06139},
    primaryClass={cs.CG math.CO}
}