×

A SAT attack on Erdős-Szekeres numbers in \(\mathbb{R}^d\) and the empty hexagon theorem. (English) Zbl 1535.52016

Summary: A famous result by P. Erdős and G. Szekeres [Compos. Math. 2, 463–470 (1935; Zbl 0012.27010; JFM 61.0651.04)] asserts that, for all \(k, d \in \mathbb{N}\), there is a smallest integer \(n = g^{(d)}(k)\) such that every set of at least \(n\) points in \(\mathbb{R}^d\) in general position contains a \(k\)-gon, that is, a subset of \(k\) points in convex position. We present a SAT model based on acyclic chirotopes (oriented matroids) to investigate Erdős-Szekeres numbers in small dimensions. SAT instances are solved using modern SAT solvers and unsatisfiability results are verified using DRAT certificates. We show \(g^{(3)}(7) = 13, g^{(4)}(8) \leq 13\), and \(g^{(5)}(9) \leq 13\), which are the first improvements for decades. For the setting of \(k\)-holes (i.e., \(k\)-gons with no other points in the convex hull), where \(h^{(d)}(k)\) denotes the smallest integer \(n\) such that every set of at least \(n\) points in \(R^d\) in general position contains a \(k\)-hole, we show \(h^{(3)}(7) \leq 14, h^{(4)}(8) \leq 13\), and \(h^{(5)}(9) \leq 13\). All obtained bounds are sharp in the setting of acyclic chirotopes and we conjecture them to be sharp also in the original setting of point sets. Last but not least, we verify all previously known bounds and, in particular, we present the first computer-assisted proof for the existence of 6-holes in sufficiently planar point sets by verifying Gerken’s estimate \(h^{(2)}(6) \leq g^{(2)}(9)\).

MSC:

52C10 Erdős problems and related topics of discrete geometry
68V05 Computer assisted proofs of proofs-by-exhaustion type
52C40 Oriented matroids in discrete geometry

Software:

DRAT-trim; CaDiCaL
Full Text: DOI

References:

[1] O. Aichholzer. Webpage: Enumerating order types for small point sets with applications. http://www.ist.tugraz.at/aichholzer/research/rp/triangulations/ordertypes/.
[2] O. Aichholzer, F. Aurenhammer, and H. Krasser. Enumerating order types for small point sets with applications. Order, 19(3):265-281, 2002. doi:10.1023/A:1021231927255. · Zbl 1027.68127 · doi:10.1023/A:1021231927255
[3] O. Aichholzer and H. Krasser. Abstract order type extension and new results on the rectilinear crossing number. Computational Geometry: Theory and Applications, 36(1):2-15, 2006. doi:10.1016/j.comgeo.2005.07.005. · Zbl 1110.65019 · doi:10.1016/j.comgeo.2005.07.005
[4] G. Audemard and L. Simon. Predicting Learnt Clauses Quality in Modern SAT Solvers. In Proc. 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), pages 399-404, 2009. http://ijcai.org/Proceedings/2009/.
[5] A. Biere. CaDiCaL at the SAT Race 2019. In Proc. of SAT Race 2019 -Solver and Bench-mark Descriptions, volume B-2019-1 of Department of Computer Science Series, pages 8-9. University of Helsinki, 2019. URL: http://researchportal.helsinki.fi/en/publications/ proceedings-of-sat-race-2019-solver-and-benchmark-descriptions.
[6] T. Bisztriczky and H. Harborth. On empty convex polytopes. Journal of Geometry, 52:25-29, 1995. doi:10.1007/BF01406823. · Zbl 0818.52008 · doi:10.1007/BF01406823
[7] T. Bisztriczky and V. Soltan. Some Erdős-Szekeres type results about points in space. Monatshefte für Mathematik, 118(1):33-40, 1994. doi:10.1007/BF01305772. · Zbl 0811.52005 · doi:10.1007/BF01305772
[8] A. Björner, M. Las Vergnas, B. Sturmfels, N. White, and G. M. Ziegler. Oriented Matroids, volume 46 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, second edition, 1999. doi:10.1017/CBO9780511586507. · Zbl 0944.52006 · doi:10.1017/CBO9780511586507
[9] J. Bokowski and J. Richter. On the finding of final polynomials. European Journal of Combinatorics, 11(1):21-34, 1990. doi:10.1016/S0195-6698(13)80052-2. · Zbl 0693.05021 · doi:10.1016/S0195-6698(13)80052-2
[10] W. E. Bonnice. On convex polygons determined by a finite planar set. The American Mathematical Monthly, 81(7):749-752, 1974. doi:10.2307/2319566. · Zbl 0295.52002 · doi:10.2307/2319566
[11] B. Bukh, T.-W. Chao, and R. Holzman. On convex holes in d-dimensional point sets. Combi-natorics, Probability and Computing, 31(1):101-108, 2022. doi:10.1017/S0963548321000195. · Zbl 1511.52018 · doi:10.1017/S0963548321000195
[12] D. Conlon and J. Lim. Fixing a hole, 2021. arXiv:2108.07087.
[13] Klee V. Danzer L., Grünbaum B. Helly’s theorem and its relatives. In Proceedings of Symposia in Pure Mathematics: Convexity, volume 7, pages 101-180. AMS, 1963. doi: doi.org/10.1090/pspum/007. · Zbl 0132.17401 · doi:10.1090/pspum/007
[14] P. Erdős and G. Szekeres. A combinatorial problem in geometry. Compositio Mathematica, 2:463-470, 1935. URL: http://www.renyi.hu/ p_erdos/1935-01.pdf. · Zbl 0012.27010
[15] P. Erdős and G. Szekeres. On some extremum problems in elementary geometry. Annales Universitatis Scientiarium Budapestinensis de Rolando Eötvös Nominatae, Sectio Mathematica, 3-4:53-63, 1960.
[16] P. Erdős. Some more problems on elementary geometry. Australian Mathematical Society Gazette, 5:52-54, 1978. URL: http://www.renyi.hu/ p_erdos/1978-44.pdf. · Zbl 0417.52002
[17] W. Evans, P. Rzazewski, N. Saeedi, C.-S. Shin, and A. Wolff. Representing graphs and hypergraphs by touching polygons in 3d. In Graph Drawing and Network Visualization, volume 11904 of LNCS, pages 18-32. Springer, 2019. doi:10.1007/978-3-030-35802-0_2. · Zbl 1542.68143 · doi:10.1007/978-3-030-35802-0_2
[18] S. Felsner and H. Weil. Sweeps, arrangements and signotopes. Discrete Applied Mathematics, 109(1):67-94, 2001. doi:10.1016/S0166-218X(00)00232-8. · Zbl 0967.68159 · doi:10.1016/S0166-218X(00)00232-8
[19] L. Finschi. Webpage: Homepage of oriented matroids. https://finschi.com/math/om.
[20] L. Finschi. A graph theoretical approach for reconstruction and generation of oriented matroids. PhD thesis, ETH Zürich, Switzerland, 2001. doi:10.3929/ethz-a-004255224. · Zbl 1005.52013 · doi:10.3929/ethz-a-004255224
[21] L. Finschi and K. Fukuda. Generation of oriented matroids-a graph theoretical approach. Discrete & Computational Geometry, 27(1):117-136, 2002. doi:10.1007/s00454-001-0056-5. · Zbl 1005.52013 · doi:10.1007/s00454-001-0056-5
[22] R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner. The Crossing Tverberg Theorem. In 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of LIPIcs, pages 38:1-38:13. Schloss Dagstuhl, 2019. doi:10.4230/LIPIcs.SoCG.2019.38. · Zbl 07559238 · doi:10.4230/LIPIcs.SoCG.2019.38
[23] C G T 2:12 A SAT Attack on Erdős-Szekeres Numbers in R d and the Empty Hexagon Theorem
[24] T. Gerken. Empty Convex Hexagons in Planar Point Sets. Discrete & Computational Geometry, 39(1):239-272, 2008. doi:10.1007/s00454-007-9018-x. · Zbl 1184.52016 · doi:10.1007/s00454-007-9018-x
[25] H. Harborth. Konvexe Fünfecke in ebenen Punktmengen. Elemente der Mathematik, 33:116-118, 1978. URL: http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002079801. · Zbl 0397.52005
[26] A. F. Holmsen, H. N. Mojarrad, J. Pach, and G. Tardos. Two extensions of the Erdős-Szekeres problem. Journal of the European Mathematical Society, pages 3981-3995, 2020. doi:10.4171/jems/1000. · Zbl 1454.52015 · doi:10.4171/jems/1000
[27] J. D. Horton. Sets with no empty convex 7-gons. Canadian Mathematical Bulletin, 26:482-484, 1983. doi:10.4153/CMB-1983-077-8. · Zbl 0521.52010 · doi:10.4153/CMB-1983-077-8
[28] J. D. Kalbfleisch, J. G. Kalbfleisch, and R. G. Stanton. A combinatorial problem on convex n-gons. In Louisiana Conference on Combinatorics, Graph Theory, and Computing, pages 180-188, 1970. · Zbl 0223.52009
[29] G. Károlyi. Ramsey-remainder for convex sets and the Erdős-Szekeres theorem. Discrete Applied Mathematics, 109(1):163-175, 2001. doi:10.1016/S0166-218X(00)00234-1. · Zbl 0974.52014 · doi:10.1016/S0166-218X(00)00234-1
[30] G. Károlyi and P. Valtr. Point configurations in d-space without large subsets in convex position. Discrete & Computational Geometry, 30(2):277-286, 2003. doi:10.1007/s00454-003-0009-4. · Zbl 1051.52012 · doi:10.1007/s00454-003-0009-4
[31] D. E. Knuth. Axioms and Hulls, volume 606 of LNCS. Springer, 1992. doi:10.1007/ 3-540-55611-7_1. · Zbl 0777.68012 · doi:10.1007/3-540-55611-7_1
[32] V. A. Koshelev. On the Erdős-Szekeres problem. Doklady Mathematics, 16(2):603-605, 2007. doi:10.1134/S106456240704031X. · Zbl 1162.52009 · doi:10.1134/S106456240704031X
[33] V. A. Koshelev. On Erdős-Szekeres problem for empty hexagons in the plane. Modelirovanie i Analiz Informatsionnykh Sistem, 16(2):22-74, 2009. In Russian. URL: http://mi.mathnet. ru/eng/mais52.
[34] H. Krasser. Order Types of Point Sets in the Plane. PhD thesis, Institute for Theoretical Computer Science, Graz University of Technology, Austria, 2003.
[35] F. Marić. Fast formal proof of the Erdős-Szekeres conjecture for convex polygons with at most 6 points. Journal of Automated Reasoning, 62:301-329, 2019. doi:10.1007/s10817-017-9423-7. · Zbl 1468.68302 · doi:10.1007/s10817-017-9423-7
[36] J. Matoušek. Lectures on Discrete Geometry. · Zbl 0999.52006
[37] Springer, 2002. doi:10.1007/ · doi:10.1007/978-1-4613-0039-7
[38] W. Morris and V. Soltan. The Erdős-Szekeres problem on points in convex position -a survey. Bulletin of the AMS. New Series, 37(4):437-458, 2000. doi:10.1090/S0273-0979-00-00877-6. · Zbl 0958.52018 · doi:10.1090/S0273-0979-00-00877-6
[39] M. C. Nicolás. The Empty Hexagon Theorem. Discrete & Computational Geometry, 38(2):389-397, 2007. doi:10.1007/s00454-007-1343-6. · Zbl 1146.52010 · doi:10.1007/s00454-007-1343-6
[40] M. Overmars. Finding Sets of Points without Empty Convex 6-Gons. Discrete & Computational Geometry, 29(1):153-158, 2002. doi:10.1007/s00454-002-2829-x. · Zbl 1019.52010 · doi:10.1007/s00454-002-2829-x
[41] M. Scheucher. Webpage: A SAT attack on higher dimensional Erdős-Szekeres numbers. http://page.math.tu-berlin.de/ scheuch/suppl/ES/highdim/. · Zbl 07912972
[42] M. Scheucher. Points, Lines, and Circles: Some Contributions to Combinatorial Geometry. Doctoral thesis, Technische Universität Berlin, 2020. doi:10.14279/depositonce-9542. · doi:10.14279/depositonce-9542
[43] M. Scheucher. Two disjoint 5-holes in point sets. Computational Geometry, 91:101670, 2020. doi:10.1016/j.comgeo.2020.101670. · Zbl 1474.68428 · doi:10.1016/j.comgeo.2020.101670
[44] M. Scheucher. A SAT attack on higher dimensional Erdős-Szekeres numbers. In Extended Abstracts EuroComb 2021, volume 14 of TM, pages 103-110. Springer, 2021. doi:10.1007/ 978-3-030-83823-2_17. · Zbl 07912972 · doi:10.1007/978-3-030-83823-2_17
[45] A. Suk. On the Erdős-Szekeres convex polygon problem. Journal of the AMS, 30:1047-1053, 2017. doi:10.1090/jams/869. · Zbl 1370.52032 · doi:10.1090/jams/869
[46] G. Szekeres and L. Peters. Computer solution to the 17-point Erdős-Szekeres problem. Australia and New Zealand Industrial and Applied Mathematics, 48(2):151-164, 2006. doi: 10.1017/S144618110000300X. · Zbl 1152.52008 · doi:10.1017/S144618110000300X
[47] G. Tóth and P. Valtr. The Erdős-Szekeres theorem: Upper bounds and related results. In Combinatorial and Computational Geometry, volume 52 of MSRI Publications, pages 557-568. · Zbl 1090.52014
[48] P. Valtr. Convex independent sets and 7-holes in restricted planar point sets. Discrete & Computational Geometry, 7(2):135-152, 1992. doi:10.1007/bf02187831. · Zbl 0748.52005 · doi:10.1007/bf02187831
[49] P. Valtr. Sets in R d with no large empty convex subsets. Discrete Mathematics, 108(1):115-124, 1992. doi:10.1016/0012-365x(92)90665-3. · Zbl 0766.52003 · doi:10.1016/0012-365x(92)90665-3
[50] P. Valtr. On Empty Hexagons. In Surveys on Discrete and Computational Geometry: Twenty Years Later, volume 453 of Contemporary Mathematics, pages 433-441. AMS, 2008. doi:10.1090/conm/453/08809. · Zbl 1147.52301 · doi:10.1090/conm/453/08809
[51] N. Wetzler, M. J. H. Heule, and W. A. Hunt. DRAT-trim: Efficient checking and trimming using expressive clausal proofs. In Theory and Applications of Satisfiability Testing -SAT 2014, volume 8561 of LNCS, pages 422-429. Springer, 2014. doi:10.1007/978-3-319-09284-3_31. · Zbl 1423.68475 · doi:10.1007/978-3-319-09284-3_31
[52] C. Pohoata D. Zakharov. Convex polytopes from fewer points, 2022. arXiv:2208.04878.
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.