Perfect Matchings with Crossings

O. Aichholzer, R. Fabila-Monroy, P. Kindermann, I. Parada, R. Paul, D. Perz, P. Schnider, and B. Vogtenhuber

Abstract:

For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least

$$C_{n/2}$$

different plane perfect matchings, where

$$C_{n/2}$$

is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every

$$k\le \frac{1}{64}n^2-\frac{35}{32}n\sqrt{n}+\frac{1225}{64}n$$

, any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most

$$\frac{5}{72}n^2-\frac{n}{4}$$

crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for

$$k=0,1,2$$

, and maximize the number of perfect matchings with

$$\left( {\begin{array}{c}n/2\\ 2\end{array}}\right)$$

crossings and with

$${\left( {\begin{array}{c}n/2\\ 2\end{array}}\right) }\!-\!1$$

crossings.

Reference: O. Aichholzer, R. Fabila-Monroy, P. Kindermann, I. Parada, R. Paul, D. Perz, P. Schnider, and B. Vogtenhuber. Perfect matchings with crossings. Algorithmica, 86:697-716, 2024.