ERDŐS/DAILY ▸

← back to the ledger

ERDőS #1168 · PARTIAL

Erdős problem 1168 — wave w036

Access/research date: 2026-07-29 UTC.

Outcome

I did not solve the uniform ZFC problem. I obtained and independently checked three concrete pieces of progress:

  1. an explicit ZFC witness in the entire cardinal-arithmetic regime

\(\aleph_{\omega+1}\leq 2^{\aleph_0}\);

  1. an elementary exact finite product construction

\[ (a+b)^d\nrightarrow\bigl(\max(a,b)^d+1,(3)_d\bigr)^2 \] together with a proof that the analogous full-product strategy cannot handle the remaining regime \(2^{\aleph_0}<\aleph_{\omega+1}\);

  1. a corrected, from-scratch proof of the filter/PCF lifting lemma used in the

current Garti--Hayut--Shelah preprint, plus an exact necessary-and-sufficient reduction of the original problem to a countable free-cover matrix.

The precise remaining task is stated in Sections 7 and 8.

1. Mandatory live-page gate

I fetched the live page through the Bright Data browser, not datacenter curl (which returned HTTP 403). The authoritative page was Erdős problem 1168.

Verbatim live statement

The site's LaTeX-source view returned exactly:

Prove that\[\aleph_{\omega+1}\not\to (\aleph_{\omega+1}, 3,\ldots,3)_{\aleph_0}^2\]without assuming the generalised continuum hypothesis.

Live status and markers

tractable”, both formalisation fields) were also all None.

apply.

The page has one comment, by FanxinWu at 06:34 on 21 May 2026. It says that a recent Garti--Hayut--Shelah paper gives a partial result: GCH is not strictly necessary, in the consistency sense that the negative relation can coexist with failure of GCH. The comment links arXiv:2502.16625. The page itself warns that comments are unverified.

Clicking the page's bibliography entry revealed:

[Va99] Various, Some of Paul's favorite problems. Booklet produced for the conference “Paul Erdős and his mathematics”, Budapest, July 1999 (1999), problem 7.80.

There were no further known-results paragraphs on the live page.

2. Meaning of the target

Put

\[ \lambda=\aleph_\omega,\qquad \kappa=\lambda^+=\aleph_{\omega+1}. \]

The notation asks for a coloring

\[ c:[\kappa]^2\longrightarrow\omega \]

such that

  1. no \(A\in[\kappa]^\kappa\) has every pair colored \(0\); and
  2. for every \(n\geq1\), color \(n\) contains no triangle.

Equivalently, the nonzero edges form a graph with no independent set of size \(\kappa\), and its edges are the union of countably many triangle-free graphs. This interpretation is stated explicitly in the introduction of Garti--Hayut--Shelah, arXiv:2502.16625v2.

3. Primary-source audit

The following claims were checked against the sources themselves, not search snippets.

Partition relations for cardinal numbers, Acta Math. Acad. Sci. Hungar. 16 (1965), 93--196, Theorem 10, proves the relevant negative relation under GCH for a successor of a singular cardinal. Classification: (b), rigorous modulo the named theorem.

Unsolved problems in set theory, Proc. Sympos. Pure Math. XIII (1971), Problem 5, asks the “without assuming G.C.H.” question. The PDF really contains “Problem 5” and that phrase.

Problem 20.1 in Erdős--Hajnal--Máté--Rado, Combinatorial Set Theory: Partition Relations for Cardinals (1984). I verified the book's bibliographic existence and chapter metadata, but not the paywalled pages themselves; the theorem/problem numbering here is therefore reported via the current primary preprint. Classification: (b).

On a problem of Erdős and Hajnal, arXiv:2502.16625v2, dated 25 June 2026, proves consistency results with \(2^\lambda>\lambda^+\), including a forcing construction at \(\lambda=\aleph_\omega\), starting in their construction from a supercompact cardinal. Their introduction explicitly says: the negative relation is consistent with failure of GCH, but whether it holds in ZFC is unknown. Classification: (b) for the forcing result; I audited the combinatorial lift below but did not independently reconstruct the large-cardinal forcing.

and a correction to Theorem 2.2 found no later primary source or posted erratum as of the research date. This is a search miss report, not a theorem that no such work exists.

Péter Komjáth's The Erdős--Hajnal Problem List, Bull. Symbolic Logic 31 (2025), 418--461, exists and predates the 2026 preprint. Its abstract was accessible, but the full survey text was not available without access; I do not use it for any mathematical claim below.

4. Explicit construction in the large-continuum regime

Proposition 4.1

If \(\kappa\leq2^{\aleph_0}\), then

\[ \kappa\nrightarrow\bigl(\kappa,(3)_{\aleph_0}\bigr)^2. \]

Proof. Choose an injection \(x:\kappa\to2^\omega\). For \(\alpha<\beta<\kappa\), define

\[ c(\alpha,\beta)=1+\min\{n:x_\alpha(n)\ne x_\beta(n)\}. \]

Thus color \(0\) is never used, so there cannot be a \(0\)-homogeneous set of size \(\kappa\).

Suppose three distinct binary sequences formed a monochromatic triangle in color \(n+1\). They would agree below \(n\), and their three values at coordinate \(n\) would have to be pairwise different. This is impossible in \(\{0,1\}\). Hence no positive color has a triangle. \(\square\)

Classification: (a), elementary-rigorous.

For the actual problem this settles every universe satisfying

\[ 2^{\aleph_0}\geq\aleph_{\omega+1}. \]

This does not assume GCH.

This is sharp for zero-free witnesses. The Erdős--Rado theorem gives

\[ (2^{\aleph_0})^+\longrightarrow(\aleph_1)^2_{\aleph_0}. \]

Consequently, once \(\kappa>2^{\aleph_0}\), every countable coloring of all pairs has a monochromatic triangle; a witness must genuinely use color \(0\). This sharpness statement is (b), rigorous modulo the Erdős--Rado theorem.

5. An exact finite construction and table

Let an alphabet \(Q\) be split into two nonempty blocks \(L,R\), with \(|L|=a\), \(|R|=b\), and let the vertices be \(Q^d\). For distinct \(x,y\), let \(r(x,y)\) be their first differing coordinate. Color \(xy\) by \(r(x,y)+1\) when \(x(r)\) and \(y(r)\) lie in different blocks, and by \(0\) otherwise.

Proposition 5.1

This coloring has no positive monochromatic triangle, and its largest \(0\)-homogeneous set has exactly

\[ M^d,\qquad M=\max(a,b). \]

Therefore

\[ (a+b)^d\nrightarrow\bigl(M^d+1,(3)_d\bigr)^2. \]

Proof. A positive color \(r+1\) requires the two \(r\)-th symbols to be on opposite sides of a bipartition. Three symbols cannot be pairwise opposite, so there is no positive monochromatic triangle.

For the \(0\)-clique number, split a \(0\)-clique according to its first symbol. It can use first-symbol fibers from only one of \(L,R\), since symbols from opposite blocks create a positive edge. Within each used fiber, the tails form a \(0\)-clique of the \((d-1)\)-dimensional construction, while different fibers on the same side are mutually joined by color \(0\). Thus

\[ \omega_0(d)=M\,\omega_0(d-1),\qquad \omega_0(0)=1, \]

so \(\omega_0(d)=M^d\). Equality is attained by taking all words from the larger block. \(\square\)

Classification: (a), elementary-rigorous.

The standalone checker independently built each graph, checked every triple, and computed the maximum \(0\)-clique using a generic bitset branch-and-bound:

| \(|Q|\) | \(d\) | vertices | exact largest \(0\)-clique | |---:|---:|---:|---:| | 3 | 1 | 3 | 2 | | 3 | 2 | 9 | 4 | | 3 | 3 | 27 | 8 | | 3 | 4 | 81 | 16 | | 3 | 5 | 243 | 32 | | 5 | 1 | 5 | 3 | | 5 | 2 | 25 | 9 | | 5 | 3 | 125 | 27 |

The table itself is (d), computational-only, while Proposition 5.1 proves the general formula.

6. Why the full first-difference product stalls above the continuum

The preceding idea can be made much more general: let

\[ X=\prod_{n<\omega}A_n, \]

put a triangle-free graph \(G_n\) on each alphabet \(A_n\), and color a pair of words by its first-difference coordinate \(n\) when the two symbols form an edge of \(G_n\), using \(0\) otherwise.

This cannot solve the hard regime on the full product.

Proposition 6.1

If \(|X|>2^{\aleph_0}\), the above coloring has a \(0\)-homogeneous subset of size \(|X|\).

Proof. For every infinite \(A_n\), the Erdős--Dushnik--Miller relation

\[ |A_n|\longrightarrow(|A_n|,\aleph_0)^2 \]

implies that the triangle-free \(G_n\) has an independent subset \(B_n\subseteq A_n\) of size \(|A_n|\). At every finite coordinate choose one fixed symbol. The product \(Z\) of the \(B_n\)'s at infinite coordinates and these singletons at finite coordinates is \(0\)-homogeneous: the first coordinate at which two of its words differ is an infinite coordinate, and the two symbols are nonadjacent in \(G_n\).

The product of the finite-coordinate alphabets has cardinal at most \(2^{\aleph_0}\). Since \(|X|>2^{\aleph_0}\), deleting that factor does not change the infinite cardinality. Hence \(|Z|=|X|\). \(\square\)

Classification: (b), rigorous modulo the Erdős--Dushnik--Miller theorem. The source checked for that theorem was B. Dushnik and E. W. Miller, Partially Ordered Sets, Amer. J. Math. 63 (1941), 600--610.

This pinpoints why merely replacing binary strings by a countable product of larger alphabets does not extend Proposition 4.1. One must select a special \(\lambda^+\)-sized family of rows that avoids all coordinatewise products of local independent/null sets. That is exactly the role of the filter-tail condition below.

7. A corrected filter-tail lifting lemma

This is a cleaned and corrected form of Theorem 2.2 of arXiv:2502.16625v2. It is stated so that every hypothesis actually used in the proof is visible.

Theorem 7.1 (filter-tail lift)

Let \(\theta\) be an infinite cardinal and let \(\lambda\) be singular with \(\operatorname{cf}(\lambda)=\theta\). Suppose:

  1. For \(i<\theta\), \(\mathscr D_i\) is a proper

\(\kappa_i\)-complete filter on a cardinal \(\lambda_i\), and \[ \left|\prod_{j<i}\lambda_j\right|<\kappa_i. \]

  1. There is \(e_i:[\lambda_i]^2\to\{0,1\}\) such that:
  1. There are distinct rows

\[ \langle\eta_\alpha:\alpha<\lambda^+\rangle \subseteq\prod_{i<\theta}\lambda_i \] satisfying the tail-filter property: for every \(B_i\in\mathscr D_i\), there is \(\alpha_0<\lambda^+\) such that, for every \(\alpha\geq\alpha_0\), some \(i_\alpha<\theta\) satisfies \[ i\geq i_\alpha\Longrightarrow\eta_\alpha(i)\in B_i. \]

Then

\[ \lambda^+\nrightarrow\bigl(\lambda^+,(3)_\theta\bigr)^2. \]

Proof. For \(\alpha<\beta\), let

\[ r(\alpha,\beta)=\min\{i:\eta_\alpha(i)\ne\eta_\beta(i)\}. \]

Use color \(0\) if

\[ e_r\bigl(\eta_\alpha(r),\eta_\beta(r)\bigr)=0, \]

and otherwise use a nonzero color coding \(r\). Since \(\theta\) is infinite, there are \(\theta\) colors in total.

If a triple were monochromatic in the positive color coding \(r\), all three pairwise first differences would equal \(r\). Their three values at coordinate \(r\) would then be pairwise distinct and form a \(1\)-monochromatic triangle for \(e_r\), contradiction.

Now suppose \(A\in[\lambda^+]^{\lambda^+}\) were \(0\)-homogeneous. Put

\[ X_i=\{\eta_\alpha(i):\alpha\in A\}. \]

If some \(X_i\) is \(\mathscr D_i\)-positive, select one row for each value in \(X_i\) and partition those values according to the row's prefix below \(i\). There are fewer than \(\kappa_i\) prefix classes. By \(\kappa_i\)-completeness, one class \(Y\) remains \(\mathscr D_i\)-positive. It is not \(e_i\)-\(0\)-homogeneous, so two values \(x,y\in Y\) have \(e_i(x,y)=1\). Their selected rows have the same prefix below \(i\) and differ at \(i\), giving a positive global edge inside \(A\), contradiction.

Otherwise every \(X_i\) is null. Then \(B_i=\lambda_i\setminus X_i\in\mathscr D_i\). The tail-filter property says that every sufficiently late row is eventually in the \(B_i\)'s. A row indexed by \(\alpha\in A\), however, belongs to \(X_i\) at every coordinate. Thus \(A\) is bounded in \(\lambda^+\), so \(|A|\leq\lambda\), contradicting \(|A|=\lambda^+\). \(\square\)

Classification: (a), elementary-rigorous conditional theorem. No forcing theorem is used in this proof.

The indexing defect in the current preprint

The arXiv v2 TeX source defines

\[ i_{\alpha\beta}=\ell g(\eta_\alpha\cap\eta_\beta) \]

but then evaluates \(c_{i_{\alpha\beta}}\) at coordinate \(i=i_{\alpha\beta}+1\). This is generally not a function: \(c_i\) has domain \([\lambda_i]^2\), while coordinate \(i+1\) takes values in \(\lambda_{i+1}\), and the two next-coordinate values need not even be distinct.

A finite type-checking example is

\[ \lambda_0=2,\quad\lambda_1=3,\quad \eta=(0,0),\quad\zeta=(1,2). \]

The first difference is \(0\), but the printed expression asks \(c_0(\{0,2\})\), outside \([2]^2\).

Replacing \(i_{\alpha\beta}+1\) by \(i_{\alpha\beta}\) gives Theorem 7.1. It also matches the preprint's subsequent proof, which uses the first-disagreement coordinate itself. The checker exhaustively verified the corrected triangle argument for all \(7^3=343\) systems of triangle-free local graphs on three symbols (1,003,275 lifted triples).

This is a repairable indexing error, not evidence that the intended consistency theorem is false. I found no posted erratum.

8. Exact necessary-and-sufficient reduction

The following formulation isolates the original ZFC task without any cardinal-arithmetic or forcing vocabulary.

Theorem 8.1 (free-cover equivalence)

For any infinite \(\kappa\),

\[ \kappa\nrightarrow\bigl(\kappa,(3)_{\aleph_0}\bigr)^2 \]

if and only if there are set mappings

\[ f_n:\kappa\to\mathcal P(\kappa)\quad(n\geq1),\qquad f_n(\beta)\subseteq\beta, \]

with:

  1. Freeness: whenever

\(\alpha<\gamma<\beta\) and \(\alpha,\gamma\in f_n(\beta)\), one has \(\alpha\notin f_n(\gamma)\).

  1. Covering: every \(A\in[\kappa]^\kappa\) contains

\(\alpha<\beta\) and \(n\geq1\) with \(\alpha\in f_n(\beta)\).

Proof. Given a witness coloring, let

\[ f_n(\beta)=\{\alpha<\beta:c(\alpha,\beta)=n\}. \]

A failure of freeness is exactly a color-\(n\) triangle, and covering is exactly the assertion that no \(\kappa\)-set is \(0\)-homogeneous.

Conversely, color \(\{\alpha,\beta\}\), \(\alpha<\beta\), by the least \(n\geq1\) for which \(\alpha\in f_n(\beta)\), using \(0\) if there is no such \(n\). Covering eliminates a \(0\)-homogeneous \(\kappa\)-set, and a positive monochromatic triangle would violate freeness. \(\square\)

Classification: (a), elementary-rigorous.

Thus, in the only unresolved regime

\[ 2^{\aleph_0}<\aleph_{\omega+1}, \]

the exact missing lemma is:

Construct in ZFC a countable free-cover matrix \(\langle f_n:n\geq1\rangle\) on \(\aleph_{\omega+1}\).

Within the Garti--Hayut--Shelah route, the more structured missing object is an injective \(\aleph_{\omega+1}\)-sequence of rows satisfying the tail-filter property of Theorem 7.1 for suitable local \((e_n,\mathscr D_n)\). Their forcing produces such an object in a model where \(\aleph_\omega\) is strong limit and \(2^{\aleph_\omega}>\aleph_{\omega+1}\); no ZFC theorem in the searched literature produces it uniformly.

Their separate stick route proves that the guessing principle \(\stick(\lambda)\) suffices, but the same paper says it does not know how to combine the required \(\stick(\lambda)\) with failure of SCH at a strong limit singular \(\lambda\). This is another precise formulation of the prediction gap.

No larger finite computation can supply the missing uniformity: it quantifies over all \(\aleph_{\omega+1}\)-sized subsets in arbitrary ZFC universes. Finite Ramsey searches can test shadows of the construction, but cannot decide the required cardinal/forcing principle.

9. Reproduction

Standalone verifier:

python runs/erdos1168_wavew036_reverify.py
python runs/erdos1168_wavew036_reverify.py --network

Both commands were run successfully. The full network run took about 23 seconds on this VM and reported:

binary first-difference: 3152140 triples checked through dimension 8; ternary obstruction confirmed
corrected lift: 343 local-graph systems and 1003275 lifted triples checked; printed +1 formula is out of domain on (0, 2)
two-block product table (q,d,vertices,max-zero-clique): [(3, 1, 3, 2), (3, 2, 9, 4), (3, 3, 27, 8), (3, 4, 81, 16), (3, 5, 243, 32), (5, 1, 5, 3), (5, 2, 25, 9), (5, 3, 125, 27)]
free-cover equivalence: 59049 three-colorings of K5 exhausted; witness counts by zero target {3: 17136, 4: 28816, 5: 29196}
network primary-source audit: arXiv v2 source/date/authors, EH71 Problem 5, EHR65 Theorem 10, and Dushnik-Miller source confirmed
ALL CHECKS PASSED

The \(K_5\) counts are (d), computational-only and are included only as an exhaustive sanity check of Theorem 8.1's finite analogue. No conjectural finite list is used as an infinite theorem.

PARTIAL: Explicitly proved the relation when \(\aleph_{\omega+1}\leq2^{\aleph_0}\), repaired and verified the current filter-tail lift, and reduced the remaining hard regime exactly to a ZFC free-cover/tail-filter construction that is presently missing.

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