A RamseyType Result for Geometric ℓHypergraphsMubayi, Dhruv and Suk, Andrew (2013) A RamseyType Result for Geometric ℓHypergraphs. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 364375(Official URL: http://dx.doi.org/10.1007/9783319038414_32). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_32
AbstractLet 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ősSzekeres 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 Nvertex 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 Steppingup lemma of Erdős and Hajnal. This is in contrast to the fact that the upper and lower bounds for the usual 3uniform hypergraph Ramsey problem for two colors differ by one exponential in the tower.
Actions (login required)
