A Ramsey-Type Result for Geometric ℓ-Hypergraphs

Mubayi, Dhruv and Suk, Andrew (2013) A Ramsey-Type Result for Geometric ℓ-Hypergraphs. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 364-375(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_32).

Full text not available from this repository.


Let n ≥ ℓ ≥ 2 and q ≥ 2. We consider the minimum N such that whenever we have N points in the plane in general position and the ℓ-subsets of these points are colored with q colors, there is a subset S of n points all of whose ℓ-subsets have the same color and furthermore S 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, we establish a single exponential bound on the minimum N such that every complete N-vertex geometric graph whose edges are colored with q colors, yields a monochromatic convex geometric graph on n vertices. For fixed ℓ ≥ 2 and q ≥ 4, our results determine the correct exponential tower growth rate for N as a function of n, 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 and q = 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.

Item Type: Conference Paper
Classifications: P Styles > P.420 Hyper
Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1389

Actions (login required)

View Item View Item