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 Norwich handout 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,” 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,” 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

[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

[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

[a] Well-order \(V(G)\). For each edge \(xy\), with \(x<y\), assign the edge the label \(c_y(x)\). For every label \(\alpha<C_q(\theta)\), let \(E_\alpha\) be the edges with label \(\alpha\). The graph \((V(G),E_\alpha)\) is triangle-free. Indeed, if \(x<y<z\) formed a triangle all of whose edges had label \(\alpha\), then the 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<C_q(\theta)\). The coordinate map

uses at most \(\theta^{C_q(\theta)}=C_{q+1}(\theta)\) colors. If \(xy\) is an edge with label \(\alpha\), then \(f_\alpha(x)\ne f_\alpha(y)\), so this coordinate map properly colors \(G\). This completes the induction. \(\square\)

2.2 Infinite-cardinal form

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

2.3 One cardinal uniform over every finite clique bound

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

3. Reductions toward the exact live question

3.1 Exact-target dichotomy

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

1. \(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.

3.2 Hosts containing a large clique

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

3.3 A finite-clique covering reduction

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)<B^+\) pieces of finite clique number. Section 2 gives each piece a coloring with fewer than \(B\), hence certainly with at most \(B\), colors. Since \(\delta<B^+\), cardinal succession gives \(\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:

• if \(K_\kappa\subseteq G\), the exact target follows from the clique lemma;
• if \(\operatorname{fc}(G)<\Lambda\), a triangle-free

\(H\) with \(\chi(H)>\kappa\) exists, and the exact target follows unless \(H\) is a triangle-free interpolation counterexample at \(\kappa\);

• the remaining structural regime has no \(K_\kappa\) and

\(\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.

4. Why the global edge-decomposition method is saturated

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.

4.1 Sharp edge coloring of a complete graph

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

4.2 Pullback to an arbitrary graph

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

5. Independent finite re-verification

[d] The standalone checker is erdos1175_wave8i_reverify.py. It uses only the Python standard library, has no network access, no random choices, and no stored certificate.

5.1 What the checker recomputes

[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;

1. computes the clique number by exhaustive vertex-subset enumeration;
2. computes the largest chromatic number of a triangle-free weak subgraph by

an edge-subset maximum-zeta transform;

1. constructs the local neighborhood colorings used in Section 2;
2. verifies that every resulting edge class is triangle-free; and
3. 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.

5.2 Core algorithm

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

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

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

5.3 Reproduction and output

Run from the repository root:

python3 runs/erdos1175_wave8i_reverify.py

[d] On this VM the final run took about 5.7 seconds and printed ALL CHECKS PASSED. The principal exact enumeration table was:

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

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

0335c4f996cbb55d7929a03405608876e87d74a44fe51e092a80a81b2aabd25e

5.4 Computational boundary

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

6. Verified outcome and exact remaining wall

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

1. The single explicit cardinal \(\beth_\omega(\kappa)\) therefore forces a

triangle-free subgraph of chromatic number \(>\kappa\) in every finite-clique-number host.

1. At \((\beth_\omega(\kappa))^+\), the same conclusion holds whenever the

host is the union of fewer than that many finite-clique-number pieces.

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