EuroGIGA_Erdös-Szekeres type problems for colored point sets and compatible graphs

Problems on geometric graphs are the central topic of the EUROCORES program EuroGIGA. Within this program in the CRP ComPoSe we will focus on combinatorial questions of graphs and objects. This individual project consists of two main topics. In 1935 Erdös and Szekeres considered a problem about the existence of a number g(k) such that any set S of g(k) points in general position (no three points of S lie on a line) in the plane has a subset of k points that are the vertices of a convex k-gon. Later Erdös and Guy stated the following more general question. "What is the least number of convex k-gons determined by any set of n points in the plane?". Both versions turned out to be rather challenging and have attracted many researchers. Meanwhile there exists a whole family of problems based on these questions. In our IP we will focus on variations of Erdös-Szekeres type problems, where the points of a given set S belong to different classes - usually described as "colors". A concrete example of the problems to be considered is the Empty monochromatic convex quadrilaterals problem. Let S be a bichromatic set of n points in the plane, r of them colored red, b = n - r colored blue. A quadrilateral is called monochromatic if it is spanned by four points of the same color, and empty if no point (of any color) lies in its interior. Does there exist an empty monochromatic convex quadrilateral on every sufficiently large point set S in the plane? Related question on empty monochromatic simplices and blocking colored Delaunay triangulations will also be investigated in this context. The second class of problems deals with compatible geometric graphs. A plane perfect matching on a set S of an even number of points in the plane is a crossing-free geometric graph, where every point in S has degree exactly 1. Two plane geometric graphs are compatible if they both exist on the same point set and their union is plane. They are called disjoint if the two graphs have no edge in common. We will investigate the "Compatible Matching Conjecture": For every perfect matching on a set S of 4n points in the plane, there exists a disjoint compatible perfect matching. Related questions exist on (disjoint) compatible spanning pathsrees/circles and also on (disjoint) compatible (pointed) pseudo-triangulations, including the problem of the length of transformations (successively compatible sequences). Also a "dual" version for triangulations will be considered: two sets of points are given, can we obtain isomorphic triangulations for them? The mentioned classes of problems are well known and considered to be rather difficult. Thus the joint effort of a CRP in the European context will be the perfect setting to tackle the mentioned questions.

Problems on geometric graphs are the central topic of the EUROCORES program EuroGIGA. Within this program, the CRP ComPoSe focused on combinatorial questions on graphs and objects. Our group at the Graz University of Technology took also the lead of ComPoSe, thereby coordinating research teams from six additional well-known European universities: Université Libre de Bruxelles, University of Technology Berlin, Universitat Politècnica de Catalunya Barcelona, Alfréd Rényi Institut of Mathematics Budapest, Charles University Prague, and ETH Zürich. In joint collaboration, many of the proposed problems have been successfully investigated. An example is the problem of Erdos and Szekeres from 1935 about the existence of a number g(k) such that any set S of g(k) points in general position (no three points of S lie on a line) in the plane has a subset of k points that are the vertices of a convex k-gon. Later Erdos and Guy stated the following more general question. "What is the least number of convex k-gons determined by any set of n points in the plane?". Both versions turned out to be rather challenging and have attracted many researchers. In a series of papers, we considered different aspects of these problems, including versions where the points of a given set belong to different classes - usually described as "colors" - or lie in higher dimensional space. In an international project like ComPoSe, it is a major benefit when newly developed methods can be applied to long-standing open questions, where these questions might not even have been part of the application. In a breakthrough work with Spanish, Mexican, and US-American colleagues we were able to provide the first combinatorial condition on a topological drawing of the complete graph that guarantees that the Harary-Hill conjecture holds. This was the first such step after 50 years of research on this conjecture, and it was obtained by translating geometric concepts to the topological setting. Experts in the area are now positive that the full conjecture can be settled within the next 5-10 years. Currently the next steps towards settling the Harary-Hill conjecture are done, an excellent example for a collaboration established during the project, but lasting beyond it and this is not the only example where we will continue to collaborate with international research groups on topics of this project.