A Nonuniversality Obstruction to an Ordinal Graph Partition Relation
Overview
Erdős #597 asks whether certain graphs must appear in two-colorings of the ordinal square ω₁². Using Baumgartner's negative partition relation as reported by Erdős, this paper gives a counterexample to the unrestricted infinite-target assertion: the target has exactly ℵ₁ vertices, is connected and bipartite, has diameter at most three, and contains no countably infinite complete bipartite graph. The argument uses a well-founded tree measuring finite bicliques and credits Shelah's nonuniversality theorem. A Lean companion checks the deduction from one explicit published-result premise (Reference-Gated); Baumgartner's construction itself is not formalized. The separate finite-target question remains unresolved.
Original public questions
Erdős #597: the unrestricted infinite-target assertion
Paul Erdős: Some problems on finite and infinite graphs (1987) — Printed p.224: the forbidden-K4 and forbidden-countable-biclique graph question, the reported Baumgartner relation, and the separately posed finite-target variant.
Erdős Problems: problem 597 — The result addresses the unrestricted infinite-target assertion; it does not settle the finite-target question or claim endorsement by the problem-list maintainer.
Original abstract (English)
Erdős asked whether every graph on at most ℵ₁ vertices omitting both a four-vertex clique and a countably infinite complete bipartite graph is forced as a blue subgraph in every colouring of the ordinal square ω₁² with no red homogeneous set of order type ω₁·ω. We apply the nonuniversality of graphs omitting the countable biclique to Baumgartner's negative partition relation, as recorded by Erdős, to obtain a negative answer to this unrestricted assertion. The obstructing target can have exactly ℵ₁ vertices and be connected and bipartite, with diameter at most three. We give an elementary well-founded-tree proof of the required special case of Shelah's nonuniversality theorem. The separate question about finite target graphs remains unresolved by this argument.
Mathematical review
These conclusions remain conditional on the documented external theorem assumptions. This is an intermediate release; a final formalization must also supply checked proofs for every such assumption.
Review standard