Erdős problem 918 — live audit, relative independence, and the exact remaining compactness gap
Date: 2026-07-27 UTC
Claim labels:
- (a) elementary-rigorous: proved here from definitions.
- (b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the cited published theorem.
- (c) plausible/structural-unverified: a literature-search conclusion or interpretation, not a theorem.
- (d) computational-only: a machine audit with its scope stated.
This report does not claim a uniform ZFC solution of both questions. It establishes that the first question is relatively independent, gives an exact conditional positive answer to the second, and isolates the precise unresolved compactness statement.
0. Mandatory live-page gate
I used the Bright Data browser path to access the live problem page and discussion thread on 2026-07-27. Direct datacenter curl returned HTTP 403.
(d, live observation) The page says:
- status: OPEN;
- claimed proofs: 0;
- “Interested in collaborating”: None;
- “Currently working on this problem”: None;
- formalised statement: Yes;
- last edited: 24 October 2025.
Thus neither mandatory stop condition applied.
The following is the problem statement verbatim from the live page (only Markdown quoting has been added):
> Is there a graph with $\aleph_2$ vertices and chromatic number $\aleph_2$ such that every subgraph on $\aleph_1$ vertices has chromatic number $\leq\aleph_0$?
>
> Is there a graph with $\aleph_{\omega+1}$ vertices and chromatic number $\aleph_1$ such that every subgraph on $\aleph_\omega$ vertices has chromatic number $\leq\aleph_0$?
(d, live known-result transcription) The page attributes the questions to Erdős–Hajnal, On chromatic number of infinite graphs (1968), and says that they proved: for every finite \(k\), there is a graph of chromatic number \(\aleph_1\) for which every subgraph on fewer than \(\aleph_k\) vertices is countably chromatic. It also notes that Erdős's 1969 formulation printed equality with \(\aleph_0\); the page interprets the intended condition as \(\leq\aleph_0\).
The page reports “5 comments.” The rendered thread contains five visible mathematical comments plus one deleted-post placeholder:
1. a deleted post, with no recoverable mathematical content;
2. Nat Sothanaphan explains that the suggested Thomassen paper concerns properties of already uncountably chromatic graphs and does not prove the required existence;
3. Salvatore Mercuri asks whether both terminal conditions should be \(\leq\aleph_0\);
4. Thomas Bloom notes that the two original sources differ and adds an ambiguity note;
5. LouisD observes that equality is impossible for arbitrary (not necessarily induced) subgraphs, since one may retain the vertices and delete all edges;
6. Salvatore Mercuri gives the analogous pigeonhole argument if “induced subgraph” had been intended.
The site says the statement was updated to incorporate the inequality clarification. No comment claims a partial or complete solution.
1. A normalization lemma
Write \(|H|\) for the number of vertices of a graph \(H\).
Lemma 1 (a, padding). Let \(\lambda\) be infinite, let \(\kappa=\lambda^+\), and let \(G\) have \(\kappa\) vertices. Then these are equivalent:
1. every subgraph of \(G\) on exactly \(\lambda\) vertices has chromatic number at most \(\aleph_0\);
2. every subgraph \(H\subseteq G\) with \(|H|<\kappa\) has chromatic number at most \(\aleph_0\).
Proof. Only \(1\Rightarrow2\) needs proof. Since \(\kappa=\lambda^+\), \(|H|<\kappa\) implies \(|H|\leq\lambda\). Extend \(V(H)\) to a set \(X\subseteq V(G)\) of cardinality \(\lambda\). The induced graph \(G[X]\) is countably chromatic by (1), and \(H\subseteq G[X]\), so restricting a coloring gives \(\chi(H)\leq\aleph_0\). This also handles non-induced subgraphs, because deleting edges cannot increase chromatic number. \(\square\)
Consequently:
- the first question asks for an \((\aleph_0,\aleph_2)\)-chromatic graph of size \(\aleph_2\);
- the second asks for an \((\aleph_0,\aleph_1)\)-chromatic graph of size \(\aleph_{\omega+1}\).
Here “\((\mu,\theta)\)-chromatic” means that the whole graph has chromatic number \(\theta\), while every strictly smaller subgraph has chromatic number at most \(\mu\).
2. Primary literature audit
2.1 The first question
(b) James E. Baumgartner, Generic graph construction, J. Symbolic Logic 49 (1984), 234–240, states in its abstract:
\[ \operatorname{Con}(\mathrm{ZF})\Longrightarrow \operatorname{Con}\bigl(\mathrm{ZFC}+\mathrm{GCH}+\text{“the first requested graph exists”}\bigr). \tag{2.1} \]The abstract uses the stronger local condition “every subgraph of cardinality \(\leq\aleph_1\).”
(b) Matthew Foreman and Richard Laver, Some downwards transfer properties for \(\aleph_2\)90041-2), Adv. Math. 67 (1988), 230–238, constructed—assuming the consistency of a huge cardinal—a model satisfying the transfer principle
\[ \operatorname{Tr}_{\rm Chr}(\aleph_2,\aleph_1): \quad \begin{array}{l} \text{every graph of size and chromatic number }\aleph_2\\ \text{has a subgraph of size and chromatic number }\aleph_1. \end{array} \tag{2.2} \]The exact huge-cardinal attribution and formulation are restated in Fuchino–Ottenbreit–Sakai, On some downward transfer properties in Foreman–Laver model (2017). Lambie-Hanson–Rinot, Reflection on the coloring and chromatic numbers, Results 2.1–2.2, record both Baumgartner's positive model and Foreman–Laver's negative model.
2.2 The second question
(b) Assaf Rinot, Chromatic numbers of graphs — large gaps, Combinatorica 35 (2015), 215–233, DOI, proves:
> If \(\square_\lambda+\mathrm{CH}_\lambda\) holds for an uncountable cardinal \(\lambda\), then for every infinite \(\mu\leq\lambda\) there is an \((\aleph_0,\mu)\)-chromatic graph of size \(\lambda^+\).
This is an exact-chromatic-number theorem, not merely a construction whose chromatic number is “uncountable.”
(b) Shelah, Incompactness for chromatic numbers of graphs (1990), proved a complementary consistency theorem. Lambie-Hanson–Rinot state it as follows: relative to a large-cardinal hypothesis, it is consistent with GCH that for every \(1\leq n<\omega\), if \(G\) has size \(\aleph_{\omega+1}\) and all its subgraphs of size \(<\aleph_\omega\) have chromatic number at most \(\aleph_n\), then
\[ \chi(G)\leq\aleph_n. \tag{2.3} \]Their footnote immediately after this theorem says that the case \(n=0\) remained open.
(b/c, current boundary) Radek Honzik's June 2026 v5 survey, arXiv:2510.27618, still says that it is open whether a non-weakly-compact cardinal can be countably chromatically compact; every such cardinal would have to be at least \(\beth_\omega\). This does not itself prove that the specific second question is open, but it confirms that the natural negative route at the accessible cardinal \(\aleph_{\omega+1}\) remains in unresolved territory.
(c, honest search miss) Exact-statement searches, title/DOI searches, forward-context searches around Rinot 2015 and Shelah 1990, and searches through the current Shelah and Rinot publication lists found no later primary source giving a uniform ZFC construction or a negative consistency model for the second question. This is a documented search result, not a proof of absence. The authoritative live page also remains OPEN with zero claims.
3. What follows rigorously
3.1 First question: relative independence
Proposition 2 (b). Assuming the consistency of a huge cardinal, the first displayed existence assertion is independent of ZFC, even while GCH is held fixed in the two comparison models.
Proof.
- Baumgartner gives a ZFC+GCH model containing exactly the requested graph.
- In the Foreman–Laver model, suppose such a graph \(G\) existed. By (2.2), \(G\) would have a subgraph \(H\) with \(|H|=\chi(H)=\aleph_1\). The requested local property instead gives \(\chi(H)\leq\aleph_0\), a contradiction.
Thus the first assertion holds in one ZFC+GCH model and fails in another. \(\square\)
This is a relative-consistency conclusion; it is not an absolute declaration about which side holds in the ambient universe.
3.2 Second question: an exact conditional positive answer
Proposition 3 (b). The second requested graph exists under
\[ \square_{\aleph_\omega}+\mathrm{CH}_{\aleph_\omega}. \tag{3.1} \]In particular, it exists in Gödel's constructible universe \(L\).
Proof. Apply Rinot's theorem with
\[ \lambda=\aleph_\omega,\qquad \mu=\aleph_1. \]The inequality \(\aleph_1\leq\aleph_\omega\) meets the theorem's parameter condition. The output has
\[ |G|=\lambda^+=\aleph_{\omega+1}, \qquad \chi(G)=\mu=\aleph_1, \]and every subgraph of size \(<\lambda^+\) is countably chromatic. This is stronger than the live requirement on subgraphs of size exactly \(\aleph_\omega\). Jensen's square and GCH hold in \(L\), giving the last sentence. \(\square\)
This settles the second question in a broad, standard class of models, but (3.1) is not a theorem of ZFC. Therefore Proposition 3 is not a uniform ZFC solution.
4. Exact remaining reduction
Define \(\mathrm{CC}_{\rm Chr}(\kappa)\) to mean:
\[ \forall G\ (|G|=\kappa\ \wedge\ [\forall H\subseteq G,\ |H|<\kappa\Rightarrow\chi(H)\leq\aleph_0] \ \Rightarrow\ \chi(G)\leq\aleph_0). \tag{4.1} \]This is countable chromatic compactness for graphs of size \(\kappa\).
Proposition 4 (a). The second question asks whether
\(\neg\mathrm{CC}_{\rm Chr}(\aleph_{\omega+1})\) has a witness of chromatic number exactly \(\aleph_1\).
This is immediate from Lemma 1.
Proposition 5 (b). In Shelah's model satisfying (2.3), the second question is equivalent to
\[ \neg\mathrm{CC}_{\rm Chr}(\aleph_{\omega+1}). \tag{4.2} \]Proof. A requested graph directly refutes compactness. Conversely, let \(G\) refute (4.1). Its small subgraphs are countably chromatic, and \(\chi(G)>\aleph_0\). Applying (2.3) with \(n=1\) gives \(\chi(G)\leq\aleph_1\), hence \(\chi(G)=\aleph_1\). Lemma 1 supplies the exact \(\aleph_\omega\)-vertex local condition. \(\square\)
This identifies two honest ways forward:
1. Positive ZFC route: remove the square/cardinal-arithmetic hypothesis from Rinot's exact \((\aleph_0,\aleph_1)\) construction at \(\aleph_{\omega+1}\).
2. Negative consistency route: construct a model with \(\mathrm{CC}_{\rm Chr}(\aleph_{\omega+1})\). The often-cited stronger sufficient lemma is the missing \(n=0\) extension of Shelah's (2.3); it would assume local countable chromaticity only below \(\aleph_\omega\), so it is stronger than what is needed merely to refute the live statement.
The distinction between “\(\chi(G)>\aleph_0\)” and “\(\chi(G)=\aleph_1\)” is essential. A generic high-chromatic incompactness theorem does not supply the second graph, and there is no general operation that thins an arbitrary uncountably chromatic graph to exact chromatic number \(\aleph_1\) while retaining its vertex cardinality and local property.
5. Re-verification
The standalone checker is erdos918_wave6r_verify.py. It:
1. optionally re-fetches the protected live page and thread through Bright Data (--live);
2. queries Crossref for the five named publications and checks Baumgartner's exact abstract;
3. downloads and extracts the primary texts of Rinot 2015, Lambie-Hanson–Rinot 2019, Shelah 1990 (OCR from the original scan), the Foreman–Laver follow-up, and Honzik 2026 v5;
4. checks the substitutions \((\lambda,\mu)=(\aleph_\omega,\aleph_1)\) and the Foreman–Laver contradiction;
5. exhaustively verifies the finite analogue of Lemma 1 on all 1,099 labelled graphs through five vertices, including all 59,049 same-vertex edge-subgraph pairs.
Command:
python runs/erdos918_wave6r_verify.py --live
The final run exited 0 and printed ALL CHECKS PASSED. Source SHA-256 values in that run were:
- Rinot 2015 preprint:
1fefcfde342edc68c5115ca4015f6d581d885f0efd668214582e3da9d54c8526; - Lambie-Hanson–Rinot 2019:
77aa9b9702f4709972f4d625fb72d2af7195775dd4bbea7279bdddd70b0ddfde; - Shelah 1990 original scan:
13ace42e464cb91d7e20c46c4b8aeae28b6ff681556d5949c77821c15abf723d; - Foreman–Laver follow-up:
42c53d0416ddffe83091af102d5898b16746293be16f2724edd295a088467486; - Honzik 2026 v5:
b450f6d1ea8e2f6155bd84b7f250cee72b26a31f28eb1bcea49d68234b7d0b76.
No finite search can decide (4.1): the remaining work is a forcing/inner-model construction or a ZFC infinitary-combinatorics theorem, not a computation with a meaningful core-hour estimate.
PARTIAL: The first question is relatively independent (even with GCH); the second has an exact positive solution under square+CH, hence in L, and reduces uniformly to the unresolved countable-chromatic-compactness issue at aleph_(omega+1).