Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Statement

Notation (p. 11). EN→2(X1,X2)\mathbb E^N\xrightarrow{2}(X_1,X_2) means that for every partition EN=C1∪C2\mathbb E^N=C_1\cup C_2, either C1C_1 contains a congruent copy of X1X_1 or C2C_2 contains a congruent copy of X2X_2; a crossed arrow denies it. P2P_2 is a set of two points at distance 11.

The chapter lists, unnumbered, as a sampling of results of this type (p. 11, items (i) to (v)):

(i) E2→2(T2,T3)\mathbb E^2\xrightarrow{2}(T_2,T_3), where TiT_i is any subset of E2\mathbb E^2 with ii points, i=2,3i=2,3.

(ii) E2→2(P2,P4)\mathbb E^2\xrightarrow{2}(P_2,P_4), where P4P_4 is a set of four collinear points with distance 11 between consecutive points.

(iii) E3→2(T,Q2)\mathbb E^3\xrightarrow{2}(T,Q^2), where TT is an isosceles right triangle and Q2Q^2 is a square.

(iv) E2→2(P2,T4)\mathbb E^2\xrightarrow{2}(P_2,T_4), where T4T_4 is any set of four points [Juh79]. So for every partition of the plane into C1C_1 and C2C_2, either C1C_1 contains two points at distance 11 or C2C_2 contains a congruent copy of T4T_4.

(v) There is a set T8T_8 of 88 points such that E2\mathbb E^2 does not arrow (P2,T8)(P_2,T_8) [CT94]: some partition of the plane into C1C_1 and C2C_2 has no two points of C1C_1 at distance 11 and no congruent copy of T8T_8 in C2C_2. The chapter says this strengthens an earlier result of Juhász [Juh79], who proved it for a certain set of 1212 points.

The chapter introduces items (i) to (iii) without individual citations and points to [EGM+73], [EGM+75a] and [EGM+75b] for more results of this type.

Source. R. L. Graham, Euclidean Ramsey theory, Chapter 11 of the Handbook of Discrete and Computational Geometry, 2nd edition, CRC Press (2004), read in the preprint of the chapter identified on the source card, whose own page number is cited: the notation and items (i) to (v) on p. 11, in the subsection "Asymmetric Ramsey theorems" of Section 11.6. Item (iv) cites R. Juhász, Ramsey type theorems in the plane, J. Combin. Theory Ser. A 27 (1979), 152--160; item (v) cites G. Csizmadia and G. Tóth, Note on a Ramsey-type problem in geometry, J. Combin. Theory Ser. A 65 (1994), 302--306.

Read depth. Claims checked: the notation and each item were read clause by clause on the page image of the preprint. The chapter gives no proofs, and the cited papers were not read for this page. Nothing here is independently reviewed.

Proof pointer

No proof is printed; the items are cited to the papers named above.

Dependencies

None in the chapter.

Bears on

  • Problem 214: item (iv) reports Juhász's theorem that in every partition of the plane into C1C_1 and C2C_2 with no two points of C1C_1 at distance 11, C2C_2 contains a congruent copy of every four-point set, in particular of the four vertices of a unit square, which is the problem's question. Item (v) reports the eight-point set of Csizmadia and Tóth and Juhász's earlier twelve-point set, for which the corresponding statement fails.
  • Problem 188: item (ii) states that every partition of the plane into C1C_1 and C2C_2 with no two points of C1C_1 at distance 11 has four collinear points of C2C_2 with consecutive distances 11, that is a four-term progression with a step of length 11. The chapter gives no colouring that avoids longer such progressions and states no value of the problem's kk.