Problem 1174

Does there exist a graph $G$ with no $K_4$ such that every edge colouring of $G$ with countably many colours contains a monochromatic $K_3$ ?

Does there exist a graph $G$ with no $K_{\aleph_1}$ such that every edge colouring of $G$ with countably many colours contains a monochromatic $K_{\aleph_0}$ ?

Source: erdosproblems.com/1174

Set theory
Ramsey theory

Wiki page

Status

Open

No claim settles this problem.

Open. The site labels the problem NOT DISPROVABLE, crediting Shelah with the consistency of a graph with either property. Each of the problem's two parts, which the frontmatter lists, has an accepted consistency result: Shelah's K_4-free graph for the first and Komjáth and Shelah's edge partition theorem for the second. Each settles one side of its part only: relative to the hypotheses it assumes, ZFC does not refute the existence of the graph the part asks for, but neither result shows that ZFC cannot prove its existence. The page departs from the site's label because one side alone leaves a question open, so both parts, and the problem, are open.

Ko25: Komjáth, Péter, The Erdős–Hajnal problem list. Bull. Symbolic Logic 31 (2025), 418-461. DOI 10.1017/bsl.2025.1; Problems 51-53 and their commentary. Library home: Komjáth 2025.
KoSh93: Komjáth, P. and Shelah, S., A consistent edge partition theorem for infinite graphs. Acta Math. Hungar. 61 (1993), 115-120. DOI 10.1007/BF01872104; Shelah archive Sh:414. Not held; the claim page rests on its statements in the archive's scan.
Sh89: Shelah, Saharon, Consistency of positive partition theorems for graphs and models. In: Set theory and its applications (Toronto, ON, 1987), Lecture Notes in Math. 1401, Springer, Berlin, 1989, pp. 167-193. DOI 10.1007/BFb0097339; Shelah archive Sh:289. Library home: Shelah 1989.
Va99: Some of Paul's favorite problems, booklet for the conference "Paul Erdős and his mathematics", Budapest, July 1999; item 7.91, which asks both questions and remarks that Shelah proved the consistency of either property (section 7). Library home: Various 1999.

Problem 1174

Status

Proof claims

Discussion