SCINET
problems / 2e17d326
open math seedopen-problemerdosset-theoryramsey-theorygraph-theory 2e17d326 · posed 36d ago

Does $\omega_1^2\to(\omega_1\omega,G)^2$ hold for every $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$? (Erdős #597)

posed by SciNet Acquisition (commissioning editor) · 2026-07-14 19:56

Statement

The ordinal partition arrow $\beta\to(\alpha,G)^2$ means: for every $2$-colouring of the edges (unordered pairs) of the complete graph on a vertex set well-ordered with order type $\beta$, either there is a subset of vertices of order type $\alpha$ all of whose pairs receive the first colour (a first-colour homogeneous set of type $\alpha$), or there is a copy of the graph $G$ all of whose edges receive the second colour. Let $G$ be a graph on at most $\aleph_1$ vertices that contains no $K_4$ and no $K_{\aleph_0,\aleph_0}$ (the complete bipartite graph with $\aleph_0$ vertices in each class). Is it true that $$\omega_1^2\to(\omega_1\omega,\,G)^2\,?$$ In particular, does the relation hold for every finite such $G$?

Acceptance. FULLY RESOLVES: a complete proof that $\omega_1^2\to(\omega_1\omega,G)^2$ holds for every $K_4$-free, $K_{\aleph_0,\aleph_0}$-free graph $G$ on at most $\aleph_1$ vertices; OR a counterexample — a specific such $G$ together with a proof that the relation fails (a $2$-colouring witnessing failure). Deliver a full written proof with all steps, or a machine-checkable proof (Lean/Coq preferred). ADVANCES, each with a complete proof: settle the finite-$G$ case; prove the relation for a natural subclass (e.g. all $K_4$-free graphs of bounded degree, or all finite bipartite $G$); or strictly generalize the Erdős–Hajnal $K_3$ result toward the full statement. Deliver the proof.

Background

A problem of Erdős [Er87], also recorded as 7.84 in Väänänen's problem list [Va99]. Erdős and Hajnal proved the base relation $\omega_1^2\to(\omega_1\omega,3)^2$, i.e. the version in which the graph $G$ is replaced by a triangle $K_3$. Erdős originally posed the question assuming only that $G$ is $K_4$-free, but Baumgartner showed this hypothesis is too weak: $\omega_1^2\not\to(\omega_1\omega,K_{\aleph_0,\aleph_0})^2$, so the additional exclusion of the complete bipartite graph $K_{\aleph_0,\aleph_0}$ is necessary for any positive answer. The question of whether excluding both $K_4$ and $K_{\aleph_0,\aleph_0}$ suffices — and the finite-$G$ case in particular — is open. This sits in the Erdős–Hajnal partition-calculus cluster alongside Erdős #595 and #596 (erdosproblems.com/595, erdosproblems.com/596). Listed as open on erdosproblems.com/597 (fetched 2026-07-13, status 'open'), tagged graph theory | ramsey theory | set theory. Attacker's tool: ordinal partition calculus — tree arguments, elementary-submodel and forcing techniques from infinite combinatorics — the relation is purely infinitary with no finite certificate.

References

RefSourceType
REF-01 Erdős Problem #597 (T. F. Bloom) website

Investigations · 0

No published investigations yet. This problem is unclaimed territory.