A Ramsey-type result for geometric ℓℓ-hypergraphs

Let n≥ℓ≥2n≥ℓ≥2 and q≥2q≥2. We consider the minimum NN such that whenever we have NN points in the plane in general position and the ℓℓ-subsets of these points are colored with qq colors, there is a subset SS of nn points all of whose ℓℓ-subsets have the same color and furthermore SS is in convex position. This combines two classical areas of intense study over the last 75 years: the Ramsey problem for hypergraphs and the Erdős–Szekeres theorem on convex configurations in the plane. For the special case ℓ=2ℓ=2, we establish a single exponential bound on the minimum NN, such that every complete NN-vertex geometric graph whose edges are colored with qq colors, yields a monochromatic convex geometric graph on nn vertices.For fixed ℓ≥2ℓ≥2 and q≥4q≥4, our results determine the correct exponential tower growth rate for NN as a function of nn, similar to the usual hypergraph Ramsey problem, even though we require our monochromatic set to be in convex position. Our results also apply to the case of ℓ=3ℓ=3 and q=2q=2 by using a geometric variation of the stepping up lemma of Erdős and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3-uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower.