Characterize the graph pairs $(G_1,G_2)$ with a finite-colour vs $\aleph_0$-colour Ramsey gap (Erdős #596)
Statement
Given finite graphs $G_1,G_2$, say the pair $(G_1,G_2)$ has the finite-vs-infinite colouring gap if BOTH of the following hold: (i) for every integer $n\geq 1$ there is a (possibly infinite) graph $H$ containing no copy of $G_1$ such that every $n$-colouring of the edges of $H$ contains a monochromatic copy of $G_2$; and (ii) for every graph $H$ containing no copy of $G_1$ there is an $\aleph_0$-colouring (a colouring using countably many colours) of the edges of $H$ with no monochromatic copy of $G_2$. For which pairs $(G_1,G_2)$ does this gap hold?
Acceptance. FULLY RESOLVES: a complete proof characterizing exactly the set of pairs $(G_1,G_2)$ for which both (i) and (ii) hold. Because this is an OPEN problem (no finite computation can decide it), deliver a full written proof with all steps, or a machine-checkable proof (Lean/Coq preferred). ADVANCES, each with a complete proof: (a) exhibit and verify a new specific pair beyond $(C_4,C_6)$ satisfying both (i) and (ii); (b) prove the gap holds (or fails) for a natural infinite class of pairs; or (c) rule out a class — prove no pair with a stated property qualifies. A partial characterization must come with a proof that the stated class is exactly correct. Deliver the proof (Lean file preferred, else a complete written argument).
Background
Posed by Erdős [Er87] and studied with Hajnal. Erdős and Hajnal originally conjectured that no such pair $(G_1,G_2)$ exists — that (i) and (ii) can never hold simultaneously. This turned out to be false: the pair $(G_1,G_2)=(C_4,C_6)$ (four- and six-cycles) is an example. For this pair Nešetřil and Rödl established property (i), and Erdős and Hajnal established property (ii); the key structural fact is that every $C_4$-free graph is a countable union of trees, which makes the $\aleph_0$-colouring in (ii) possible. The analogous question for $(G_1,G_2)=(K_4,K_3)$ is the separate open Erdős #595 (erdosproblems.com/595), an Erdős–Hajnal cluster to which this problem belongs. The general characterization — exactly which pairs exhibit the gap — remains open. Listed as open on erdosproblems.com/596 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory | set theory; a Lean formalisation exists in the DeepMind formal-conjectures repository. Attacker's tool: infinite combinatorics and partition-calculus arguments, together with structural decompositions of $G_1$-free graphs (representing them as countable unions of simpler graphs such as trees or forests) — the problem is inherently infinitary and admits no finite certificate.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #596 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #596 (DeepMind formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.