Erdős problem #62 — wave 7c
Access date: 2026-07-27 UTC
Live page: <https://www.erdosproblems.com/62>
Standalone verifier: erdos62_wave7c_verify.py
Claim labels
I use the requested labels throughout:
- (a) elementary-rigorous: a complete argument is given here.
- (b) rigorous modulo a named theorem: the exact theorem and a primary
source are identified.
- (c) plausible/structural-unverified: a search miss, novelty assessment,
or engineering estimate, never a theorem.
- (d) computational-only: a finite exhaustive statement reproduced by the
standalone checker.
0. Mandatory live-page gate
(d, live-page observation) I used the Bright Data browser route and
evaluated document.body.innerText on the rendered page; I also inspected the
rendered screenshot. Direct datacenter curl was not used. The live fields
were:
| live field | value |
|---|---:|
| status | OPEN |
| claimed proofs | 0 |
| comments | 0 |
| interested in collaborating | None |
| currently working on this problem | None |
| last edited | 23 January 2026 |
The page shows no solved/falsified marker, proof claim, current worker, or
interested collaborator. The mandatory stop condition therefore did not
trigger.
Verbatim current statement
> If \(G_1,G_2\) are two graphs with chromatic number \(\aleph_1\) then must
> there exist a graph \(G\) whose chromatic number is \(4\) (or even
> \(\aleph_0\)) which is a subgraph of both \(G_1\) and \(G_2\)?
This quotation is the complete question displayed by the live page. As usual,
“subgraph” is not assumed to mean induced subgraph.
Everything else mathematical on the live page
The page additionally says, verbatim:
> Erdős also asked [Er87] about finding a common subgraph \(H\) (with chromatic
> number either \(4\) or \(\aleph_0\)) in any finite collection of graphs with
> chromatic number \(\aleph_1\).
> Every graph with chromatic number \(\aleph_1\) contains all sufficiently
> large odd cycles (which have chromatic number \(3\)), see [594]. This was
> proved by Erdős, Hajnal, and Shelah [EHS74]. Erdős wrote [Er87] that
> “probably” every graph with chromatic number \(\aleph_1\) contains as
> subgraphs all graphs with chromatic number \(4\) with sufficiently large
> girth.
The live page cites [Er87], [Er90], [Er95d], and [Va99, 7.89] for the
question. It lists no other result, comment, or claimed proof.
1. Primary-source audit
The original question and its finite-age formulation
(b) Erdős, Some Problems on Finite and Infinite Graphs (1987),
primary scan, p. 224, Problem 4,
asks the displayed two-graph question, asks the \(\aleph_0\)-chromatic
strengthening, extends it to finitely many graphs, and records the
large-girth guess.
(b) Erdős, *Problems and Results on Chromatic Numbers in Finite and
Infinite Graphs* (1985),
primary scan, pp. 203–205, asks
the same two-graph question and recasts it using hereditary families of finite
graphs. It also discusses the finite ages of shift/“edge” graphs, proves that
these ages form a strictly decreasing sequence, and asks whether the
intersection of two “good” families is always good. Section 5 below gives the
precise reduction and does not rely on the terminology.
The known three-colour result
(b) Theorem 3 of Erdős–Hajnal–Shelah, *On Some General Properties of
Chromatic Numbers, in Topics in Topology* (1974), 243–255,
primary scan, proves the
eventual-odd-cycle assertion recorded by the live page. It forces a common
3-chromatic graph for any two inputs, but its conclusion does not produce a
non-3-colourable common finite graph.
Shift graphs and slow finite-subgraph growth
(b) Füredi–Hajnal–Rödl–Trotter, Interval Orders and Shift Graphs,
in Sets, Graphs and Numbers (1992), 297–313,
defines the ordinary and double shift graphs. Its Theorem 2.2 identifies the
chromatic number of the double shift graph using antichains of a Boolean
lattice. The order-ideal lifting proof in Section 3 below is given from
scratch, works at every finite shift order, and specializes to that published
double-shift formula. I make no novelty claim for the general iterated-poset
description.
(b) Komjáth–Shelah, Finite subgraphs of uncountably chromatic graphs,
J. Graph Theory 49 (2005), 28–38,
arXiv:math/0212064, proves consistency
results showing that finite chromatic complexity inside uncountably
chromatic graphs can grow arbitrarily slowly.
(b) Lambie-Hanson, *On the growth rate of chromatic numbers of finite
subgraphs*, Advances in Mathematics 369 (2020), 107176,
arXiv:1902.08177, proves in ZFC that for
every \(f:\mathbb N\to\mathbb N\) there is an uncountably chromatic graph
whose subgraphs with fewer than \(f(k)\) vertices all have chromatic number
less than \(k\), for every \(k\ge3\). In particular, no universal finite
order bound can locate a 4-chromatic subgraph in every \(\aleph_1\)-chromatic
graph.
(c, status search) I searched the exact question, its 1985/1987 wording,
“intersection of two good families,” “common subgraph” together with
uncountable chromatic number, the cited shift-graph terminology, arXiv, and
author/title records. I found the sources above and a 2015 specialist handout
by Dániel Soukup,
Open Problems Around Uncountable Graphs,
that still lists the question as open, but no primary source claiming a
solution or counterexample. This is only a documented search miss; the
authoritative current-status evidence is the live page.
2. Concrete result of this run
The output is a complete affirmative answer for the canonical finite-order
shift-graph test family, plus exact first 4-chromatic members through shift
order five.
For \(r,n\ge1\), define the finite \(r\)-shift graph \(S_r(n)\) as follows:
- its vertices are increasing \(r\)-tuples
\((x_0,\ldots,x_{r-1})\) from \([n]=\{0,\ldots,n-1\}\);
- every increasing \((r+1)\)-tuple
\((x_0,\ldots,x_r)\) gives the edge
\[ \{(x_0,\ldots,x_{r-1}),(x_1,\ldots,x_r)\}. \]
Thus \(S_1(n)=K_n\), \(S_2(n)\) is the ordinary shift graph, and \(S_3(n)\)
is the double shift graph.
Exact threshold theorem
Let \(P_0(q)\) be a \(q\)-element antichain. Recursively let
\[ P_{i+1}(q)=J(P_i(q)), \]where \(J(P)\) is the poset of all order ideals of \(P\), ordered by
inclusion.
Theorem (a). For all finite \(q,r,n\ge1\),
\[ \boxed{\quad \chi(S_r(n))\le q \quad\Longleftrightarrow\quad n\le |P_{r-1}(q)|. \quad} \tag{1} \]Consequently, the first \(S_r(n)\) that is not 3-colourable occurs at
\[ n=|P_{r-1}(3)|+1. \tag{2} \]It is not merely at least 4-chromatic: it has chromatic number exactly 4.
Exact computed table
**(a) for the theorem and the \(+1\) construction; (d) for the two last
poset counts.**
| shift order \(r\) | \(|P_{r-1}(3)|\) | first \(n\) with \(\chi(S_r(n))=4\) | vertices | edges |
|---:|---:|---:|---:|---:|
| 1 | 3 | 4 | 4 | 6 |
| 2 | 8 | 9 | 36 | 84 |
| 3 | 20 | 21 | 1,330 | 5,985 |
| 4 | 84 | 85 | 2,024,785 | 32,801,517 |
| 5 | 8,573 | 8,574 | 385,682,147,136,966,714 | 550,818,386,469,444,628,711 |
The graph sizes are
\[ |V(S_r(n))|=\binom nr,\qquad |E(S_r(n))|=\binom n{r+1}. \]Each increasing \((r+1)\)-tuple gives a distinct edge, so these formulas are
elementary, not empirical.
The counts underlying the second column are
\[ |P_0(3)|,|P_1(3)|,|P_2(3)|,|P_3(3)|,|P_4(3)| =3,8,20,84,8573. \tag{3} \]Here \(P_1(3)\) is the eight-element Boolean lattice. Its order-ideal
lattice has 20 elements: equivalently, the antichains of the Boolean lattice
are the empty antichain (1), singletons (8), incomparable pairs (9), and its
two three-element rank levels (2), totalling 20. The checker exhausts all
\(2^{20}\) subsets to get 84 at the next level. It then counts the ideals of
that 84-element poset by the exact recurrence
\[ F(Q)=F(Q\setminus\uparrow x)+F(Q\setminus\downarrow x) \tag{4} \]and obtains 8,573 under each of three different pivot policies. No random
sampling or external sequence table is involved. As a structurally separate
cross-check, the verifier also counts antichains by scanning the 84 elements
and branching on whether each is included; it again obtains 8,573.
3. Proof of the exact threshold theorem
This section proves (1) from scratch.
Poset-valued shift labels
For a finite poset \(P\), call a labeling \(\lambda\) of the increasing
\(k\)-tuples from \([n]\) valid when
\[ \lambda(x_1,\ldots,x_k)\not\le \lambda(x_0,\ldots,x_{k-1}) \tag{5} \]for every \(x_0<\cdots If \(P=P_0(q)\) is a \(q\)-element antichain, (5) says exactly that the two labels are unequal. Thus a valid \(P_0(q)\)-valued labeling of the \(r\)-tuples is exactly a proper \(q\)-colouring of \(S_r(n)\). Lemma (a). For \(k\ge2\), a valid \(P\)-valued labeling of the increasing \(k\)-tuples from \([n]\) exists if and only if a valid \(J(P)\)-valued labeling of the increasing \((k-1)\)-tuples exists. Forward direction. Given \(\lambda\), label a \((k-1)\)-tuple \(y\) by the order ideal For adjacent \((k-1)\)-tuples the value \(z=\lambda(x_0,\ldots,x_{k-1})\) lies in \(D(B)\). If it also lay in \(D(A)\), then \(z\le\lambda(h,x_0,\ldots,x_{k-2})\) for some \(h contradicting (5) on \((h,x_0,\ldots,x_{k-1})\). Hence \(D(B)\nsubseteq D(A)\), which is exactly validity in \(J(P)\). Reverse direction. Given valid ideal labels \(D\), for every increasing \(k\)-tuple choose The set difference is nonempty by validity. On two adjacent \(k\)-tuples, the first chosen value belongs to the shared middle ideal, whereas the second does not. If the second value were at most the first, downward closure would put it in that ideal, a contradiction. Thus (5) holds. Apply the lemma \(r-1\) times. A \(q\)-colouring of \(S_r(n)\) exists if and only if there is a sequence \(p_0,\ldots,p_{n-1}\) in \(P_{r-1}(q)\) such that size of the poset. Conversely, list every element in any linear extension (smaller elements first). A later element cannot be at most an earlier one, so the resulting sequence has length \(|P_{r-1}(q)|\). This proves (1). Finally let \(N=|P_{r-1}(3)|\). Equation (1) says \(S_r(N+1)\) is not 3-colourable. Its induced copy on the first \(N\) ground elements is 3-colourable. Every remaining vertex contains the new largest ground element \(N\), and these remaining vertices form an independent set: in a shift edge only the suffix endpoint can contain the largest element. Give that independent set a fourth colour. Therefore as claimed. The following explicit embedding is the structural payoff. Sliding-window embedding (a). If \(R\ge r\), put \(L=R-r+1\). Order all \(L\)-subsets of \([n]\) lexicographically, and let \(\rho\) be their zero-based ranks. Map Successive windows are strictly increasing in lexicographic order, so the image is a vertex of \(S_r\bigl(\binom nL\bigr)\). The overlapping windows recover the original \(R\)-tuple, so the map is injective. When two \(R\)-tuples form a shift edge, their image tuples overlap in exactly the shift-edge pattern. Thus (8) preserves every edge and realizes as a (not necessarily induced) subgraph. Corollary (a). Let \(G_1\) and \(G_2\) be canonical infinite shift graphs of any two finite orders \(r,s\), on infinite ordered bases. Put \(R=\max(r,s)\) and Then \(\chi(H_R)=4\), and (9) embeds an isomorphic copy of \(H_R\) into both \(G_1\) and \(G_2\). In particular, the answer to Erdős #62 is affirmative for every pair drawn from this entire canonical test family whenever the two ambient graphs have chromatic number \(\aleph_1\). In fact, the ambient chromatic-number assumption is only needed to place the pair in the problem; infinite ordered bases already contain every finite base required above. This also directly witnesses the decreasing finite-age relation for shift graphs discussed by Erdős. The standalone checker exhaustively verifies the nontrivial sample embedding on all 1,330 vertices and 5,985 source edges. For a graph \(X\), let This is a hereditary family: it is closed under taking subgraphs. Reduction (b for de Bruijn–Erdős compactness; otherwise a). The 4-chromatic part of Erdős #62 is equivalent to the assertion that, whenever \(\chi(G_1)=\chi(G_2)=\aleph_1\), contains a graph of chromatic number at least 4. First, there is no loss in requiring the common 4-chromatic graph to be finite. The de Bruijn–Erdős compactness theorem says that if every finite subgraph of a graph is 3-colourable, then the whole graph is 3-colourable. Thus every 4-chromatic graph has a finite non-3-colourable subgraph. If a common finite graph \(F\) has \(\chi(F)>4\), delete vertices one at a time until the chromatic number first becomes at most 4. Deleting one vertex decreases chromatic number by at most one, so the graph at that step has chromatic number exactly 4. It remains in both hereditary ages. Following Erdős's 1985 definition, call a family \(\mathcal A\) of finite graphs good when there is an at least \(\aleph_1\)-chromatic graph \(X\) all of whose finite subgraphs belong to \(\mathcal A\). Each \(\operatorname{Age}(G_i)\) is good, witnessed by \(G_i\). (a) Therefore the following statement would suffice to settle the finite 4-chromatic question: > The intersection of every two good hereditary families of finite graphs is > good. Indeed, if the intersection is good, its witnessing uncountably chromatic graph cannot have all finite subgraphs 3-colourable, by de Bruijn–Erdős compactness. Hence the intersection contains a finite graph of chromatic number at least 4. This is the exact family-intersection problem Erdős isolated in 1985. (b) Erdős records that every finite-order shift age is very good; together with the elementary inclusion (9), this proves the intersection assertion for every pair of canonical finite-order shift ages, but not for arbitrary good families. The complete dependency-free source is erdos62_wave7c_verify.py. Run: The script independently: 1. enumerates each order-ideal lattice through the 20-element level; 2. recomputes 8,573 by recurrence (4) with pivot policies, then independently recomputes it with an incremental antichain DP; 3. directly proves \(S_2(8)\) is 3-colourable and \(S_2(9)\) is not by an exhaustive from-scratch DSATUR search; 4. constructs and checks proper colourings of \(S_2(9)\), \(S_3(20)\), and \(S_3(21)\); 5. checks a compact explicit 4-colouring certificate at \(S_4(85)\); 6. recomputes every table entry using integer binomial coefficients; and 7. checks injectivity and every edge of the displayed \(S_3(21)\to S_2(210)\) embedding, and recomputes the logarithmic order-six cost bounds in Section 7. The final run took 0.56 seconds with maximum resident size 19,848 KB on this VM. Its SHA-256 is It printed: The checker uses only Python's standard library. The non-3-colourability certificates are the exact equivalence (1) plus the independently recomputed finite-poset cardinalities; they are not heuristic graph-colouring failures. The EHS odd-cycle theorem forces common members at chromatic number 3. The missing uniform lemma is an operation on two uncountably chromatic finite ages that forces one common non-3-colourable finite member. Neither the EHS cycle tail nor the order-ideal machinery supplies such an operation for arbitrary ages. Equivalently, what remains is the good-family intersection statement in Section 5 (or a weaker theorem that merely forces chromatic number 4 in the intersection). Lambie-Hanson's theorem explains why a bounded catalogue search cannot fill this gap: for every proposed finite cutoff \(B\), an uncountably chromatic graph may have no 4-chromatic subgraph on fewer than \(B\) vertices. Accordingly, verifying all pairs or all candidate common graphs through a fixed order is not a uniformity argument and cannot close #62. A concrete next shift computation would be the number of ideals of the 8,573-element poset used at the last verified level. Naively this exposes \(2^{8573}\approx10^{2581}\) subsets. At a still optimistic \(10^7\) closure checks per core-second, this is about \(10^{2570}\) core-hours; even granting \(10^9\) checks per second, it exceeds \(10^{2564}\) single-core years. A symmetry-aware decision diagram might do far better, but no tractable state bound was found here. More importantly, that calculation would only give the first 4-chromatic member at shift order six; the all-orders embedding theorem already holds symbolically, so it would not resolve the arbitrary-age lemma. (c) I therefore make no claim that the numerical sequence, the all-shift-orders corollary, or the reduction is new. The verified advance in this run is an exact worked-out test family and a reproducible finite table, not a solution of the full problem. PARTIAL: Proved the common-4-chromatic conclusion for every pair of canonical finite-order shift-graph ages and computed exact first thresholds 4, 9, 21, 85, 8574 through order five; the arbitrary good-family intersection lemma remains open.One-step lifting lemma
Finish
4. A common 4-chromatic graph for every pair of finite shift orders
5. Exact reduction for arbitrary graphs
6. Verification
/usr/bin/time -f 'elapsed=%e sec maxrss=%M KB' \
python3 runs/erdos62_wave7c_verify.py
first, last, and balanced82997c9e73b3ff8b513b1a6e8d3f1a2ac642b0ac1d39d78913622817b86cd6b3.iterated ideal sizes for q=3: 3, 8, 20, 84, 8573
independent antichain DP for the 84-element level: 8573 (76481 states)
first 4-chromatic S_r(n), r=1..5: n=4, 9, 21, 85, 8574
S_3(21): 1330 vertices, 5985 edges, exact chromatic number 4
direct DSATUR S_2 check: n=8 SAT (42 nodes), n=9 UNSAT (562 nodes)
explicit 4-colouring and S_3(21)->S_2(210) embedding: verified
ALL CHECKS PASSED
7. Precise wall