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, Bordeaux, France , 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
ID Code:1389

Repository Staff Only: item control page


Ajtai, M., Komlós, J., Szemerédi, E.: A note on Ramsey numbers. J. Combin. Theory Ser. A 29, 354–360 (1980)

Ábrego, B.M., Fernández-Merchant, S., Salazar, G.: The rectilinear crossing number of K n : Closing in (or are we?), Thirty Essays on Geometric Graph Theory. In: Pach, J. (ed.) Algorithms and Combinatorics, vol. 29, pp. 5–18. Springer (2012)

Aronov, B., Erdős, P., Goddard, W., Kleitman, D.J., Klugerman, M., Pach, J., Schulman, L.J.: Crossing families. Combinatorica 14, 127–134 (1994)

Bohman, T.: The triangle-free process. Adv. Math. 221, 1653–1677 (2009)

Bohman, T., Keevash, P.: The early evolution of the H-free process. Invent. Math. 181, 291–336 (2010)

Conlon, D., Fox, J., Sudakov, B.: Journal of the American Mathematical Society 23, 247–266 (2010)

Dey, T., Pach, J.: Extremal problems for geometric hypergraphs. Discrete Comput. Geom. 19, 473–484 (1998)

Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. of Math. 51, 161–166 (1950)

Erdős, P.: Some remarks on the theory of graphs. Bull. Amer. Math. Soc. 53, 292–294 (1947)

Erdős, P., Hajnal, A., Rado, R.: Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. 16, 93–196 (1965)

Erdős, P., Rado, R.: Combinatorial theorems on classifications of subsets of a given set. Proc. London Math. Soc. 3, 417–439 (1952)

Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)

Erdős, P., Szekeres, G.: On some extremum problems in elementary geometry. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 3(4), 53–62 (1960-1961)

Fox, J., Pach, J., Sudakov, B., Suk, A.: Erdős-Szekeres-type theorems for monotone paths and convex bodies. Proceedings of the London Mathematical Society 105, 953–982 (2012)

Graham, R.L., Rothschild, B.L., Spencer, J.H.: Ramsey Theory, 2nd edn. Wiley, New York (1990)

Károlyi, G.: Ramsey-remainder for convex sets and the Erdős-Szekeres theorem. Dsicrete Appl. Math. 109, 163–175 (2001)

Károlyi, G., Pach, J., Tóth, G.: Ramsey-type results for geometric graphs, I. Disc. Comp. Geom. 18, 247–255 (1997)

Károlyi, G., Pach, J., Tóth, G., Valtr, P.: Ramsey-type results for geometric graphs, II. Disc. Comp. Geom. 20, 375–388 (1998)

Károlyi, G., Valtr, P.: Point configurations in d-space without large subsets in convex position. Disc. Comp. Geom. 30, 277–286 (2003)

Kim, J.H.: The Ramsey number R(3,t) has order of magnitude t 2/logt. Random Structures Algorithms 7, 173–207 (1995)

Matoušek, J.: Lectures on Discrete Geometry. Springer-Verlag New York, Inc. (2002)

Pach, J., Agarwal, P.: Combinatorial geometry. Wiley-Interscience, New York (1995)

Ramsey, F.P.: On a problem in formal logic. Proc. London Math. Soc. 30, 264–286 (1930)

Suk, A.: A note on geometric 3-hypergraphs, Thirty Essays on Geometric Graph Theory. In: Pach, J. (ed.) Algorithms and Combinatorics, vol. 29, pp. 489–498. Springer (2012)

Van Lint, J.H., Wilson, R.M.: A Course in Combinatorics. Cambridge University Press (2001)

Wagner, U.: k-sets and k-facets, Discrete and Computational Geometry - 20 Years Later. In: Goodman, E., Pach, J., Pollack, R. (eds.) Contemporary Mathematics, vol. 453, pp. 443–514. American Mathematical Society (2008)