Graham 1994 recent trends euclidean ramsey theory

../

conjecture_p120: Graham's prize conjecture that every finite spherical set in Euclidean space is Ramsey, posed beside the theorem of Erdős et al. that every Ramsey set is spherical.

conjecture_p127: Graham's prize conjecture that the least W such that every 2-coloring of 1 to W has a monochromatic n-term progression is at most a tower of n twos, posed after Shelah's primitive recursive bound.

example_p124: Graham's partition of N-space into four classes, by the residue modulo 4 of the floor of the squared norm, none of which contains a congruent copy of (2t+1)X_3 for an integer t, where X_3 is three collinear points at unit spacing.

section_6: The survey's account of the bounds then known for the least number of classes partitioning Euclidean space with no class containing two points at distance 1: from 4 to 7 for the plane, and exponential in the dimension in general.

theorem_p122: Graham's theorem that for a nonspherical finite set X and any dimension N there is a set of positive upper density in N-space and a set of scales of positive lower density such that the set contains no congruent copy of any of those dilates of X.

---

R. L. Graham, Recent trends in Euclidean Ramsey theory. Discrete Mathematics 136 (1994), 119-127. doi:10.1016/0012-365X(94)00110-5. Received 19 January 1993, revised 9 July 1993.

Graham surveys Euclidean Ramsey theory as of 1993. Section 2 (p. 120) records that the characterization of Ramsey sets is open, that every Ramsey set is spherical (Erdős et al.), that three collinear points are therefore not Ramsey and E^N splits into 16 classes avoiding them (Straus), that simplices are Ramsey (Frankl-Rödl), that products of Ramsey sets are Ramsey, and Kříž's theorem that a set with a solvable transitive automorphism group is Ramsey; it closes with the prize conjecture that every spherical set is Ramsey. Section 3 (pp. 120-121) states that simplices on the unit sphere are sphere-Ramsey with radius 1+epsilon (Matoušek-Rödl) and Graham's earlier obstruction: if X on S^k(1) is unit-sphere-Ramsey, every linear dependence among its points has a nonempty set of coefficients summing to zero, so a set whose convex hull contains the origin is not unit-sphere-Ramsey. Section 4 (pp. 121-123) states Bourgain's density theorem for simplices and proves, answering a question of Furstenberg, that for a nonspherical X and any N some set of positive upper density in E^N contains no congruent copy of tX for t in a set of positive lower density. Section 5 (pp. 124-125) partitions E^N into four classes, none containing a congruent copy of an odd integer dilate of three collinear points at unit spacing. Section 6 (pp. 125-126) reports the chromatic-number bounds of the time, 4 <= chi <= 7 for the plane and (1+o(1))(1.2)^n < chi(n) < (3+o(1))^n in general. Section 7 (pp. 126-127) states Graham's fixed-dimension theorems: for any finite partition of E^n some class contains, for all alpha > 0 and all sets of lines L_1, ..., L_n spanning E^n, a simplex of volume alpha with edges through one vertex parallel to the L_i; and for any r there is a positive integer T(r) such that any r-class partition of the integer lattice points of the plane has a class containing the vertices of a right triangle of area T(r). It mentions Kunen's partition of the plane, under the continuum hypothesis, into ℵ classes (printed without a subscript) with no class containing the vertices of a triangle of rational area, and closes with the prize conjecture that the two-color van der Waerden function W(n) is at most a tower of n twos.

Source: https://doi.org/10.1016/0012-365X(94)00110-5. The file prints "0012-365X/94/$07.00 © 1994—Elsevier Science B.V. All rights reserved", every other right reserved.

Bears on.

• Problem 174: the paper records the characterization of Ramsey sets as unanswered in 1993, surveys the known necessary and sufficient conditions, and conjectures that the Ramsey sets are the spherical sets. It proves nothing toward that conjecture.
• Problem 508: the paper reports 4 and 7 as the best bounds known in 1993 for the chromatic number of the plane; it proves no new bound.
• Problem 704: the paper reports the bounds (1+o(1))(1.2)^n and (3+o(1))^n for the chromatic number of n-space, citing Frankl and Wilson for both and crediting the lower bound to them; it does not discuss whether the n-th root converges.
• Problem 138: the paper conjectures that the two-color van der Waerden number W(n) is at most a tower of n twos, and reports Shelah's primitive recursive upper bound and a lower bound of roughly n 2^n; it proves no bound.
• Problem 214: background only. The paper treats partitions of the plane avoiding unit distances but never discusses the problem's question, whether the complement of a set with no two points at distance 1 must contain a unit square.

Result pages.

• Conjecture (p. 120): every spherical set is Ramsey.
• Theorem (p. 122): for nonspherical X and any N, a set of positive upper density in E^N avoids congruent copies of tX for all t in a set of positive lower density.
• Example (p. 124): four classes by the floor of the squared norm modulo 4 avoid congruent copies of (2t+1)X_3 for every integer t.
• Section 6 (pp. 125-126): the chromatic-number bounds reported for the plane and for n-space.
• Conjecture (p. 127): W(n) is at most a tower of n twos.

The other theorems the paper states are quoted from the works it cites, among them the theorem of Erdős et al. that Ramsey sets are spherical (p. 120), which has its page under Euclidean Ramsey theorems I; they have no page here.

Read status: claims checked, for the statements on the result pages above, which record their read depth. The copy read for this card is the journal's PDF of that edition.

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