Wiki
Wiki

Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated


Claim. For every finite K4K_4-free block graph GG (every block, that is every maximal 22-connected piece with a bridge counted as a K2K_2, is a clique, so here a K2K_2 or a K3K_3), ω12→(ω1ω,G)2\omega_1^2\to(\omega_1\omega,G)^2 in ZFC. The family includes every finite forest, the friendship graphs, every tree of edge and triangle blocks, and the disjoint unions of such graphs. Moreover the relation for every finite K4K_4-free graph is equivalent to the relation for every finite 22-connected K4K_4-free graph, so the finite question of Problem 597 is reduced to its 22-connected instances, of which C4C_4 and K4−eK_4-e are the first that the report does not settle.

Argument, in outline. As the report presents it, the base cases are K1K_1 and K2K_2, which are immediate, and K3K_3, the Erdős–Hajnal theorem ω12→(ω1ω,3)2\omega_1^2\to(\omega_1\omega,3)^2, which the report derives from Theorem 5 of P. Erdős and A. Hajnal, Ordinary partition relations for ordinal numbers, Period. Math. Hungar. 1 (1971), 171–185. Two closure lemmas then cover the block graphs. The relation passes from two finite graphs to their disjoint union, by deleting the finitely many vertices of a blue copy of the first graph. It passes to their one-point sum (two rooted graphs glued at their roots) by a conflict-graph argument: the vertices at which a blue copy of the first graph can be rooted, with one witness copy chosen for each, carry a conflict graph whose finite subgraphs have bounded degeneracy, hence of finite chromatic number by the de Bruijn–Erdős compactness theorem, and the finite indivisibility of ω12\omega_1^2 then gives a conflict-free set of order type ω12\omega_1^2 on which the relation for the second graph completes a blue one-point sum. A finite connected graph is built from its blocks by repeated one-point sums along its block-cut tree, so the two lemmas give the theorem and the reduction. The report's own labels mark these deductions as rigorous relative to the named published theorems; its exhaustive computer checks of the block decomposition and of the local combinatorics on graphs with at most six vertices are presented as sanity checks and not as part of the proof. The argument was not reconstructed here.

Covers. The second question of Problem 597, the relation for finite GG, for the finite K4K_4-free block graphs only, together with the reduction of that question to the finite 22-connected K4K_4-free graphs; it leaves the finite question open from C4C_4 and K4−eK_4-e on, and it says nothing about the first question, the infinite targets of size at most ℵ1\aleph_1, where the argument's finiteness bound is lost. The triangle case of Erdős and Hajnal is the report's base case, not a new result.

Depends on. The Erdős–Hajnal triangle case, the base case of the report's induction over blocks.

Standing. The claimant is Patrick White, who published the result on 2026-07-27 as a working report on erdosproblemaday.com, a public ledger of AI-assisted reports on the catalog's problems that names its authors as Patrick White and Claude (Anthropic) and labels each entry by outcome; this entry is labeled PARTIAL, and the ledger states that an entry is not an independently verified claim unless labeled PROVED. The report is not filed on the site's proof-claims tab, is not refereed, and no reviewer is recorded, so the claim stays claimed. The site's label for the problem is OPEN.