Erdős problem 1175 — wave 8i
Date checked: 2026-07-28 UTC
Claim labels
Every substantive claim below is marked as requested:
- [a] elementary-rigorous: proved here from definitions and elementary
cardinal arithmetic;
- [b] rigorous-modulo-named-theorem: depends on a named theorem or a
directly inspected primary source;
- [c] plausible/structural-unverified: a proposed route or missing
structural assertion, not a theorem;
- [d] computational-only: exhaustively checked only in the explicitly
stated finite range.
Source quotations and page-status observations are marked [b] because they
depend on the named live page rather than on an internal mathematical proof.
0. Mandatory live-page check
[b] I fetched the live
problem page through the Bright Data
browser route on 2026-07-28 UTC and visually inspected the rendered page. The
page was not inferred from the stale YAML.
[b] Verbatim current statement:
> Let \(\kappa\) be an uncountable cardinal. Must there exist a cardinal
> \(\lambda\) such that every graph with chromatic number \(\lambda\) contains
> a triangle-free subgraph with chromatic number \(\kappa\)?
[b] The page gives the source key #1175: [Va99,7.92], status OPEN, and
the following known result:
> Shelah proved that a negative answer is consistent if
> \(\kappa=\lambda=\aleph_1\).
[b] The live markers were:
- claimed proofs: 0;
- currently working: None;
- interested in collaborating: None.
[b] The linked
discussion page contained
one comment and no claimed solution. The complete substantive text of that
comment, posted by ebarschkis at 21:22 on 09 Feb 2026, was:
> Here are some relevant files I was able to find with GPT:
> https://shelah.logic.at/files/95727/303.pdf
> https://arxiv.org/pdf/2002.02480
> https://danieltsoukup.github.io/academic/norwich_handout.pdf
[b] Therefore none of the mandatory stop conditions applied: the live
problem is open, there is no claimed proof, and there is no current worker.
[a] Important quantifier caution. The displayed consistency result only
says that the particular diagonal choice
\(\kappa=\lambda=\aleph_1\) can fail. By itself it does not refute the live
statement, which asks whether some \(\lambda\) works for each uncountable
\(\kappa\).
1. Primary-source audit
1.1 The 1988 forcing paper
[b] Péter Komjáth and Saharon Shelah,
“Forcing constructions for uncountably chromatic graphs,”
Journal of Symbolic Logic 53 (1988), 696–707,
DOI 10.2307/2274566, is the primary source
behind the page's consistency note. Its introduction explicitly formulates
the conjecture that every \(\kappa\)-chromatic graph should contain a
triangle-free \(\kappa\)-chromatic graph and says that the authors make it
consistently false at \(\aleph_1\).
[b] More precisely, Theorem 2 of that paper constructs, consistently with
CH, an uncountably chromatic graph \(X\) on \(\omega_1\) for which every
triangle-free subgraph is countably chromatic. This verifies the page's
diagonal consistency statement, but it does not rule out a larger witness
\(\lambda\) for \(\kappa=\aleph_1\).
[b] Theorem 4 of the same paper proves that if \(X\) is \(K_4\)-free and
\(\operatorname{Chr}(X)>2^{\aleph_0}\), then \(X\) has an uncountably
chromatic triangle-free subgraph. It also records the corresponding
strongly-compact-cardinal result. The elementary recurrence proved in
Section 2 below recovers the \(K_4\)-free cardinal bound and extends its
finite-clique induction; this is not asserted to be new to the literature.
[b] The introduction of the paper also cites the Erdős–Rado theorem that
for every infinite cardinal \(\kappa\) there is a triangle-free
\(\kappa\)-chromatic graph of cardinality \(\kappa\). I use that named
existence theorem only in Section 3.2.
1.2 The two other files in the live comment
[b] Dániel T. Soukup's
states the \(\omega_1\) instance as a conjecture and says that the desired
counterexample exists consistently, even while omitting \(K_4\), but that its
existence in ZFC remained open at the time of the 2015 handout. This is useful
historical evidence, not a 2026 status certificate.
[b] Chris Lambie-Hanson and Dániel T. Soukup,
“[Extremal triangle-free and odd-cycle-free colourings of uncountable
graphs](https://arxiv.org/abs/2002.02480),” arXiv:2002.02480, studies the
least-difference coloring
\(\Delta_\kappa:[2^\kappa]^2\to\kappa\) and extremal colorings without
monochromatic odd cycles. Its abstract and theorem list do not claim a
solution of problem 1175. The least-difference construction is directly
relevant to the sharp obstruction in Section 4.
1.3 Chromatic interpolation and finite antecedents
[b] The exact-target difficulty below is a genuine infinite-graph issue.
Komjáth's
“Consistency results on infinite graphs,”
Israel Journal of Mathematics 61 (1988), 285–294, gives consistency
results in which a graph has chromatic number \(\aleph_2\) but has no subgraph
of chromatic number \(\aleph_1\). Thus one may not silently replace
“chromatic number exactly \(\kappa\)” by “chromatic number at least
\(\kappa\)” in ZFC.
[b] For comparison, the finite analogue is supplied by Vojtěch Rödl,
“[On the chromatic number of subgraphs of a given
graph](https://doi.org/10.1090/S0002-9939-1977-0469806-4),” *Proceedings of
the American Mathematical Society* 64 (1977), 370–371: for every finite
target \(k\), sufficiently large finite chromatic number forces a
triangle-free subgraph of chromatic number exactly \(k\). That theorem does
not supply the infinite-cardinal interpolation step needed here.
[b] Search limitation. I searched the exact problem wording, the 1988
paper title, its citing literature, the three live-comment files, and recent
problem-list metadata. I found no primary source claiming a general solution.
This is a report of the search performed, not a proof that no unindexed or
unpublished result exists. The live page remains the authoritative status
source for this run.
2. A finite-clique hierarchy
Throughout, a “subgraph” is a weak subgraph: vertices and edges may both be
deleted. When convenient, a weak subgraph is padded by isolated vertices,
which does not change its chromatic number.
2.1 The recurrence
For a cardinal \(\theta\ge 2\) and a finite integer \(q\ge3\), define
\[ C_3(\theta)=\theta,\qquad C_{q+1}(\theta)=\theta^{C_q(\theta)}. \][a] Bounded-clique theorem. Let \(q\ge3\) be finite. If \(G\) is
\(K_q\)-free and every triangle-free subgraph of \(G\) has chromatic number at
most \(\theta\), then
\[ \chi(G)\le C_q(\theta). \tag{1} \][a] Proof. Induct on \(q\). For \(q=3\), the whole graph \(G\) is
triangle-free, so the hypothesis gives \(\chi(G)\le\theta=C_3(\theta)\).
[a] Suppose the assertion holds for \(q\), and let \(G\) be
\(K_{q+1}\)-free. For every vertex \(v\), the induced neighborhood
\(G[N(v)]\) is \(K_q\)-free: a \(K_q\) inside \(N(v)\), together with \(v\),
would be a \(K_{q+1}\). Every triangle-free subgraph of \(G[N(v)]\) is also a
triangle-free subgraph of \(G\), so the induction hypothesis gives a proper
coloring
\[ c_v:N(v)\longrightarrow C_q(\theta). \][a] Well-order \(V(G)\). For each edge \(xy\), with \(x edge the label \(c_y(x)\). For every label \(\alpha The graph \((V(G),E_\alpha)\) is triangle-free. Indeed, if \(x two edges \(xz\) and \(yz\) would give \(c_z(x)=c_z(y)=\alpha\), contradicting the fact that \(c_z\) properly colors the adjacent vertices \(x,y\in N(z)\). [a] By hypothesis, choose a proper coloring \(f_\alpha:(V(G),E_\alpha)\to\theta\) for every \(\alpha edge with label \(\alpha\), then \(f_\alpha(x)\ne f_\alpha(y)\), so this coordinate map properly colors \(G\). This completes the induction. \(\square\) Write [a] If \(\kappa\) is infinite and \(C\ge\kappa\) is infinite, then Consequently \(\kappa^C=2^C\), and induction in (1) gives the exact closed form [a] Finite-clique consequence. If \(G\) is \(K_q\)-free and then \(G\) has a triangle-free subgraph \(H\) with \(\chi(H)>\kappa\). [a] This is precisely the contrapositive of (1) and (2). Notice that the conclusion is \(>\kappa\), not \(=\kappa\). [a] Uniform finite-clique consequence. Let Every graph \(G\) with \(\chi(G)=B\) and finite clique number contains a triangle-free subgraph \(H\) with \(\chi(H)>\kappa\). [a] Proof. If \(G\) has finite clique number, it is \(K_q\)-free for some finite \(q\). If all its triangle-free subgraphs had chromatic number at most \(\kappa\), (2) would give a contradiction. \(\square\) [a] This gives a single explicit cardinal \(B\), independent of the unknown finite clique bound of the host. It is a genuine uniformity step, but it applies only to hosts of finite clique number and still produces chromatic number \(>\kappa\), not exactly \(\kappa\). [a] Apply Section 2.3 to a finite-clique-number graph \(G\) of chromatic number \(B=\beth_\omega(\kappa)\), and let \(H\subseteq G\) be triangle-free with \(\chi(H)>\kappa\). Exactly one of the following happens: 1. \(H\) has a subgraph \(J\) with \(\chi(J)=\kappa\). Since a subgraph of a triangle-free graph is triangle-free, \(J\) is the exact witness requested in problem 1175. 2. \(H\) has no subgraph of chromatic number \(\kappa\). Then \(H\) itself is a triangle-free counterexample to chromatic interpolation at \(\kappa\). [a] Thus, on the finite-clique-number regime, the only missing step is the following sharply stated assertion: > Triangle-free interpolation at \(\kappa\). Every triangle-free graph of > chromatic number \(>\kappa\) has a subgraph of chromatic number exactly > \(\kappa\). [c] I do not know a ZFC proof of this assertion, and the general interpolation consistency results cited in Section 1.3 show why it cannot be treated as formal monotonicity. I found no primary source in the search above that proves this stronger triangle-free version. [b] Clique lemma. If a graph \(G\) contains \(K_\kappa\), then \(G\) contains a triangle-free subgraph of chromatic number exactly \(\kappa\). [b] Proof modulo Erdős–Rado. By the named existence theorem in Section 1.1, take a triangle-free \(\kappa\)-chromatic graph \(T\) on \(\kappa\) vertices. Identify \(V(T)\) with the vertices of the \(K_\kappa\) inside \(G\), and retain precisely the edges of \(T\). All those edges occur in the clique, so this is a subgraph of \(G\) with the required properties. \(\square\) [b] Therefore an obstruction to problem 1175 cannot contain a \(\kappa\)-clique. Merely containing \(K_n\) for every finite \(n\) is not enough for this argument. Define the finite-clique covering number [a] The pieces may be made disjoint by assigning each vertex to its first piece, so “cover” and “partition” give the same minimum here. [a] Successor covering theorem. Put If \(\chi(G)=\Lambda\) and \(\operatorname{fc}(G)<\Lambda\), then \(G\) has a triangle-free subgraph \(H\) with \(\chi(H)>\kappa\). [a] Proof. Suppose instead that every triangle-free subgraph of \(G\) has chromatic number at most \(\kappa\). Partition \(V(G)\) into \(\delta=\operatorname{fc}(G) 2 gives each piece a coloring with fewer than \(B\), hence certainly with at most \(B\), colors. Since \(\delta \(\delta\le B\). Color a vertex by the pair consisting of its piece and its color within that piece. This uses at most colors, contradicting \(\chi(G)=B^+\). \(\square\) [a] Combined reduction. At the explicit cardinal \(\Lambda=(\beth_\omega(\kappa))^+\), every host \(G\) falls into the following rigorous decision tree: \(H\) with \(\chi(H)>\kappa\) exists, and the exact target follows unless \(H\) is a triangle-free interpolation counterexample at \(\kappa\); \(\operatorname{fc}(G)\ge\Lambda\). [c] Closing problem 1175 by this route requires at least one genuinely new input: either triangle-free interpolation at \(\kappa\), or a theorem controlling the last high-\(\operatorname{fc}\), \(K_\kappa\)-free regime (or a different argument that bypasses both). I have not proved either assertion. A standard attempt is to split every host graph into a small number of triangle-free edge classes and then multiply colorings of those classes. The following calculation shows the exact obstruction to that method. [b] Erdős–Rado lower bound. For infinite \(\mu\), the partition relation implies that any \(\mu\)-coloring of the edges of \(K_\lambda\) with no monochromatic triangle must satisfy [a] Matching construction. On the \(2^\mu\) binary sequences \({}^\mu2\), color an edge \(\{x,y\}\) by the least coordinate \(\Delta(x,y)<\mu\) where \(x\) and \(y\) differ. For a fixed coordinate \(\alpha\), its color class is bipartite, split according to the value \(x(\alpha)\in\{0,1\}\); hence it is triangle-free. Thus (3) is sharp. [a] Let \(p:V(G)\to\lambda\) be a proper coloring of \(G\), and pull such an edge coloring of \(K_\lambda\) back along \(p\). Each pulled-back edge class is triangle-free: a monochromatic triangle in \(G\) would map, under the proper coloring \(p\), to a monochromatic triangle on three distinct vertices of \(K_\lambda\). [a] If there are \(\mu\) edge classes and every triangle-free subgraph of \(G\) is \(\kappa\)-colorable, then color each class with \(\kappa\) colors and take the coordinatewise product. This colors \(G\) with \(\kappa^\mu\) colors. To contradict \(\chi(G)=\lambda\), this scheme would need [b] Exact wall. Erdős–Rado forces \(\lambda\le2^\mu\), while elementary cardinal arithmetic gives \(2^\mu\le\kappa^\mu\) for every \(\kappa\ge2\). Therefore (3) makes (4) impossible. The least-difference coloring attains the obstruction with even bipartite, not merely triangle-free, classes. Consequently no argument consisting only of 1. a global \(\mu\)-color triangle-free edge decomposition of \(K_\lambda\), 2. pullback along a proper \(\lambda\)-coloring, and 3. a coordinate product of \(\kappa\)-colorings can prove the desired contradiction for any cardinals \(\lambda,\mu\). [a] The local-neighborhood proof in Section 2 avoids this particular wall because its edge labels come from colorings of neighborhoods and use the finite forbidden-clique hypothesis. It does not solve the unrestricted high-\(\operatorname{fc}\) regime. [d] The standalone checker is It uses only the Python standard library, has no network access, no random choices, and no stored certificate. [d] From scratch, for every one of the \(33{,}867\) labeled graphs on at most six vertices, it: 1. computes the exact chromatic number by independent-set dynamic programming; 2. computes the clique number by exhaustive vertex-subset enumeration; 3. computes the largest chromatic number of a triangle-free weak subgraph by an edge-subset maximum-zeta transform; 4. constructs the local neighborhood colorings used in Section 2; 5. verifies that every resulting edge class is triangle-free; and 6. independently colors every edge class and verifies that the coordinate-product coloring is proper. [d] It additionally verifies the first-difference coloring on all binary words in dimensions \(1,\ldots,8\), checking every triple, and exhaustively checks the small triangle-free edge-partition values [d] For \(K_6\), all \(2^{15}=32{,}768\) red/blue edge colorings are tested, so the lower bound \(\rho(K_6)>2\) is not imported from a Ramsey-number table. [d] The complete executable code is in the companion file. Its two central from-scratch operations are the following; the file also contains all enumeration, assertions, and output formatting. [d] The maximum-zeta transform considers arbitrary weak subgraphs, not only induced subgraphs. A weak subgraph using fewer vertices is represented by padding it with isolates. Run from the repository root: [d] On this VM the final run took about 5.7 seconds and printed | vertices \(n\) | labeled graphs | maximum \(\chi(G)\) | maximum triangle-free-subgraph \(\chi\) | |---:|---:|---:|---:| | 1 | 1 | 1 | 1 | | 2 | 2 | 2 | 2 | | 3 | 8 | 3 | 2 | | 4 | 64 | 4 | 2 | | 5 | 1,024 | 5 | 3 | | 6 | 32,768 | 6 | 3 | [d] Across those graphs, the program checked exactly \(33{,}867\) local edge decompositions and \(66{,}955\) resulting triangle-free edge classes. It also checked that the product coloring is proper in every case. [d] The finite bounded-clique audit obtained: | \(\theta\) | forbidden clique | exact maximum \(\chi\) through \(n=6\) | |---:|:---:|---:| | 2 | \(K_3\) | 2 | | 2 | \(K_4\) | 3 | | 2 | \(K_5\) | 4 | | 2 | \(K_6\) | 4 | | 3 | \(K_3\) | 3 | | 3 | \(K_4\) | 4 | | 3 | \(K_5\) | 4 | | 3 | \(K_6\) | 5 | [d] These finite values are sanity checks, not evidence that the cardinal bounds in (2) are sharp. [d] SHA-256 of the checked companion file: [d] A naive extension from \(n=6\) to \(n=7\) increases the graph count from \(2^{15}=32{,}768\) to \(2^{21}=2{,}097{,}152\), a factor of 64 before the larger subset dynamic programs are counted. Extrapolating this checker gives roughly 6–15 core-minutes and hundreds of megabytes for \(n=7\), so I did not run it under the stated few-CPU-minute limit. [a] Such an extension would not address the actual missing steps: those assertions quantify over uncountable graphs and cardinals, whereas that extended raw exhaustive result would quantify only over graphs with at most seven vertices. The enumeration alone therefore cannot prove either missing assertion. [a] Verified progress. 1. For every finite \(q\ge3\), a \(K_q\)-free graph with no triangle-free subgraph of chromatic number \(>\kappa\) has chromatic number at most \(\beth_{q-3}(\kappa)\). 2. The single explicit cardinal \(\beth_\omega(\kappa)\) therefore forces a triangle-free subgraph of chromatic number \(>\kappa\) in every finite-clique-number host. 3. At \((\beth_\omega(\kappa))^+\), the same conclusion holds whenever the host is the union of fewer than that many finite-clique-number pieces. 4. In these regimes the exact-\(\kappa\) conclusion is reduced to triangle-free chromatic interpolation. [b] If the host contains \(K_\kappa\), the Erdős–Rado existence theorem immediately supplies the exact triangle-free \(\kappa\)-chromatic subgraph. [b] Verified method wall. The Erdős–Rado partition bound and the matching least-difference construction prove that the unrestricted global edge-decomposition/product-coloring strategy cannot have the cardinal inequality needed to work. [c] What is not proved. I have neither proved triangle-free interpolation at \(\kappa\) nor controlled graphs with no \(K_\kappa\) and \(\operatorname{fc}(G)\ge(\beth_\omega(\kappa))^+\). Hence this report does not solve problem 1175 and does not claim that the displayed cardinal is a witness for unrestricted graphs. PARTIAL: Proved the finite-clique hierarchy \(\chi(G)\le\beth_{q-3}(\kappa)\), obtained uniform \(>\kappa\) consequences at \(\beth_\omega(\kappa)\) and its successor-cover extension, reduced exact \(\kappa\) to triangle-free interpolation plus a precisely isolated unbounded-clique regime, and verified the finite skeleton exhaustively.2.2 Infinite-cardinal form
2.3 One cardinal uniform over every finite clique bound
3. Reductions toward the exact live question
3.1 Exact-target dichotomy
3.2 Hosts containing a large clique
3.3 A finite-clique covering reduction
4. Why the global edge-decomposition method is saturated
4.1 Sharp edge coloring of a complete graph
4.2 Pullback to an arbitrary graph
5. Independent finite re-verification
5.1 What the checker recomputes
5.2 Core algorithm
def exact_coloring(U, graph):
independent = [
not (graph & U.inside[s]) for s in range(1 << U.n)
]
dp = [0] + [U.n + 1] * ((1 << U.n) - 1)
choice = [0] * (1 << U.n)
for vertices in range(1, 1 << U.n):
first = vertices & -vertices
rest = vertices ^ first
sub = rest
while True:
color_class = sub | first
if independent[color_class]:
candidate = 1 + dp[vertices ^ color_class]
if candidate < dp[vertices]:
dp[vertices] = candidate
choice[vertices] = color_class
if sub == 0:
break
sub = (sub - 1) & rest
# The companion reconstructs and verifies an optimal coloring here.
return dp[-1]
def local_edge_classes(U, graph, local_colors, label_count):
classes = [0] * label_count
for e, (u, v) in enumerate(U.edges):
if (graph >> e) & 1:
earlier, later = (u, v) if u < v else (v, u)
label = local_colors[later][earlier]
classes[label] |= 1 << e
return classes
5.3 Reproduction and output
python3 runs/erdos1175_wave8i_reverify.py
ALL CHECKS PASSED. The principal exact enumeration table was:0335c4f996cbb55d7929a03405608876e87d74a44fe51e092a80a81b2aabd25e
5.4 Computational boundary
6. Verified outcome and exact remaining wall