Perfect matchings with crossings. (English) Zbl 07823154
Summary: 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 \(\binom{n/2}{2}\) crossings and with \(\binom{n/2}{2} - 1\) crossings.
References:
| [1] | Aichholzer, O.; Fabila-Monroy, R.; Kindermann, P.; Parada, I.; Paul, R.; Perz, D.; Schnider, P.; Vogtenhuber, B.; Bazgan, C.; Fernau, H., Perfect matchings with crossings, Combinatorial Algorithms, 46-59, 2022, Cham: Springer, Cham · Zbl 07577689 · doi:10.1007/978-3-031-06678-8_4 |
| [2] | Aichholzer, O., Fabila-Monroy, R., Kindermann, P., Parada, I., Paul, R., Perz, D., Schnider, P., Vogtenhuber, B.: In: Abstracts of the Computational Geometry: Young Researchers Forum, pp. 24-27 (2021). https://cse.buffalo.edu/socg21/files/YRF-Booklet.pdf#page=24 |
| [3] | Asinowski, A.:The number of non-crossing perfect plane matchings is minimized (almost) only by point sets in convex position. arXiv preprint arXiv:1502.05332 (2015) |
| [4] | Asinowski, A.; Rote, G., Point sets with many non-crossing perfect matchings, Comput. Geom., 68, 7-33, 2018 · Zbl 1380.05156 · doi:10.1016/j.comgeo.2017.05.006 |
| [5] | García, A.; Noy, M.; Tejel, J., Lower bounds on the number of crossing-free subgraphs of \(K_n\), Comput. Geom., 16, 4, 211-221, 2000 · Zbl 0966.68158 · doi:10.1016/S0925-7721(00)00010-9 |
| [6] | Sharir, M.; Welzl, E., On the number of crossing-free matchings, cycles, and partitions, SIAM J. Comput., 36, 3, 695-720, 2006 · Zbl 1120.68085 · doi:10.1137/050636036 |
| [7] | You, C.: Improving Sharir and Welzl’s bound on crossing-free matchings through solving a stronger recurrence. arXiv preprint arXiv:1701.05909 (2017) |
| [8] | Callan, D.: A combinatorial survey of identities for the double factorial (2009) |
| [9] | Aronov, B.; Erdős, P.; Goddard, W.; Kleitman, DJ; Klugerman, M.; Pach, J.; Schulman, LJ, Crossing families, Combinatorica, 14, 127-134, 1994 · Zbl 0804.52010 · doi:10.1007/BF01215345 |
| [10] | Aichholzer, O.; Kynčl, J.; Scheucher, M.; Vogtenhuber, B.; Valtr, P., On crossing-families in planar point sets, Comput. Geom., 107, 2022 · Zbl 1491.05058 · doi:10.1016/j.comgeo.2022.101899 |
| [11] | Pach, J.; Rubin, N.; Tardos, G., Planar point sets determine many pairwise crossing segments, Adv. Math., 386, 2021 · Zbl 1467.05050 · doi:10.1016/j.aim.2021.107779 |
| [12] | Pach, J.; Solymosi, J., Halving lines and perfect cross-matchings, Adv. Discrete Comput. Geom., 223, 245-249, 1999 · Zbl 0934.05120 · doi:10.1090/conm/223 |
| [13] | Flajolet, P.; Noy, M.; Krob, D.; Mikhalev, AA; Mikhalev, AV, Analytic combinatorics of chord diagrams, Formal Power Series and Algebraic Combinatorics, 191-201, 2000, Berlin: Springer, Berlin · Zbl 0956.05007 · doi:10.1007/978-3-662-04166-6_17 |
| [14] | Pilaud, V.; Rue, J., Analytic combinatorics of chord and hyperchord diagrams with \(k\) crossings, Adv. Appl. Math., 57, 60-100, 2014 · Zbl 1295.05036 · doi:10.1016/j.aam.2014.04.001 |
| [15] | Riordan, J., The distribution of crossings of chords joining pairs of \(2n\) points on a circle, Math. Comput., 29, 129, 215-222, 1975 · Zbl 0319.05004 · doi:10.2307/2005477 |
| [16] | Aichholzer, O.; Aurenhammer, F.; Krasser, H., Enumerating order types for small point sets with applications, Order, 19, 265-281, 2002 · Zbl 1027.68127 · doi:10.1023/A:1021231927255 |
| [17] | Ábrego, BM; Fernández-Merchant, S.; Leaños, J.; Salazar, G., A central approach to bound the number of crossings in a generalized configuration, Electron. Not. Discrete Math., 30, 273-278, 2008 · Zbl 1341.05035 · doi:10.1016/j.endm.2008.01.047 |
| [18] | Aichholzer, O.; Hackl, T.; Huemer, C.; Hurtado, F.; Krasser, H.; Vogtenhuber, B., On the number of plane geometric graphs, Graphs Combin., 23, 1, 67-84, 2007 · Zbl 1119.05056 · doi:10.1007/s00373-007-0704-5 |
| [19] | Nivasch, G., An improved, simple construction of many halving edges, Contemp. Math., 453, 299-306, 2008 · Zbl 1148.68552 · doi:10.1090/conm/453/08804 |
| [20] | Dey, TK, Improved bounds for planar k-sets and related problems, Discrete Comput. Geom., 19, 373-382, 1998 · Zbl 0899.68107 · doi:10.1007/PL00009354 |
| [21] | Eppstein, D., Counting polygon triangulations is hard, Discrete Comput. Geom., 64, 4, 1210-1234, 2020 · Zbl 1460.52022 · doi:10.1007/s00454-020-00251-7 |
| [22] | Cabello, S.; Cardinal, J.; Langerman, S., The clique problem in ray intersection graphs, Discrete Comput. Geom., 50, 3, 771-783, 2013 · Zbl 1275.05032 · doi:10.1007/s00454-013-9538-5 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
