Skip to content

Erdős Problem #1175

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: open (not automatically the live result).
Subject areas: set theory, chromatic number.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

Erdős Problem #1175 is classified OPEN in the maintained catalogue.

For each uncountable cardinal \(\kappa\), does there exist some cardinal \(\lambda\) (possibly larger than \(\kappa\)) so that every graph \(G\) of chromatic number \(\chi(G)=\lambda\) contains a triangle-free subgraph \(H\) with \(\chi(H)=\kappa\)? The quantifier order is \(\forall\kappa\ \exists\lambda\ \forall G\ \exists H\). Subgraph need not be induced unless the original theorem says so; equality versus \(\ge\kappa\) for the subgraph chromatic number must be verified. A counterexample at \(\lambda=\kappa\) is not enough to refute possible larger \(\lambda\).

A small example

\(K_5\) has chromatic number five and contains \(C_5\) as a spanning, noninduced, triangle-free subgraph with chromatic number three. Exhaustive proper-coloring enumeration checks that the five-cycle cannot be colored with two vertex colors but admits a three-coloring. This shows a concrete high-chromatic graph with a smaller triangle-free chromatic subgraph, but does not give a universal \(\lambda\) for any uncountable cardinal.

What is known

The maintained catalogue [Va99,7.92] leaves the general assertion OPEN. Shelah reportedly showed that it is consistent for the special \(\kappa=\lambda=\aleph_1\) instance to fail: some graph of chromatic number \(\aleph_1\) lacks a triangle-free subgraph of chromatic number \(\aleph_1\). But the original statement permits a different \(\lambda\) for the same \(\kappa\), so that relative-consistency obstruction does not disprove the \(\forall\kappa\exists\lambda\) conjecture. The site marks it formalized; formalization without a kernel proof is not mathematical certification.

GCL's current state

GCL posted an authenticated issue-bound research return and independently reproduced only the explicitly finite checks in ci/erdos_compendium_007_phase20_checks.py. This is an unaccepted editorial explanation, not an independent primary-paper verification or theorem proof.

What remains

Read Shelah's original consistent-special-case theorem; verify the scope \(\forall\kappa\exists\lambda\), the noninduced-subgraph interpretation and exact versus at-least chromatic number in the current formal conjecture. Inspect higher-chromatic/girth results only as relevant analogues, not substitutes for the uncountable universal assertion.

The source-status and theorem-strength distinctions must be settled before final protected admission. The cohort still has mandatory independent critical-review obligations.

Sources and claim boundaries

https://www.erdosproblems.com/1175 ; [Va99,7.92], Shelah (reported model-relative counterexample for lambda=kappa=aleph1).

Phase20 exact receipt: governance/erdos_compendium/batches/EC-BULK-007_FINITE_CHECKS_PHASE20.json. Source-fidelity PENDING; protected publication and V2 NOT ADMITTED.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #2446 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction