ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1171 · PARTIAL

Erdős problem 1171 — wave 8h

Date: 2026-07-28 UTC

Outcome

This run does not solve the all-finite-\(k\) problem. It does establish a useful correction/reduction that is absent from the live page:

Baumgartner and Hajnal proved \[ \omega_1^2\longrightarrow(\omega_1\omega,3,3)^2 \] in 1987. Consequently, the live question is equivalent to its restriction to \(3\leq k<\omega\).

for every finite \(k\). The published input is Baumgartner's theorem \(\omega_1\omega\to(\omega_1\omega,3)^2\); the finite-color iteration below is elementary.

and also exactly a coherent selection problem across the \(\omega_1\)-blocks of \(\omega_1^2\). Both reductions are proved below.

red/blue \(5\)-cycle. A standalone exhaustive checker verifies \(R_2(3)=6\), all labeled extremal colorings, and the finite blow-up.

Labels used throughout, as requested:

No [c] assertion is used in a proof.

Step 0: live-page gate

I fetched the live page through the Bright Data browser path on 2026-07-28. The direct /latex/1171 rendering gives the following verbatim statement:

Is it true that, for all finite \(k<\omega\), \[ > \omega_1^2\to (\omega_1\omega, 3,\ldots,3)_{k+1}^2? > \]

The live record was last edited 26 January 2026 and displayed:

Martin's axiom, that \(\omega_1\omega\to(\omega_1\omega,3)^2\).”;

Thus neither stop condition (claimed solution nor current worker) was present.

Here and below, the arrow means that every coloring

\[ c:[\omega_1^2]^2\longrightarrow\{0,1,\ldots,k\} \]

has either a color-\(0\) set of order type \(\omega_1\omega\), or a monochromatic triangle in one of colors \(1,\ldots,k\).

Primary-source audit

  1. [b] Erdős and Hajnal wrote in their 1974 problem paper that they had

proved \[ \omega_1^2\to(\omega_1\cdot\alpha,3)^2\qquad(\alpha<\omega_1). \] Taking \(\alpha=\omega\) settles \(k=1\). This appears on p. 274 of their primary scan, Unsolved and solved problems in set theory; the cited original paper is their 1970 paper.

  1. [b] J. E. Baumgartner and A. Hajnal,

A remark on partition relations for infinite ordinals with an application to finite combinatorics, Contemporary Mathematics 65 (1987), 157–167, explicitly state in their introduction that they prove in ZFC \[ \omega_1^2\to(\omega_1\omega,3,3)^2. \] The same introduction says that the analogous relation with \(n>2\) triangle colors was not known. It also records the CH negative relation \[ \omega_1^2\nrightarrow(\omega_1\omega,4)^2. \] I checked the title, authors, year, pages, and DOI independently in the AMS volume listing and Crossref, and checked the mathematical assertions in the scan/snippets at Google Books, pp. 157–162. Jean Larson's historical survey independently reproduces the theorem and was used only as a locator, not as the primary authority.

  1. [b] Baumgartner's

Remarks on partition ordinals, Lecture Notes in Mathematics 1401 (1989), 5–17, has an official publisher abstract stating that \(\mathrm{MA}(\aleph_1)\) makes \(\omega_1\omega\) and \(\omega_1\omega^2\) partition ordinals. By definition this includes \(\omega_1\omega\to(\omega_1\omega,3)^2\).

  1. The exact higher-color formula was searched in multiple notational forms,

as were citations forward from the 1987 paper. I found no primary source claiming a ZFC solution for any \(k\geq3\), and no claimed solution on the live page. This is an honest search miss, not a proof that no such paper exists; the live page remains the authority for current open status.

First clean reduction: only \(k\geq3\) remains

[b] For \(k=0\), the assertion is immediate. For \(k=1\), use the Erdős–Hajnal theorem above with \(\alpha=\omega\). For \(k=2\), use Baumgartner–Hajnal's 1987 ZFC theorem. Therefore

\[ \bigl[\forall k<\omega\;P(k)\bigr] \quad\Longleftrightarrow\quad \bigl[\forall k\;(3\leq k<\omega\Rightarrow P(k))\bigr], \]

where \(P(k)\) denotes the live-page relation. This is a genuine narrowing of the open quantifier, but not a solution of it.

Why Martin's axiom settles every finite \(k\)

Let \(\beta=\omega_1\omega\), and assume the published relation \(\beta\to(\beta,3)^2\).

[a] Given a \((k+1)\)-coloring with no triangle in any nonzero color, restrict it to the initial copy of \(\beta\) inside \(\omega_1^2\). Starting with \(H_0\) of type \(\beta\), for \(i=1,\ldots,k\), two-color \([H_{i-1}]^2\) according as the original color is \(i\) or is not \(i\). The relation \(\beta\to(\beta,3)^2\) gives either an \(i\)-colored triangle or a subset \(H_i\) of type \(\beta\) with no edge of color \(i\). The former is forbidden, so the latter occurs. At the end, every edge of \(H_k\) has color \(0\).

[b] Baumgartner's theorem supplies the input under \(\mathrm{MA}(\aleph_1)\), so the live relation holds for all finite \(k\) in that theory. This also shows why a ZFC disproof cannot be an absolute construction valid in every model.

Exact graph reformulation

For a graph \(G\), let

\[ \tau_\triangle(G)=\min\{m:E(G)\text{ is the union of }m \text{ triangle-free graphs}\}, \]

with value \(\infty\) if there is no finite cover.

[a] The \(k\)-th instance of problem 1171 is equivalent to:

Every graph \(G\) on the ordered vertex set \(\omega_1^2\) with \(\tau_\triangle(G)\leq k\) has an independent set of order type \(\omega_1\omega\).

Indeed, from a coloring take \(G_i\) to consist of the edges of color \(i\), \(1\leq i\leq k\). Each \(G_i\) is triangle-free when the forbidden alternative is absent, and a color-\(0\) set is precisely an independent set in \(G=\bigcup_iG_i\). Conversely, from a triangle-free cover assign each edge of \(G\) to one covering graph and color all other pairs \(0\). Removing overlaps from a cover preserves triangle-freeness.

[b] In this language, the 1987 theorem says that \(\tau_\triangle(G)\leq2\) forces the desired independent set. Under CH their other theorem supplies a \(K_4\)-free graph \(G\) on \(\omega_1^2\) with no such independent set; the positive theorem forces \(\tau_\triangle(G)>2\). The precise unresolved possibility is whether a bad graph can have \(3\leq\tau_\triangle(G)<\omega\).

Thus a counterexample for some finite \(k\) must give a bad ordered graph together with an explicit finite triangle-free edge cover. A proof of the all-\(k\) assertion must show that every bad graph has \(\tau_\triangle(G)=\infty\). This is an exact equivalence, not a heuristic.

Why the standard finite-Ramsey coarsening is too strong

Let \(R_k(3)\) be the least \(r\) such that every \(k\)-coloring of \([r]^2\) has a monochromatic triangle.

[a] The following is a valid sufficient reduction:

\[ \omega_1^2\to(\omega_1\omega,R_k(3))^2 \quad\Longrightarrow\quad \omega_1^2\to(\omega_1\omega,3,\ldots,3)_{k+1}^2. \]

Collapse colors \(1,\ldots,k\) to one color. If the collapsed coloring produces \(R_k(3)\) vertices whose pairs are all nonzero, Ramsey's definition produces an original monochromatic triangle; otherwise it produces the required color-\(0\) set.

[a] Graphically, a union of \(k\) triangle-free graphs is \(K_{R_k(3)}\)-free. The converse is false in general: clique-freeness does not provide a triangle-free edge cover.

[b] This loss is fatal here. \(R_2(3)=6\), so coarsening the already-solved \(k=2\) case would demand \(\omega_1^2\to(\omega_1\omega,6)^2\). Baumgartner–Hajnal's CH coloring has neither a color-\(0\) \(\omega_1\omega\) nor even a color-\(1\) \(K_4\), and hence refutes the target-\(6\) relation under CH. Therefore this standard coarsening route cannot be a ZFC proof even for \(k=2\), where the desired multicolor statement is nevertheless a ZFC theorem.

Exact block reduction

Write

\[ B_\xi=[\omega_1\xi,\omega_1(\xi+1))\qquad(\xi<\omega_1). \]

Each \(B_\xi\) has order type \(\omega_1\).

Block-support lemma

[a] For \(X\subseteq\omega_1^2\), \(X\) contains a subset of order type \(\omega_1\omega\) if and only if

\[ S_X=\{\xi<\omega_1:|X\cap B_\xi|=\aleph_1\} \]

is infinite.

Proof. If \(S_X\) is infinite, choose \(\xi_0<\xi_1<\cdots\) from it. Every uncountable subset of a copy of \(\omega_1\) has order type \(\omega_1\), so choosing one in each selected block and taking their union gives the ordinal sum \(\sum_{n<\omega}\omega_1=\omega_1\omega\).

Conversely, suppose \(S_X\) has \(m<\omega\) elements. Before and between those finitely many block indices there are only countably many blocks, each meeting \(X\) countably, while the final tail contributes order type at most \(\omega_1\). Together with the \(m\) exceptional block intersections this bounds \(\operatorname{otp}(X)\) by a finite multiple of \(\omega_1\), hence strictly below \(\omega_1\omega\). ∎

Local thinning and the missing coherent choice

Assume no nonzero color contains a triangle, and define

\[ \mathcal Z_\xi=\{A\in[B_\xi]^{\aleph_1}:c``[A]^2=\{0\}\}. \]

[b] Every \(\mathcal Z_\xi\) is nonempty. Collapse all nonzero colors in \(B_\xi\). The Erdős–Dushnik–Miller theorem \(\omega_1\to(\omega_1,\omega)^2\) gives either an uncountable color-\(0\) set, or an infinite set all of whose edges have nonzero original colors. In the second case, ordinary infinite Ramsey applied to the finite original palette gives a monochromatic triangle, a contradiction.

[a] By the block-support lemma, the original \(k\)-color problem is now exactly the demand for increasing indices \(\xi_0<\xi_1<\cdots\) and choices \(A_n\in\mathcal Z_{\xi_n}\) such that

\[ c``[A_n,A_m]=\{0\}\qquad(n<m<\omega). \tag{\(*_k\)} \]

Local thinning alone does not give \((\!*_k)\): after internal edges are made color \(0\), a single bipartite cross-rectangle can still carry an arbitrary nonzero coloring without creating a nonzero monochromatic triangle. The constraint only becomes effective through configurations involving three or more blocks. The missing ingredient is therefore a genuinely coherent cross-block fusion/canonization lemma, not another within-block Ramsey argument.

A regime where the block reduction closes

[a] Suppose there is an infinite set \(I\subseteq\omega_1\) and choices \(A_\xi\in\mathcal Z_\xi\) for \(\xi\in I\) such that every rectangle \([A_\xi,A_\eta]\), \(\xi<\eta\), is monochromatic. Color pairs from \(I\) by that rectangle color. Infinite Ramsey gives an infinite homogeneous \(J\subseteq I\). Its color cannot be nonzero, since three blocks and one point from each would form a forbidden triangle. Hence its color is \(0\), and the increasing union of the \(A_\xi\), \(\xi\in J\), has type \(\omega_1\omega\). Thus problem 1171 is true in the block-constant regime for every finite \(k\).

Sharp finite block obstruction

[a] More generally, if all cross-rectangles among \(m\) internally color-\(0\) blocks are monochromatic and nonzero, their colors form a \(k\)-coloring of \(K_m\) without a monochromatic triangle. Therefore

\[ m\leq R_k(3)-1, \]

and the bound is sharp by blowing up any critical Ramsey coloring.

For \(k=2\), take five blocks of type \(\omega_1\), color within each block \(0\), color cross-edges red when their block indices are adjacent on \(C_5\), and blue otherwise. Both \(C_5\) and its complement are triangle-free. Hence there is no red or blue triangle, while every color-\(0\) homogeneous set lies in one block. In particular this explicit coloring witnesses the sharp block-constant relation

\[ \omega_1\cdot5\nrightarrow(\omega_1\cdot2,3,3)^2. \]

It is a concrete finite-coefficient obstruction, not a counterexample on \(\omega_1^2\).

Standalone re-verification

The checker is erdos1171_wave8h_reverify.py. It uses only the Python standard library and exhausts all \(2^{\binom n2}\) labeled red/blue colorings for \(1\leq n\leq6\). Run:

python runs/erdos1171_wave8h_reverify.py

Observed output:

triangle-free labeled 2-colorings of K_n:
  n=1: 1
  n=2: 2
  n=3: 6
  n=4: 18
  n=5: 12
  n=6: 0
R_2(3)=6 verified by exhaustive enumeration.
Every extremal coloring of K_5 is C5/complement (degree check).
C5 two-color witness has no monochromatic triangle.
5-block blow-up (2 vertices/block) has:
  no monochromatic triangle in colors 1 or 2;
  maximum color-0 clique size 2, attained by exactly the 5 blocks.
ALL CHECKS PASSED

[d] The labeled counts and finite blow-up assertions above are computational-only outputs of the exhaustive run. [a] The value \(R_2(3)=6\) and the transfinite \(C_5\)-block construction also have the elementary proofs given above. The computation is deliberately not presented as evidence for the uncountable uniformity step.

Precise remaining wall

[a] After the verified \(k\leq2\) cases, the first instance not settled by any source found in this audit is

\[ \omega_1^2\to(\omega_1\omega,3,3,3)^2. \]

Equivalently, one must show that a union of three triangle-free graphs on \(\omega_1^2\) has an independent set of type \(\omega_1\omega\), or produce a counterexample. In block language, one must prove or refute \((\!*_3)\).

The two standard simplifications fail for exact reasons:

  1. [b] Replacing “finite triangle-free cover” by the weaker finite

clique-number condition is too strong; Baumgartner–Hajnal's CH \(K_4\)-free bad graph already refutes that approach.

  1. [b] Erdős–Dushnik–Miller gives a large zero set separately in every

block. [a] This supplies no simultaneous control of the \(\binom{\omega}{2}\) cross-rectangles. Arbitrary pairwise bipartite behavior is compatible with the local hypotheses.

Finite search cannot certify \((\!*_3)\), because the missing assertion is the existence of uncountable subsets with countably many simultaneous rectangle constraints. What is needed is either:

\((\!*_k)\) for every finite \(k\); or

triangle-free cover number, together with the cover itself.

No uniformity or finiteness step of that strength was found, so no claim of closure is made.

PARTIAL: The live problem remains open, but k=2 is a verified 1987 ZFC theorem; only k>=3 remains, with an exact triangle-free-cover/block-fusion reduction and a checked sharp C5 block obstruction.

This is the AI working report, labelled by outcome — not an independently verified claim unless marked PROVED. ← ledger