Erdős problem 919 — live audit, a CH construction, and the exact ZFC wall
Date: 2026-07-27 UTC
Claim labels used throughout:
- (a) elementary-rigorous: proved here from definitions (possibly under an explicitly stated hypothesis such as CH).
- (b) rigorous-modulo-named-theorem: the deduction is rigorous assuming the cited theorem.
- (c) plausible/structural-unverified: a search conclusion or interpretation, not a theorem.
- (d) computational-only: a browser/source/code observation with its finite scope stated.
The main progress is an explicit graph for the second question under CH. Its
local order-type property is proved below in ZFC; CH is used only to make its
global chromatic number \(\aleph _1\). The report does not claim a uniform
ZFC solution.
0. Mandatory live-page gate
I accessed the live problem page through
the Bright Data browser on 2026-07-27. This was a browser render of the live
page, not the stale tracker metadata.
(d, live observation) The current page has:
- status OPEN;
- 0 comments;
- 0 claimed proofs;
- “Interested in collaborating”: None;
- “Currently working on this problem”: None.
Thus neither mandatory stop condition applied.
Here is the statement verbatim from the live page's LaTeX source (only
Markdown quotation marks have been added):
> Is there a graph $G$ with vertex set $\omega_2^2$ and chromatic number $\aleph_2$ such that every subgraph whose vertices have a lesser type has chromatic number $\leq \aleph_0$?
>
> What if instead we ask for $G$ to have chromatic number $\aleph_1$?
(d, live known-results audit) The page also lists the following
background:
1. Babai proved that a graph on a well-ordered set with chromatic number at
least \(\aleph _0\) has a subgraph on a vertex set of order type \(\omega\)
with chromatic number \(\aleph _0\).
2. Erdős and Hajnal constructed a graph on a set of type \(\omega _1^2\)
having chromatic number \(\aleph _1\), while every lesser-order-type
subgraph is countably chromatic.
3. The analogous construction at \(\omega _2^2\) has chromatic number
\(\aleph _2\), with every lesser-order-type subgraph of chromatic number at
most \(\aleph _1\).
The page cites only Erdős's 1969 paper [Er69b] for this discussion.
1. A verified transcription error in the displayed background
Proposition 1 (a). The edge formula displayed on the live page cannot
define the claimed Erdős--Hajnal example.
The page says that, for lexicographically ordered pairs, two vertices are
joined when
\[ \alpha _1<\alpha _2\quad\hbox{and}\quad\beta _1<\beta _2. \tag{1.1} \]For every infinite cardinal \(\kappa\), the diagonal
\[ D=\{(\alpha,\alpha):\alpha<\kappa\} \]is then a clique of size and order type \(\kappa\). Since
\(\kappa<\kappa^2\), this is a lesser-order-type subgraph with chromatic
number \(\kappa\). At \(\kappa=\omega _1\), that directly contradicts the
advertised countable local bound. At \(\kappa=\omega _2\), it also
contradicts the advertised \(\aleph _1\) bound. \(\square\)
(d, primary-source observation) Page 29 of Erdős,
Problems and results in chromatic graph theory
(1969), actually says, after assuming
\((\alpha _1,\beta _1)<_{\rm lex}(\alpha _2,\beta _2)\),
\[ \alpha _1<\alpha _2\quad\hbox{and}\quad\alpha _2<\beta _1. \tag{1.2} \]Thus the live page has changed the source's second inequality. Formula
(1.2) makes the diagonal independent, not complete. This audit does not
challenge the cited Erdős--Hajnal result; it identifies a transcription error
in the site's explanatory formula.
2. Primary-literature audit
(d, source observation) Erdős's 1969 paper states both live questions
essentially word for word and says that Erdős and Hajnal could not solve
either the \((\aleph _2,\aleph _0)\) case or the
\((\aleph _1,\aleph _0)\) case. It also records the easy
\((\aleph _2,\aleph _1)\) version.
(d, source observation) Erdős--Hajnal,
On chromatic number of infinite graphs
(1968), Theorem 2, uses the shift graph on increasing \(k\)-tuples. Its
\(k=2\) instance is precisely the graph on pairs used in Section 5 below.
Their CH consequence gives an \((\aleph _0,\aleph _1)\)-chromatic graph of
cardinality \(\aleph _2\).
(d, independently checked modern source) Lambie-Hanson--Rinot,
Reflection on the coloring and chromatic numbers,
Results 2.1--2.2, explicitly records:
- under \(2^{\aleph _0}=\aleph _1\), the Erdős--Hajnal construction gives an
\((\aleph _0,\aleph _1)\)-chromatic graph of size \(\aleph _2\);
- relative to a large-cardinal hypothesis, Foreman--Laver obtained a
GCH model with no \((\aleph _0,\aleph _2)\)-chromatic graph of size
\(\aleph _2\).
Here \((\mu,\lambda)\)-chromatic means global chromatic number \(\lambda\)
and chromatic number at most \(\mu\) on every strictly smaller-cardinality
subgraph.
(b, named-theorem precision) The latter result is Foreman--Laver,
Some downwards transfer properties for \(\aleph _2\)90041-2),
Adv. Math. 67 (1988), 230--238.
Fuchino--Ottenbreit--Sakai,
On some downward transfer properties in Foreman--Laver model,
states the large-cardinal assumption as the existence of a huge cardinal and
the conclusion as transfer of maximal chromatic number from \(\aleph _2\) to
\(\aleph _1\).
(b, comparison theorem) Baumgartner,
Generic graph construction, J. Symbolic
Logic 49 (1984), 234--240, gives a GCH consistency model containing an
ordinary cardinal-local \((\aleph _0,\aleph _2)\)-chromatic graph of size
\(\aleph _2\). Section 6 explains why that does not automatically settle
the stronger order-type requirement.
(c, documented search miss) Exact-statement searches using “vertices
form a set of type \(\omega _2^2\),” “lesser type,” and the two chromatic
bounds found the live page and the 1969 source, but no later primary paper
settling this stronger order-type formulation. Modern papers found in the
search concern the weaker cardinality-local ideal. This is a report of the
search, not a proof that no such paper exists.
3. The order-type ideal on \(\omega _2^2\)
Put \(\kappa=\omega _2\), and identify
\[ [\kappa]^2=\{(\alpha,\beta):\alpha<\beta<\kappa\} \]with increasing pairs ordered lexicographically. Every row has order type
\(\kappa\), so this set has order type
\(\kappa\cdot\kappa=\kappa^2\). Transporting a graph across an order
isomorphism gives a graph whose literal vertex set is \(\omega _2^2\).
For \(S\subseteq[\kappa]^2\), define its \(\alpha\)-th row and its set of full
rows by
\[ S_\alpha=\{\beta:(\alpha,\beta)\in S\},\qquad A(S)=\{\alpha<\kappa:|S_\alpha|=\kappa\}. \]Lemma 2 (a, exact characterization).
\[ \operatorname{otp}(S)=\kappa^2 \quad\Longleftrightarrow\quad |A(S)|=\kappa. \tag{3.1} \]Proof. Let \(\delta_\alpha=\operatorname{otp}(S_\alpha)\). As
\(\kappa\) is an initial ordinal,
\[ \delta_\alpha=\kappa\iff |S_\alpha|=\kappa, \qquad \operatorname{otp}(S)=\sum_{\alpha<\kappa}\delta_\alpha. \tag{3.2} \]If \(A(S)\) has cardinality \(\kappa\), it has order type \(\kappa\).
Keeping only those rows embeds the ordinal sum of \(\kappa\) copies of
\(\kappa\) into \(S\). Thus
\(\operatorname{otp}(S)\geq\kappa^2\), while the reverse inequality follows
from \(S\subseteq[\kappa]^2\).
Conversely, suppose \(|A(S)|<\kappa\). The successor cardinal \(\kappa\) is
regular, so \(A(S)\) is bounded; choose \(\gamma<\kappa\) above it. The
initial \(\gamma\) rows contribute at most \(\kappa\cdot\gamma\). Every
later row has order type below \(\kappa\). Each proper partial sum of the
tail is below \(\kappa\), by regularity, so the whole tail has order type at
most \(\kappa\). Consequently
\[ \operatorname{otp}(S) \leq\kappa\cdot\gamma+\kappa =\kappa\cdot(\gamma+1)<\kappa^2. \]This proves (3.1). \(\square\)
In particular, “lesser type” is much stronger here than “smaller
cardinality”: a single full row already has cardinality \(\aleph _2\), but
has order type only \(\omega _2\).
4. The shift-coloring lemma
Let \(H\) be a graph whose edges are oriented according to a linear order.
Its shift graph \(\operatorname{Sh}(H)\) has the oriented edges of \(H\) as
vertices, with
\[ (u,v)\sim(v,w) \quad\text{whenever }u\to v\to w. \tag{4.1} \]Lemma 3 (a). For every nonzero cardinal \(\mu\):
1. if \(\chi(H)\leq 2^\mu\), then
\(\chi(\operatorname{Sh}(H))\leq2\mu\), and this is at most \(\mu\)
when \(\mu\) is infinite;
2. if \(\chi(\operatorname{Sh}(H))\leq\mu\), then
\(\chi(H)\leq2^\mu\).
Proof of 1. Properly color \(V(H)\) with subsets of a set \(Q\) of
cardinality \(\mu\), using different subsets for different base colors, and
well-order \(Q\). For an arc \(u\to v\), let
\(\xi(u,v)\) be the least coordinate on which the two subsets differ, and
let \(\varepsilon(u,v)\in\{0,1\}\) record the tail's bit there. Color the
arc by
\[ (\xi(u,v),\varepsilon(u,v)). \tag{4.2} \]If \(u\to v\to w\), the two arcs cannot receive the same pair: at the
claimed common coordinate, the middle vertex \(v\) would have to carry both
bits. There are at most \(2\mu\) colors, and \(2\mu=\mu\) for infinite
\(\mu\). \(\square\)
Proof of 2. Given a proper coloring \(c\) of the shift graph by a set
\(Q\), assign to each base vertex
\[ C(v)=\{c(v,w):v\to w\}. \tag{4.3} \]For an oriented edge \(u\to v\), its color \(c(u,v)\) belongs to \(C(u)\).
It does not belong to \(C(v)\), because \((u,v)\) is adjacent to every
outgoing arc \((v,w)\). Hence \(C(u)\neq C(v)\), so \(v\mapsto C(v)\) is a
proper coloring of \(H\) by at most \(2^\mu\) subsets of \(Q\). \(\square\)
Both implications are explicit: (4.2) and (4.3) are the coloring maps used
by the checker.
5. Explicit conditional solution of the \(\aleph _1\) variant
Define
\[ G=\operatorname{Sh}(K_\kappa),\qquad \kappa=\omega _2, \tag{5.1} \]where \(K_\kappa\) is naturally oriented from the smaller ordinal to the
larger one. Thus
\[ V(G)=[\kappa]^2,\qquad (\alpha,\beta)\sim(\beta,\gamma) \quad(\alpha<\beta<\gamma<\kappa). \tag{5.2} \]Theorem 4 (a).
1. In ZFC, every subgraph of \(G\) whose vertex set has order type below
\(\omega _2^2\) is countably chromatic.
2. Under CH, \(\chi(G)=\aleph _1\). Therefore CH gives an explicit positive
answer to the second live question.
3. If CH fails, this same \(G\) has chromatic number \(\aleph _0\), so this
construction does not give a uniform ZFC answer.
Proof of the local assertion. Let
\(S\subseteq[\kappa]^2\) have order type below \(\kappa^2\). Regard \(S\)
as the oriented edge set of a base graph \(H_S\) on \(\kappa\): its edge
\(\{\alpha,\beta\}\), with \(\alpha<\beta\), is present exactly when
\((\alpha,\beta)\in S\). Then
\[ G[S]=\operatorname{Sh}(H_S). \tag{5.3} \]By Lemma 2, \(A=A(S)\) has cardinality below \(\kappa\), hence at most
\(\aleph _1\). In \(H_S-A\), every vertex \(\alpha\) has:
- fewer than \(\kappa\), hence at most \(\aleph _1\), later neighbors,
because \(\alpha\notin A\);
- at most \(|\alpha|\leq\aleph _1\) earlier neighbors.
Thus \(H_S-A\) has maximum degree at most \(\aleph _1\). Every one of its
connected components has cardinality at most \(\aleph _1\): from a root,
each finite-distance sphere has size at most \(\aleph _1\), and there are
only countably many spheres. Color each component injectively with a common
\(\aleph _1\)-sized palette. Give the at most \(\aleph _1\) vertices in
\(A\) distinct colors from a disjoint palette. This proves
\[ \chi(H_S)\leq\aleph _1. \tag{5.4} \]Cantor's theorem gives \(\aleph _1\leq2^{\aleph _0}\) in ZFC. Lemma 3(1)
with \(\mu=\aleph _0\), applied to (5.4), now gives
\(\chi(G[S])\leq\aleph _0\). Deleting edges cannot raise chromatic number,
so this covers arbitrary, not only induced, subgraphs on \(S\). \(\square\)
Proof of the global assertions. Cantor's theorem also gives
\[ \aleph _2\leq2^{\aleph _1}. \tag{5.5} \]Since \(\chi(K_\kappa)=\aleph _2\), Lemma 3(1) with
\(\mu=\aleph _1\) gives \(\chi(G)\leq\aleph _1\) in every model of ZFC.
Under CH, a hypothetical countable coloring of \(G\), followed by Lemma
3(2), would give
\[ \aleph _2=\chi(K_\kappa)\leq 2^{\aleph _0}=\aleph _1, \]a contradiction. Hence \(\chi(G)=\aleph _1\).
If CH fails, \(2^{\aleph _0}\geq\aleph _2\), so Lemma 3(1) instead gives a
countable coloring of \(G\). It cannot have finite chromatic number:
Lemma 3(2), with a finite color set, would color \(K_\kappa\) by finitely
many subsets. Thus \(\chi(G)=\aleph _0\) in this case. \(\square\)
This pinpoints the construction's exact limitation: it succeeds precisely
when \(2^{\aleph _0}<\aleph _2\), which is CH.
6. What can be said rigorously about the \(\aleph _2\) variant
Proposition 5 (a). Any positive answer to the first live question is an
\((\aleph _0,\aleph _2)\)-chromatic graph of cardinality \(\aleph _2\) in
the ordinary cardinal-local sense.
Proof. Let \(X\) be any vertex subset of cardinality below
\(\aleph _2\). Its inherited order type has cardinality at most
\(\aleph _1\), so it is below the initial ordinal \(\omega _2\), and
therefore below \(\omega _2^2\). The live local condition makes the
subgraph on \(X\) countably chromatic. The whole graph has cardinality and
chromatic number \(\aleph _2\). \(\square\)
Corollary 6 (b, Foreman--Laver). Assuming the consistency of the relevant
large cardinal (a huge cardinal suffices), it is consistent with ZFC+GCH
that no graph requested in the first question exists.
Proof. In the Foreman--Laver model there is no
\((\aleph _0,\aleph _2)\)-chromatic graph of size \(\aleph _2\).
Proposition 5 says that a first-question witness would be one. \(\square\)
This is a genuine ZFC obstruction: subject to that standard consistency
assumption, no ZFC proof can construct the first graph. It is not a
relative-independence proof for the order-type question, because the search
did not locate a positive consistency theorem for this stronger ideal.
Baumgartner's positive model for the cardinal-local problem does not by
itself suffice: a subset of order type below \(\omega _2^2\) may still have
cardinality \(\aleph _2\).
7. Exact remaining wall
(a, reduction) Under the lexicographic identification, the “lesser type”
sets form the ideal
\[ \mathcal J=\left\{S\subseteq[\omega _2]^2: \{\alpha:|S_\alpha|=\aleph _2\}\text{ is bounded in }\omega _2 \right\}. \tag{7.1} \]The two live questions ask for a graph of the specified global chromatic
number whose restriction to every member of \(\mathcal J\) is countably
chromatic.
The precise missing advances are therefore:
1. First variant: either a positive consistency construction for
\(\mathcal J\)-local countable chromaticity and global chromatic number
\(\aleph _2\) (which, together with Foreman--Laver, would establish
independence), or an absolute ZFC nonexistence theorem. Ordinary
cardinal-local incompactness is insufficient, while Foreman--Laver already
prevents a ZFC positive theorem.
2. Second variant: a construction that remains uncountably chromatic
when \(2^{\aleph _0}\geq\aleph _2\), or a consistency model showing that
no such graph exists. The particular shift graph cannot serve in the
large-continuum regime: Lemma 3 makes it countably chromatic there.
(c, structural diagnosis) These are infinitary/set-theoretic gaps, not
finite-search gaps. Exhaustively enumerating graphs on a finite
\(n\times n\) grid would already require
\(2^{\binom{n^2}{2}}\) candidates. For \(n=5\), this is \(2^{300}\);
even at the unrealistically optimistic rate of \(10^9\) complete candidate
checks per second, it exceeds \(5.6\times10^{77}\) core-hours. More
importantly, a complete finite table would say nothing about the
Foreman--Laver consistency obstruction or the continuum dichotomy. The open
ZFC cases require an infinitary theorem or forcing construction, not a larger
finite computation.
8. Reproducible verification
The standalone checker is
erdos919_wave6r_verify.py. It contains the
complete executable code. It:
1. re-extracts and audits the three downloaded primary PDFs and their
SHA-256 hashes;
2. optionally verifies the three modern DOI records through Crossref;
3. optionally repeats the mandatory live-page gate through Bright Data;
4. uses an exact, from-scratch DSATUR branch-and-bound solver;
5. exhaustively checks both maps in Lemma 3 on every ordered graph through
five vertices (1,099 graphs);
6. recomputes the exact finite shift table; and
7. checks the diagonal transcription obstruction for grids through order 10.
Commands used:
python runs/erdos919_wave6r_verify.py --live --network
The final combined run exited 0 with ALL CHECKS PASSED. The exact table
was:
| \(n\) | \(|V(\operatorname{Sh}(K_n))|\) | exact \(\chi\) |
|---:|---:|---:|
| 2 | 1 | 1 |
| 3 | 3 | 2 |
| 4 | 6 | 2 |
| 5 | 10 | 3 |
| 6 | 15 | 3 |
| 7 | 21 | 3 |
| 8 | 28 | 3 |
| 9 | 36 | 4 |
(d) This independently matches
\(\chi(\operatorname{Sh}(K_n))=\lceil\log _2 n\rceil\) on the tested range;
the infinite statements in Sections 3--7 rely on the written proofs, not on
this finite pattern.
The audited source hashes are:
- Erdős 1969:
3e8361bfa3f1042906d3cbae5ade7636e02b8cb64cb06d733b8092057ad3f254;
- Erdős--Hajnal 1968:
ba03270c63af8bd76abf6bef720370136cc9f6d41e3ffb243bff22d978bb8a60;
- Lambie-Hanson--Rinot:
77aa9b9702f4709972f4d625fb72d2af7195775dd4bbea7279bdddd70b0ddfde.
PARTIAL: Under CH the explicit shift graph on \([\omega_2]^2\) has chromatic number \(\aleph_1\) and every lesser-order-type subgraph is countably chromatic; the first variant is blocked in the Foreman--Laver model, and the live page's displayed background formula is a verified transcription error.