Approaching Problems from Combinatorics and Geometry using Computer Assistance

• Applicant: Dr. Manfred Scheucher
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: since 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 466040716

In this project we will investigate problems on point sets, line arrangements, circle arrangements, and other basic structures from geometry. For our studies, the excessive usage of computer proofs and the combination with classical mathematical proving techniques will play a central role.The project consists of the following three major parts:Part I: The biggest part of this project will be focussing on the computer-assisted investigation of problems arising in combinatorics and geometry, for which we plan to combine classical pen-and-paper proving-techniques with heavy computer-assistance. In the last years, the applicant and his coauthors successfully attacked several long-standing open questions from different branches of combinatorics and geometry using computer assistance. Two of the attacked conjectures have even been open for almost 40 years. We will discuss various problems which we want to investigate in the future and for which modern SAT solvers and exhaustive enumeration techniques will certainly play a key role.Part II: In a recent SoCG article, Martin Balko, Pavel Valtr, and the applicant have successfully applied a random sampling method from stochastic geometry to upper-bound the expected number of holes and islands in higher dimensional random point sets, improving bounds from Bárány & Füredi (1987), Fabila-Monroy & Huemer (2012), and Fabila-Monroy et al. (2015). Since then we have intensively studied the recent work of Reitzner & Temesvari (2019) and further managed to generalize the method to determine asymptotically tight bounds. We discuss the current state of our research, where we see a lot of unused potential, and how we would like to proceed in the future.Part III: We discuss realizability problems on various structures from combinatorial geometry. Besides the question that arise from the computer-assisted part of this project, we also hope to address some long-standing conjectures by Grünbaum (1972) and to further improve long-standing results by Richter-Gebert (1996).As part of the working group Diskrete Mathematik of his doctoral supervisor, Prof. Stefan Felsner at Technische Universität Berlin the applicant wants to bring recent computer-assisted techniques more into the focus of research and teaching. We also want to continue our international collaborations with experts from the field of combinatorial and computational geometry such as Prof. Valtr and Prof. Balko from Charles University in Prague.

• DFG Programme: Research Grants