Graham 2004 euclidean ramsey theory

../

conjecture_11_1_1: The chapter's three conjectures on triangles in the plane: every nonequilateral triangle is 2-Ramsey for the plane; in every two-coloring one class holds every triangle except possibly one equilateral triangle; and no triangle is 3-Ramsey for the plane.

conjecture_11_5_6: The chapter states Erdős's conjecture that a set of natural numbers whose reciprocals have divergent sum contains arbitrarily long arithmetic progressions, beside Szemerédi's and Gowers's theorems and Graham's two-dimensional analogue for axes-parallel squares.

problem_11_1_6: The chapter defines the chromatic number of n-dimensional Euclidean space through the unit-distance pair, reports 4 <= chi(E^2) <= 7, bounds of (6/5 + o(1))^n and (3 + o(1))^n in dimension n and 6 <= chi(E^3) <= 15, and poses the exact value for the plane as Problem 11.1.6.

theorem_11_1_4: The chapter's catalog, credited to Erdős, Graham, Montgomery, Rothschild, Spencer and Straus and to others, of triangles for which every two-coloring of the plane has a monochromatic congruent copy, with results in three and more dimensions and colorings that avoid squares and degenerate triangles.

theorem_11_1_5: O'Donnell's theorem as the chapter reports it: for every g > 0 there is a unit distance graph in the plane with chromatic number 4 and girth greater than g, offered as evidence that the chromatic number of the plane is at least 5.

theorem_11_2_5: The chapter's necessary condition for a finite set to be Ramsey, that it lie on a sphere, with the positive classes it reports (rectangular sets, simplices, sets with suitable transitive isometry groups) and Graham's prize conjecture that every spherical set is Ramsey.

theorem_11_5_9: Graham's theorem, as the chapter reports it, that Bourgain's density theorem for simplices fails for every nonspherical set: in every dimension some set of positive upper density contains no congruent copy of tX for t in a set of reals of positive lower density.

theorem_11_6_4: The chapter's statement of the Erdős–Szekeres theorem that a least f(n) exists such that f(n) points in general position in the plane contain a convex n-gon, the bounds 2^(n-2) + 1 <= f(n) <= C(2n-5, n-3) + 2 it reports, and the conjecture that the lower bound is exact.

theorem_p11: The chapter's sampling of asymmetric Euclidean Ramsey results for two-colorings: the plane forces any prescribed two-point set in the first class or any prescribed three-point set in the second; it forces a unit pair in the first class or, in the second, four collinear unit-spaced points, or by Juhász any four-point set; space forces an isosceles right triangle in the first or a square in the second; and Csizmadia and Tóth give an eight-point set for which the unit-pair statement fails.

---

R. L. Graham, Euclidean Ramsey theory, Chapter 11 of the Handbook of Discrete and Computational Geometry, 2nd edition (J. E. Goodman and J. O'Rourke, eds.), CRC Press (2004).

This handbook chapter surveys Euclidean Ramsey theory, mostly by stating results with citations and without proofs. Section 11.1 poses three conjectures on two- and three-colourings of the plane and congruent triangles (Conjectures 11.1.1 to 11.1.3, p. 2), lists the triangles known to be 2-Ramsey for the plane with related results in higher dimensions (Theorem 11.1.4, pp. 2--3), defines the chromatic number of $\mathbb E^n$ with the bounds known to it, and poses the chromatic number of the plane as Problem 11.1.6 (pp. 3--4). Section 11.2 gives sphericity as a necessary condition for a set to be Ramsey (Theorem 11.2.5, p. 5), the classes of sets proved Ramsey, and Graham's prize conjecture that every spherical set is Ramsey (Conjecture 11.2.13, p. 6). Sections 11.3 and 11.4 treat sphere-Ramsey and edge-Ramsey configurations (pp. 6--8). Section 11.5 treats homothetic copies and density theorems, including Erdős's conjecture on sets with divergent sum of reciprocals (Conjecture 11.5.6, p. 10), Bourgain's theorem for simplices and Graham's nonspherical counterpart (Theorems 11.5.8 and 11.5.9, p. 11). Section 11.6 surveys variations (pp. 11--13): asymmetric results in the notation $\mathbb E^N\xrightarrow{2}(X_1,X_2)$, among them Juhász's theorem that the plane arrows $(P_2,T_4)$ for a unit-distance pair $P_2$ and every four-point set $T_4$ and the eight-point set $T_8$ of Csizmadia and Tóth for which it fails (p. 11), polychromatic results (p. 12), partitions into arbitrarily or infinitely many parts (pp. 12--13), and the Erdős--Szekeres theorem with its bounds and conjecture (Theorem 11.6.4 and Conjecture 11.6.5, p. 13).

Source: https://www.cs.umd.edu/~gasarch/TOPICS/ERT/GrahamERT.pdf. The copy read for this card is a preprint of the chapter (header "11 EUCLIDEAN RAMSEY THEORY R.L. Graham"), paginated 1 to 16, which prints no copyright or license line, and the hosting site (https://www.cs.umd.edu/~gasarch/, read 2026-10-02) states no terms; the publisher's edition is not the edition read; the term is unstated. Page numbers on this card and its result pages are the preprint's own.

Read status: claims checked for the statements on the result pages below, read clause by clause on the page images of the preprint. The chapter gives no proofs of the results it reports, and the cited papers were not read for this card. Nothing here is independently reviewed.

Bears on. #214: the asymmetric item (iv) (p. 11) reports Juhász's theorem that in every partition of the plane into $C_1$ and $C_2$, either $C_1$ has two points at distance $1$ or $C_2$ contains a congruent copy of any given four-point set, the unit square included; item (v) reports the eight-point set of Csizmadia and Tóth, and Juhász's earlier twelve-point set, for which this fails. #188: item (ii) on the same page states that in every such partition either $C_1$ has two points at distance $1$ or $C_2$ has four collinear points spaced $1$ apart; the chapter states no value of the problem's $k$. #173: Conjecture 11.1.2 (p. 2) conjectures that in every two-colouring of the plane one class holds every triangle except possibly one equilateral triangle, and the strip colouring shows the exception occurs; Theorem 11.1.4 (pp. 2--3) lists triangles for which a monochromatic copy is forced. #174: Theorem 11.2.5 (p. 5) states that every Ramsey set is spherical, and Conjecture 11.2.13 (p. 6) conjectures the converse; the chapter calls the characterisation open. #508: Problem 11.1.6 (p. 4) asks for $\chi(\mathbb E^2)$, with $4\le\chi(\mathbb E^2)\le7$ reported (p. 3). #704: the same page reports $(6/5+o(1))^n<\chi(\mathbb E^n)<(3+o(1))^n$ (p. 4). #705: Theorem 11.1.5 (p. 4) reports O'Donnell's 4-chromatic unit distance graphs in the plane of girth above any bound, stated without saying whether the graphs are finite. #3: Conjecture 11.5.6 (p. 10) states the problem's question as a conjecture of Erdős. #107: Conjecture 11.6.5 (p. 13) states the problem's assertion $f(n)=2^{n-2}+1$ for $n\ge3$, with $2^{n-2}+1\le f(n)\le\binom{2n-5}{n-3}+2$ reported.

Results.

• Conjectures 11.1.1 to 11.1.3 (p. 2): every nonequilateral triangle is 2-Ramsey for the plane; one class of every two-colouring holds all triangles but possibly one equilateral one; no triangle is 3-Ramsey for the plane.
• Theorem 11.1.4 (pp. 2--3): triangles 2-Ramsey for $\mathbb E^2$, all nondegenerate triangles 2-Ramsey for $\mathbb E^3$, and negative results for the square and degenerate triangles.
• Problem 11.1.6 (p. 4), with the definition of $\chi(\mathbb E^n)$ (p. 3): the chromatic number of the plane and the bounds reported in dimensions $2$, $3$ and $n$.
• Theorem 11.1.5 (p. 4): O'Donnell's 4-chromatic unit distance graphs of large girth.
• Theorem 11.2.5 (p. 5) and Conjecture 11.2.13 (p. 6): every Ramsey set is spherical; conjecturally conversely.
• Conjecture 11.5.6 (p. 10): Erdős's conjecture on divergent sums of reciprocals and arithmetic progressions.
• Theorem 11.5.9 (p. 11): for a nonspherical set, a set of positive upper density with no congruent copy of any dilate by a scale from a set of positive lower density.
• Asymmetric Ramsey theorems (p. 11): items (i) to (v), including Juhász's four-point theorem and the eight-point set of Csizmadia and Tóth.
• Theorem 11.6.4 and Conjecture 11.6.5 (p. 13): the Erdős--Szekeres function, its bounds, and $f(n)=2^{n-2}+1$.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.