Hostname: page-component-7c8c6479df-nwzlb Total loading time: 0 Render date: 2024-03-29T00:54:19.682Z Has data issue: false hasContentIssue false

A Ramsey-Type Theorem in the Plane

Published online by Cambridge University Press:  12 September 2008

Jaroslav Nešetřil
Affiliation:
Department of Applied Mathematics, Charles University, Malostranské nám. 25, 118 00 Praha 1, Czech Republic
Pavel Valtr
Affiliation:
Graduiertenkolleg ‘Algorithmische Diskrete Mathematik’, Fachbereich Mathematik, Freie Universität Berlin, Takustrasse 9, 14195 Berlin, Germany

Abstract

We show that, for any finite set P of points in the plane and for any integer k ≥ 2, there is a finite set R = R(P, k) with the following property: for any k-colouring of R there is a monochromatic set , R, such that is combinatorially equivalent to the set P, and the convex hull of P contains no point of R \ . We also consider related questions for colourings of p-element subsets of R (p > 1), and show that these analogues have negative solutions.

Type
Research Article
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Bárány, I. and Füredi, Z. (1987) Empty simplices in Euclidean space. Canadian Math. Bull. 30 436445.CrossRefGoogle Scholar
[2]Erdős, P. and Szekeres, G. (1935) A combinatorial problem in geometry. Compositio Math. 2 463470.Google Scholar
[3]Goodman, J. E. and Pollack, R. (1991) The complexity of point configurations. Discrete Appl. Math. 31 167180.CrossRefGoogle Scholar
[4]Goodman, J. E. and Pollack, R. (1993) Allowable sequences and order types in discrete and computational geometry, in: Pach, J. (ed.), New trends in discrete and computational geometry, Springer-Verlag.Google Scholar
[5]Graham, R. L., Rothschild, B., and Spencer, J., (1980) Ramsey Theory, J. Wiley & Sons, New York.Google Scholar
[6]Hales, A. W., and Jewett, R. I., (1963) Regularity of Positional Games, Trans. Am. Math. Soc. 106 222229.CrossRefGoogle Scholar
[7]Harborth, H., (1978) Konvexe Fünfecke in ebenen Punktmengen. Elem. Math. 33 116118.Google Scholar
[8]Horton, J. D., (1983) Sets with no empty convex 7-gons. Canadian Math. Bull. 26 482484.CrossRefGoogle Scholar
[9]Korte, B., and Lovász, L., (1985) Posets, matroids, and greedoids. in: Lovász, L. and Recski, A. (eds.), Matroid theory, North-Holland, 239265.Google Scholar
[10]Korte, B.Lovász, L. and Schrader, R. (1991) Greedoids, Springer-Verlag, Berlin.CrossRefGoogle Scholar
[11]Lovász, L. (1979) Topological and algebraic methods in graph theory. In: Bondy, A. and Murty, U. S. R. (eds.), Graph Theory and Related Topics, Academic Press 114.Google Scholar
[12]Moser, W. and Pach, J. (1993) Recent developments in combinatorial geometry. In: Pach, J. (ed.) New trends in discrete and computational geometry, Springer-Verlag.Google Scholar
[13]Nešetřil, J.Poljak, S. and Turzík, D. (1981) Amalgamation of matroids and its applications, J. Comb. Th. B 31 922.CrossRefGoogle Scholar
[14]Nešetřil, J. and Rödl, V. (eds.) (1990) Mathematics of Ramsey Theory, Springer-Verlag (1990).CrossRefGoogle Scholar
[15]Nešetřil, J. and Valtr, P. (preprint) Order types containing approximately an affine transformation of the grid k × k.Google Scholar
[16]Pach, J. (1991) Notes on Geometric Graph Theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science 6 273285.CrossRefGoogle Scholar
[17]Ramsey, F. P. (1930) On a problem of formal logic. Proc. Lond. Math. Soc, II. Ser. 30 264286.CrossRefGoogle Scholar
[18]Shelah, S. (1988) Primitive recursive bounds for van der Waerden numbers. Journal AMS 1 683697.Google Scholar
[19]Valtr, P. (1992) Convex independent sets and 7-holes in restricted planar point sets. Discrete Comput. Geom. 7 135152.CrossRefGoogle Scholar