Finding Structures within Large Point Sets

Student report (2024)

Authors

L.K.M. Verlinde Electrical Engineering, Mathematics and Computer Science

Contributors

W.P.S. Cames van Batenburg Discrete Mathematics and Optimization - EEMCS (supervisor 1)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2024 Lander Verlinde
More Info
expand_more

Published Date

19-01-2024

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

We investigate two open problems in discrete geometry regarding how large subsets of sets of points need to be in order for certain structures to emerge. First of all there is the Erdős-Szekeres convex polygon problem, also known as the Happy Ending problem. Interestingly, there is a clear distinction between the number of points required to ensure a lot of points in convex position in the plane and in higher dimensions. This raises the question whether such a difference depending on the considered dimension can also be found in other problems concerning subsets of point sets.
The second problem where we research this difference is the Big-Line-Big-Clique Conjecture. As far as we know, this conjecture has not been studied yet in other dimensions than the plane.

Apart from discussing the relevant literature for both problems, we present a formulation of the Big-Line-Big-Clique Conjecture in higher dimensions and a generalisation in terms of (hyper)graphs. We also state a stronger version of the conjecture that would imply the BLBC Conjecture to be true. However, we show a counterexample to the stronger conjecture, leaving the original one open.