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:
[b]The cases \(k=0,1,2\) are already theorems of ZFC. In particular,
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\).
[b]Under \(\mathrm{MA}(\aleph_1)\), the answer is yes simultaneously
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.
[a]The remaining question is exactly a triangle-free edge-cover problem,
and also exactly a coherent selection problem across the \(\omega_1\)-blocks
of \(\omega_1^2\). Both reductions are proved below.
[a]A sharp block-constant obstruction is given explicitly by the
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:
[a]elementary-rigorous;[b]rigorous modulo the named published theorem;[c]plausible/structural-unverified;[d]computational-only.
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:
- status: OPEN;
- source:
[Va99, 7.84]; - known-result remark, verbatim: “Baumgartner proved that, assuming a form of
Martin's axiom, that
\(\omega_1\omega\to(\omega_1\omega,3)^2\).”;
- comments: \(0\);
- claimed proofs: \(0\);
- “Currently working”: None;
- “Interested in collaborating”: None;
- likes: None.
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
2. [b] J. E. Baumgartner and A. Hajnal,
[*A remark on partition relations for infinite ordinals with an application
to finite combinatorics*](https://doi.org/10.1090/conm/065/891246),
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
Jean Larson's
independently reproduces the theorem and was used only as a locator, not as
the primary authority.
3. [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\).
4. 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:
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(ncolor \(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.
2. [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:
- a ZFC cross-block fusion/canonization theorem strong enough to establish
\((\!*_k)\) for every finite \(k\); or
- in some model (CH is the natural candidate), a bad graph of finite
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.