---

Claim. Some graph with no $K_4$ on at most $3\cdot10^9$ vertices has a monochromatic triangle in every $2$-coloring of its edges. This answers Problem 582 yes by a probabilistic argument that does not use Folkman's construction: a random graph $G(n,p)$ loses one edge from each of its copies of $K_4$, and the analysis shows that the resulting $K_4$-free graph arrows $(3,3)$ with positive probability, for $n=3\cdot10^9$ and $p=6n^{-1/2}$ as Radziszowski and Xu describe the proof (their survey). Since $3\cdot10^9<10^{10}$, the result also meets Erdős's challenge [Er75d] to find such a graph on fewer than $10^{10}$ vertices, as the site's commentary records. The paper claimed $3\cdot10^8$ points, as its title says. The erratum in J. Combin. Theory Ser. A 50 (1989), no. 2, 323 corrects the count to $3\cdot10^9$; Lu cites it as Spencer's, and Lange, Radziszowski and Xu credit it to M. Hovey. That corrected bound is the one the site, Lu, and Lange, Radziszowski and Xu record. The paper is not held; the statement is taken from these accounts of it.

Depends on. Nothing in this wiki.

Acceptance. Refereed: J. Spencer, Three hundred million points suffice, J. Combin. Theory Ser. A 49 (1988), no. 2, 210--217 (November 1988; the day is a placeholder), with the erratum in 50 (1989), no. 2, 323. Lu (SIAM J. Discrete Math. 21 (2008), p. 1053) records that Spencer claimed Erdős's reward for the $10^{10}$ challenge. The site's label rests on Folkman's existence proof, so the site's commentary crediting Spencer is not listed as evidence.