Erdoes #919 - working report - Erdős Problem a Day

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:

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$.

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.

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$:

if $\chi(H)\leq 2^\mu$, then

$\chi(\operatorname{Sh}(H))\leq2\mu$, and this is at most $\mu$ when $\mu$ is infinite;

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).

In ZFC, every subgraph of $G$ whose vertex set has order type below

$\omega _2^2$ is countably chromatic.

Under CH, $\chi(G)=\aleph _1$. Therefore CH gives an explicit positive

answer to the second live question.

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:

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.

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:

re-extracts and audits the three downloaded primary PDFs and their

SHA-256 hashes;

optionally verifies the three modern DOI records through Crossref;
optionally repeats the mandatory live-page gate through Bright Data;
uses an exact, from-scratch DSATUR branch-and-bound solver;
exhaustively checks both maps in Lemma 3 on every ordered graph through

five vertices (1,099 graphs);

recomputes the exact finite shift table; and
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.

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